A Nash Equilibriun (NE) is a strategy profile that is resilient to
unilateral deviations, and is predominantly used in analysis of
competitive games. A downside of NE is that it is not necessarily
stable against deviations by coalitions. Yet, as we show in this
paper, in some cases, NE does exhibit stability against
coalitional deviations, in that the benefits from a joint
deviation are bounded. In this sense, NE approximates \emph{strong
equilibrium} (SE) \cite{aumann1959}.

We provide a framework for quantifying the stability and the
performance of various assignment policies and solution concept in
the face of coalitional deviations. Within this framework we
evaluate a given configuration according to three measurements:
(i) $IR_{min}$: the maximal number $\alpha$, such that there
exists a coalition in which the minimum improvement ratio among
the coalition members is $\alpha$ (ii) $IR_{max}$: the maximum
improvement ratio among the coalition's members. (iii) $DR_{max}$:
the maximum possible damage ratio of an agent outside the
coalition.

This framework can be used to study the proximity between
different solution concepts, as well as to study the existence of
approximate SE in settings that do not possess any such
equilibrium. We analyze these measurements in job scheduling games
on identical machines. In particular, we provide upper and lower
bounds for the above three measurements for both NE and the
well-known assignment rule \emph{Longest Processing Time} (LPT)
(which is known to yield a NE). Most of our bounds are tight for
any number of machines, while some are tight only for three
machines. We show that both NE and LPT configurations yield small
constant bounds for $IR_{min}$ and $DR_{max}$. As for $IR_{max}$,
it can be arbitrarily large for NE configurations, while a small
bound is guaranteed for LPT configurations. For all three
measurements, LPT performs strictly better than NE.

With respect to computational complexity aspects, we show that
given a NE on $m \geq 3$ identical machines and a coalition, it is
NP-hard to determine whether the coalition can deviate such that
every member decreases its cost. For the unrelated machines
settings, the above hardness result holds already for $m\geq 2$
machines.