Computational Complexity of k -stable Matchings
Haris Aziz, Gergely Csáji, Ágnes Cseh
ACM Transactions on Economics and Computation,
Volume 13 , Issue 1 Paper 5. 25 p. (2025) – March 2025
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 of each model.
