On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games
On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games
复制标题
DOI：
10.1007/11561071_8
复制
发表时间：
2005-10
期刊：
影响因子：
--
通讯作者：
G. Christodoulou;E. Koutsoupias
中科院分区：
文献类型：
--
作者：
G. Christodoulou;E. Koutsoupias
我们考虑的价格稳定的纳什均衡和相关的线性拥塞游戏。稳定的代价是无政府状态的乐观代价，即最佳纳什均衡或相关均衡的成本与社会最优的成本之比。我们表明，对于社会成本的总和，这对应于玩家的平均成本，每个线性拥塞游戏的纳什和相关价格的稳定性最多为1.6。我们也给出了一个几乎匹配的下界。我们还考虑了相关均衡的无政府状态的代价。我们扩展现有的结果纳什均衡相关的均衡，并表明，为社会成本的总和，无政府状态的价格正好是2.5，相同的纯和混合纳什和相关的均衡。同样的界限也适用于对称博弈。我们还将纳什均衡的结果扩展到加权拥塞博弈的相关均衡，并证明了当社会成本为总延迟时，无政府状态的代价为。
We consider the price of stability for Nash and correlated equilibria of linear congestion games. The price of stability is the optimistic price of anarchy, the ratio of the cost of the best Nash or correlated equilibrium over the social optimum. We show that for the sum social cost, which corresponds to the average cost of the players, every linear congestion game has Nash and correlated price of stability at most 1.6. We also give an almost matching lower bound of.We also consider the price of anarchy of correlated equilibria. We extend existing results about Nash equilibria to correlated equilibria and show that for the sum social cost, the price of anarchy is exactly 2.5, the same for pure and mixed Nash and for correlated equilibria. The same bound holds for symmetric games as well. We also extend the results about Nash equilibria to correlated equilibria for weighted congestion games and we show that when the social cost is the total latency, the price of anarchy is.