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 metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00752265
Contributor : Frédéric Davesne <>
Submitted on : Tuesday, March 18, 2014 - 12:28:32 PM
Last modification on : Wednesday, September 23, 2020 - 4:28:59 AM
Long-term archiving on: : Wednesday, June 18, 2014 - 10:36:32 AM

File

Sagt_congcap.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

322

Files downloads

365