Upper bounds for the convergence rate of a randomized local search in a load-balancing game with variable-capacity resources

This paper studies the upper bounds of the number of steps required to reach a pure Nash equilibrium in a load balancing game where resources have arbitrary capacities. It has been known that a series of "self-improving" moves will lead to a Nash equilibrium. We consider a simple generic method for local optimization called Randomized Local Search that can make self improving moves. Another motivation for consider Randomized Local Search is it can be realized by a simple distributed network of users. We present two upper bounds that are polynomial in term of the number of players, the number of links, the maximum flow of players and the maximum capacity of links.