Tighter bounds on the inefficiency ratio of stable equilibria in load balancing games

摘要

In this paper we study the inefficiency ratio of stable equilibria in load balancing games introduced by Asadpour and Saberi (2009). We prove tighter lower and upper bounds of 7/6 and 4/3, respectively. This improves over the best known bounds for the problem (19/18 and 3/2, respectively). Equivalently, the results apply to the question of how well the optimum for the L-2-norm can approximate the L-infinity-norm (makespan) in identical machines scheduling. (C) 2016 Elsevier B.V. All rights reserved.