Abstract:

We study the number of steps required to reach a pure Nash Equilibrium 
in a load balancing scenario where each job behaves selfishly and 
attempts to migrate to a machine which will minimize its cost.

We consider variety of load balancing models, including identical,
restricted, related and unrelated machines. Our results have a crucial
dependence on the allowable weights assigned to jobs. We consider
arbitrary weights, integer weights, K distinct weights and identical
(unit) weights. We look both at an arbitrary schedule (where the only
restriction is that a job migrates to a machine which lowers its cost)
and specific efficient schedulers (such as allowing the largest weight
job to move first).

This is a joint work with Eyal Even-Dar and Alex Kesselman.