Document Open Access Logo

Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for All Distributions

Authors Meryem Essaidi, Matheus V. X. Ferreira, S. Matthew Weinberg

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.66.pdf
  • Filesize: 0.71 MB
  • 19 pages

Document Identifiers

Author Details

Meryem Essaidi
  • Computer Science, Princeton University, NJ, USA
Matheus V. X. Ferreira
  • Computer Science, Harvard University, MA, USA
S. Matthew Weinberg
  • Computer Science, Princeton University, NJ, USA

Funding

  • Ferreira, Matheus V. X.: completed part of this work while at Princeton University.

Cite AsGet BibTex

Meryem Essaidi, Matheus V. X. Ferreira, and S. Matthew Weinberg. Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for All Distributions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 66:1-66:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.66

Abstract

We consider a revenue-maximizing seller with a single item for sale to multiple buyers with independent and identically distributed valuations. Akbarpour and Li (2020) show that the only optimal, credible, strategyproof auction is the ascending price auction with reserves which has unbounded communication complexity. Recent work of Ferreira and Weinberg (2020) circumvents their impossibility result assuming the existence of cryptographically secure commitment schemes, and designs a two-round credible, strategyproof, optimal auction. However, their auction is only credible when buyers' valuations are MHR or α-strongly regular: they show their auction might not be credible even when there is a single buyer drawn from a non-MHR distribution. In this work, under the same cryptographic assumptions, we identify a new single-item auction that is credible, strategyproof, revenue optimal, and terminates in constant rounds in expectation for all distributions with finite monopoly price.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic mechanism design
  • Applied computing → Online auctions
  • Security and privacy → Cryptography
Keywords
  • Credible Auctions
  • Cryptographically Secure
  • Single-Item

Metrics

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

References

  1. Mohammad Akbarpour and Shengwu Li. Credible auctions: A trilemma. Econometrica, 88(2):425-467, 2020. Google Scholar
  2. Moshe Babaioff, Shahar Dobzinski, Sigal Oren, and Aviv Zohar. On bitcoin and red balloons. In Proceedings of the 13th ACM conference on electronic commerce, pages 56-73, 2012. Google Scholar
  3. Iddo Bentov and Ranjit Kumaresan. How to use bitcoin to design fair protocols. In Annual Cryptology Conference, pages 421-439, 2014. Google Scholar
  4. Phillip G. Bradford, Sunju Park, Michael H Rothkopf, and Heejin Park. Protocol completion incentive problems in cryptographic vickrey auctions. Electronic Commerce Research, 8(1):57-77, 2008. Google Scholar
  5. Vitalik Buterin, Eric Conner, Rick Dudley, Matthew Slipper, and Ian Norden. Ethereum improvement proposal 1559: Fee market change for eth 1.0 chain. URL: https://github.com/ethereum/EIPs/blob/master/EIPS/eip-1559.md.
  6. Xi Chen, Christos Papadimitriou, and Tim Roughgarden. An axiomatic approach to block rewards. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, pages 124-131, 2019. Google Scholar
  7. Hao Chung and Elaine Shi. Foundations of transaction fee mechanism design. arXiv preprint arXiv:2111.03151, 2021. Google Scholar
  8. Richard Cleve. Limits on the security of coin flips when half the processors are faulty. In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 364-369, 1986. Google Scholar
  9. Constantinos Daskalakis, Maxwell Fishelson, Brendan Lucier, Vasilis Syrgkanis, and Santhoshini Velusamy. Simple, credible, and approximately-optimal auctions. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 713-713, 2020. Google Scholar
  10. Danny Dolev, Cynthia Dwork, and Moni Naor. Nonmalleable cryptography. SIAM review, 45(4):727-784, 2003. Google Scholar
  11. Matheus V. X. Ferreira, Daniel J. Moroz, David C. Parkes, and Mitchell Stern. Dynamic posted-price mechanisms for the blockchain transaction-fee market. In Proceedings of the 3rd ACM conference on Advances in Financial Technologies, AFT '21, New York, NY, USA, 2021. Association for Computing Machinery. Google Scholar
  12. Matheus VX Ferreira and S Matthew Weinberg. Credible, truthful, and two-round (optimal) auctions via cryptographic commitments. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 683-712, 2020. Google Scholar
  13. Matheus VX Ferreira and S Matthew Weinberg. Proof-of-stake mining games with perfect randomness. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 433-453, 2021. Google Scholar
  14. Shengwu Li. Obviously strategy-proof mechanisms. American Economic Review, 107(11):3257-87, 2017. Google Scholar
  15. Qingmin Liu, Konrad Mierendorff, Xianwen Shi, and Weijie Zhong. Auctions with limited commitment. American Economic Review, 109:876-910, 2019. Google Scholar
  16. Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981. Google Scholar
  17. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2009. URL: http://www.bitcoin.org/bitcoin.pdf.
  18. Marek Pycia and Madhav Raghavan. Non-bossiness and first-price auctions, 2021. Google Scholar
  19. Daniël Reijsbergen, Shyam Sridhar, Barnabé Monnot, Stefanos Leonardos, Stratis Skoulakis, and Georgios Piliouras. Transaction fees on a honeymoon: Ethereum’s eip-1559 one month later. arXiv preprint arXiv:2110.04753, 2021. Google Scholar
  20. Tim Roughgarden. Transaction fee mechanism design. arXiv preprint arXiv:2106.01340, 2021. Google Scholar
  21. Vasiliki Skreta. Optimal auction design under non-commitment. Journal of Economic Theory, 159:854-890, 2013. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact