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.

- 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).

- 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).

- FedEx:
- Polynomially many menu items suffice, and are in fact required when ε=1/n (Saxena et al., 2018).

- 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