Organizer(s):

Sepehr Assadi, Rutgers University

Swastik Kopparty, Rutgers University

Ariel Schvartzman, DIMACS

Abstract

How should a seller price items when facing a single buyer in order to maximize the seller's revenue? In seminal work, Myerson showed that it suffices to post a single, deterministic price in order to extract the optimal revenue. Incredibly, the result still holds even if the seller is selling n identical copies of the same item. Unfortunately, this beautiful result fails to generalize beyond a single item: even for two non-identical goods, there exist distributions for which a seller might have to present uncountably many options in order to extract the full revenue! In this talk I will present some recent lines of work that explore the space between selling n identical and n heterogeneous items. First, we present a recent model proposed by [Fiat et al. 2016] known as the FedEx setting where there is a total ordering over the items. In this more restricted model, [Fiat et al. 2016] show that optimal mechanisms can be characterized and give an algorithm whose menu complexity, that is the number of options the seller must present the buyer in order to get the optimal revenue, is at most exponential in the worst case. In our work [Saxena et al. 2018] we provide a tight lower bound for the FedEx problem, proving that even in this setting optimal mechanisms may require exponential menu complexity. We then show something surprising: if the seller is willing to lose a small fraction of the optimal revenue, a mechanism with polynomial menu complexity suffices.

Next, I will present a generalization of the FedEx problem, denoted as the single-minded setting, where there is instead a partial ordering over the items. For the single-minded setting we show that even for an instance with three partially ordered items, the minimal single-minded instance that is not a FedEx instance, the menu complexity of the optimal mechanism might be unbounded but finite [Devanur et al. 2020].

Taken together, our results place the menu complexity of these inter-dimensional settings (as they came to be known) in a smooth scale between the single item case (where the menu complexity is one) and the multi-item case (where the menu complexity is un- countable), with the menu complexity of the FedEx setting being exponential and the menu complexity of the single-minded setting being unbounded but finite.

This talk is based on three papers:

- The FedEx Problem. Fiat, Goldner, Karlin, Koutsoupias. EC 2016.

- The Menu Complexity of “One-and-a-Half-Dimensional" Mechanism Design. Saxena, Schvartzman, Weinberg. SODA 2018.

- Optimal Mechanism Design for Single-Minded Agents. Devanur, Goldner, Saxena, Schvartzman, Weinberg. EC 2020.

The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar.