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

The men's and women's preferences:
m: w:

Let us use "engagement" for a provisional agreement to marry, and call a set of engagements (un)stable in the obvious sense.

  1. Initially nobody is engaged -- which is certainly a stable (and empty) set of engagements.
  2. At some intermediate step, men m0, ..., mi-1, i ≥ 0, are stably engaged to women wpartner(m0), ..., wpartner(mi-1), respectively. Man mi now becomes the current proposer, cp, and proposes to each of his preferences, in order, until one of them accepts him. For such a proposal the woman, w,
    1. rejects cp if she is engaged to someone she prefers over cp,
      (cp keeps on trying -- with his next preference -- until one of the following conditions applies.)
    2. accepts cp if she is engaged but prefers cp to her current partner, m, who she jilts,
      (cp would not or could not elope with another engaged woman, w', either because he prefers w to w', or w' prefers her current partner to cp. And, w has just got a better offer, so she remains stable. m now takes over the role of current proposer, cp.)
    3. accepts cp if she is not currently engaged.
      (The new set is stable because cp is now engaged to the highest of his preferences that would take him, and none of the other m0, ..., mi prefer w to their current partners otherwise at least one would have previously proposed to w and been accepted -- she would have been engaged.)
    After this plays out, men m0, ..., mi are stably engaged to members of the previous set of women plus one more.
  3. Repeat, with the next man, until all the men and women are stably engaged -- married.

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.

References