TOPICS

# Stable Marriage Problem

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

Divorce Digraph, Matching

## Explore with Wolfram|Alpha

More things to try:

## References

Gale, D. and Shapley, L. S. "College Admissions and the Stability of Marriage." Amer. Math. Monthly 69, 9-14, 1962.Gusfield, D. and Irving, R. W. The Stable Marriage Problem: Structure and Algorithms. Cambridge, MA: MIT Press, 1989.Skiena, S. "Stable Marriages." §6.4.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 245-246, 1990.

## Cite this as:

Weisstein, Eric W. "Stable Marriage Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/StableMarriageProblem.html