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` .
