Home News About Us Contact Contributors Disclaimer Help FAQ

 Display Documents

ID: 202082.0, MPI für Informatik / Algorithms and Complexity Group
The Structure and Complexity of Nash Equilibria for a Selfish Routing Game
Authors:
Editors:
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2002
Title of Proceedings:Automata, Languages and Programming : 29th International Colloquium, ICALP 2002
Start Page:123
End Page:134
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Málaga, Spain
(Start) Date of Conference/Meeting
(YYYY-MM-DD):
2002-07-08
Review Status:not specified
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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,

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.
Last Change of the Resource (YYYY-MM-DD):2003-08-27
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:
Identifiers:ISBN:3-540-43864-5
LOCALID:C1256428004B93B8-E53C35265502B4D9C1256B9E004B4898-...
 The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.