Congestion games with capacitated resources - Université d'Évry Access content directly
Conference Papers Year : 2012

Congestion games with capacitated resources


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.
Fichier principal
Vignette du fichier
Sagt_congcap.pdf (173.39 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-00752265 , version 1 (18-03-2014)



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⟩
136 View
182 Download



Gmail Facebook Twitter LinkedIn More