Brief Announcement: Bayesian Auctions with Efficient Queries

Authors Jing Chen, Bo Li, Yingkai Li, Pinyan Lu



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.108.pdf
  • Filesize: 333 kB
  • 4 pages

Document Identifiers

Author Details

Jing Chen
  • Department of Computer Science, Stony Brook University, Stony Brook, NY 11794, USA
Bo Li
  • Department of Computer Science, Stony Brook University, Stony Brook, NY 11794, USA
Yingkai Li
  • Department of Computer Science, Stony Brook University, Stony Brook, NY 11794, USA
Pinyan Lu
  • Institute for Theoretical Computer Science, Shanghai University of Finance and Economics, Shanghai 200433, China

Cite AsGet BibTex

Jing Chen, Bo Li, Yingkai Li, and Pinyan Lu. Brief Announcement: Bayesian Auctions with Efficient Queries. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 108:1-108:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.108

Abstract

Generating good revenue is one of the most important problems in Bayesian auction design, and many (approximately) optimal dominant-strategy incentive compatible (DSIC) Bayesian mechanisms have been constructed for various auction settings. However, most existing studies do not consider the complexity for the seller to carry out the mechanism. It is assumed that the seller knows "each single bit" of the distributions and is able to optimize perfectly based on the entire distributions. Unfortunately this is a strong assumption and may not hold in reality: for example, when the value distributions have exponentially large supports or do not have succinct representations. In this work we consider, for the first time, the query complexity of Bayesian mechanisms. We only allow the seller to have limited oracle accesses to the players' value distributions, via quantile queries and value queries. For a large class of auction settings, we prove logarithmic lower-bounds for the query complexity for any DSIC Bayesian mechanism to be of any constant approximation to the optimal revenue. For single-item auctions and multi-item auctions with unit-demand or additive valuation functions, we prove tight upper-bounds via efficient query schemes, without requiring the distributions to be regular or have monotone hazard rate. Thus, in those auction settings the seller needs to access much less than the full distributions in order to achieve approximately optimal revenue.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory and mechanism design
Keywords
  • The complexity of Bayesian mechanisms
  • quantile queries
  • value queries

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Pablo Azar, Constantinos Daskalakis, Silvio Micali, and S Matthew Weinberg. Optimal and efficient parametric auctions. In 24th Symposium on Discrete Algorithms (SODA'13), pages 596-604, 2013. Google Scholar
  2. Pablo Azar and Silvio Micali. Parametric digital auctions. In 4rd Innovations in Theoretical Computer Science Conference (ITCS'13), pages 231-232, 2013. Google Scholar
  3. Yang Cai and Constantinos Daskalakis. Learning multi-item auctions with (or without) samples. In 58th Symposium on Foundations of Computer Science (FOCS'17), pages 516-527, 2017. Google Scholar
  4. Yang Cai, Constantinos Daskalakis, and S Matthew Weinberg. An algorithmic characterization of multi-dimensional mechanisms. In 44th Annual ACM Symposium on Theory of Computing (STOC'12), pages 459-478, 2012. Google Scholar
  5. Yang Cai, Constantinos Daskalakis, and S Matthew Weinberg. Optimal multi-dimensional mechanism design: Reducing revenue to welfare maximization. In 53rd Symposium on Foundations of Computer Science (FOCS'12), pages 130-139, 2012. Google Scholar
  6. Yang Cai, Nikhil R Devanur, and S Matthew Weinberg. A duality based unified approach to Bayesian mechanism design. In 48th Annual ACM Symposium on Theory of Computing (STOC'16), pages 926-939, 2016. Google Scholar
  7. Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In 43th ACM Symposium on Theory of Computing (STOC'10), pages 311-320, 2010. Google Scholar
  8. Jing Chen, Bo Li, and Yingkai Li. From Bayesian to crowdsourced Bayesian auctions. arXiv:1702.01416, 2016. Google Scholar
  9. Jing Chen, Bo Li, Yingkai Li, and Pinyan Lu. Bayesian auctions with efficient queries, full version. arXiv:1804.07451, 2018. Google Scholar
  10. Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In 46th Annual ACM Symposium on Theory of Computing (STOC'14), pages 243-252, 2014. Google Scholar
  11. Jacques Cremer and Richard P McLean. Full extraction of the surplus in Bayesian and dominant strategy auctions. Econometrica, 56(6):1247-1257, 1988. Google Scholar
  12. Nikhil R. Devanur, Zhiyi Huang, and Christos-Alexandros Psomas. The sample complexity of auctions with side information. In 48th Annual ACM Symposium on Theory of Computing (STOC'16), pages 426-439, 2016. Google Scholar
  13. Zhiyi Huang, Yishay Mansour, and Tim Roughgarden. Making the most of your samples. In 16th ACM Conference on Economics and Computation (EC'15), pages 45-60, 2015. Google Scholar
  14. Robert Kleinberg and S Matthew Weinberg. Matroid prophet inequalities. In 44th Annual ACM Symposium on Theory of Computing (STOC'12), pages 123-136, 2012. Google Scholar
  15. Jamie Morgenstern and Tim Roughgarden. Learning simple auctions. In 29th Conference on Learning Theory (COLT'16), pages 1298-1318, 2016. Google Scholar
  16. Roger B Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58-73, 1981. Google Scholar
  17. Amir Ronen. On approximating optimal auctions. In 3rd ACM Conference on Electronic Commerce (EC'01), pages 11-17, 2001. Google Scholar
  18. Tim Roughgarden and Okke Schrijvers. Ironing in the dark. In 17th ACM Conference on Economics and Computation (EC'16), pages 1-18, 2016. Google Scholar
  19. Andrew Chi-Chih Yao. An n-to-1 bidder reduction for multi-item auctions and its applications. In 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15), pages 92-109, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail