论文标题
菜单尺寸的复杂性和收入连续性的购买机制
Menu-size Complexity and Revenue Continuity of Buy-many Mechanisms
论文作者
论文摘要
我们研究了多项目机制设计问题，其中垄断者向单个买家出售$ n $异质物品。我们专注于买入机制，这是一种自然的机制，经常在实践中使用。买家可以多次与该机构进行互动，而不是像经常研究的购买机制一样多次与该机构进行交互。这施加了其他激励限制，因此限制了卖方可以使用的机制的空间。 在本文中，我们探讨了一项重点介绍两个重要属性的购买和购买机制之间的质差：收入连续性和菜单尺寸的复杂性。 我们的第一个主要结果是，当买方的价值函数乘以$ 1 \pmε$的扰动时，通过买入机制获得的最佳收入仅会变化$ 1 \ pm \ pm \ textrm {poly} {poly}（poly}（poly}（n，ε）$）。相反，对于购买机制，这种扰动后所产生的最佳机制的收入可以任意改变。 我们的第二个主要结果表明，在任何任意估值的分布下，有限的菜单大小就足以实现$（1-ε）$ - 与最佳购买机制的近似。我们在菜单条目的数量上给出了紧密的上和下限，该功能是$ n $和$ε$。另一方面，这样的结果也无法保留购买一种机制，即使对于两个物品和具有单位需求或添加剂估值的买家，大约最佳机制的菜单尺寸复杂性也没有结合。
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\pmε$, the optimal revenue obtained by buy-many mechanisms only changes by a factor of $1 \pm \textrm{poly}(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.
