Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game

Abstract

This paper studies a load balancing game introduced by Koutsoupias and Papadimitriou, that is intended to model a set of users who share several internet-based resources. Some of the recent work on this topic has considered the problem of constructing Nash equilibria, which are choices of actions where each user has optimal utility given the actions of the other users. A related (harder) problem is to find sequences of utility-improving moves that lead to a Nash equilibrium, starting from some given assignment of resources to users.We consider the special case where all resources are the same as each other. It is known already that there exist efficient algorithms for finding Nash equilibria; our contribution here is to show furthermore that Nash equilibria for this type of game are reached rapidly by Randomized Local Search, a simple generic method for local optimization. Our motivation for studying Randomized Local Search is that (as we show) it can be realised by a simple distributed network of users that act selfishly, have no central control and only interact via the effect they have on the cost functions of resources.