On the Complexity of Computing an Equilibrium in Combinatorial Auctions
On the Complexity of Computing an Equilibrium in Combinatorial Auctions
复制标题
关于组合拍卖中计算均衡的复杂性
DOI：
10.1137/1.9781611973730.9
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Robert D. Kleinberg
中科院分区：
文献类型：
--
作者：
Shahar Dobzinski;Hu Fu;Robert D. Kleinberg
我们研究组合拍卖，每个项目分别出售，但同时通过第二价格拍卖。我们问是否有可能有效地计算在这个游戏中的纯纳什均衡与社会福利接近最优的。我们表明，当投标人的估值是次模块化的，在许多有趣的设置（例如，投标人数量恒定，预算附加投标人）计算具有良好福利的均衡基本上与计算完全忽略激励问题的具有良好福利的分配一样容易。另一方面，对于次可加估值，我们证明了计算均衡需要指数通信。最后，对于XOS（a.k.a.分数次加性）估值，我们表明，如果存在一个有效的算法，找到一个均衡，它必须使用的技术是非常不同的，从目前已知的。
We study combinatorial auctions where each item is sold separately but simultaneously via a second price auction. We ask whether it is possible to efficiently compute in this game a pure Nash equilibrium with social welfare close to the optimal one. We show that when the valuations of the bidders are submodular, in many interesting settings (e.g., constant number of bidders, budget additive bidders) computing an equilibrium with good welfare is essentially as easy as computing, completely ignoring incentives issues, an allocation with good welfare. On the other hand, for subadditive valuations, we show that computing an equilibrium requires exponential communication. Finally, for XOS (a.k.a. fractionally subadditive) valuations, we show that if there exists an efficient algorithm that finds an equilibrium, it must use techniques that are very different from the ones currently known.