Convergence speed analysis for evolutionary congestion games

It is well known that any congestion game admits a pure Nash Equilibrium. This paper investigates a particular congestion game such that strategies are exactly the facilities. We prove that for such a congestion game endowed with the nondeterministic best-reply update rule, every strategy profile can reach a Nash equilibrium after at most n iterations; and particularly when the best-reply update rule is deterministic, every strategy profile will enter a limit cycle of length ≤ 2 after at most 3p + 1 iterations, where p and n denote the number of strategies and the number of players, respectively. Besides, based on these results, for a traffic network, we consider a stochastic evolutionary congestion game, and prove that every profile will converge to a Nash equilibrium almost surely.