Coordination mechanism for selfish scheduling under a grade of service provision

In this paper, we study the problem of selfish scheduling game under a grade of service provision, where all machines and all jobs are labeled with the different grade of service (GoS) levels such that a job J can be assigned to execute on machine M only when the GoS level of machine M is not higher than the GoS level of job J. We consider two coordination mechanisms for this selfish scheduling game: the makespan policy and the LG‐LPT policy. For the first mechanism, we show that the price of anarchy is exactly $\frac{3}{2}$ for two machines and $\Theta (\frac{\log m}{\log \log m})$ for m $(⩾3)$ machines, respectively. For the second mechanism, we point out that the price of anarchy is $\frac{5}{4}$ for two machines and $2-\frac{1}{m-1}$ for m $(⩾3)$ machines, respectively, and we finally analyze the convergence to a Nash equilibrium of the induced game.