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
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).
Copyright © 2009–2024 IEEE
