Credible, Truthful, and Two-Round (Optimal) Auctions via Cryptographic Commitments
This addresses the challenge of ensuring credibility in revenue-maximizing auctions for sellers and buyers, offering a novel solution for specific valuation types, though it is incremental as it builds on prior work on credibility.
The paper tackles the problem of designing optimal, credible, and strategyproof auctions for selling a single item, showing that with cryptographically secure commitments, a simple two-round auction achieves these properties for MHR valuations and extends to α-strongly regular valuations with arbitrary ε in credibility, but cannot be extended to regular distributions or remove ε with multiple bidders.
We consider the sale of a single item to multiple buyers by a revenue-maximizing seller. Recent work of Akbarpour and Li formalizes \emph{credibility} as an auction desideratum, and prove that the only optimal, credible, strategyproof auction is the ascending price auction with reserves (Akbarpour and Li, 2019). In contrast, when buyers' valuations are MHR, we show that the mild additional assumption of a cryptographically secure commitment scheme suffices for a simple \emph{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 $\varepsilon$ in credibility. Interestingly, we also prove that this construction cannot be extended to regular distributions, nor can the $\varepsilon$ be removed with multiple bidders.