Locally stable matchings for the roommates problem

Stability of matchings under preferences has been extensively studied in operations research and in economics. In the classical stable roommates problem, the aim is to match pairs of individuals who intend to share living spaces or to trade indivisible resources, as in kidney exchange programs. A matching is called stable when it has no blocking pair, meaning a pair of individuals who would prefer to be matched together rather than to their current mates, or rather than remaining unmatched. Due to its relevance in real-world settings, various extensions of this problem have been investigated in the literature. These extensions have been analyzed from an algorithmic perspective, and polynomial algorithms or hardness results are available for many of them. The present paper examines locally stable matchings, a recently introduced generalization of stable matchings. A matching is locally stable if no blocking pair intersects it. Every stable matching is locally stable, but the converse is not true: a stable matching may not exist for some preference structures, whereas a locally stable matching always exists (though it may be empty). We present several structural results on locally stable matchings, including a strong property of such matchings with respect to stable partitions. From these results, we derive a polynomial-time algorithm to compute a locally stable matching of maximum size.