10.02.2010

We consider the load balancing problem introduced by Koutsoupias and Papadimitriou 1999. Given a set of machines and players where each player own a job, the players can choose the machine that processes their job. The question is how good is a Nash equilibrium in relation to an optimal schedule for a given objective function. The makespan and average completion times are often considered as objective functions. We consider variants where we use the completion time in relation to the job size instead of the completion time and thus normalize by the job sizes. The idea of these objective functions is to model that a player with a small job suffers more from the same amount of delay than a player with a large job. The processing model used by Koutsoupias and Papadimitriou has a bad coordination ratio for such objective functions. With a natural change of the processing model we improve on the performance for the new set of objective functions. In the case of identical machines we give tight upper bounds on the coordination ratio for the unnormalized and normalized objective functions and prove that any Nash equilibrium is an optimal solution for the average and normalized average completion times.