Stable marriage problem

Rob Speer

Emperor of Graphland

• to increase its population and its world influence, every eligible citizen must get married!

Stability

• We don't want to destabilize the kingdom with people cheating and running off with each other
• We can collect everyone's preferences about who they want to marry
• Never let there be two unmarried people who would rather be with each other than their spouses

Naive solution

• assign pairs arbitrarily
• let people run off with each other as they want, marrying their dumped spouses together
• when this terminates, the result is a stable matching
• Problem: doesn't always terminate!

A: Q > P > R
B: arbitrary
C: P > Q > R

a: A > C > B
b: C > A > B
c: arbitrary

A-P B-Q C-R    A and Q elope
A-Q B-P C-R    C and Q elope
A-R B-P C-Q    C and P elope
A-R B-Q C-R    A and P elope
A-P B-Q C-R

Gale-Shapley algorithm

• very traditional

Loop until all men are engaged:
  For each unengaged ("free") man m:
    [make joke about 'freedom' here]
    m proposes to his most-preferred woman who has not already rejected him
    [Does such a woman exist?]
    If w is unmarried:
      m becomes engaged to w
    If w is married to m':
      If w prefers m to m':
        w rejects m'
        w becomes engaged to m
      If w doesn't prefer m to m':
        w rejects m
Finally, all engagements become marriages

All men end up engaged because:

• Suppose one man, M, is left out
• A woman W must be left out too
• But M proposed to W at some point because all rankings are complete
• W would have accepted her first proposal - contradiction

Definitions

• B is a feasible spouse for A if A and B are married in some stable matching
• B is the optimal spouse for A if B is the highest ranked feasible spouse for A
• B is unattainable for A if B is ranked higher than A's optimal spouse (and therefore the marriage must not be feasible)

Algorithm is optimal for men:

• By contradiction, suppose that man m is the first to be rejected by his optimal wife w
• w must have rejected m for some other man, z
• w must be z's optimal partner or better (because this happened first to m, not z)
• There exists a stable pairing S where m is married to w (by definition of "optimal"), and z is married to a
• In S, w prefers z > m
• In S, z prefers w > a (because w is either optimal or unattainable for z)
• So the marriage is unstable - contradiction

But any male-optimal assignment is female-pessimal.

• Consider a stable, male-optimal pairing G, and some other stable pairing S
• In G, m is married to his optimal wife w
• In S, m is married to w', and w is married to m'
  • If there is no such S, then m and w are the only stable partners for each other, so their marriage is both optimal and pessimal
• m prefers w to w', because w is his optimal wife
• w prefers m' to m, so that S is stable -- otherwise m and w would run off together

Pathological case:

 A: P > Q > R > S > T
 B: Q > R > S > T > P
 C: R > S > T > P > Q
 D: S > T > P > Q > R
 E: T > P > Q > R > S
 
 P: B > C > D > E > A
 Q: C > D > E > A > B
 R: D > E > A > B > C
 S: E > A > B > C > D
 T: A > B > C > D > E

Opposite columns are stable matchings.

Other topics

• A set of marriages is Pareto optimal if no couple can elope with the consent of their spouses; that is, there is no exchange of spouses that would be acceptable for everyone involved.
  • In general, "Pareto optimal" is the economics term that means "not stupid".
• A set of marriages is maximum if it maximizes the sum of people's happiness. (People need to assign utility values to their potential spouses, not just rankings.) Maximum marriages are not necessarily stable!
• Fuku, Takai, and Namatame have proposed an algorithm that compromises on marriages that are neither male-optimal nor female-optimal. I don't understand it, because it's in really broken English.

Gay marriage?

The following situation cannot be stable:

A: B > C > Z
B: C > A > Z
C: A > B > Z
Z: A > B > C

This problem was called the stable roommate problem by Knuth. (Hey, he's not necessarily a prude. It was the 70's, not the 00's.) Complete stable solutions aren't guaranteed to exist! But certain algorithms make stable assignments for the largest set of people who can be matched stably.

Where SMP is used

• Assigning graduating medical students to hospitals ("the Match")
• Stereo reconstruction in computer vision (dude!)