Name
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s00224-014-9541-0 | Theory of Computing Systems |
Keywords | Field | DocType |
Congestion games,Pure nash equilibrium,Potential function,Algorithms | Coordination game,Congestion game,Mathematical economics,Epsilon-equilibrium,Best response,Equilibrium selection,Repeated game,Game theory,Nash equilibrium,Mathematics | Conference |
Volume | Issue | ISSN |
57 | 3 | 1432-4350 |
Citations | PageRank | References |
2 | 0.42 | 17 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laurent Gourvès | 1 | 241 | 30.97 |
| Jérôme Monnot | 2 | 512 | 55.74 |
| Stefano Moretti | 3 | 2 | 0.76 |
| Nguyen Kim Thang | 4 | 6 | 1.17 |