The Stable Marriage Problem
The stable marriage problem is a classic bipartite graph matching problem. The 2012 Nobel Prize in Economics went to Alvin E. Roth and Lloyd S. Shapley "for the theory of stable allocations and the practice of market design." This was for work starting with the stable marriage problem, David Gale and Shapley (1962). Gale died in 2008. In 2012 a Nobel prize was 8 million Swedish kronor (SEK), us$1.2 million.
In the simplest version of the stable marriage problem there are N men and N women, each man wants to marry one of the women, and each woman wants to marry one of the men. Each man lists the N women in order of preference, and each woman lists the N men in order of preference.
A set of marriages is unstable if you can find two couples, 〈m1, w1〉 and 〈m2, w2〉, such that m1 prefers w2 to w1, and w2 prefers m1 to m2. It is unstable because m1 and w2 would run off together. The set is stable if you cannot find two such couples. It is not immediately obvious that there is a set of stable marriages but there always is at least one solution, and in general there can be more than one.
It turns out that if the men take the initiative and the women are passive, the result is male optimal. This happens if a woman merely waits for a proposal and either rejects or (provisionally) accepts it but is allowed to change her mind if she gets a better offer. If the women take the initiative and the men are passive, the result is female optimal. It does not pay to be backward.
male optimalThe men's and women's preferences:
Let us use "engagement" for a provisional agreement to marry, and call a set of engagements (un)stable in the obvious sense.
The stable marriage problem has real-world applications. For example, when prospective students apply to Universities, a student can be modelled as a "man", and a University place can be modelled as a "woman".
Variations on the stable marriage problem include (male|female|global)-optimal, different "cost" functions to be optimised, equality allowed in a preference list, incomplete (short) lists of preferences, unequal numbers of men and women, and so on.
↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated).
Created with "vi (Linux)", charset=iso-8859-1, fetched Friday, 01-Mar-2024 05:22:38 UTC.
Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.