Paths to marriage stability (Q1902886)

In the stable marriage problem, one can start with an arbitrary matching and repeatedly adjust it to satisfy a blocking pair (a woman and a man who each prefer the other to their current partner). This need not converge, but it has been shown that judicious choice of the blocking pair to be satisfied leads to convergence. In this paper, the authors examine in some detail the conditions under which the algorithm does converge.