A note on the lower bound for the Price of Anarchy of scheduling games on unrelated machines

This note presents a lower bound for the Strong Price of Anarchy (SPoA) of coordination mechanisms for unrelated parallel machine scheduling games with social cost of minimizing the makespan. The SPoA of any set of non-preemptive strongly local policies satisfying the IIA property is at least mm, the number of machines. Combining with the upper bound of the worst-case ratio of Shortest First algorithm for unrelated parallel machine scheduling problem with objective of minimizing the makespan (Ibarra and Kim, 1977), the SPoA of SPTSPT policy, as well as the worst-case ratio of Shortest First algorithm, is exactly mm.