Simultaneous bayesian auctions and computational complexity
Simultaneous bayesian auctions and computational complexity
复制标题
同时贝叶斯拍卖和计算复杂性
DOI：
10.1145/2600057.2602877
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
C. Papadimitriou
中科院分区：
文献类型：
--
作者：
Yang Cai;C. Papadimitriou
最近研究了单个物品同时拍卖的贝叶斯均衡[Christodoulou et al. 2008; Bhawalkar and Roughgarden 2011; Hassidim et al. 2011; Feldman et al. 2013]，作为不完全信息组合拍卖中众所周知的复杂性问题的替代方案，并且已经显示了一些关于其性能的强有力的积极结果。我们指出了这种方法的一些非常严重的复杂性障碍：计算这样的拍卖中的贝叶斯均衡对于PP -一个介于多项式层次和PSPACE之间的复杂性类-是困难的，甚至对于一些小的近似比，找到这样的均衡的近似值也像NP一样困难（加法或乘法）;因此，假设这种均衡将达到理性的代理人是很有问题的。事实上，即使是识别贝叶斯纳什均衡也是困难的。此外，即使投标人的估值是相当良性的，这些结果仍然成立：在我们的构造中，只有一个投标人的估值是单位需求或单调子模，而所有其他的都是可加的。我们还探讨了贝叶斯同步拍卖博弈的无遗憾动态无政府状态的有利价格的可能性，并确定复杂性障碍。
Bayesian equilibria of simultaneous auctions for individual items have been explored recently [Christodoulou et al. 2008; Bhawalkar and Roughgarden 2011; Hassidim et al. 2011; Feldman et al. 2013] as an alternative to the well-known complexity issues plaguing combinatorial auctions with incomplete information, and some strong positive results have been shown about their performance. We point out some very serious complexity obstacles to this approach: Computing a Bayesian equilibrium in such auctions is hard for PP --- a complexity class between the polynomial hierarchy and PSPACE --- and even finding an approximate such equilibrium is as hard as NP, for some small approximation ratio (additive or multiplicative); therefore, the assumption that such equilibria will be arrived at by rational agents is quite problematic. In fact, even recognizing a Bayesian Nash equilibrium is intractable. Furthermore, these results hold even if bidder valuations are quite benign: Only one bidder valuation in our construction is unit demand or monotone submodular, while all others are additive. We also explore the possibility of favorable price of anarchy results for no-regret dynamics of the Bayesian simultaneous auctions game, and identify complexity obstacles there as well.