  We study deviations by a group of agents in the three main types of matching
markets: the house allocation, the marriage, and the roommates models. For a
given instance, we call a matching $k$-stable if no other matching exists that
is more beneficial to at least $k$ out of the $n$ agents. The concept
generalizes the recently studied majority stability. We prove that whereas the
verification of $k$-stability for a given matching is polynomial-time solvable
in all three models, the complexity of deciding whether a $k$-stable matching
exists depends on $\frac{k}{n}$ and is characteristic to each model.

Discrete Mathematics