# Menu-size Complexity and Revenue Continuity of Buy-many Mechanisms

arXiv: https://arxiv.org/abs/2003.10636 · HTML: https://mlsanity.com/paper/2003.10636/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Mar 2020.

## Built on by (most cited first, 1 of 1)

- [Learning Optimal Posted Prices for a Unit-Demand Buyer](https://mlsanity.com/paper/2506.02284/) (2025)

## Abstract (arXiv)

We study the multi-item mechanism design problem where a monopolist sells n heterogeneous items to a single buyer. We focus on buy-many mechanisms, a natural class of mechanisms frequently used in practice. The buy-many property allows the buyer to interact with the mechanism multiple times instead of once as in the more commonly studied buy-one mechanisms. This imposes additional incentive constraints and thus restricts the space of mechanisms that the seller can use. In this paper, we explore the qualitative differences between buy-one and buy-many mechanisms focusing on two important properties: revenue continuity and menu-size complexity. Our first main result is that when the value function of the buyer is perturbed multiplicatively by a factor of 1±ε, the optimal revenue obtained by buy-many mechanisms only changes by a factor of 1 ± textrmpoly(n,ε). In contrast, for buy-one mechanisms, the revenue of the resulting optimal mechanism after such a perturbation can change arbitrarily. Our second main result shows that under any distribution of arbitrary valuations, finite menu size suffices to achieve a (1-ε)-approximation to the optimal buy-many mechanism. We give tight upper and lower bounds on the number of menu entries as a function of n and ε. On the other hand, such a result fails to hold for buy-one mechanisms as even for two items and a buyer with either unit-demand or additive valuations, the menu-size complexity of approximately optimal mechanisms is unbounded.