Tata Institute of Fundamental Research

Simple, Credible, and Approximately-Optimal Auctions

STCS Seminar
Speaker: Santhoshini Velusamy (Harvard University Cambridge, Massachusetts.)
Organiser: Arkadev Chattopadhyay
Date: Tuesday, 28 Jul 2020, 14:00 to 15:00

(Scan to add to calendar)
Abstract:  Abstract:  We present a general framework, applicable to both truthful and non-truthful auctions, for designing approximately revenue-optimal mechanisms for multi-item additive auctions. Given a (not necessarily truthful) single-item auction format satisfying certain technical conditions, we run simultaneous item auctions augmented with a personalized entry fee that each bidder must pay before accessing the auction. The entry fee depends only on the prior distribution of bidder types, and in particular, is independent of the realized bids.
We bound the revenue of the resulting two-part tariff mechanism using a novel geometric lemma that enables us to provide revenue guarantees for many common non-truthful auctions that previously had none. Our framework can be used with many common auction formats, such as simultaneous first-price, simultaneous second-price, and simultaneous all-pay auctions. For all-pay auctions, we prove that the resulting mechanism is also credible in the sense that the auctioneer cannot benefit by deviating from the stated mechanism after observing agent bids. This is the first static credible mechanism for multi-item additive auctions that guarantees a constant factor of the optimal revenue.
A paper based on this joint work with Costis Daskalakis, Maxwell Fishelson, Brendan Lucier, and Vasilis Syrgkanis was presented at the Twenty-First ACM Conference on Economics and Computation (EC 2020). The arXiv version of the paper is available at https://arxiv.org/abs/2002.06702