Elias Koutsoupias
Professor of Computer Science
University of Athens
Panepistimiopolis, Ilissia
Athens 15784
Greece

phone: +30 210 7275122
fax: +30 210 7275114

G. Christodoulou, E. Koutsoupias, and P. Spirakis. On the performance of approximate equilibria in congestion games. In Algorithmica 61(1): 116-140, 2011

### Abstract

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 $\epsilon$. We give almost tight upper and lower bounds for both the price of anarchy and the price of stability for atomic and non-atomic congestion games. Our results not only encompass and generalize the existing results of exact equilibria to $\epsilon$-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.

### Bib

@article{CKS11,
author    = {George Christodoulou and
Elias Koutsoupias and
Paul G. Spirakis},
title     = {On the Performance of Approximate Equilibria in Congestion
Games},
journal   = {Algorithmica},
volume    = {61},
number    = {1},
year      = {2011},
pages     = {116-140},
ee        = {http://dx.doi.org/10.1007/s00453-010-9449-2},
}

@string{ESA09 = {European Symposium, Copenhagen}}

@inproceedings{CKS09,
author    = {G. Christodoulou and
E. Koutsoupias and
P. Spirakis},
title     = {On the Performance of Approximate Equilibria in Congestion
Games},
booktitle = ESA09,
year      = {2009},
month	    = {7-9} # sep,