de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# 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.