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 k rounds, defined as the highest possible ratio among the total latency cost and the minimum possible cost, is close to optimum and asymptotically matches the lower bound that we determine as a refinement of the one by [Christodoulou et al. 06]. As a consequence, we prove that order of loglogn 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 the number n of players. We then provide a new lower bound for load balancing games, that is congestion games in which every strategy consists of a single resource, thus showing that a number of rounds proportional to loglogn 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.