On the Computational Complexity of Optimal Simple Mechanisms
On the Computational Complexity of Optimal Simple Mechanisms
复制标题
关于最优简单机构的计算复杂性
DOI：
10.1145/2840728.2840736
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. Rubinstein
中科院分区：
文献类型：
--
作者：
A. Rubinstein
我们考虑一个垄断卖方面对一个单一的买方，在n个异质的，独立的项目的附加价值。众所周知，在这个重要的设置中，优化机制可能需要随机化[12]，使用无限大小的菜单[9]，并且可能是计算上难以处理的[8]。这引发了最近的兴趣，寻找简单的机制，获得合理的近似最佳收入[10，15，3]。在这项工作中，我们试图找到最佳的简单机制。有许多方法可以定义简单的机制。在这里，我们将搜索限制在分区机制上，卖方将物品分成不相交的捆绑包，并为每个捆绑包发布价格;买方可以购买任何数量的捆绑包。我们给出了一个PTAS的问题，找到一个收入最大化的分区机制，并证明了该问题是强NP-困难的。途中，我们证明了结构特性的近最优分区机制，这可能是独立的利益：例如，总是存在一个近最优分区机制，只使用一个常数的非平凡束（即束与一个以上的项目）。
We consider a monopolist seller facing a single buyer with additive valuations over n heterogeneous, independent items. It is known that in this important setting optimal mechanisms may require randomization [12], use menus of infinite size [9], and may be computationally intractable [8]. This has sparked recent interest in finding simple mechanisms that obtain reasonable approximations to the optimal revenue [10, 15, 3]. In this work we attempt to find the optimal simple mechanism. There are many ways to define simple mechanisms. Here we restrict our search to partition mechanisms, where the seller partitions the items into disjoint bundles and posts a price for each bundle; the buyer is allowed to buy any number of bundles. We give a PTAS for the problem of finding a revenue-maximizing partition mechanism, and prove that the problem is strongly NP-hard. En route, we prove structural properties of near-optimal partition mechanisms which may be of independent interest: for example, there always exists a near-optimal partition mechanism that uses only a constant number of non-trivial bundles (i.e. bundles with more than one item).
DOI：
10.1145/2764468.2764539
发表时间：
2014-09
期刊：
Proceedings of the Sixteenth ACM Conference on Economics and Computation
影响因子：
--
作者：
C. Daskalakis;Alan Deckelbaum;Christos Tzamos
通讯作者：
C. Daskalakis;Alan Deckelbaum;Christos Tzamos