Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:

http://sirius.lcc.uma.es/ICALP2002/

URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 03:42:17 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
icalp02.ps