Skip to Main content Skip to Navigation
Conference papers

Congestion games with capacitated resources

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Frédéric Davesne Connect in order to contact the contributor
Submitted on : Tuesday, March 18, 2014 - 12:28:32 PM
Last modification on : Tuesday, January 25, 2022 - 8:30:02 AM
Long-term archiving on: : Wednesday, June 18, 2014 - 10:36:32 AM


Files produced by the author(s)



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⟩



Record views


Files downloads