Locally stable matchings in kidney exchanges programs

Kidney Exchange Programs (KEP) address the challenge of optimally assigning
compatible kidney donors to patients who have willing but incompatible donors. Local
stability was introduced in KEP by Baratto et al. to capture exchanges that avoid blocking
pairs intersecting the exchange. When exchanges are restricted to matchings, it turns out
that this notion coincides exactly with the concept of irreversible pairs, introduced by Birò
et al. in order to study Q-stable matchings. Using a polynomial algorithm, we evaluate the
consequences of imposing local stability in synthetic KEP instances.