Convergence Time to Nash Equilibria in Load Balancing
Yishay Mansour, TAU
September 19th, 2003, Wean 7220 3:30pm

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.