The stable marriage problem asks for a stable marriage from the preference rankings of two equally sized sets of participants. The Gale-Shapley
algorithm always produces such a matching for complete strict preference lists (Gale
and Shapley 1962). In the United States, this algorithm 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.
This problem is distinct from the secretary problem, an optimal-stopping problem that is also sometimes called a marriage problem, and
from Hall's marriage theorem, which gives a criterion
for the existence of a matching.
