Local stability of kidney exchanges with length- two cycles

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. 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.