Nash Dynamics in Constant Player and Bounded Jump Congestion Games

摘要

We study the convergence time of Nash dynamics in two classes of congestion games - constant player congestion games and bounded jump congestion games. It was shown by Ackermann and Skopa-lik [2] that even 3-player congestion games are PLS-complete. We design an FPTAS for congestion games with constant number of players. In particular, for any ∈ > 0, we establish a stronger result, namely, any sequence of (1 + ∈)-greedy improvement steps converges to a (1 + ∈)-approximate equilibrium in a number of steps that is polynomial in ∈~(-1) and the size of the input. As the number of strategies of a player can be exponential in the size of the input, our FPTAS result assumes that a (1 + ∈)-greedy improvement step, if it exists, can be computed in polynomial time. This assumption holds in previously studied models of congestion games, including network congestion games [9] and restricted network congestion games [2].rnFor bounded jump games, where jumps in the delay functions of resources are bounded by β, we show that there exists a game with an exponentially long sequence of α-greedy best response steps that does not converge to an α-approximate equilibrium, for all α ≤ β~(o(n/log n)), where n is the number of players and the size of the game is O(n). So in the worst case, Nash dynamics may fail to converge in polynomial time to such an approximate equilibrium. We also prove the same result for bounded jump network congestion games. In contrast, we observe that it is easy to show that a β~(2n)-approximate equilibrium is reached in at most n best response steps.