TY - GEN
T1 - Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for All Distributions
AU - Essaidi, Meryem
AU - Ferreira, Matheus V.X.
AU - Weinberg, S. Matthew
N1 - Publisher Copyright:
© Meryem Essaidi, Matheus V.X. Ferreira, and S. Matthew Weinberg; licensed under Creative Commons License CC-BY 4.0
PY - 2022/1/1
Y1 - 2022/1/1
N2 - 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.
AB - 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.
KW - Credible auctions
KW - Cryptographically secure
KW - Single-item
UR - http://www.scopus.com/inward/record.url?scp=85120603083&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85120603083&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2022.66
DO - 10.4230/LIPIcs.ITCS.2022.66
M3 - Conference contribution
AN - SCOPUS:85120603083
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 13th Innovations in Theoretical Computer Science Conference, ITCS 2022
A2 - Braverman, Mark
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 13th Innovations in Theoretical Computer Science Conference, ITCS 2022
Y2 - 31 January 2022 through 3 February 2022
ER -