research-article

Limitations of Deterministic Auction Design for Correlated Bidders

Authors:

Ioannis Caragiannis,

Christos Kaklamanis,

Maria KyropoulouAuthors Info & Claims

ACM Transactions on Computation Theory (TOCT), Volume 8, Issue 4

Article No.: 13, Pages 1 - 18

https://doi.org/10.1145/2934309

Published: 29 June 2016 Publication History

Abstract

The seminal work of Myerson (Mathematics of OR ’81) characterizes incentive-compatible single-item auctions among bidders with independent valuations. In this setting, relatively simple deterministic auction mechanisms achieve revenue optimality. When bidders have correlated valuations, designing the revenue-optimal deterministic auction is a computationally demanding problem; indeed, Papadimitriou and Pierrakos (STOC ’11) proved that it is APX-hard, obtaining an explicit inapproximability factor of 1999/2000 = 99.95%. In the current article, we strengthen this inapproximability factor to 63/64 ≈ 98.5%. Our proof is based on a gap-preserving reduction from the Max-NM 3SAT problem; a variant of the maximum satisfiability problem where each clause has exactly three literals and no clause contains both negated and unnegated literals. We furthermore show that the gap between the revenue of deterministic and randomized auctions can be as low as 13/14 ≈ 92.9%, improving an explicit gap of 947/948 ≈ 99.9% by Dobzinski, Fu, and Kleinberg (STOC ’11).

References

[1]

Ioannis Caragiannis, Christos Kaklamanis, and Maria Kyropoulou. 2013. Limitations of deterministic auction design for correlated bidders. In Proceedings of the 21st Annual European Symposium on Algorithms (ESA’13). 277--288.

[2]

Xue Chen, Guangda Hu, Pinyan Lu, and Lei Wang. 2011. On the approximation ratio of k-lookahead auction. In Proceedings of the 7th International Conference on Internet and Network Economics (WINE’11). 61--71.

Digital Library

[3]

Florin Constantin, Takayuki Ito, and David C. Parkes. 2007. Online auctions for bidders with interdependent values. In Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS’07). Article 110, 3 pages.

Digital Library

[4]

Jacques Crémer and Richard P. McLean. 1985. Optimal selling strategies under uncertainty for a discriminating monopolist when demands are interdependent. Econometrica 53, 2 (1985), 345--361.

[5]

Jacques Crémer and Richard P. McLean. 1988. Full extraction of the surplus in Bayesian and dominant strategy auctions. Econometrica 56, 6 (1988), 1247--1257.

[6]

Ilias Diakonikolas, Christos Papadimitriou, George Pierrakos, and Yaron Singer. 2012. Efficiency-revenue trade-offs in auctions. In Proceedings of the 39th International Colloquium Conference on Automata, Languages, and Programming—Volume Part II (ICALP’12). 488--499. 10.1007/978-3-642-31585-5_44

Digital Library

[7]

Shahar Dobzinski, Hu Fu, and Robert D. Kleinberg. 2011. Optimal auctions with correlated bidders are easy. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC’11). 129--138.

Digital Library

[8]

Péter Esö. 2005. An optimal auction with correlated values and risk aversion. J. Econ. Theory 125, 1 (2005), 78--89.

[9]

Venkatesan Guruswami and Subhash Khot. 2005. Hardness of Max 3SAT with no mixed clauses. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC’05). 154--162.

Digital Library

[10]

Vijay Krishna. 2009. Auction Theory. Academic Press, San Diego, CA.

[11]

Dan Levin and James L. Smith. 1996. Optimal reservation prices in auctions. Econ. J. 106, 438 (1996), 1271--1283.

[12]

Eric Maskin. 2003. Auctions and efficiency. In Advances in Economics and Econometrics: Theory and Applications, Eighth World Congress (Econometric Society Monographs), M. Dewatripont, L. P. Hansen, and S. J. Turnovsky (Eds.). Vol. 3. 1--24.

[13]

Paul R. Milgrom and Robert J. Weber. 1982. A theory of auctions and competitive bidding. Econometrica 50, 5 (1982), 1089--1122.

[14]

Roger B. Myerson. 1981. Optimal auction design. Math. Operat. Res. 6, 1 (1981), 58--73.

Digital Library

[15]

Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press, New York, NY.

Digital Library

[16]

Christos H. Papadimitriou and George Pierrakos. 2011. On optimal single-item auctions. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC’11). 119--128.

Digital Library

[17]

Amir Ronen. 2001. On approximating optimal auctions. In Proceedings of the 3rd ACM Conference on Electronic Commerce (EC’01). 11--17.

Digital Library

[18]

Amir Ronen and Amin Saberi. 2002. On the hardness of optimal auctions. In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS’02). 396--405. http://dl.acm.org/citation. cfm?id=645413.652138.

Digital Library

[19]

Tim Roughgarden and Inbal Talgam-Cohen. 2013. Optimal and near-optimal mechanism design with interdependent values. In Proceedings of the 14th ACM Conference on Electronic Commerce (EC’13). 767--784.

Digital Library

Cited By

Kampouridis MKanellopoulos PKyropoulou MMelissourgos TVoudouris AAlbrecht SWoolridge M(2022)Multi-agent systems for computational economics and financeAI Communications10.3233/AIC-22011735:4(369-380)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.3233/AIC-220117
Gerstgrasser MAndre EKoenig SDastani MSukthankar G(2018)On the Complexity of Optimal Correlated Auctions and Reverse AuctionsProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237474(605-613)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237474
Fu HLiaw CLu PTang ZCzumaj A(2018)The value of information concealmentProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175467(2533-2544)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175467
Show More Cited By

Index Terms

Limitations of Deterministic Auction Design for Correlated Bidders
1. Applied computing
  1. Law, social and behavioral sciences
    1. Economics
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A robust combinatorial auction mechanism against shill bidders
AAMAS '06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems

This paper presents a method for discovering and detecting shill bids in combinatorial auctions. The Vickrey-Clarke-Groves Mechanism is one of the most important combinatorial auctions because it can satisfy the strategy-proof property, individual ...
Optimal design of English auctions with discrete bid levels
EC '05: Proceedings of the 6th ACM conference on Electronic commerce

In this paper we consider a common form of the English auction that is widely used in online Internet auctions. This discrete bid auction requires that the bidders may only submit bids which meet some predetermined discrete bid levels and, thus, there ...
Sequences of take-it-or-leave-it offers: near-optimal auctions without full valuation revelation
AAMAS '06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems

We introduce take-it-or-leave-it auctions (TLAs) as an allocation mechanism that allows buyers to retain much of their private valuation information, yet generates close-to-optimal expected utility for the seller. We show that if each buyer receives at ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Computation Theory

ACM Transactions on Computation Theory Volume 8, Issue 4

July 2016

97 pages

ISSN:1942-3454

EISSN:1942-3462

DOI:10.1145/2956681

Editor:
Eric Allender
Rutgers University, USA

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 June 2016

Accepted: 01 March 2016

Revised: 01 August 2015

Received: 01 March 2014

Published in TOCT Volume 8, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

University of Patras
European Social Fund and Greek national funds through the research funding program Thales on “Algorithmic Game Theory,” by ”Caratheodory“ research
ERC Advanced

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
158
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kampouridis MKanellopoulos PKyropoulou MMelissourgos TVoudouris AAlbrecht SWoolridge M(2022)Multi-agent systems for computational economics and financeAI Communications10.3233/AIC-22011735:4(369-380)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.3233/AIC-220117
Gerstgrasser MAndre EKoenig SDastani MSukthankar G(2018)On the Complexity of Optimal Correlated Auctions and Reverse AuctionsProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237474(605-613)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237474
Fu HLiaw CLu PTang ZCzumaj A(2018)The value of information concealmentProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175467(2533-2544)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175467
Dobzinski SUziely NTardos EElkind EVohra R(2018)Revenue Loss in Shrinking MarketsProceedings of the 2018 ACM Conference on Economics and Computation10.1145/3219166.3219196(431-442)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3219166.3219196

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents