Time

4:30-6pm, Monday, Nov 25, 2024

Location

Rice 109

Speaker

Matheus Ferreira

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

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 (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 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 \(\alpha\)-strongly regular for any \(\alpha > 0\), up to arbitrary \(\epsilon\) in credibility. Interestingly, we also prove that this construction cannot be extended to regular distributions, nor can the \(\epsilon\) be removed with multiple bidders.

Bio:

Matheus is an Assistant Professor of Computer Science at the University of Virginia. His research interests include AI, Algorithmic Economics, and Security. He applies artificial intelligence, optimization, and theoretical computer science tools to create secure, transparent, and auditable platforms. For instance, he designs auctions that prevent auctioneers from profiting from manipulations. Previously he was a Postdoctoral Fellow of Computer Science at Harvard University. He earned his Ph.D. (2022) and M.A. (2018) in Computer Science from Princeton University and his B.S. in Computer Engineering (2016) from the Federal University of Itajubá. Matheus hails from Itabira, the Brazilian capital of poetry.