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) and to Dobzinski (2011). Corollaries involving menu sizes have been deduced by several papers since (Daskalakis, Deckelbaum, Tzamos, 2013, 2015; 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 and 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; Riley and Zeckhauser, 1983).
- Two or more heterogeneous goods, even with independent valuations:
- Infinitely many menu entries are required (at the worst case) for optimal revenue extraction (Daskalakis et al., 2013, 2015).
- "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; Riley and Zeckhauser, 1983).
- Two or more goods with independent valuations:
- 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^2 (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) [slides]
- 11:00am – 12:30am: The menu size of FedEx and related auctions (Kira) [slides]
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, and is the recipient of the 2018 Michael B. Maschler Prize of the Israeli Chapter of the Game Theory Society.
- Roger B. Myerson, Optimal Auction Design, MOR 1981
- John Riley and Richard Zeckhauser, Optimal Selling Strategies: When to Haggle, When to Hold Firm, QJE 1983
- Patrick Briest, Shuchi Chawla, Robert Kleinberg, and S. Matthew Weinberg, Pricing Randomized Allocations, SODA 2010 [PDF]
- Shahar Dobzinski, An Impossibility Result for Truthful Combinatorial Auctions with Submodular Valuations, STOC 2011 [PDF]
- Shaddin Dughmi and Jan Vondrak, Limitations of Randomized Mechanisms for Combinatorial Auctions, FOCS 2011 [PDF]
- Shahar Dobzinski and Jan Vondrak, The Computational Complexity of Truthfulness in Combinatorial Auctions, EC 2012 [PDF]
- Costantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos, Mechanism Design via Optimal Transport, EC 2013 [PDF]
- Sergiu Hart and Noam Nisan, The Menu-Size Complexity of Auctions, EC 2013 [PDF]
- Noam Nisan, Algorithmic Mechanism Design through the Lens of Multi-Unit Auctions, Handbook of Game Theory, Volume 4, 2014 [PDF]
- Zihe Wang and Pingzhong Tang, Optimal Mechanisms with Simple Menus, EC 2014 [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]
- Nikhil R. Devanur and S. Matthew Weinberg, The Optimal Mechanism for Selling to a Budget Constrained Buyer: The General Case, EC 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]
- Moshe Babaioff, Noam Nisan, and Aviad Rubinstein, Optimal Deterministic Mechanisms for an Additive Buyer, EC 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 [PDF]