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

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.