Optimal auctions with correlated bidders are easy

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

Hu Fu, Shahar Dobzinski, 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 (15)

• On the Efficiency of All-Pay Mechanisms
• Multi-Item Nontruthful Auctions Achieve Good Revenue
• Revenue maximization in a Bayesian double auction market
• Sequential Posted Price Mechanisms with Correlated Valuations
• Optimal mechanism design for the private supply of a public good
• Lookahead auctions with pooling
• Approximation in mechanism design with interdependent values
• Worst-Case Mechanism Design via Bayesian Analysis
• Limitations of Deterministic Auction Design for Correlated Bidders
• Limitations of Deterministic Auction Design for Correlated Bidders
• Revenue Maximization for Market Intermediation with Correlated Priors
• On the complexity of dynamic mechanism design
• Optimal deterministic auctions with correlated priors
• Reverse auctions are different from auctions
• Truthful mechanisms with implicit payment computation

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)