PATHS TO MARRIAGE-STABILITY

We obtain a family of algorithms that determine stable matchings for t he stable marriage problem by starting with an arbitrary matching and iteratively satisfying blocking pairs, that is, matching couples who b oth prefer to be together over the outcome of the current matching. Th e existence of such an algorithm is related to a question raised by Kn uth (1976) and was recently resolved positively by Roth and Vande Vate (1992). The basic version of our method depends on a fixed ordering o f all mutually acceptable man-woman pairs which is consistent with the preferences of either all men or of all women. Given such an ordering , we show that starting with an arbitrary matching and iteratively sat isfying the highest blocking pair at each iteration will eventually yi eld a stable matching. We show that the single-proposal variant of the Gale-Shapley algorithm as well as the Roth-Vande Vate algorithm are i nstances of our approach. We also demonstrate that an arbitrary decent ralized system does not guarantee convergence to a stable matching.