TOPICS
Search

Stable Marriage Problem


Given a set of n men and n women, marry them off in pairs after each man has ranked the women in order of preference from 1 to n, {w_1,...,w_n} and each women has done likewise, {m_1,...,m_n}. If the resulting set of marriages contains no pairs of the form {m_i,w_j}, {m_k,w_l} such that m_i prefers w_l to w_j and w_l prefers m_i to m_k, 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).

StableMarriage

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


See also

Divorce Digraph, Matching

Explore with Wolfram|Alpha

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

Subject classifications