hide
Free keywords:
-
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.
