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