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

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

George Christodoulou, Elias Koutsoupias, Akash Nanavati: Coordination mechanisms. Theor. Comput. Sci. 410(36): 3327-3336, 2009.
Download: pdf ps

Abstract

We introduce the notion of coordination mechanisms to improve the performance in systems with independent selfish and non-colluding agents. The quality of a coordination mechanism is measured by its price of anarchy---the worst-case performance of a Nash equilibrium over the (centrally controlled) social optimum. We give upper and lower bounds for the price of anarchy for selfish task allocation and congestion games.

Bib

@article{CKN09,
  author    = {George Christodoulou and
               Elias Koutsoupias and
               Akash Nanavati},
  title     = {Coordination mechanisms},
  journal   = {Theor. Comput. Sci.},
  volume    = {410},
  number    = {36},
  year      = {2009},
  pages     = {3327-3336},
  ee        = {http://dx.doi.org/10.1016/j.tcs.2009.01.005},
  notes	    = {An earlier version appeared in ICALP 2004}
}

@string{ICALP04 = {Automata, Languages and Programming: 31st
International Colloquium}}

@InProceedings{CKN04,
  author =       {G. Christodoulou and E. Koutsoupias and A. Nanavati.
},
  title =        {Coordination Mechanisms},
  booktitle =    ICALP04,
  year =         2004,
  month =        {12--16 } # jul,
  pages =        {345--357},
  address =      {Turku, Finland},
}