论文标题
与两名玩家的加权拥塞游戏无政府状态的确切价格
Exact Price of Anarchy for Weighted Congestion Games with Two Players
论文作者
论文摘要
本文为各种具有两个玩家和仿射成本功能的加权拥堵游戏的最差平衡提供了完整的分析。结果是无政府状态界限的确切价格，这在两个玩家的权重中是参数，并确切地确定了游戏的原语如何进入平衡质量。有趣的是，当玩家的重量仅略有不同时，就会达到一些最差的案例。我们的发现还表明，顺序游戏在所有情况下都提高了无政府状态的价格，但是，这种效果随着玩家的重量的差异而消失。从方法上讲，我们基于计算最坏情况实例的紧凑型线性编程公式，通过基于二重性的证明机制获得无政府状态界限的精确价格。该机制产生了基于偶性的最佳证书，最终可以将其转变为纯粹的代数证明。
This paper gives a complete analysis of worst-case equilibria for various versions of weighted congestion games with two players and affine cost functions. The results are exact price of anarchy bounds which are parametric in the weights of the two players, and establish exactly how the primitives of the game enter into the quality of equilibria. Interestingly, some of the worst-cases are attained when the players' weights only differ slightly. Our findings also show that sequential play improves the price of anarchy in all cases, however, this effect vanishes with an increasing difference in the players' weights. Methodologically, we obtain exact price of anarchy bounds by a duality based proof mechanism, based on a compact linear programming formulation that computes worst-case instances. This mechanism yields duality-based optimality certificates which can eventually be turned into purely algebraic proofs.
