Inefficiency analysis of the scheduling game on limited identical machines with activation costs

• Some important properties are obtained about the Nash Equilibrium (NE) of our considered model.
• The quality of the worst and best NE assignments is qualified by the Price of Anarchy (PoA) and Price of Stability (PoS), respectively.
• The tight upper bounds of PoA and PoS are proved with respect to different jobs' total lengths, and some examples are also presented.

We investigate the scheduling game on a fixed number m of identical machines that no machines are initially activated and each machine activated incurs the same activation cost. Every job, as a selfish player, is interested in minimizing its own individual cost composing of both the load of its chosen machine and its share in the machine's activation cost, whereas the social cost focuses on the sum of makespan and total activation cost. The inefficiency of pure Nash equilibria is assessed by the Price of Anarchy (PoA) and Price of Statibility (PoS). First, when the jobs' total length is no larger than a single machine's activation cost, we demonstrate that m   is the tightness upper bound of PoA and PoS equals to 1. Then, for the case that the total length is large, we prove that the PoA is tightly bounded by (m+1)/2(m+1)/2. Finally, a lower bound of the PoS is also given.