Given a set of
men and
women, marry them off in pairs after each man has ranked the women in order of preference
from 1 to ,
and each women has done likewise, . If the resulting set of marriages contains no
pairs of the form , such that prefers to and prefers to , the marriage is said to be stable. Gale and Shapley (1962)
showed that a stable marriage exists for any choice of rankings (Skiena 1990, p. 245).
In the United States, the algorithm of Gale and Shapley (1962) is used to match hospitals
to medical interns (Skiena 1990, p. 245).

In the rankings illustrated above, the male-optimal stable marriage is 4, 2, 6, 5, 3, 1, 7, 9, 8, and the female-optimal stable marriage is 1, 2, 8, 9, 3, 4, 7, 6,
5. A stable marriage can be found using StableMarriage[m,
w] in the Wolfram Language
package Combinatorica` .