Worst-case Analysis of Non-Cooperative Load Balancing

We investigate the impact of heterogeneity in the amount of incoming traffic routed by dispatchers in a non-cooperative load balancing game. For a fixed amount of total incoming traffic, we give sufficient conditions on the cost function under which the worst-case social cost occurs when each dispatcher routes the same amount of traffic, that is, the game is symmetric. We then analyze the symmetric game and derive an explicit expression for the equilibrium flows. We also obtain lower bounds on the Price of Anarchy for (i) cost functions that are polynomial on server loads; and (ii) cost functions representing the mean delay of the Shortest Remaining Processing Time (SRPT) service discipline