On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer
复制标题
关于单位需求购买者的最优彩票定价和随机机制的复杂性
DOI：
10.1137/17m1136481
复制
发表时间：
2022
影响因子：
1.6
通讯作者：
Yannakakis, Mihalis
中科院分区：
文献类型：
--
作者：
Chen, Xi;Diakonikolas, Ilias;Orfanou, Anthi;Paparas, Dimitris;Sun, Xiaorui;Yannakakis, Mihalis
我们研究了单个单位需求买家的最优彩票问题和最优机制设计问题，其物品价值来自独立分布。这两个问题的最佳解决方案的特点是具有指数级多个变量的线性规划。对于最优彩票问题的菜单大小复杂性，我们提出了一个明确、简单的实例，其分布的支持大小为 2，并表明需要指数级数量的彩票才能实现最优收入。我们还表明，当分布具有支持大小 2 并共享相同的高值时，更简单的项目定价方案可以获得与彩票最优菜单相同的收入。对于支持大小为 2 的两个项目的情况也是如此（但不一定具有相同的高值）。对于最优机制设计问题的计算复杂性，我们表明，除非多项式时间层次结构崩溃（更准确地说），否则即使分布的支持大小为 3，也没有有效的随机算法来实现最优机制。
We study the optimal lottery problem and the optimal mechanism design problem in the setting of a single unit-demand buyer with item values drawn from independent distributions. Optimal solutions to both problems are characterized by a linear program with exponentially many variables. For the menu size complexity of the optimal lottery problem, we present an explicit, simple instance with distributions of support size 2, and show that exponentially many lotteries are required to achieve the optimal revenue. We also show that, when distributions have support size 2 and share the same high value, the simpler scheme of item pricing can achieve the same revenue as the optimal menu of lotteries. The same holds for the case of two items with support size 2 (but not necessarily the same high value). For the computational complexity of the optimal mechanism design problem, we show that unless the polynomial-time hierarchy collapses (more exactly,), there is no efficient randomized algorithm to implement an optimal mechanism even when distributions have support size 3.