Name
Abstract | ||
|---|---|---|
We investigate from the computational viewpoint multi-player games that are guaranteed to have pure Nash equilibria. We focus on congestion games, and show that a pure Nash equilibrium can be computed in polynomial time in the symmetric network case, while the problem is PLS-complete in general. We discuss implications to non-atomic congestion games, and we explore the scope of the potential function method for proving existence of pure Nash equilibria. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1145/1007352.1007445 | STOC |
Keywords | Field | DocType |
pure nash equilibrium,congestion game,symmetric network case,potential function method,computational viewpoint multi-player game,polynomial time,nash equilibrium,complexity,nash equilibria,local search,games | Correlated equilibrium,Coordination game,Mathematical optimization,Mathematical economics,Risk dominance,Epsilon-equilibrium,Computer science,Best response,Nash equilibrium,Folk theorem,Trembling hand perfect equilibrium | Conference |
ISBN | Citations | PageRank |
1-58113-852-0 | 305 | 16.11 |
References | Authors | |
16 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alex Fabrikant | 1 | 847 | 55.60 |
| Christos H. Papadimitriou | 2 | 16671 | 3192.54 |
| Kunal Talwar | 3 | 4423 | 259.79 |