  We consider polymatrix coordination games with individual preferences where
every player corresponds to a node in a graph who plays with each neighbor a
separate bimatrix game with non-negative symmetric payoffs. In this paper, we
study $\alpha$-approximate $k$-equilibria of these games, i.e., outcomes where
no group of at most $k$ players can deviate such that each member increases his
payoff by at least a factor $\alpha$. We prove that for $\alpha \ge 2$ these
games have the finite coalitional improvement property (and thus
$\alpha$-approximate $k$-equilibria exist), while for $\alpha < 2$ this
property does not hold. Further, we derive an almost tight bound of
$2\alpha(n-1)/(k-1)$ on the price of anarchy, where $n$ is the number of
players; in particular, it scales from unbounded for pure Nash equilibria ($k =
1)$ to $2\alpha$ for strong equilibria ($k = n$). We also settle the complexity
of several problems related to the verification and existence of these
equilibria. Finally, we investigate natural means to reduce the inefficiency of
Nash equilibria. Most promisingly, we show that by fixing the strategies of $k$
players the price of anarchy can be reduced to $n/k$ (and this bound is tight).
