The Effect of Collusion in Congestion Games Extended Abstract
The Effect of Collusion in Congestion Games Extended Abstract
复制标题
拥塞博弈中共谋的影响扩展摘要
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
T. Wexler
中科院分区：
文献类型：
--
作者：
A. Hayrapetyan;É. Tardos;T. Wexler
在本文中，我们开始研究共谋如何改变竞争对策中获得的解的质量。混乱的代价旨在通过比较纳什均衡与集中设计的最优解的质量来衡量缺乏协调的成本。这一概念假设参与者不仅自我行动，而且独立行动。我们提出了一个框架，建模组串通的球员，在一个联盟的成员合作，以selshly最大限度地提高他们的集体福利。显然，这种联盟可以改善参与者的社会福利，但也可能损害联盟之外的人的福利。人们可能希望联盟参与者的改善超过对其他人的负面影响。这意味着加强合作只会提高稳定成果的整体解决质量。然而，协调的增加实际上会导致总社会福利的显著下降。有鉴于此，我们提出了价格的共谋作为衡量可能的负面影响的共谋，指定的因素，解决方案的质量可以恶化的联盟的存在。我们给出的例子表明，合谋的价格可以任意高，即使在凸博弈。我们的主要研究结果表明，在负载平衡博弈的背景下，合谋的价格取决于市场力量的差距在游戏中的participants。我们发现，在一些对称的非原子游戏（所有用户都可以使用相同的策略集）增加合作总是提高解决方案的质量，并在离散的类似游戏，共谋的价格是由两个有界的。
In this paper we initiate the study of how collusion alters the qual- ity of solutions obtained in competitive games. The price of anar- chy aims to measure the cost of the lack of coordination by com- paring the quality of a Nash equilibrium to that of a centrally de- signed optimal solution. This notion assumes that players act not only selshly , but also independently. We propose a framework for modeling groups of colluding players, in which members of a coalition cooperate so as to selshly maximize their collective welfare. Clearly, such coalitions can improve the social welfare of the participants, but they can also harm the welfare of those out- side the coalition. One might hope that the improvement for the coalition participants outweighs the negative effects on the others. This would imply that increased cooperation can only improved the overall solution quality of stable outcomes. However, increases in coordination can actually lead to signicant decreases in total so- cial welfare. In light of this, we propose the price of collusion as a measure of the possible negative effect of collusion, specifying the factor by which solution quality can deteriorate in the presence of coalitions. We give examples to show that the price of collusion can be arbitrarily high even in convex games. Our main results show that in the context of load-balancing games, the price of collusion depends upon the disparity in market power among the game partic- ipants. We show that in some symmetric nonatomic games (where all users have access to the same set of strategies) increased co- operation always improves the solution quality, and in the discrete analogs of such games, the price of collusion is bounded by two.