1st International Conference on Game Theory for Networks

Research Article

Congestion games: Equilibria, convergence and complexity

  • @INPROCEEDINGS{10.1109/GAMENETS.2009.5137458,
        author={Berthold  V\o{}cking},
        title={Congestion games: Equilibria, convergence and complexity},
        proceedings={1st International Conference on Game Theory for Networks},
        publisher={IEEE},
        proceedings_a={GAMENETS},
        year={2009},
        month={6},
        keywords={},
        doi={10.1109/GAMENETS.2009.5137458}
    }
    
  • Berthold Vöcking
    Year: 2009
    Congestion games: Equilibria, convergence and complexity
    GAMENETS
    IEEE
    DOI: 10.1109/GAMENETS.2009.5137458
Berthold Vöcking1,*
  • 1: Department of Computer Science, RWTH Aachen University, Germany.
*Contact email: voecking@cs.rwth-aachen.de

Abstract

Congestion games model the allocation of resources by selfish players. For example, players aim at allocating shortest paths in a network. The cost (delay) of a resource (edge) is assumed to be a function of the congestion, i.e., the number of players allocating the resource. We survey results about the existence and complexity of Nash equilibria in different variants of congestion games. Towards this end, we draw a connection to the complexity of local search and elaborate on the complexity class PLS (polynomial local search).