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

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

G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games. STOC, pages 67--73, Baltimore, MD,USA, 22--24 May, 2005.
Download: pdf ps


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.


@string{STOC05 = {37th ACM Symposium on Theory of Computing}}

  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},