On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer
On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer
复制标题
关于添加剂买家的简单且最优确定性机制的复杂性
DOI：
10.1137/1.9781611975031.133
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Yannakakis, Mihalis.
中科院分区：
文献类型：
--
作者：
Chen, Xi;Matikas, George;Paparas, Dimitris;Yannakakis, Mihalis.
我们证明了单加性买方的收益最优确定性机制设计问题是#P难的，即使分布对每个项目的支持度为2，更重要的是，即使当最优解被保证是非常简单的：卖方为每个单独的项目选择一个价格，并为所有项目的大包选择一个价格；买方可以按给定的价格购买大包，也可以以其总的单独价格购买项目的任何子集。作为证明的直接推论，下列问题也是#P-困难的：1.确定单个物品的定价对于给定的实例是否最优，2.确定大捆绑定价是否最优，3.计算最优(确定性)收入.在积极的一面，我们证明了当分布是I.I.D.时.在支持度为2的情况下，任何机制所能获得的最优收益，即使是随机机制，都可以通过上述类型的简单解(大捆绑的折扣价的单个项目定价)来实现，并且可以在多项式时间内计算。当项目个数不变时，该问题也可以在多项式时间内求解。
We show that the Revenue-Optimal Deterministic Mechanism Design problem for a single additive buyer is #P-hard, even when the distributions have support size 2 for each item and, more importantly, even when the optimal solution is guaranteed to be of a very simple kind: the seller picks a price for each individual item and a price for the grand bundle of all the items; the buyer can purchase either the grand bundle at its given price or any subset of items at their total individual prices. The following problems are also #P-hard, as immediate corollaries of the proof:1.determining if individual item pricing is optimal for a given instance,2.determining if grand bundle pricing is optimal, and3.computing the optimal (deterministic) revenue.On the positive side, we show that when the distributions are i.i.d. with support size 2, the optimal revenue obtainable by any mechanism, even a randomized one, can be achieved by a simple solution of the above kind (individual item pricing with a discounted price for the grand bundle) and furthermore, it can be computed in polynomial time. The problem can be solved in polynomial time too when the number of items is constant.
登录
查看更多内容
关于最优简单机构的计算复杂性
DOI：
10.1145/2840728.2840736
发表时间：
2015
期刊：
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science
影响因子：
--
作者：
A. Rubinstein
通讯作者：
A. Rubinstein
关于销售多个独立分布的商品的收入最大化
DOI：
--
发表时间：
2013
影响因子：
11.1
作者：
Xinye Li;A. Yao
通讯作者：
A. Yao
DOI：
10.1137/1.9781611973075.49
发表时间：
2009
期刊：
ArXiv
影响因子：
--
作者：
Patrick Briest;Shuchi Chawla;Robert D. Kleinberg;S. Weinberg;A. P. Sloan;Foundation Fellowship
通讯作者：
Foundation Fellowship
DOI：
--
发表时间：
2011
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Yang Cai;C. Daskalakis
通讯作者：
C. Daskalakis
均匀分布拍卖的二元性和最优性
DOI：
10.1145/2600057.2602883
发表时间：
2014
期刊：
Proceedings of the fifteenth ACM conference on Economics and computation
影响因子：
--
作者：
Yiannis Giannakopoulos;E. Koutsoupias
通讯作者：
E. Koutsoupias