We consider approximate strong equilibria (SE) in strategic job
scheduling games with two uniformly related machines. Jobs are assigned
to machines, and each job wishes to minimize its cost, given by the
completion time of the machine it is assigned to.
Finding a Nash equilibrium (NE) in this game is simple. However,
NE-configurations are not stable against coordinated deviations of
several jobs. Various measures can be used to evaluate how well an NE-configuration approximates SE.
A schedule is said to be an $\alpha$-SE if there is no
coalitional deviation such that every member of the coalition
reduces its cost by a factor greater than $\alpha$. We show that any
pure-NE on two related machines of speed ratio s is a
$\frac{s^2+s-1}{s^2}\leq 5/4$-SE, and provide a matching
lower bound. In addition, we show that the LPT (Longest Processing
Time) algorithm provides a better approximation ratio than a general
NE, in particular, any LPT schedule is a 1.1011-SE. This is
in contrast to the LS (List Scheduling) greedy algorithm for which
the improvement ratio of coalitional deviations can be arbitrarily
large. In addition, we design a fully polynomial time approximation
scheme (\FPTAS), which computes an NE that is a $(1+\eps)$-SE.
We also provide bounds for two other measures of approximate SE,
considering the supremum possible improvement of a deviating job
and the maximal increase in the cost of non-coalition members, and
show that checking whether a specific schedule is an SE is co-NP-complete, which motivates the study of approximate
strong equilibria.
Finally, we consider multiple machines. We show that any pure NE on m related machines is a 2-SE.
We give improved results for identical machines, and in particular, we show that any pure NE is a 1.32-SE.