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

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