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.
Abstract
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.Bib
@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},
}