TY - GEN
T1 - Credible, Truthful, and Two-Round (Optimal) Auctions via Cryptographic Commitments
AU - Ferreira, Matheus V.X.
AU - Weinberg, S. Matthew
N1 - Publisher Copyright:
© 2020 ACM.
PY - 2020/7/13
Y1 - 2020/7/13
N2 - 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.
AB - 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.
KW - credible mechanisms
KW - cryptographic auctions
KW - mechanism design and approximation
KW - mechanism design with imperfect commitment
KW - optimal auction design
UR - http://www.scopus.com/inward/record.url?scp=85089262679&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089262679&partnerID=8YFLogxK
U2 - 10.1145/3391403.3399495
DO - 10.1145/3391403.3399495
M3 - Conference contribution
AN - SCOPUS:85089262679
T3 - EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
SP - 683
EP - 712
BT - EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
PB - Association for Computing Machinery
T2 - 21st ACM Conference on Economics and Computation, EC 2020
Y2 - 13 July 2020 through 17 July 2020
ER -