We study coordination mechanisms for scheduling n selfish tasks on m identical parallel machines and we focus on the price of anarchy of non-preemptive coordination mechanisms, i.e., mechanisms whose local policies do not delay or preempt tasks. We prove that the price of anarchy of every non-preemptive coordination mechanism for m > 2 is Ω((log log m)/(log log log m)), while for m = 2, we prove a 7/6 lower bound. Our lower bounds indicate that it is impossible to produce a non-preemptive coordination mechanism that improves on the currently best known price of anarchy for identical machine scheduling, which is 4/3- 1/(3m).
展开▼
