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 optimal 

↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso88591, fetched Tuesday, 25Jun2019 16:43:25 EDT. Free: Linux, Ubuntu operatingsys, OpenOffice officesuite, The GIMP ~photoshop, Firefox webbrowser, FlashBlock flash on/off. 