Tight Bounds for Selfish and Greedy Load Balancing

We study the load balancing problem in the context of a set of clients eachwishing to run a job on a server selected among a subset of permissible servers forthe particular client. We consider two different scenarios. In selfish load balancing,each client is selfish in the sense that it chooses, among its permissible servers, torun its job on the server having the smallest latency given the assignments of thejobs of other clients to servers. In online load balancing, clients appear online and,when a client appears, it has to make an irrevocable decision and assign its job toone of its permissible servers. Here, we assume that the clients aim to optimize someglobal criterion but in an online fashion. A natural local optimization criterion thatcan be used by each client when making its decision is to assign its job to that serverthat gives the minimum increase of the global objective. This gives rise to greedyonline solutions. The aim of this paper is to determine how much the quality of loadbalancing is affected by selfishness and greediness.We characterize almost completely the impact of selfishness and greediness inload balancing by presenting new and improved, tight or almost tight bounds on theprice of anarchy of selfish load balancing as well as on the competitiveness of thegreedy algorithm for online load balancing when the objective is to minimize thetotal latency of all clients on servers with linear latency functions. In addition, weprove a tight upper bound on the price of stability of linear congestion games.