2008 · 133 citations · 20 references
Social SciencesMathematicsDecision TheoryDynamical SystemsGame TheoryAlgorithmic Game TheoryApproximation AlgorithmsDynamic GamesNash EquilibriumNoncooperative Game TheoryPotential GamesApproximate Nash EquilibriumApproximation Algorithms For EquilibriaComputational Game TheoryConvergenceConvergence TimeLiveness PropertiesSymmetric GamesWeighted Potential Games
We study the speed of convergence of decentralized dynamics to approximately optimal solutions in potential games. We consider α-Nash dynamics in which a player makes a move if the improvement in his payoff is more than an α factor of his own payoff. Despite the known polynomial convergence of α-Nash dynamics to approximate Nash equilibria in symmetric congestion games [7], it has been shown that the convergence time to approximate Nash equilibria in asymmetric congestion games is exponential [25]. In contrast to this negative result, and as the main result of this paper, we show that for asymmetric congestion games with linear and polynomial delay functions, the convergence time of α-Nash dynamics to an approximate optimal solution is polynomial in the number of players, with approximation ratio that is arbitrarily close to the price of anarchy of the game. In particular, we show this polynomial convergence under the minimal liveness assumption that each player gets at least one chance to move in every T steps. We also prove that the same polynomial convergence result does not hold for (exact) best-response dynamics, showing the α-Nash dynamics is required. We extend these results for congestion games to other potential games including weighted congestion games with linear delay functions, cut games (also called party affiliation games) and market sharing games.
20
Tim Roughgarden, Éva Tardos · Journal of the ACM · 2002 · 1.6K citations
Algorithms, games, and the internet
Christos H. Papadimitriou · 2001 · 1.1K citations
The complexity of pure Nash equilibria
Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar · 2004 · 662 citations