 |
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.
Cited literature [19 references]
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 : Friday, November 20, 2020 - 7:00:07 PM
Long-term archiving on: : Wednesday, June 18, 2014 - 10:36:32 AM
Contributor : Frédéric Davesne <>
Submitted on : Tuesday, March 18, 2014 - 12:28:32 PM
Last modification on : Friday, November 20, 2020 - 7:00:07 PM
Long-term archiving on: : Wednesday, June 18, 2014 - 10:36:32 AM
File
Sagt_congcap.pdf
Files produced by the author(s)
