A solution to the stable marriage problem

1. A solution to the stable marriage problem
Emily Riehl
Harvard University
http://www.math.harvard.edu/~eriehl
6 March 2013
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 1 / 20

2. Stable marriages
A matching is
other to his or her spouse.
The stable marriage problem
Find a stable matching for any dating pool.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 2 / 20

3. Stable marriages
A matching is
other to his or her spouse.
The stable marriage problem
Find a stable matching for any dating pool.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 2 / 20

4. The deferred-acceptance algorithm (Gale-Shapley)
description via a metaphor Day 0: each individual ranks the opposite sex
Day 1: (a.m.) each man proposes to his top choice
(p.m.) each woman rejects all but her top suitor
Dayn+ 1: (a.m.) each man rejected on daynproposes to his top
remaining choice
(p.m.) each woman rejects all but her top suitor
When each man is engaged, the algorithm terminates.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 3 / 20

5. The deferred-acceptance algorithm (Gale-Shapley)
description via a metaphor Day 0: each individual ranks the opposite sex
Day 1: (a.m.) each man proposes to his top choice
(p.m.) each woman rejects all but her top suitor
Dayn+ 1: (a.m.) each man rejected on daynproposes to his top
remaining choice
(p.m.) each woman rejects all but her top suitor
When each man is engaged, the algorithm terminates.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 3 / 20

6. The deferred-acceptance algorithm (Gale-Shapley)
description via a metaphor Day 0: each individual ranks the opposite sex
Day 1: (a.m.) each man proposes to his top choice
(p.m.) each woman rejects all but her top suitor
Dayn+ 1: (a.m.) each man rejected on daynproposes to his
top remaining choice
(p.m.) each woman rejects all but her top suitor
When each man is engaged, the algorithm terminates.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 4 / 20

7. The deferred-acceptance algorithm (Gale-Shapley)
description via a metaphor Day 0: each individual ranks the opposite sex
Day 1: (a.m.) each man proposes to his top choice
(p.m.) each woman rejects all but her top suitor
Dayn+ 1: (a.m.) each man rejected on daynproposes to his
top remaining choice
(p.m.) each woman rejects all but her top suitor
When each man is engaged, the algorithm terminates.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 4 / 20

8. An example
KenBev Cat Ada
LeoAda Cat Bev
MaxAda Bev Cat
AdaKen Leo Max
BevLeo Max Ken
CatMax Leo Ken
Day 1:
Leo & Max propose to Ada. Ken proposes to Bev.
Ada rejects Max. Ada & Leo and Bev & Ken are engaged.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 5 / 20

9. An example
KenBev Cat Ada
LeoAda Cat Bev
MaxAda Bev Cat
AdaKen Leo Max
BevLeo Max Ken
CatMax Leo Ken
Day 1:
Leo & Max propose to Ada. Ken proposes to Bev.
Ada rejects Max. Ada & Leo and Bev & Ken are engaged.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 5 / 20

10. An example
KenBevCat Ada
LeoAdaCat Bev
MaxAdaBev Cat
AdaKen Leo Max
BevLeo Max Ken
CatMax Leo Ken
Day 1:
Leo & Max propose to Ada. Ken proposes to Bev.
Ada rejects Max. Ada & Leo and Bev & Ken are engaged.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 5 / 20

11. An example
KenBevCat Ada
LeoAdaCat Bev
Max/////AdaBev Cat
AdaKen Leo /////Max
BevLeo Max Ken
CatMax Leo Ken
Day 1:
Leo & Max propose to Ada. Ken proposes to Bev.
Ada rejects Max. Ada & Leo and Bev & Ken are engaged.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 5 / 20

12. An example
KenBevCat Ada
LeoAdaCat Bev
Max/////AdaBevCat
AdaKen Leo Max
BevLeo Max Ken
CatMax Leo Ken
Day 2:
Max proposes to Bev.
Bev rejects Ken. Ada & Leo and Bev & Max are engaged.
Day 3:
Ken proposes to Cat.
It's a match: Ada & Leo, Bev & Max, Cat & Ken.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 6 / 20

13. An example
Ken////BevCat Ada
LeoAdaCat Bev
Max/////AdaBevCat
AdaKen Leo Max
BevLeo Max /////Ken
CatMax Leo Ken
Day 2:
Max proposes to Bev.
Bev rejects Ken. Ada & Leo and Bev & Max are engaged.
Day 3:
Ken proposes to Cat.
It's a match: Ada & Leo, Bev & Max, Cat & Ken.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 6 / 20

14. An example
Ken////BevCatAda
LeoAdaCat Bev
Max/////AdaBevCat
AdaKen Leo Max
BevLeo Max /////Ken
CatMax Leo Ken
Day 2:
Max proposes to Bev.
Bev rejects Ken. Ada & Leo and Bev & Max are engaged.
Day 3:
Ken proposes to Cat.
It's a match: Ada & Leo, Bev & Max, Cat & Ken.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 6 / 20

15. An example
Ken////BevCatAda
LeoAdaCat Bev
Max/////AdaBevCat
AdaKen Leo Max
BevLeo Max /////Ken
CatMax Leo Ken
Day 2:
Max proposes to Bev.
Bev rejects Ken. Ada & Leo and Bev & Max are engaged.
Day 3:
Ken proposes to Cat.
It's a match: Ada & Leo, Bev & Max, Cat & Ken.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 6 / 20

16. A solution to the stable marriage problem
Theorem
The deferred-acceptance algorithm arranges stable marriages.
Proof:
Each of the women that a given man prefers to his wife rejected him in
favor of a suitor she preferred.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 7 / 20

17. A solution to the stable marriage problem
Theorem
The deferred-acceptance algorithm arranges stable marriages.
Proof:
Each of the women that a given man prefers to his wife rejected him in
favor of a suitor she preferred.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 7 / 20

18. Heteronormativity
Heteronormativity is an essential feature of the algorithm: the \stable
roommates" problem might have no solution!
Example
Given oommate" preferences:
AdaBet - Dot
BetCat - Dot
CatAda - Dot
Dot- - -
then
whomever is paired with Dot would rather swap to be with the suitor who
ranks her rst.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 8 / 20

19. Heteronormativity
Heteronormativity is an essential feature of the algorithm: the \stable
roommates" problem might have no solution!
Example
Given oommate" preferences:
AdaBet - Dot
BetCat - Dot
CatAda - Dot
Dot- - -
then
whomever is paired with Dot would rather swap to be with the suitor who
ranks her rst.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 8 / 20

20. Comparing stable matchings
Say a man and a woman are
matching marries them.
Theorem (Gale-Shapley)
In the solution found by the deferred-acceptance algorithm,
gets his best possible match!
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 9 / 20

21. Comparing stable matchings
Say a man and a woman are
matching marries them.
Theorem (Gale-Shapley)
In the solution found by the deferred-acceptance algorithm,
gets his best possible match!
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 9 / 20

22. Comparing stable matchings
Theorem (Gale-Shapley)
Every man gets his best possible match.
Proof:
We show (by induction) that no man is rejected by a possible wife:
~w~m's preferencesw
bb
possible match
""
"b
"b
"b
"b
"b
~m w's preferences
OO
m
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 10 / 20

23. Comparing stable matchings
Theorem (Gale-Shapley)
Every man gets his best possible match.
Proof:
We show (by induction) that no man is rejected by a possible wife:
~w~m's preferencesw
oo
propose
/o/o/o/o

reject
""
"b
"b
"b
"b
"b
~m w's preferences
OO
m
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 10 / 20

24. Comparing stable matchings
Theorem (Gale-Shapley)
Every man gets his best possible match.
Proof:
We show (by induction) that no man is rejected by a possible wife:
~w
aa
possible match
!!
!a
!a
!a
!a
!a
~m's preferences
OO
w
bb
possible match
""
"b
"b
"b
"b
"b
~m w's preferences
OO
m
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 10 / 20

25. Comparing stable matchings
Theorem (Gale-Shapley)
Every man gets his best possible match.
Proof:
We show (by induction) that no man is rejected by a possible wife:
~w

reject
!!
!a
!a
!a
!a
!a
~m's preferences
OO
w
oo
propose

/o/o/o/o
~m w's preferences
OO
m
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 10 / 20

26. Partial order on stable matchings
DeneMto mean
Wto mean.
Theorem
Mis equivalent toW.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 11 / 20

27. Partial order on stable matchings
DeneMto mean
Wto mean.
Theorem
Mis equivalent toW.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 11 / 20

28. Better for men is worse for women
Theorem
Mis equivalent toW.
Proof:
SupposeM!but some womanwprefers.
~wm's preferencesw
oo

///o/o/o
__
!

_
_
_
_
m w 's preferences
OO
~m
Stability of!implies that!matchesmto some woman~whe prefers, but
thenM!.Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 12 / 20

29. Better for men is worse for women
Theorem
Mis equivalent toW.
Proof:
SupposeM!but some womanwprefers.
~w
__
!

_
_
_
_
_
m's preferences
OO
w
oo

///o/o/o
__
!

_
_
_
_
m w 's preferences
OO
~m
Stability of!implies that!matchesmto some woman~whe prefers, but
thenM!.Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 12 / 20

30. The complete lattice of stable matchings
Theorem (Conway)
The set of stable matchings for any xed dating pool is a complete lattice
with partial orderM.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 13 / 20

31. The complete lattice of stable matchings
Theorem (Conway)
The set of stable matchings for any xed dating pool is a complete lattice
with partial orderM.
Proof: construction of_!
Suppose everyone joins right hands with their-match and left hands with
their!-match (forming disjoint circles with men facing in and women
facing out).
If all drop hands and point at their preferred partner, in each circle,
everyone will point in the same direction (so that the men and women
have opposite preferences).
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 14 / 20

32. The complete lattice of stable matchings
Theorem (Conway)
The set of stable matchings for any xed dating pool is a complete lattice
with partial orderM.
Proof: construction of_!
Suppose everyone joins right hands with their-match and left hands with
their!-match (forming disjoint circles with men facing in and women
facing out).
If all drop hands and point at their preferred partner, in each circle,
everyone will point in the same direction (so that the men and women
have opposite preferences).
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 14 / 20

33. Sexism in the male-proposing algorithm
Corollary
In the stable matching found by the male-proposing algorithm, every
woman gets her worst possible match! Of course it's a dierent matter if the women propose... Upshot: waiting to receive proposals is a bad strategy.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 15 / 20

34. Sexism in the male-proposing algorithm
Corollary
In the stable matching found by the male-proposing algorithm, every
woman gets her worst possible match! Of course it's a dierent matter if the women propose... Upshot: waiting to receive proposals is a bad strategy.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 15 / 20

35. Can the women retaliate?
Yes! Strategy: truncate preference lists The women steal preference lists and compute their optimal matches.
Each woman truncates her preference list below her best match. Male proposals will be rejected until the result is women-optimal.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 16 / 20

36. Can the women retaliate?
Yes! Strategy: truncate preference lists The women steal preference lists and compute their optimal matches.
Each woman truncates her preference list below her best match. Male proposals will be rejected until the result is women-optimal.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 16 / 20

37. Can the women retaliate?
Yes! Strategy: truncate preference lists The women steal preference lists and compute their optimal matches.
Each woman truncates her preference list below her best match. Male proposals will be rejected until the result is women-optimal.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 16 / 20

38. Can the women retaliate?
Yes! Strategy: truncate preference lists The women steal preference lists and compute their optimal matches.
Each woman truncates her preference list below her best match. Male proposals will be rejected until the result is women-optimal.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 16 / 20

39. Men shouldn't lie.
Theorem (Dubins-Freedman)
No man or consortium of men can improve their results in the
male-proposing algorithm by submitting false preferences.
Real-world consequences
At least on one side, the deferred-acceptance algorithm is
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 17 / 20

40. Men shouldn't lie.
Theorem (Dubins-Freedman)
No man or consortium of men can improve their results in the
male-proposing algorithm by submitting false preferences.
Real-world consequences
At least on one side, the deferred-acceptance algorithm is
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 17 / 20

41. National Resident Matching Program: History
Prehistory
In the 1940s, hospitals competed for residents by making oers early
in medical school and demanding immediate responses.
General instability encouraged private negotiations between students
and hospitals.
The medical match
In 1952, after a few false starts, the National Intern Matching
Program (NRMP) found a stable solution:
... the deferred-acceptance algorithm!
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 18 / 20

42. National Resident Matching Program: History
Prehistory
In the 1940s, hospitals competed for residents by making oers early
in medical school and demanding immediate responses.
General instability encouraged private negotiations between students
and hospitals.
The medical match
In 1952, after a few false starts, the National Intern Matching
Program (NRMP) found a stable solution:
... the deferred-acceptance algorithm!
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 18 / 20

43. NRMP: Who proposes?
Failure to communicate (Gale-Sotomayor 1985)
\The question of course then arises as to whether these results can be
applied `in practice'. [Gale-Shapley '62] had expressed some reservations
on this point,|and then came another surprise. Not only could the
method be applied, it had been more than ten years earlier!"
But who proposes? Prior to the mid-1990s the hospitals acted as the proposers.
After a review by Roth et al., the students propose.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 19 / 20

44. NRMP: Who proposes?
Failure to communicate (Gale-Sotomayor 1985)
\The question of course then arises as to whether these results can be
applied `in practice'. [Gale-Shapley '62] had expressed some reservations
on this point,|and then came another surprise. Not only could the
method be applied, it had been more than ten years earlier!"
But who proposes? Prior to the mid-1990s the hospitals acted as the proposers.
After a review by Roth et al., the students propose.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 19 / 20

45. Real-world complications
A problem
Medical students are often married (in real life) to each other.
Solution: couples match
Couples rank pairs of preferences. Only one problem:
Theorem (Ronn)
The couples match is NP-complete.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 20 / 20

46. Real-world complications
A problem
Medical students are often married (in real life) to each other.
Solution: couples match
Couples rank pairs of preferences. Only one problem:
Theorem (Ronn)
The couples match is NP-complete.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 20 / 20

47. Real-world complications
A problem
Medical students are often married (in real life) to each other.
Solution: couples match
Couples rank pairs of preferences. Only one problem:
Theorem (Ronn)
The couples match is NP-complete.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 20 / 20

48. Real-world complications
A problem
Medical students are often married (in real life) to each other.
Solution: couples match
Couples rank pairs of preferences. Only one problem:
Theorem (Ronn)
The couples match is NP-complete.
Emily Riehl (Harvard University) A solution to the stable marriage problem 6 March 2013 20 / 20