Algorithms - ESA 2015
Algorithms - ESA 2015
复制标题
算法 - ESA 2015
DOI：
10.1007/978-3-662-48350-3_30
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Christodoulou G
中科院分区：
文献类型：
--
作者：
Christodoulou G
我们研究了三种不同环境下的混合均衡的无效率，表示为无政府状态的价格，所有支付拍卖：组合，多单位和单一项目的拍卖。首先，我们考虑项目投标组合拍卖的mall-pay拍卖并行运行，每一个好。对于分数次可加估值，我们通过证明一些表征博弈混合纳什均衡的结构性质，将上限从2 [22]加强到1.82。接下来，我们设计了一个多单位拍卖的随机分配规则的所有支付机制。我们发现，投标人与子模块化的估值，该机制承认一个独特的，75%的效率，纯纳什均衡。该机制的效率优于所有已知的无政府状态下的多单位拍卖机制的价格界限。最后，我们分析了单一项目的所有支付拍卖的动机，他们的连接到比赛，并显示紧界的社会福利，收入和最高出价的无政府状态的价格。
We study the inefficiency of mixed equilibria, expressed as the price of anarchy, of all-pay auctions in three different environments: combinatorial, multi-unit and single-item auctions. First, we consider item-bidding combinatorial auctions wheremall-pay auctions run in parallel, one for each good. For fractionally subadditive valuations, we strengthen the upper bound from 2 [22] to 1.82 by proving some structural properties that characterize the mixed Nash equilibria of the game. Next, we design an all-pay mechanism with a randomized allocation rule for the multi-unit auction. We show that, for bidders with submodular valuations, the mechanism admits a unique, 75% efficient, pure Nash equilibrium. The efficiency of this mechanism outperforms all the known bounds on the price of anarchy of mechanisms used for multi-unit auctions. Finally, we analyze single-item all-pay auctions motivated by their connection to contests and show tight bounds on the price of anarchy of social welfare, revenue and maximum bid.