Thumbnail

Congestion Games with Capacitated Resources

Gourvès, Laurent; Monnot, Jérôme; Moretti, Stefano; Kim Thang, Nguyen (2012), Congestion Games with Capacitated Resources, dans 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

Voir/Ouvrir
Type
Communication / Conférence
Lien vers un document non conservé dans cette base
http://hal.archives-ouvertes.fr/hal-00752265
Date
2012
Titre du colloque
5th International Symposium on Algorithmic Game Theory, SAGT 2012
Date du colloque
2012-10
Ville du colloque
Barcelone
Pays du colloque
Espagne
Titre de l'ouvrage
Algorithmic Game Theory 5th International Symposium, SAGT 2012, Barcelona, Spain, October 22-23, 2012. Proceedings
Auteurs de l’ouvrage
Serna, Maria
Éditeur
Springer
Titre de la collection
Lecture Notes in Computer Science
Numéro dans la collection
7615
Ville d’édition
Berlin
Isbn
978-3-642-33995-0
Nombre de pages
263
Pages
204-215
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
Gourvès, Laurent
Monnot, Jérôme cc
Moretti, Stefano cc
Kim Thang, Nguyen
Résumé (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.
Mots-clés
Polynomial algorithms; pure Nash equilibrium; congestion games