Congestion games with capacitated resources - Archive ouverte HAL Access content directly
Conference Papers Year : 2012

Congestion games with capacitated resources

(1) , (1) , (1) , (2)
1
2

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.
Fichier principal
Vignette du fichier
Sagt_congcap.pdf (173.39 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00752265 , version 1 (18-03-2014)

Identifiers

Cite

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⟩
124 View
171 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More