  A Nash Equilibrium (NE) is a strategy profile resilient to unilateral
deviations, and is predominantly used in the analysis of multiagent systems. 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 strong equilibrium.
  Coalition formation is a key issue in multiagent systems. We provide a
framework for quantifying the stability and the performance of various
assignment policies and solution concepts in the face of coalitional
deviations. Within this framework we evaluate a given configuration according
to three measures: (i) IR_min: the maximal number alpha, such that there exists
a coalition in which the minimal improvement ratio among the coalition members
is alpha, (ii) IR_max: the maximal number alpha, such that there exists a
coalition in which the maximal improvement ratio among the coalition members is
alpha, and (iii) DR_max: the maximal possible damage ratio of an agent outside
the coalition.
  We analyze these measures in job scheduling games on identical machines. In
particular, we provide upper and lower bounds for the above three measures for
both NE and the well-known assignment rule Longest Processing Time (LPT).
  Our results indicate that LPT performs better than a general NE. However, LPT
is not the best possible approximation. In particular, we present a polynomial
time approximation scheme (PTAS) for the makespan minimization problem which
provides a schedule with IR_min of 1+epsilon for any given epsilon. With
respect to computational complexity, we show that given an NE on m >= 3
identical machines or m >= 2 unrelated machines, it is NP-hard to determine
whether a given coalition can deviate such that every member decreases its
cost.
