G. Christodoulou and E. Koutsoupias.
The price of anarchy of finite congestion games.
STOC, pages 67--73, Baltimore, MD,USA, 22--24 May, 2005.
Abstract
We consider the price of anarchy of pure Nash equilibria in congestion games with linear latency functions. For asymmetric games, the price of anarchy of maximum social cost is \Theta(\sqrt{N}), where N is the number of players. For all other cases of symmetric or asymmetric games and for both maximum and average social cost, the price of anarchy is 5/2. We extend the results to latency functions that are polynomials of bounded degree. We also extend some of the results to mixed Nash equilibria.Bib
@string{STOC05 = {37th ACM Symposium on Theory of Computing}}
@InProceedings{CK05,
author = {G. Christodoulou and E. Koutsoupias},
title = {The price of anarchy of finite congestion games},
booktitle = STOC05,
pages = {67--73},
year = 2005,
month = {22--24 } #may,
address = {Baltimore, MD, USA},
}