Near-optimal and robust mechanism design for covering problems with correlated players

DOI10.1007/978-3-642-45046-4_31MaRDI QIDQ2937773zbMATH OpenOpenAlexFDO

Authors Hadi Minooei, Chaitanya Swamy

Publication date 12 January 2015

Published in Web and Internet Economics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.6883

zbMATH Keywords

correlated playersprocurement auctionsrobust mechanism design

Mathematics Subject Classification ID

(n)-person games, (n>2) (91A06) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: We consider the problem of designing incentive-compatible, ex-post individually rational (IR) mechanisms for covering problems in the Bayesian setting, where players' types are drawn from an underlying distribution and may be correlated, and the goal is to minimize the expected total payment made by the mechanism. We formulate a notion of incentive compatibility (IC) that we call {em support-based IC} that is substantially more robust than Bayesian IC, and develop black-box reductions from support-based-IC mechanism design to algorithm design. For single-dimensional settings, this black-box reduction applies even when we only have an LP-relative {em approximation algorithm} for the algorithmic problem. Thus, we obtain near-optimal mechanisms for various covering settings including single-dimensional covering problems, multi-item procurement auctions, and multidimensional facility location.

Recommendations

• Bayesian incentive compatibility via fractional assignments
• Bayesian algorithmic mechanism design
• Bayesian incentive compatibility via matchings
• Bayesian incentive compatible mechanisms
• Bayesian Mechanism Design

Cited in

(4)

• Mechanism design for set cover games with selfish element agents
• Reverse auctions are different from auctions
• scientific article; zbMATH DE number 6783427 (Why is no real title available?)
• On improved interval cover mechanisms for crowdsourcing markets

This page was built for publication: Near-optimal and robust mechanism design for covering problems with correlated players

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2937773)