The Menu Size of Precise and Approximate Revenue-Maximizing Auctions

A Tutorial at EC 2018

Monday, June 18th, 2018    8:30am – 12:30pm

Kira Goldner and Yannai A. Gonczarowski


The menu-size measure of the complexity of auctions was introduced in the seminal paper of Hart and Nisan (2013), with some key ideas going back to Briest, Chawla, Kleinberg, Weinberg (2010). Corollaries involving menu sizes have been deduced by several papers since (Daskalakis, Deckelbaum, Tzamos 2013; Dughmi, Han, Nisan 2014). However, in the past year or so, we have seen a significant surge in papers dealing centrally with menu sizes in two major directions.

The first direction is regarding the multi-item auctions setting as in Hart and Nisan (Babaioff, Gonczarowski, Nisan 2017; Gonczarowski 2018). The second direction is regarding the FedEx setting and its variants, where a buyer has a single preferred outcome, and there is some structure on the outcomes that is known to the seller, such that reporting a buyer's preferred outcome and the value for it describes the buyer's value for all other outcomes as well (Fiat, Goldner, Karlin, Koutsoupias 2016; Devanur, Weinberg 2017, Saxena, Schvartzman, Weinberg 2018; Devanur, Goldner, Saxena, Schvartzman, Weinberg 2018). These settings are becoming better and better understood to nicely lie within the phase transition between single- and multi-item auctions.

Target Audience and Prerequisites

The tutorial is self-contained, and previous knowledge of menu-size concepts (or of any particular auction setting such as the FedEx setting) is not required. The tutorial is intended for students and researchers who are interested in getting acquainted with the recent explosion of results, directions, and open questions on menu sizes, as well as their far-reaching implications, e.g., for the communication complexity of auctions.


Precise revenue maximization

For precise revenue maximization, there is a harsh dichotomy between the required menu size when selling one good on the one hand, and when selling two or more goods on the other hand: The FedEx problem is a setting where a buyer has a value for shipping a package and a deadline by which it must be received. The buyer is content with receiving any shipping option that gets the package to its destination in time. This problem and its recent variants provide a very interesting middle ground between the dichotomous one-good and multiple-good settings:

Approximate revenue maximization

The harsh dichotomy between the one-good and multiple-goods settings carries over to approximate revenue maximization: Once again, the FedEx setting provides a very interesting middle ground here:


This will be a half-day tutorial that mostly focuses on results, with only glimpses of proofs/techniques. It will consist of two lectures with a 30-minute break in between:

Speakers Biographies

Kira Goldner is a fourth-year PhD student at the University of Washington in Computer Science and Engineering, advised by Anna Karlin. Her research focuses on problems in mechanism design, particularly on (1) maximizing revenue in settings that are motivated by practice, (2) relaxing traditional assumptions, and (3) on mechanism design for social good, e.g. within health insurance and online labor markets. She is a 2017–19 recipient of the Microsoft Research PhD Fellowship and was a 2016 recipient of a Google Anita Borg Scholarship.

Yannai Gonczarowski is a Ph.D. student at the School of Computer Science, the Department of Mathematics, and the Center for the Study of Rationality, at the Hebrew University of Jerusalem, where his advisors are Noam Nisan and Sergiu Hart. He holds an M.Sc. in mathematics and a B.Sc. in mathematics and computer science from the same institution. He is also a professionally trained opera singer, holding a master's as well as a bachelor's degree in classical singing. He is also a research intern at Microsoft Research in Herzliya, Israel. His main research interests lie in game theory and algorithmic game theory, spanning topics from mechanism design with and without money, to epistemic logic. He is an Adams Fellow of the Israel Academy of Sciences and Humanities.

Related Papers