On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games

George Christodoulou, Elias Koutsoupias

Abstract

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 \(1+\sqrt{3}/3=1.577\).
BibTeX
@inproceedings{christodoulou2005price,
  author = {George Christodoulou and Elias Koutsoupias},
  title = {{On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games}},
  booktitle = {ESA},
  year = {2005},
  doi = {10.1007/11561071\_8},
}

Loading related content...

Figure