Near-Optimal and Robust Mechanism Design for Covering Problems with Correlated Players

Hadi Minooei, Chaitanya Swamy · Workshop on Internet and Network Economics · 2013

Summary

A notion of incentive compatibility that is substantially more robust than Bayesian IC is formulated, black-box reductions from support-based-IC mechanism design to algorithm design are developed, and near-optimal mechanisms for various covering settings are obtained.

Type: article
Published: 2013-11-26
Cited by: 5
References: 29
Access: Open access
DOI: https://doi.org/10.1145/2790133
arXiv: https://arxiv.org/abs/1311.6883
OpenAlex: https://openalex.org/W1502128320
Semantic Scholar: https://api.semanticscholar.org/CorpusID:7009633

Keywords

Incentive compatibility, Mechanism design, Mathematical optimization, Computer science, Bayesian probability

References

Packing Steiner treesKamal Jain, Mohammad Mahdian, Mohammad R. Salavatipour — 2003
Multi-parameter mechanism design and sequential posted pricingShuchi Chawla, Jason D. Hartline, David Malec — 2010
On optimal single-item auctionsChristos H. Papadimitriou, George Pierrakos — 2010
Nearly optimal multi attribute auctionsAmir Ronen, Daniel Lehmann — 2005
Optimal and near-optimal mechanism design with interdependent valuesTim Roughgarden, Inbal Talgam-Cohen — 2013
Optimal auctions with correlated bidders are easyShahar Dobzinski, Hu Fu, Robert Kleinberg — 2010
Correlated Information and Mechanism DesignR. Preston McAfee, Philip J. Reny — 1992
Bayesian optimal auctions via multi- to single-agent reductionSaeed Alaei, Hu Fu, Nima Haghpanah — 2012
Optimal Auction DesignRoger B. Myerson — 1981
On approximating optimal auctionsAmir Ronen — 2001
Optimal Multi-dimensional Mechanism Design: Reducing Revenue to Welfare MaximizationYang Cai, Constantinos Daskalakis, S. Matthew Weinberg — 2012
Optimal Selling Strategies under Uncertainty for a Discriminating Monopolist When Demands Are InterdependentJacques Crémer, Richard P. McLean — 1985
Greedy facility location algorithms analyzed using dual fitting with factor-revealing LPKamal Jain, Mohammad Mahdian, Evangelos Markakis — 2002
FULL EXTRACTION OF THE SURPLUS IN BAYESIAN AND DOMINANT STRATEGY AUCTIONSJacques Crémer, Richard P. McLean — 1988
Truthful and near-optimal mechanism design via linear programmingRon Lavi, Chaitanya Swamy — 2005
Auction Theory: A Guide to the LiteraturePaul Klemperer — 1999
On the hardness of optimal auctionsAmir Ronen, Amin Saberi — 2002
Understanding Incentives: Mechanism Design Becomes Algorithm DesignYang Cai, Constantinos Daskalakis, S. Matthew Weinberg — 2013
A 1.488 approximation algorithm for the uncapacitated facility location problemShi Li — 2011
Algorithmic Game TheoryMarı́a Serna, SAGT 2012 Barcelona — 2012

Cited by

Bayesian algorithmic mechanism designShuchi Chawla, Balasubramanian Sivan — 2014
Notes from the EC'14 program chairsVincent Conitzer, David Easley — 2014
Mechanism Design For Covering ProblemsHadi Minooei — 2014
On the Complexity of Optimal Correlated Auctions and Reverse AuctionsMatthias Gerstgrasser — 2018
Reverse auctions are different from auctionsMatthias Gerstgrasser — 2019

Near-Optimal and Robust Mechanism Design for Covering Problems with Correlated Players

Summary

Keywords

References

Cited by

Related papers