Price of Anarchy in Non-Cooperative Load Balancing

Urtzi Ayesta (1) , Olivier Brun (1) , Balakrishna Prabhu (1)

1 LAAS - Laboratoire d'analyse et d'architecture des systèmes

We investigate the price of anarchy of a load balancing game with $K$ dispatchers. The service rates and holding costs are assumed to depend on the server, and the service discipline is assumed to be processor-sharing at each server. The performance criterion is taken to be the weighted mean number of jobs in the system, or equivalently, the weighted mean sojourn time in the system. We first show that, for a fixed amount of total incoming traffic, the worst-case Nash equilibrium occurs when each player routes exactly the same amount of traffic, i.e., when the game is symmetric. For this symmetric game, we provide the expression for the loads on the servers at the Nash equilibrium. Using this result we then show that, for a system with two or more servers, the price of anarchy, which is the worst-case ratio of the global cost of the Nash equilibrium to the global cost of the centralized setting, is lower bounded by $K/(2\sqrt{K}-1)$ and upper bounded by$\sqrt{K}$, independently of the number of servers.

Mots clés: atomic games; load balancing; processor sharing; price of anarchy.; price of anarchy

Domaines: Réseaux et télécommunications [cs.NI]; Informatique et théorie des jeux [cs.GT]

Urtzi Ayesta, Olivier Brun, Balakrishna Prabhu. Price of Anarchy in Non-Cooperative Load Balancing. 2009. ⟨hal-00416123⟩