Worst-case Equilibria

Elias Koutsoupias, Christos H. Papadimitriou

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.
BibTeX
@inproceedings{koutsoupias1999worst,
  author = {Elias Koutsoupias and Christos H. Papadimitriou},
  title = {{Worst-case Equilibria}},
  booktitle = {STACS},
  year = {1999},
  doi = {10.1007/3-540-49116-3\_38},
}

Loading related content...

Figure