Stable marriage and indifference

Stable marriage and indifference

0.00 Avg rating0 Votes
Article ID: iaor1995675
Country: Netherlands
Volume: 48
Issue: 3
Start Page Number: 261
End Page Number: 272
Publication Date: Feb 1994
Journal: Discrete Applied Mathematics
Authors:
Keywords: marriage problem
Abstract:

It is well known that every instance of the classical stable marriage problem admits at least one stable matching, and that such a matching can be found in O(n2) time by application of the Gale/Shapley algorithm. In the classical version of the problem, each person must rank the members of the opposite sex in strict order of preference. In practical applications, a person may not wish (or be able) to choose between alternatives, thus allowing ties in the preference lists (or, more generally, allowing each preference list to be a partial order). With the introduction of such indifference, the notion of stability may be generalised in three obvious ways. For the weakest extension of stability, the same existence result holds, and essentially the same algorithm may be applied. In the other two cases, however, there is no guarantee that stable matchings exist. Nonetheless, this paper describes polynomial-time algorithms that will establish, in either of these two cases, whether a matching of the appropriate kind exists, and if so will find such a matching.

Reviews

Required fields are marked *. Your email address will not be published.