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 epsilon-Nash equilibrium occurs within a number of steps that is polynomial in the number of players and epsilon(-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 epsilon(i), the number of moves a player makes before equilibrium is reached depends only on his associated si, 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. (C) 2009 Elsevier Inc. All rights reserved.