de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

The Structure and Complexity of Nash Equilibria for a Selfish Routing Game

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44436

Fotakis,  Dimitris
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44823

Kontogiannis,  Spyros
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45532

Spirakis,  Paul G.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., & Spirakis, P. G. (2002). The Structure and Complexity of Nash Equilibria for a Selfish Routing Game. In Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 (pp. 123-134). Berlin, Germany: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-30A2-8
Zusammenfassung
In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models {\em selfish routing} over a network consisting of $m$ parallel {\em links}. We assume a collection of {\em $n$ users,} each employing a {\em mixed strategy,} which is a probability distribution over links, to control the routing of its own assigned {\em traffic}. In a {\em Nash equilibrium,} each user selfishly routes its traffic on those links that minimize its {\em expected latency cost,} given the network congestion caused by the other users. The {\em social cost} of a Nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, {\em latency} through a link. We embark on a systematic study of several algorithmic problems related to the computation of Nash equilibria for the selfish routing game we consider. In a nutshell, these problems relate to deciding the existence of a Nash equilibrium, constructing a Nash equilibrium with given support characteristics, constructing the {\em worst} Nash equilibrium (the one with {\em maximum} social cost), constructing the {\em best} Nash equilibrium (the one with {\em minimum} social cost), or computing the social cost of a (given) Nash equilibrium. Our work provides a comprehensive collection of efficient algorithms, hardness results (both as $\NP$-hardness and $\#\Pc$-completeness results), and structural results for these algorithmic problems. Our results span and contrast a wide range of assumptions on the syntax of the Nash equilibria and on the parameters of the system.