Convergence to approximate Nash equilibria in congestion games

We study the ability of decentralized, local dynamics in non-cooperative games to rapidly reach an approximate (pure) Nash equilibrium. Our main result states that for symmetric congestion games in which the cost function associated with each resource satisfies a “bounded jump” condition, convergence to an ε-Nash equilibrium occurs within a number of steps that is polynomial in the number of players and ε−1. We show moreover that this result holds under a variety of conventions governing the move orders among the players, including the minimal liveness assumption that no player is indefinitely blocked from moving. We also prove that in the generalized setting where players have different “tolerances” εi, the number of moves a player makes before equilibrium is reached depends only on his associated εi, and not on those of other players. Finally, we show that polynomial time convergence holds even when a constant number of resources have arbitrary cost functions.