Theoretical analysis demonstrates polynomial-time solvability of non-uniformly stable matchings in systems with ties, highlighting unified structural and computational properties.
Super-stability and strong stability are properties of a matching in the stable matching problem with ties. In this paper, we introduce a common generalization of super-stability and strong stability, which we call non-uniform stability. First, we prove that we can determine the existence of a non-uniformly stable matching in polynomial time. Next, we give a polyhedral characterization of the set of non-uniformly stable matchings. Finally, we prove that the set of non-uniformly stable matchings forms a distributive lattice.
No takes yet. Share an insight, caveat, or question.
Naoyuki Kamiyama (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: