Congestion games with capacitated resources

Laurent Gourvès (1) , Jérôme Monnot (1) , Stefano Moretti (1) , Kim Thang Nguyen (2)

1 LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision
2 IBISC - Informatique, Biologie Intégrative et Systèmes Complexes

We extend congestion games to the setting where every resource is endowed with a capacity which possibly limits its number of users. From the negative side, we show that a pure Nash equilibrium is not guaranteed to exist in any case and we prove that deciding whether a game possesses a pure Nash equilibrium is NP-complete. Our positive results state that congestion games with capacities are potential games in the well studied singleton case. Polynomial algorithms that compute these equilibria are also provided.

Keywords: Congestion Games; NP Complete; Polynomial algorithm; Potential games; Pure Nash equilibrium

Domains: Computer Science [cs]; Operations Research [cs.RO]

Laurent Gourvès, Jérôme Monnot, Stefano Moretti, Kim Thang Nguyen. Congestion games with capacitated resources. 5th International Symposium on Algorithmic Game Theory (SAGT 2012), Oct 2012, Barcelona, Spain. pp.204-215, ⟨10.1007/978-3-642-33996-7_18⟩. ⟨hal-00752265⟩