Distributed Selfish Load Balancing \Lambda

Abstract Suppose that a set of m tasks are to be shared as equallyas possible amongst a set of n resources. A game-theoreticmechanism to find a suitable allocation is to associate each task with a "selfish agent", and require each agent to selecta resource, with the cost of a resource being the number of agents to select it. Agents would then be expected tomigrate from overloaded to underloaded resources, until the allocation becomes balanced.Recent work has studied the question of how this can take place within a distributed setting in which agents mi-grate selfishly without any centralized control. In this paper we discuss a natural protocol for the agents which combinesthe following desirable features: It can be implemented in a strongly distributed setting, uses no central control, andhas good convergence properties. For m AE n, the systembecomes approximately balanced (an ffl-Nash equilibrium) inexpected time O(log log m). We show using a martingaletechnique that the process converges to a perfectly balanced allocation in expected time O(log log m + n4). We also givea lower bound of \Omega (maxflog log m; ng) for the convergencetime. 1 Introduction Suppose that a consumer learns the price she would becharged by some domestic power supplier other than the on