MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Fotakis, Dimitris
Kontogiannis, Spyros
Koutsoupias, Elias
Mavronicolas, Marios
Spirakis, Paul G.		dblp
dblp
dblp
dblp
dblp
Not MPG Author(s):
Koutsoupias, Elias
Mavronicolas, Marios
Spirakis, Paul G.
Editor(s):
Widmayer, Peter
Triguero, Francisco
Morales, Rafael
Hennessy, Matthew
Eidenbenz, Stephan
Conejo, Ricardo		dblp
dblp
dblp
dblp
dblp
dblp
Not MPII Editor(s):
Widmayer, Peter
Triguero, Francisco
Morales, Rafael
Hennessy, Matthew
Eidenbenz, Stephan
Conejo, Ricardo
BibTeX cite key*:
FKKMS02
Title, Booktitle
Title*:
The Structure and Complexity of Nash Equilibria for a Selfish Routing Game
icalp02.ps (204.07 KB)
Booktitle*:
Automata, Languages and Programming : 29th International Colloquium, ICALP 2002
Event, URLs
Conference URL::
http://sirius.lcc.uma.es/ICALP2002/
Downloading URL:
Event Address*:
Málaga, Spain
Language:
English
Event Date*
(no longer used):
-- July, 8-13
Organization:
Event Start Date:
8 July 2002
Event End Date:
13 July 2002
Publisher
Name*:
Springer
URL:
http://www.springer.de/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2380
Number:
Month:
July
Pages:
123-134
Year*:
2002
VG Wort Pages:
ISBN/ISSN:
3-540-43864-5
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
URL for the Abstract:
http://www.mpi-sb.mpg.de/~spyros/papers/icalp02-abs.htm
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{FKKMS02,
AUTHOR = {Fotakis, Dimitris and Kontogiannis, Spyros and Koutsoupias, Elias and Mavronicolas, Marios and Spirakis, Paul G.},
 EDITOR = {Widmayer, Peter and Triguero, Francisco and Morales, Rafael and Hennessy, Matthew and Eidenbenz, Stephan and Conejo, Ricardo},
 TITLE = {The Structure and Complexity of Nash Equilibria for a Selfish Routing Game},
 BOOKTITLE = {Automata, Languages and Programming : 29th International Colloquium, ICALP 2002},
 PUBLISHER = {Springer},
 YEAR = {2002},
 VOLUME = {2380},
 PAGES = {123--134},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Málaga, Spain},
 MONTH = {July},
 ISBN = {3-540-43864-5},
}

Entry last modified by Christine Kiesel, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Spyros Kontogiannis		Created
04/17/2002 15:42:17
Revisions
10.
9.
8.
7.
6.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
27.08.2003 14:50:32
26.08.2003 15:57:25
26.08.2003 15:05:30
26.08.2003 13:46:21
20.06.2003 15:54:14

File Attachment Icon
icalp02.ps