Local stability of kidney exchanges

Kidney Exchange Programs (KEP) address the challenge of optimally assigning
compatible kidney donors to patients who have willing but incompatible donors. In a KEP,
incompatible donor-recipient pairs can "swap" donors with other pairs to create compatible
matches. The swaps can involve multiple pairs in cyclic exchanges. The goal is to
maximize the number of matches under various constraints, e.g., an upper bound on the
cycle length or a stability requirement. Here, we restrict our attention to cycles of length 2
and to the case where each recipient expresses preferences among its compatible
donors. This is the setting of the classical Stable Roommates Problem (SRP). It gives rise to a graph model where vertices represent recipient-donor pairs and edges represent compatibilities. This setting can also be viewed as a model of CEOs looking for strategic partnerships. CEOs are like patients needing kidney exchanges. Each CEO has preferences over potential partners (based on synergy, market access, etc.). But not all matches are possible: compatibility constraints exist (like resources, values, etc.).
A matching M is called stable when it has no blocking pair, meaning a pair of vertices that would prefer to be matched together rather than to their current mates in M. Determining whether a stable matching exists for an instance of SRP, and producing one if it does, can be done in polynomial time. Baratto et al. (2024) recently introduced a new concept called local stability (or L-stability). A matching M is L-stable if no blocking pair intersects M. We present several structural results on L-stable matchings, as well as a strong property of such matchings with respect to stable partitions. From these results, we derive a polynomial-time algorithm for computing an L-stable matching of maximum size.