Inefficiency of Nash Equilibrium for scheduling games with constrained jobs: A parametric analysis

In this paper, we revisit the inefficiency of Nash Equilibrium of scheduling games by considering the Price of Anarchy (PoA) as a function of r  , which is the ratio between the maximum and minimum size of jobs. For the social costs of minimizing makespan and maximizing the minimum machine load of all machines, we obtain the PoA for two and three machines, and the bound is tight for any r⩾1r⩾1. Lower bounds on the PoA for general number of machines are also presented.