Optimal auctions with correlated bidders are easy

DOI10.1145/1993636.1993655MaRDI QIDQ5419082zbMATHOpenAlexFDO

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)

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

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)

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.

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

Cited in

(23)

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

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)