Computational complexity of $k$-stable matchings

Haris Aziz, Gergely Csáji, Ágnes Cseh

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…