Locally Stable Roommate Problem

In 1962, Gale and Shapley initiated the study of stable matching problems, introducing the Stable Marriage Problem (SMP). The aim is to match men and women based on their preferences for all members of the opposite gender. A matching is deemed stable if there are no pairs of unmatched individuals who prefer each other to their partners in the matching. We say that there are no blocking pairs.
A natural generalization of SMP is to consider non-bipartite models. For instance, consider a set of n individuals where each one ranks all the others in order of preference. In this context, a matching can be assimilated to pairing individuals to share living spaces, leading to the formulation of the Stable Roommate Problem (SRP). While there always exists a stable matching in SMP, it is not the case in some instances of SRP. However, Irving provided a polynomial algorithm that, for any instance of SRP, determines whether a stable matching exists or not. If it exists, it produces one.
We focus on a different definition of stability, namely local stability, recently introduced in the context of kidney exchange programs (KEPs).
The decision problem's complexity for non-empty locally stable exchanges remains open. When the exchange is a matching, this is equivalent to a local version of SRP. Here, a matching achieves local stability if no blocking pairs intersect with it. In this talk, we explore the trade-offs between global and local stability and discuss the complexity of local SRP.