Elias Koutsoupias / Publications

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 its own assigned traffic. In a Nash equilibrium, each user selfishly routes its traffic on those links that minimize its 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 Nash equilibrium, constructing a Nash equilibrium with given support characteristics, constructing the worst Nash equilibrium (the one with maximum social cost), constructing the best Nash equilibrium (the one with 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 #P-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.

@article{FKKMS09,
  author    = {Dimitris Fotakis and
               Spyros C. Kontogiannis and
               Elias Koutsoupias and
               Marios Mavronicolas and
               Paul G. Spirakis},
  title     = {The structure and complexity of Nash equilibria for a selfish
               routing game},
  journal   = {Theor. Comput. Sci.},
  volume    = {410},
  number    = {36},
  year      = {2009},
  pages     = {3305-3326},
  ee        = {http://dx.doi.org/10.1016/j.tcs.2008.01.004},
  notes	    = {An earlier version appeared in ICALP 2002}
}

@string{ICALP02 = {Proceedings of the 29th International Colloquium on
Automata, Languages, and Programming (ICALP)}}

@InProceedings{FKKMS02,
  author =       {D. Fotakis and S. Kontogiannis and E. Koutsoupias
                  and M. Mavronicolas and P. Spirakis},
  title =        {The Structure and Complexity of Nash Equilibria
                  for a Selfish Routing Game.},
  booktitle =    ICALP02,
  year =         2002,
  address =      {Malaga, Spain},
  pages =        {123--134},
}