Inefficiency of equilibria for the machine covering game on uniform machines

This paper studies a scheduling game on uniform machines with social cost of maximizing the minimum machine load. For the game with two machines, we present the (Strong) Price of Stability and (Strong) Price of Anarchy as a function of s, the ratio of the speeds of the two machines. These bounds are all tight for any value of s, thus the problem of measuring the inefficiency of equilibria on two uniform machines is completely solved. We also give the tight Price of Anarchy for a special case of three machines. From the results above, we achieve some new and interesting insights of scheduling games.