  We present new coordination mechanisms for scheduling selfish jobs on $m$
unrelated machines. A coordination mechanism aims to mitigate the impact of
selfishness of jobs on the efficiency of schedules by defining a local
scheduling policy on each machine. The scheduling policies induce a game among
the jobs and each job prefers to be scheduled on a machine so that its
completion time is minimum given the assignments of the other jobs. We consider
the maximum completion time among all jobs as the measure of the efficiency of
schedules. The approximation ratio of a coordination mechanism quantifies the
efficiency of pure Nash equilibria (price of anarchy) of the induced game.
  Our mechanisms are deterministic, local, and preemptive. Our first
coordination mechanism has approximation ratio $\Theta(\log m)$ and guarantees
that the induced game has pure Nash equilibria. This result improves a bound of
$O(\log^2 m)$ due to Azar, Jain, and Mirrokni and uses a global ordering of the
jobs according to their distinct IDs. Our second mechanism handles anonymous
jobs and has approximation ratio $O(\frac{\log m}{\log \log m})$ although the
game induced is not a potential game and, hence, the existence of pure Nash
equilibria is not guaranteed by potential function arguments. However, it
provides evidence that the known lower bounds for non-preemptive coordination
mechanisms could be beaten using preemptive scheduling policies. Our third
coordination mechanism also handles anonymous jobs and has a nice
cost-revealing potential function. We use this potential function in order to
prove the existence of equilibria and to upper-bound the price of anarchy of
the induced game by $O(\log^2m)$. Our third coordination mechanism is the first
that handles anonymous jobs and simultaneously guarantees that the induced game
is a potential game and has bounded price of anarchy.
