Name
Abstract | ||
|---|---|---|
We study the ability of decentralized, local dynamics in non-cooperative games to rapidly reach an approximate Nash equilibrium. For symmetric congestion games in which the edge delays satisfy a "bounded jump" condition, we show that convergence to an "-Nash equilibrium occurs within a number of steps that is polynomial in the number of players and " 1. This appears to be the first such result for a class of games that includes examples for which finding an exact Nash equilibrium is PLS-complete, and in which shortest paths to an exact equilibrium are exponentially long. We show moreover that rapid convergence holds even under only the apparently minimal assumption that no player is excluded from moving for arbitrarily many steps. We also prove that, in a generalized setting where players have different "tolerances" "i that specify their thresholds in the approximate Nash equilibrium, the number of moves made by a player before equilibrium is reached depends only on his associated "i, and not on those of the other players. Finally, we show that polynomial time convergence still holds even when a bounded number of edges are allowed to have arbitrary delay functions. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/1283383.1283402 | Games and Economic Behavior |
Keywords | Field | DocType |
non cooperative game,nash equilibria,satisfiability,cost function,best response dynamics,polynomial time,nash equilibrium | Correlated equilibrium,Discrete mathematics,Combinatorics,Epsilon-equilibrium,Best response,Equilibrium selection,Symmetric equilibrium,Nash equilibrium,Proper equilibrium,Mathematics,Trembling hand perfect equilibrium | Journal |
Volume | Issue | ISSN |
71 | 2 | Games and Economic Behavior |
ISBN | Citations | PageRank |
978-0-89871-624-5 | 99 | 4.11 |
References | Authors | |
23 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Steve Chien | 1 | 323 | 19.12 |
| Alistair Sinclair | 2 | 1506 | 308.40 |