Convergence to approximate Nash equilibria in congestion games

  • Steve Chien ,
  • Alistair Sinclair

Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |

Published by SIAM

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.