Stable marriage and indifference

AbstractIt 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, in this paper, we describe 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