  We consider a scheduling game on parallel related machines, in which jobs try
to minimize their completion time by choosing a machine to be processed on.
Each machine uses an individual priority list to decide on the order according
to which the jobs on the machine are processed. We prove that it is NP-hard to
decide if a pure Nash equilibrium exists and characterize four classes of
instances in which a pure Nash equilibrium is guaranteed to exist. For each of
these classes, we give an algorithm that computes a Nash equilibrium, we prove
that best-response dynamics converge to a Nash equilibrium, and we bound the
inefficiency of Nash equilibria with respect to the makespan of the schedule
and the sum of completion times. In addition, we show that although a pure Nash
equilibrium is guaranteed to exist in instances with identical machines, it is
NP-hard to approximate the best Nash equilibrium with respect to both
objectives.
