Credible, Truthful, and Two-Round (Optimal) Auctions via Cryptographic Commitments

Matheus V.X. Ferreira, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the sale of a single item to multiple buyers by a revenue-maximizing seller. Recent work of Akbarpour and Li formalizes credibility as an auction desideratum, and prove that the only optimal, credible, strategyproof auction is the ascending price auction with reserves. In contrast, when buyers' valuations are MHR, we show that the mild additional assumption of a cryptographically secure commitment scheme suffices for a simple two-round auction which is optimal, strategyproof, and credible (even when the number of bidders is only known by the auctioneer). We extend our analysis to the case when buyer valuations are α-strongly regular for any α > 0, up to arbitrary ϵ in credibility. Interestingly, we also prove that this construction cannot be extended to regular distributions, nor can the ϵ be removed with multiple bidders.

Original languageEnglish (US)
Title of host publicationEC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages683-712
Number of pages30
ISBN (Electronic)9781450379755
DOIs
StatePublished - Jul 13 2020
Event21st ACM Conference on Economics and Computation, EC 2020 - Virtual, Online, Hungary
Duration: Jul 13 2020Jul 17 2020

Publication series

NameEC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation

Conference

Conference21st ACM Conference on Economics and Computation, EC 2020
CountryHungary
CityVirtual, Online
Period7/13/207/17/20

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Economics and Econometrics
  • Statistics and Probability
  • Computational Mathematics

Keywords

  • credible mechanisms
  • cryptographic auctions
  • mechanism design and approximation
  • mechanism design with imperfect commitment
  • optimal auction design

Fingerprint Dive into the research topics of 'Credible, Truthful, and Two-Round (Optimal) Auctions via Cryptographic Commitments'. Together they form a unique fingerprint.

  • Cite this

    Ferreira, M. V. X., & Weinberg, S. M. (2020). Credible, Truthful, and Two-Round (Optimal) Auctions via Cryptographic Commitments. In EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation (pp. 683-712). [3399495] (EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation). Association for Computing Machinery, Inc. https://doi.org/10.1145/3391403.3399495