Computational Complexity of k-stable Matchings

Titelangaben

Aziz, Haris ; Csáji, Gergely ; Cseh, Ágnes:
Computational Complexity of k-stable Matchings.
In: ACM Transactions on Economics and Computation. Bd. 13 (2025) Heft 1 . - 5.
ISSN 2167-8383
DOI: https://doi.org/10.1145/3708507

Volltext

Link zum Volltext (externe URL):

Abstract

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.