The structure and complexity of Nash equilibria for a selfish routing game

Abstract

In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selfish routing over a network consisting of m parallel links. We assume a collection of n users, each employing a mixed strategy, which is a probability distribution over links, to control the routing of her own traffic. In a Nash equilibrium, each user selfishly routes her traffic on those links that minimize her expected latency cost, given the network congestion caused by the other users. The social cost of a Nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, 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 pure Nash equilibrium, constructing a Nash equilibrium, constructing the pure Nash equilibria of minimum and maximum social cost, and computing the social cost of a given mixed Nash equilibrium. Our work provides a comprehensive collection of efficient algorithms, hardness 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. © 2008 Elsevier B.V. All rights reserved.