MPI-INF D1 Publications: Proceedings Article: The Structure and Complexity of Nash Equilibria for a Selfish Routing Game

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

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

Action:

Options:

Goto entry point

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
Attachment(s):	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:


(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

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

Attachment Section

Attachment Section

View attachments here:

icalp02.ps

icalp02.ps