Buy-Many Mechanisms: A New Perspective on Revenue-Optimal Mechanism Design

Multi-item mechanisms can be very complex offering many different bundles to the buyer that could even be randomized. Such complexity is thought to be necessary as the revenue gaps between randomized and deterministic mechanisms, or deterministic and simple mechanisms are huge even for simple classes of valuations. We challenge this conventional belief by showing that these large gaps can only happen in situations where buyers' actions are severely restricted. These are situations where the mechanism sells a bundle of items at a higher price than the sum of the prices of the constituent items and buyers wanting to purchase such a bundle must pay this premium as they are not allowed to purchase the constituents separately.

We accordingly propose a new class of mechanisms that we call buy-many mechanisms wherein the buyer is allowed to interact with the mechanism multiple times and purchase as many (randomized) bundles as he pleases. Most real-world mechanisms are buy-many. We show that optimal buy-many mechanisms satisfy many nice properties that general mechanisms do not: they are approximable by simple mechanisms; their revenue is a smooth function of the buyer's value distribution; and they have bounded description complexity.

This talk is based on joint work with Rojin Rezvan, Yifeng Teng, and Christos Tzamos.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.