  We study strong stability of Nash equilibria in load balancing games of m (m
>= 2) identical servers, in which every job chooses one of the m servers and
each job wishes to minimize its cost, given by the workload of the server it
chooses.
  A Nash equilibrium (NE) is a strategy profile that is resilient to unilateral
deviations. Finding an NE in such a game is simple. However, an NE assignment
is not stable against coordinated deviations of several jobs, while a strong
Nash equilibrium (SNE) is. We study how well an NE approximates an SNE.
  Given any job assignment in a load balancing game, the improvement ratio (IR)
of a deviation of a job is defined as the ratio between the pre- and
post-deviation costs. An NE is said to be a r-approximate SNE (r >= 1) if there
is no coalition of jobs such that each job of the coalition will have an IR
more than r from coordinated deviations of the coalition.
  While it is already known that NEs are the same as SNEs in the 2-server load
balancing game, we prove that, in the m-server load balancing game for any
given m >= 3, any NE is a (5/4)-approximate SNE, which together with the lower
bound already established in the literature yields a tight approximation bound.
This closes the final gap in the literature on the study of approximation of
general NEs to SNEs in load balancing games. To establish our upper bound, we
make a novel use of a graph-theoretic tool.
