Congestion Games with Capacitated Resources
Gourvès, Laurent; Monnot, Jérôme; Moretti, Stefano; Kim Thang, Nguyen (2012), Congestion Games with Capacitated Resources, in Serna, Maria, Algorithmic Game Theory 5th International Symposium, SAGT 2012, Barcelona, Spain, October 22-23, 2012. Proceedings, Springer : Berlin, p. 204-215. http://dx.doi.org/10.1007/978-3-642-33996-7_18
TypeCommunication / Conférence
External document linkhttp://hal.archives-ouvertes.fr/hal-00752265
Conference title5th International Symposium on Algorithmic Game Theory, SAGT 2012
Book titleAlgorithmic Game Theory 5th International Symposium, SAGT 2012, Barcelona, Spain, October 22-23, 2012. Proceedings
Book authorSerna, Maria
Series titleLecture Notes in Computer Science
Number of pages263
MetadataShow full item record
Abstract (EN)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.
Subjects / KeywordsPolynomial algorithms; pure Nash equilibrium; congestion games
Showing items related by title and author.
Spanjaard, Olivier; Pascual, Fanny; Thang, Nguyen Kim; Gourvès, Laurent; Escoffier, Bruno (2011) Communication / Conférence