Optimal auctions with correlated bidders are easy

DOI10.1145/1993636.1993655zbMATH Open1288.91102arXiv1011.2413OpenAlexW2021734699MaRDI QIDQ5419082FDOQ5419082

Authors: Shahar Dobzinski, Hu Fu, Robert D. Kleinberg 

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Abstract: We consider the problem of designing a revenue-maximizing auction for a single item, when the values of the bidders are drawn from a correlated distribution. We observe that there exists an algorithm that finds the optimal randomized mechanism that runs in time polynomial in the size of the support. We leverage this result to show that in the oracle model introduced by Ronen and Saberi [FOCS'02], there exists a polynomial time truthful in expectation mechanism that provides a $(frac32+epsilon)$-approximation to the revenue achievable by an optimal truthful-in-expectation mechanism, and a polynomial time deterministic truthful mechanism that guarantees $frac53$ approximation to the revenue achievable by an optimal deterministic truthful mechanism. We show that the $frac53$-approximation mechanism provides the same approximation ratio also with respect to the optimal truthful-in-expectation mechanism. This shows that the performance gap between truthful-in-expectation and deterministic mechanisms is relatively small. En route, we solve an open question of Mehta and Vazirani [EC'04]. Finally, we extend some of our results to the multi-item case, and show how to compute the optimal truthful-in-expectation mechanisms for bidders with more complex valuations.

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

Recommendations

• Approximately optimal auctions for correlated bidders
• Optimal deterministic auctions with correlated priors
• Limitations of deterministic auction design for correlated bidders
• Limitations of Deterministic Auction Design for Correlated Bidders
• The complexity of optimal mechanism design

zbMATH Keywords

incentive compatibilitycombinatorial auctions

Mathematics Subject Classification ID

Linear programming (90C05) Multi-objective and goal programming (90C29) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Auctions, bargaining, bidding and selling, and other market models (91B26) Approximation algorithms (68W25)

Cited In (23)

• Mechanism design for correlated valuations: efficient methods for revenue maximization
• The power of randomness in Bayesian optimal mechanism design
• Efficiency-revenue trade-offs in auctions
• Multi-Item Nontruthful Auctions Achieve Good Revenue
• Limitations of deterministic auction design for correlated bidders
• Revenue maximization in a Bayesian double auction market
• The complexity of optimal mechanism design
• Correlation-robust auction design
• Optimal mechanism design for the private supply of a public good
• Lookahead auctions with pooling
• Revenue maximization for market intermediation with correlated priors
• Approximation in mechanism design with interdependent values
• Revenue maximization for selling multiple correlated items
• Limitations of Deterministic Auction Design for Correlated Bidders
• Auction design with a revenue target
• On the efficiency of all-pay mechanisms
• Approximately optimal auctions for correlated bidders
• Optimal deterministic auctions with correlated priors
• Worst-case mechanism design via Bayesian analysis
• Reverse auctions are different from auctions
• Sequential posted price mechanisms with correlated valuations
• Truthful mechanisms with implicit payment computation
• Correlation-robust analysis of single item auction

This page was built for publication: Optimal auctions with correlated bidders are easy

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