Paper ID: 6497
DCS Tech Report Number: TR-1999-29
Stable Marriage with Ties and Unacceptable Partners
Tech Report (internal)
DCS Tech Report
Page Numbers :
Publisher: Dept of Computing Science, University of Glasgow
An instance of the classical stable marriage problem involves n men and n women, and each person ranks all n members of the opposite sex in strict order of preference. The effect of allowing ties in the preference lists has been investigated previously, and three natural definitions of stability arise. In this paper, we extend this study by allowing a preference list to involve ties and/or be incomplete. We show that, under the weakest notion of stability, the stable matchings need not be all of the same cardinality, and the decision problem related to finding a maximum cardinality stable matching is NP-complete, even if the ties occur in the preference lists of one sex only. This result has important implications for practical matching schemes such as the well-known National Resident Matching Program (A.E. Roth, The evolution of the labor market for medical interns and residents: a case study in game theory, Journal of Political Economy, 92(6):991–1016, 1984). In the cases of the other two notions of stability, Irving (Stable marriage and indifference, Discrete Applied Mathematics, 48:261–272, 1994) has described algorithms for testing whether a stable matching exists, and for constructing such a matching if one does exist, where a preference list is complete but may involve ties. We demonstrate how to extend these algorithms to the case where a preference list may be incomplete and/or involve ties.