Abstract
We investigate coordination mechanisms that schedule n jobs on m unrelated machines. The objective is to minimize the latest completion of all jobs, i.e., the makespan. It is known that if the mechanism is non-preemptive, the price of anarchy is Omega(log m). Both Azar, Jain, and Mirrokni (SODA 2008) and Caragiannis (SODA 2009) raised the question whether it is possible to design a coordination mechanism that has constant price of anarchy using preemption. We give a negative answer.
All deterministic coordination mechanisms, if they are symmetric and satisfy the property of independence of irrelevant alternatives, even with preemption, have the price of anarchy Omega(log m/log log m). Moreover, all randomized coordination mechanisms, if they are symmetric and unbiased, even with preemption, have similarly the price of anarchy Omega(log m/log log m).
Our lower bound complements the result of Caragiannis, whose BCOORD mechanism guarantees Omega(log m/log log m) price of anarchy. Our lower bound construction is surprisingly simple. En route we prove a Ramsey-type graph theorem, which can be of independent interest.
On the positive side, we observe that our lower bound construction critically uses the fact that the inefficiency of a job on a machine can be unbounded. If, on the other hand, the inefficiency is not unbounded, we demonstrate that it is possible to break the Omega(log m/log log m) barrier on the price of anarchy by using known coordination mechanisms.