We consider a scheduling game 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 characterize four classes of instances in which a pure Nash equilibrium
is guaranteed to exist, and show, by means of an example, that we cannot expect to
find larger classes for which a pure Nash equilibrium always exists. We then bound the
performance of Nash equilibria for each of these classes with respect to the makespan
of the schedule and the sum of completion times. We also analyze the computational
complexity of several problems arising in this model. For instance, we prove that it
is NP-hard to decide whether a NE exists, and that even for instances with identical
machines, for which a NE is guaranteed to exist, it is NP-hard to approximate the best
NE within a factor of 2 -1/m-eps for all eps > 0.
In addition, we study a generalized model in which players' strategies are subsets of
resources, each having its own priority list over the players.We show that in this general
model, even unweighted symmetric games may not have a pure NE, and we bound the
price of anarchy with respect to the total players' costs.