Thumbnail

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

View/Open
Type
Communication / Conférence
External document link
http://hal.archives-ouvertes.fr/hal-00752265
Date
2012
Conference title
5th International Symposium on Algorithmic Game Theory, SAGT 2012
Conference date
2012-10
Conference city
Barcelone
Conference country
Espagne
Book title
Algorithmic Game Theory 5th International Symposium, SAGT 2012, Barcelona, Spain, October 22-23, 2012. Proceedings
Book author
Serna, Maria
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
7615
Published in
Berlin
ISBN
978-3-642-33995-0
Number of pages
263
Pages
204-215
Publication identifier
Metadata
Show full item record
Author(s)
Gourvès, Laurent
Monnot, Jérôme cc
Moretti, Stefano cc
Kim Thang, Nguyen
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 / Keywords
Polynomial algorithms; pure Nash equilibrium; congestion games