The speed of Convergence in Congestion Games under Best Response Dynamics

We investigate the speed of convergence of congestion games with linear latency functions under best response dynamics. Namely; we estimate the social performance achieved after a limited number of rounds; during each of which every player performs one best response move. In particular, we show that the price of anarchy achieved after rounds; defined as the highest possible ratio among the total latency cost; that is the sum of all players latencies; and the minimum possible cost; is O((2k-1)root n), where n is the number of players. for constant values of such a bound asymptotically matches the Omega((2k-1)root n/k) lower bound that we determine as a refinement of the one in [7]. As a consequence; we prove that order of log log n, rounds are not only necessary; but also sufficient to achieve a. constant price of anarchy; i.e. comparable to the one at Nash equilibrium. This result is particularly relevant; as reaching an equilibrium may require a number of rounds exponential in n. We then provide a new lower bound of Omega((2k-1)root n) for load balancing games, that is congestion games in which every strategy consists of a. single resource, thus shoving that a number of rounds proportional to log log n is necessary and sufficient also under such a restriction.

Our results thus solve the important left open question of the polynomial speed of convergence of linear congestion games to constant factor solutions.