论文标题
同时竞赛，奖品共享平等分配：计算复杂性和无政府状态的价格
Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of Anarchy
论文作者
论文摘要
我们研究了同时竞赛的一般情况，该比赛是根据平等分享分配奖品的一般竞赛：每个竞赛奖励其奖项颁发给所有满足特定竞赛标准的球员的奖励，并且该奖项的价值随着获奖者的数量的增加而降低。玩家为一组活动生产产出，比赛的获胜标准是基于这些输出的。我们考虑了该模型的两种变体：（i）玩家的产出成本； （ii）玩家没有成本，但具有普遍的预算限制。我们观察到这些游戏是确切的潜在游戏，因此总是具有纯粹的纳什平衡。预算模型的无政府状态价格为$ 2 $，但对于成本模型而言可能是无限的。我们的主要结果是这些游戏的计算复杂性。我们证明，对于模型的一般版本或近似计算的最佳响应是NP-HARD。对于自然限制版本的最佳响应易于计算，我们表明找到一个纯净的nash平衡是PLS完整的，并且找到混合策略的NASH平衡是（PPAD $ \ cap $ pls） - complete。另一方面，可以在伪单项时期发现近似纯构策犬NASH平衡。这些游戏是明确的拥塞游戏的严格但自然的子类，但是它们仍然具有相同的平衡硬度结果。
We study a general scenario of simultaneous contests that allocate prizes based on equal sharing: each contest awards its prize to all players who satisfy some contest-specific criterion, and the value of this prize to a winner decreases as the number of winners increases. The players produce outputs for a set of activities, and the winning criteria of the contests are based on these outputs. We consider two variations of the model: (i) players have costs for producing outputs; (ii) players do not have costs but have generalized budget constraints. We observe that these games are exact potential games and hence always have a pure-strategy Nash equilibrium. The price of anarchy is $2$ for the budget model, but can be unbounded for the cost model. Our main results are for the computational complexity of these games. We prove that for general versions of the model exactly or approximately computing a best response is NP-hard. For natural restricted versions where best response is easy to compute, we show that finding a pure-strategy Nash equilibrium is PLS-complete, and finding a mixed-strategy Nash equilibrium is (PPAD$\cap$PLS)-complete. On the other hand, an approximate pure-strategy Nash equilibrium can be found in pseudo-polynomial time. These games are a strict but natural subclass of explicit congestion games, but they still have the same equilibrium hardness results.
