The Stable Marriage Problem

The Stable Marriage problem is a classical combinatorial problem that belongs to the family of stable matching problems. An instance of the Stable Marriage problem involves n men and n women, and each person ranks all members of the opposite sex in strict order of preference. Given a matching M of the men and women (in other words, a one-one correspondence between them), we say that M admits a blocking pair if there is a man m and a woman w, not matched together in M, such that m prefers w to his partner in M and w prefers m to her partner in M.

The existence of a blocking pair (m,w) represents a situation in which the man m and woman w involved would prefer to disregard their assigned spouses in the matching and have an affair, thereby undermining the integrity of the matching. Thus we seek a matching that admits no blocking pairs as a solution to the Stable Marriage problem - such a matching is called a stable matching.

It is known that every instance of the Stable Marriage problem admits at least one stable matching, and furthermore, such a matching can be found in time linear in the size of the problem instance using an efficient algorithm known as the Gale/Shapley algorithm [1].

Here is a Java Applet containing an implementation of the Gale/Shapley algorithm (to be precise, a more efficient version, the so-called Extended Gale/Shapley algorithm, appearing in Section 1.2.4 of [2], has been implemented). The user is prompted to enter the number n of men in a given instance of the Stable Marriage problem (n must be between 1 and 16). After the button "Calculate stable matching" is clicked on, an instance with n men and n women is then created, each person having randomly generated preference lists. The program then outputs these preference lists and superimposes a stable matching (namely the man-optimal stable matching) onto them, also listing the (man,woman) pairs in the stable matching explicitly.

[1] D. Gale and L.S. Shapley, "College admissions and the stability of marriage", American Mathematical Monthly, vol. 69, pp. 9-15, 1962.

[2] D. Gusfield and R.W. Irving, "The Stable Marriage Problem, Structure and Algorithms", MIT Press, 1989.