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

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

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


In a system in which noncooperative agents share a common resource, we propose 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 in which several agents share a very simple network leads to some interesting mathematics, results, and open problems.


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

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