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

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

Elias Koutsoupias, Christos H. Papadimitriou: Worst-case equilibria. Computer Science Review 3(2): 65-69, 2009.

E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In 16th Annual Symposium on Theoretical Aspects of Computer Science, pages 404--413, Trier, Germany, 4--6 March 1999.


Download: pdf ps

Abstract

In a system where noncooperative agents share a common resource, we propose the price of anarchy, which is the ratio between the worst possible Nash equilibrium and the social optimum, as a measure of the effectiveness of the system. Deriving upper and lower bounds for this ratio in a model where several agents share a very simple network leads to some interesting mathematics, results, and open problems.

Bib

@article{DBLP:journals/csr/KoutsoupiasP09,
  author    = {Elias Koutsoupias and
               Christos H. Papadimitriou},
  title     = {Worst-case equilibria},
  journal   = {Computer Science Review},
  volume    = {3},
  number    = {2},
  year      = {2009},
  pages     = {65-69},
  ee        = {http://dx.doi.org/10.1016/j.cosrev.2009.04.003},
  notes	    = {An earlier version appeared in STACS 1999}
}

@string{STACS99 = {16th Annual Symposium on Theoretical Aspects of
Computer Science}}

@InProceedings{KP99,
  author =       {E. Koutsoupias and C. Papadimitriou},
  title =        {Worst-case equilibria},
  booktitle =    STACS99,
  year =         1999,
  month =        {4--6 } # mar,
  pages =        {404--413},
  address =      {Trier, Germany},
}