Distributed Selfish Load Balancing
P. Berenbrink (Simon Fraser University, Canada), T. Friedetzky (Durham University, UK), I. Hajirasouliha (Simon Fraser University, Canada), and Z. Hu (Simon Fraser University).
Suppose that a set of m weighted tasks have to be assigned to a set of n resources. Every resource comes with a delay function f, and the load of a resource is f(w), where w is the total weight of all tasks assigned to the resource. The goal now is to minimise the maximum load of the resources.
A game-theoretic mechanism to find a suitable allocation is to associate each task with a ``selfish agent'' and require each agent to select a resource, with the cost of a resource being the load. Agents would then be expected to migrate 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 migrate selfishly without any centralised control. In this paper we discuss a natural protocol for the agents which combines the following desirable features: It can be implemented in a strongly distributed setting, uses no central control, and has good convergence properties. We show upper and lower bounds on the time that it takes for the protocol to converge to a Nash Equilibrium, i.e. a state in which no agent would benefit from choosing another resource.