Fast convergence of selfish rerouting

We consider n anonymous selfish users that route their communication through m parallel links. The users are allowed to reroute, concurrently, from overloaded links to underloaded links. The different rerouting decisions are concurrent, randomized and independent. The rerouting process terminates when the system reaches a Nash equilibrium, in which no user can improve its state. We study the convergence rate of several migration policies. The first is a very natural policy, which balances the expected load on the links, for the case that all users are identical and apply it, we show that the rerouting terminates in expected O(log log n+ logm) stages. Later, we consider the Nash rerouting policies class, in which every rerouting stage is a Nash equilibrium and the users are greedy with respect to the next load they observe. We show a similar termination bounds for this class. We study the structural properties of the Nash rerouting policies, and derive both existence result and an efficient algorithm for the case that the number of links is small. We also show that if the users have different weights then there exists a set of weights such that every Nash rerouting terminates in Ω( n) stages with high probability. 1