# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### The Structure and Complexity of Nash Equilibria for a Selfish Routing Game

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-30A2-8

##### 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.