2015/12/10 by Akaki Mamageishvili, Mamageishvili, Akaki, Paolo Penna +1 · 1 citation
Computer Science · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #cs.GT
paper · pdf · doi:10.48550/arxiv.1512.03484
arxiv created 2015/12/10 · arxiv updated 2015/12/14
In this paper we study the inefficiency ratio of stable equilibria in load balancing games introduced by Asadpour and Saberi [3]. We prove tighter lower and upper bounds of 7/6 and 4/3, respectively. This improves over the best known bounds in problem (19/18 and 3/2, respectively). Equivalently, the results apply to the question of how well the optimum for the L2 -norm can approximate the L∞-norm (makespan) in identical machines scheduling.