The Menu-Size of Approximately Optimal Auctions

(Click “Event Website” above to access the zoom link.)

Abstract:
We consider a monopolist who wishes to sell n goods to a single additive buyer, where the buyer’s valuations for the goods are drawn according to independent distributions. It is well known that—unlike in the single item case—the revenue-optimal auction (a pricing scheme) may be complex, sometimes requiring a continuum of menu entries, that is, offering the buyer a choice between a continuum of lottery tickets. It is also known that simple auctions with a finite bounded number of menu entries (lotteries for the buyer to choose from) can extract a constant fraction of the optimal revenue, as well as that for the case of bounded distributions it is possible to extract an arbitrarily high fraction of the optimal revenue via a finite bounded menu size. Nonetheless, the question of the possibility of extracting an arbitrarily high fraction of the optimal revenue via a finite menu size, when the valuation distributions possibly have unbounded support (or via a finite bounded menu size when the support of the distributions is bounded by an unknown bound), remained open since the seminal paper of Hart and Nisan (2013), and so has the question of any lower-bound on the menu-size that suffices for extracting an arbitrarily high fraction of the optimal revenue when selling a fixed number of goods, even for two goods and even for i.i.d. bounded distributions.

In this talk, we resolve both of these questions. We first show that for every n and for every ε>0, there exists a menu-size bound C=C(n,ε) such that auctions of menu size at most C suffice for extracting a (1-ε) fraction of the optimal revenue from any valuation distributions, and give an upper bound on C(n,ε), even when the valuation distributions are unbounded and nonidentical. We then proceed to giving two lower bounds, which hold even for bounded i.i.d. distributions: one on the dependence on n when ε=1/n and n grows large, and the other on the dependence on ε when n is fixed and ε grows small. Finally, we apply these upper and lower bounds to derive results regarding the deterministic communication complexity required to run an auction that achieves such an approximation.

Based upon:
* The Menu-Size Complexity of Revenue Approximation, Moshe Babaioff, Y. A. G., and Noam Nisan, STOC 2017
* Bounding the Menu-Size of Approximately Optimal Auctions via Optimal-Transport Duality, Y. A. G., STOC 2018

Bio:
Yannai Gonczarowski is a postdoctoral researcher at Microsoft Research New England. His main research interests lie in the interface between the theory of computation, economic theory, and game theory—an area commonly referred to as Algorithmic Game Theory. In particular, Yannai is interested in various aspects of complexity in mechanism design (where mechanisms are defined broadly from auctions to matching markets), including the interface between mechanism design and machine learning. Yannai received his PhD from the Departments of Math and CS, and the Center for the Study of Rationality, at the Hebrew University of Jerusalem, where he was advised by Sergiu Hart and Noam Nisan, as an Adams Fellow of the Israel Academy of Sciences and Humanities. Throughout most of his PhD studies, he was also a long-term research intern at Microsoft Research in Herzliya. He holds an M.Sc. in Math (summa cum laude) and a B.Sc. in Math and CS (summa cum laude, Valedictorian) from the Hebrew University. Yannai is also a professionally-trained opera singer, having acquired a bachelor’s degree and a master’s degree in Classical Singing at the Jerusalem Academy of Music and Dance. For his doctoral dissertation, Yannai was awarded the Hans Wiener Prize of the Hebrew University of Jerusalem, the 2018 Michael B. Maschler Prize of the Israeli Chapter of the Game Theory Society, and the ACM SIGecom Doctoral Dissertation Award for 2018. Yannai is also the recipient of the ACM SIGecom Award for Best Presentation by a Student or Postdoctoral Researcher at EC’18, and of the Best Paper Award at MATCH-UP’19. His first textbook, “Mathematical Logic through Python” (Gonczarowski and Nisan), which introduces a new approach to teaching the material of a basic Logic course to Computer Science students, tailored to the unique intuitions and strengths of this cohort of students, is forthcoming in Cambridge University Press.