Bounding the Menu-Size of Approximately Optimal Auctions via Optimal-Transport Duality

Location: 
Feldman Building, Middle floor, Room 130
Dates: 
Sunday, June 3, 2018 - 11:30 to 13:00
Lecturers: 
Yannai A. Gonczarowski
The Hebrew University of Jerusalem and Microsoft Research
Abstract: 

The question of the minimum menu-size for approximate (i.e., up-to-ε)Bayesian revenue maximization when selling two goods to an additiverisk-neutral quasilinear buyer was introduced by Hart and Nisan (2013), whogive an upper bound of O(1/ε4) for this problem. Using theoptimal-transport duality framework of Daskalakis, Deckelbaum, and Tzamos(2013, 2015), we derive the first lower bound for this problem — of Ω(1/4√ε),even when the values for the two goods are drawn i.i.d. from "nice"distributions, establishing how to reason about approximately optimalmechanisms via this duality framework. This bound implies, for any fixednumber of goods, a tight bound of Θ(log 1/ε) on the minimum deterministiccommunication complexity guaranteed to suffice for running someapproximately revenue-maximizing mechanism, thereby completely resolvingthis problem. As a secondary result, we show that under standard economicassumptions on distributions, the above upper bound of Hart and Nisan(2013) can be strengthened to O(1/ε2).