research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleOn the Performance of Approximate Equilibria in Congestion Games
Bibtex cite IDRACTI-RU1-2009-108
Booktitle 17th Annual European Symposium Algorithms
Year published 2009
Location Denmark
Note to appear
Keywords Price of anarchy Price of stability Congestion games Algorithmic Game Theory Approximate equilibria Selfish routing
We study the performance of approximate Nash equilibria for congestion games with polynomial latency functions. We consider how much the price of anarchy worsens and how much the price of stability improves as a function of the approximation factor . We give tight bounds for the price of anarchy of atomic and non-atomic congestion games and for the price of stability of non-atomic congestion games. For the price of stability of atomic congestion games we give non-tight bounds for linear latencies. Our results not only encompass and generalize the existing results of exact equilibria to -Nash equilibria, but they also provide a unified approach which reveals the common threads of the atomic and non-atomic price of anarchy results. By expanding the spectrum, we also cast the existing results in a new light.
Christodoulou, George
Koutsoupias, Elias
Spirakis, Paul
fulltext1.pdf (main file)
Publication ID793