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.