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:
- One good:
- One menu entry suffices for optimal revenue extraction (Myerson, 1981).
- Two or more heterogeneous goods:
- Infinitely many menu entries are required (at the worst case) for optimal revenue extraction (Daskalakis et al., 2013).
- "Classic" FedEx:
- A menu size that is exponential in the number of possible deadlines n is required (Saxena et al., 2018) and sufficient (Fiat at al., 2016) for optimal revenue extraction.
- The "partially-ordered" variant:
- A finite, however arbitrarily large (not even upper-bounded exponentially) number of menu entries is required and sufficient for optimal revenue extraction (Devanur et al., 2018).
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:
- One good:
- Once again, one menu entry suffices (Myerson, 1981).
- Two or more goods:
- A menu size that is exponential in the number of items n suffices (Hart and Nisan (2013) under boundedness assumptions; Babaioff et al. (2017) generally).
- When ε=1/n, such an exponential menu size is also required (Babaioff et al., 2017); for certain constant ε, a polynomial menu size is sufficient and required (Babaioff et al., 2017).
- For a fixed number of items n, a menu size that is polynomial in ε is sufficient (Hart and Nisan (2013) under boundedness assumptions; Babaioff et al. (2017) generally) and required (Gonczarowski, 2018).
- Polynomially many menu items suffice, and are in fact required when ε=1/n (Saxena et al., 2018).
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:
- 08:30am – 10:30am: The menu size of multi-item auctions (Yannai)
- 11:00am – 12:30am: The menu size of FedEx and related auctions (Kira)
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.
- Roger B. Myerson, Optimal Auction Design, MOR 1981
- Patrick Briest, Shuchi Chawla, Robert Kleinberg, S. Matthew Weinberg, Pricing Randomized Allocations, SODA 2010 [PDF]
- Sergiu Hart and Noam Nisan, The Menu-Size Complexity of Auctions, EC 2013 [PDF]
- Costantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos, Mechanism Design via Optimal Transport, EC 2013 [PDF]
- Shaddin Dughmi, Li Han, and Noam Nisan, Sampling and Representation Complexity of Revenue Maximization, WINE 2014 [PDF]
- Amos Fiat, Kira Goldner, Anna R. Karlin, and Elias Koutsoupias, The FedEx Problem, EC 2016 [PDF]
- Moshe Babaioff, Yannai A. Gonczarowski, and Noam Nisan, The Menu-Size Complexity of Revenue Approximation, STOC 2017 [PDF]
- Raghuvansh R. Saxena, Ariel Schvartzman, and S. Matthew Weinberg, The Menu-Complexity of "One-and-a-Half Dimensional" Mechanism Design, SODA 2018 [PDF]
- Yannai A. Gonczarowski, Bounding the Menu-Size of Approximately Optimal Auctions via Optimal-Transport Duality, STOC 2018 [PDF]
- Nikhil R. Devanur, Kira Goldner, Raghuvansh R. Saxena, Ariel Schvartzman, and S. Matthew Weinberg, Selling Partially-Ordered Items: Exploring the Space between Single- and Multi-Dimensional Mechanism Design, 2018