Nonpreemptive Coordination Mechanisms for Identical Machines

We focus on the problem of scheduling n weighted selfish tasks on m identical parallel machines and we study the performance of nonpreemptive coordination mechanisms. A nonpreemptive coordination mechanism consists of m local scheduling policies that decide the processing order of the tasks on each machine without delays or interruptions. We discuss the existence of Nash equilibria for this setting and show that it is not a guaranteed property of all nonpreemptive coordination mechanisms. Next, we focus on the wider class of randomized Nash equilibria and prove lower bounds on the price of anarchy. Our lower bounds are presented in comparison to the currently best known coordination mechanism (which uses delays) and lead to the conclusion that preemption or delays are required in order to improve on the currently best known solution.