de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

• Please note that a newer version of this item is in progress.
The Structure and Complexity of Nash Equilibria for a Selfish Routing Game

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.

Item is

### Basic

show hide
Bookmark this item:
Genre: Conference Paper

show Files

show

### Creators

show
hide
Creators:
Fotakis, Dimitris1, Author
Kontogiannis, Spyros1, Author
Koutsoupias, Elias, Author
Mavronicolas, Marios, Author
Spirakis, Paul G.1, Author
Widmayer, Peter, Editor
Triguero, Francisco, Editor
Morales, Rafael, Editor
Hennessy, Matthew, Editor
Eidenbenz, Stephan, Editor
Conejo, Ricardo, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, escidoc:24019

### Content

show
hide
Free keywords: -
Abstract: 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.

### Details

show
hide
Language(s): eng - English
Dates: 2003-08-272002
Pages: -
Publishing info: -
Rev. Method: -
Identifiers: eDoc: 202082
Other: Local-ID: C1256428004B93B8-E53C35265502B4D9C1256B9E004B4898-FKKMS02
Degree: -

### Event

show
hide
Title: Untitled Event
Place of Event: Málaga, Spain
Start-/End Date: 2002-07-08 -

show

### Source 1

show
hide
Title: Automata, Languages and Programming : 29th International Colloquium, ICALP 2002
Source Genre: Proceedings
Creator(s):
-
Affiliations:
-
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 123 - 134 Identifier: ISBN: 3-540-43864-5

### Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
Creator(s):
-
Affiliations:
-
Publ. Info: -
Pages: - Volume / Issue: 2380 Sequence Number: - Start / End Page: - Identifier: -