COMP3927: Algorithm Design
Lecture 1: Stable Matching
William Umboh
School of Computer Science
The University of Sydney
1
Three abstractions
Problem statement:
– defines a computational task
– specifies what the input is and what the output should be
Algorithm:
– a step-by-step recipe to go from input to output – different from implementation
Correctness and complexity analysis:
– a formal proof that the algorithm solves the problem
– analytical bound on the resources (e.g., time and space) it uses
University of Sydney
!2
A bit of history
Residence program established in the early 20th century in US to assign residents to hospitals
Basic problem:
– Student accepts an offer and then receives an offer from a better hospital – Hospital is turned down late in the season cannot find good students
Question:
– Is there an assignment process that is self-reinforcing?
Still applicable today:
– Assigning job applicants to companies, students to universities, etc.
University of Sydney
!3
Abstract model
Let {m1,m2,…,mn} be a set of n men,and
{w1,w2,…,wn} be a set of n women
Each man has an individual ranking of the women and vice-versa
University of Sydney
!4
Abstract model
Let {m1,m2,…,mn} be a set of n men,and
{w1,w2,…,wn} be a set of n women
Each man has an individual ranking of the women and vice-versa
m1 w1 w3 w2 m2 w1 w2 w3 m3 w3 w2 w1
University of Sydney
!4
Abstract model
Let {m1,m2,…,mn} be a set of n men,and
{w1,w2,…,wn} be a set of n women
Each man has an individual ranking of the women and vice-versa
m1 w1 w3 w2 m2 w1 w2 w3 m3 w3 w2 w1
w1 m3 m2 m1 w2 m1 m2 m3 w3 m3 m2 m1
University of Sydney
!4
Abstract model
Let {m1,m2,…,mn} be a set of n men,and
{w1,w2,…,wn} be a set of n women
Each man has an individual ranking of the women and vice-versa
m1 w1 w3 w2 m2 w1 w2 w3 m3 w3 w2 w1
w3 ≻m3 w2
w1 m3 m2 m1 w2 m1 m2 m3 w3 m3 m2 m1
University of Sydney
!4
Abstract model
Let {m1,m2,…,mn} be a set of n men,and
{w1,w2,…,wn} be a set of n women
Each man has an individual ranking of the women and vice-versa
m1 w1 w3 w2 m2 w1 w2 w3 m3 w3 w2 w1
w1 m3 m2 m1 w2 m1 m2 m3 w3 m3 m2 m1
University of Sydney
!4
Matchings
Def.:A matching M is a one-to-one correspondence between a subset of the men and the women
Def.:A matching M is perfect if nobody is unassigned
m1 w1 m1 w1 m2 w2 m2 w2 m3 w3 m3 w3
m1 m2 m3
w1 w2 w3
not a matching
matching
perfect matching
University of Sydney
!5
Matchings
Def.:A matching M is a one-to-one correspondence between a subset of the men and the women
Def.:A matching M is perfect if nobody is unassigned
m1 w1 m1 w1 m2 w2 m2 w2 m3 w3 m3 w3
m1 m2 m3
w1 w2 w3
not a matching
matching
perfect
w2 = M(m3)
matching
University of Sydney
!5
Matchings
Def.:A matching M is a one-to-one correspondence between a subset of the men and the women
Def.:A matching M is perfect if nobody is unassigned
m1 w1 m1 w1 m2 w2 m2 w2 m3 w3 m3 w3
m1 m2 m3
w1 w2 w3
not a matching
matching
perfect matching
University of Sydney
!5
Stable matching
University of Sydney
!6
Stable matching
Def.:A perfect matching M is stable if there is no (m,w) such that m and w prefer each other over their matched partners
-mismatchedtow’=M(m)andw≻m w’ -wismatchedtom’=M(w)andm≻w m’
University of Sydney
!6
Stable matching
Def.:A perfect matching M is stable if there is no (m,w) such that m and w prefer each other over their matched partners
-mismatchedtow’=M(m)andw≻m w’ -wismatchedtom’=M(w)andm≻w m’
If it existed, we say that (m, w) blocks M and is a blocking pair
University of Sydney
!6
Stable matching
Def.:A perfect matching M is stable if there is no (m,w) such that m and w prefer each other over their matched partners
-mismatchedtow’=M(m)andw≻m w’ -wismatchedtom’=M(w)andm≻w m’
If it existed, we say that (m, w) blocks M and is a blocking pair
Def.: Given a set of men and women with their individual rankings, the
stable matching (SM) problem is to find a stable matching, if one exists
University of Sydney
!6
Stable matching: examples
University of Sydney
!7
Stable matching: examples
m1 w1 w2 w3 m2 w2 w3 w1 m3 w3 w2 w1
w1 m1 m2 m3 w2 m2 m3 m1 w3 m3 m1 m2
University of Sydney
!7
Stable matching: examples
m1 w1 w2 w3 m2 w2 w3 w1 m3 w3 w2 w1
w1 m1 m2 m3 w2 m2 m3 m1 w3 m3 m1 m2
University of Sydney
!7
Stable matching: examples
m1 w1 w2 w3 m2 w2 w3 w1 m3 w3 w2 w1
w1 m1 m2 m3 w2 m2 m3 m1 w3 m3 m1 m2
Stable because everyone got matched to their first choice
University of Sydney
!7
Stable matching: examples
m1w1w2w3 m2w2w3w1 m3w3w2w1
w1m1m2m3 w2m2m3m1 w3m3m1m2
Stable because everyone got matched to their first choice
m1w1w2w3 m2w2w3w1 m3w3w2w1
w1m3m2m1 w2m1m3m2 w3m2m1m3
University of Sydney
!7
Stable matching: examples
m1w1w2w3 m2w2w3w1 m3w3w2w1
w1m1m2m3 w2m2m3m1 w3m3m1m2
Stable because everyone got matched to their first choice
m1w1w2w3 m2w2w3w1 m3w3w2w1
w1m3m2m1 w2m1m3m2 w3m2m1m3
University of Sydney
!7
Stable matching: examples
m1w1w2w3 m2w2w3w1 m3w3w2w1
w1m1m2m3 w2m2m3m1 w3m3m1m2
Stable because everyone got matched to their first choice
m1w1w2w3 m2w2w3w1 m3w3w2w1
w1m3m2m1 w2m1m3m2 w3m2m1m3
Stable because every man got matched to their first choice
University of Sydney
!7
Back to hospitals and residents
University of Sydney
!8
Back to hospitals and residents
Assuming each hospital has one position, this (almost) captures the student-hospital problem from before
University of Sydney
!8
Back to hospitals and residents
Assuming each hospital has one position, this (almost) captures the student-hospital problem from before
In 1952, a centralized system (NRMP) was established
– Hospitals and students submitted their preferences to NRMP
– NRMP suggested a global matching
-95% participation in its first year even though participation was voluntary and there was no mechanism in place to enforce NRMP’s matching
University of Sydney
!8
Back to hospitals and residents
Assuming each hospital has one position, this (almost) captures the student-hospital problem from before
In 1952, a centralized system (NRMP) was established
– Hospitals and students submitted their preferences to NRMP
– NRMP suggested a global matching
-95% participation in its first year even though participation was voluntary and there was no mechanism in place to enforce NRMP’s matching
It turns out that NRMP produced stable matchings! However, the algorithm was not published until 1962, when it was re-discovered by Gale and Shapley.
University of Sydney
!8
Gale-Shapley algorithm
Thm.: Every SM instance admits at least one stable matching
University of Sydney
!9
Gale-Shapley algorithm
Thm.: Every SM instance admits at least one stable matching
Gale-Shapley(P)
University of Sydney
!9
Gale-Shapley algorithm
Thm.: Every SM instance admits at least one stable matching
Gale-Shapley(P)
M ← empty matching
University of Sydney
!9
Gale-Shapley algorithm
Thm.: Every SM instance admits at least one stable matching
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
University of Sydney
!9
Gale-Shapley algorithm
Thm.: Every SM instance admits at least one stable matching
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
University of Sydney
!9
Gale-Shapley algorithm
Thm.: Every SM instance admits at least one stable matching
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman that m has not proposed yet
University of Sydney
!9
Gale-Shapley algorithm
Thm.: Every SM instance admits at least one stable matching
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman that m has not proposed yet if w is free
University of Sydney
!9
Gale-Shapley algorithm
Thm.: Every SM instance admits at least one stable matching
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman that m has not proposed yet if w is free
add (m,w) to M
University of Sydney
!9
Gale-Shapley algorithm
Thm.: Every SM instance admits at least one stable matching
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman that m has not proposed yet if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
University of Sydney
!9
Gale-Shapley algorithm
Thm.: Every SM instance admits at least one stable matching
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman that m has not proposed yet if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
University of Sydney
!9
Gale-Shapley algorithm
Thm.: Every SM instance admits at least one stable matching
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman that m has not proposed yet if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
University of Sydney
!9
Gale-Shapley algorithm
Thm.: Every SM instance admits at least one stable matching
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman that m has not proposed yet if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M return M
University of Sydney
!9
Gale-Shapley algorithm
Thm.: Every SM instance admits at least one stable matching
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
We must show that such
woman always exists
m ← some free man
w ← most desired woman that m has not proposed yet if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M return M
University of Sydney
!9
Gale-Shapley algorithm
Thm.: Every SM instance admits at least one stable matching
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
We must show that such
woman always exists
m ← some free man
w ← most desired woman that m has not proposed yet
if w is free
add (m,w) to M
We say m and w
are engaged
if w is not free, but prefers m to m’=M(w) remove (m’,w) from M
add (m,w) to M
return M University of Sydney
!9
Gale-Shapley algorithm
Thm.: Every SM instance admits at least one stable matching
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
We must show that such
woman always exists
m ← some free man
w ← most desired woman that m has not proposed yet
if w is free
add (m,w) to M
We say m and w
are engaged
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M We say m’ and w break
return M their engagement University of Sydney
!9
Example
Matching:
Free men:
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
University of Sydney
!10
Example
Matching: {}
Free men:
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
University of Sydney
!10
Example
Matching: {}
Free men: {m1,m2,m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching: {}
Free men: {m1,m2,m3 }
☞
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
University of Sydney
!10
Example
Matching: {}
Free men: {m1,m2,m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
Free men: {m1,m2,m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
{ (m1, w1) }
Free men: {m1,m2,m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
{ (m1, w1) }
Free men:
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
University of Sydney
!10
Example
Matching:
{ (m1, w1) }
Free men:
{ m2, m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
{ (m1, w1) }
Free men:
{ m2, m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
☞
University of Sydney
!10
Example
Matching:
{ (m1, w1) }
Free men:
{ m2, m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
Free men:
{ m2, m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
{ (m2, w1) }
Free men:
{ m2, m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
{ (m2, w1) }
Free men:
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
University of Sydney
!10
Example
Matching:
{ (m2, w1) }
Free men:
{ m1, m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
{ (m2, w1) }
Free men:
{ m1, m3 }
☞
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
University of Sydney
!10
Example
Matching:
{ (m2, w1) }
Free men:
{ m1, m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
Free men:
{ m1, m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
{ (m2, w1), (m1, w3) }
Free men:
{ m1, m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
{ (m2, w1), (m1, w3) }
Free men:
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
University of Sydney
!10
Example
Matching:
{ (m2, w1), (m1, w3) }
Free men:
{ m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
{ (m2, w1), (m1, w3) }
Free men:
{ m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
☞
University of Sydney
!10
Example
Matching:
{ (m2, w1), (m1, w3) }
Free men:
{ m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
☞
University of Sydney
!10
Example
Matching:
{ (m2, w1), (m1, w3) }
Free men:
{ m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
Free men:
{ m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
{ (m2, w1), (m3, w3) }
Free men:
{ m3 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
{ (m2, w1), (m3, w3) }
Free men:
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
University of Sydney
!10
Example
Matching:
{ (m2, w1), (m3, w3) }
Free men:
{ m1 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
{ (m2, w1), (m3, w3) }
Free men:
{ m1 }
☞
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
University of Sydney
!10
Example
Matching:
{ (m2, w1), (m3, w3) }
Free men:
{ m1 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
Free men:
{ m1 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
{ (m2, w1), (m3, w3), (m1, w2) }
Free men:
{ m1 }
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Example
Matching:
{ (m2, w1), (m3, w3), (m1, w2) }
Free men:
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
University of Sydney
!10
Example
Matching:
{ (m2, w1), (m3, w3), (m1, w2) }
Free men:
{}
m1 w1 w3 w2 m2 w1 w2 w3 m3 w1 w3 w2
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w1 m2 m3 m1 w2 m2 m1 m3 w3 m3 m2 m1
University of Sydney
!10
Analysis of GS algorithm
University of Sydney
!11
Analysis of GS algorithm
Prop.: Once a woman becomes engaged, she is never free again, and
the quality of her partner can only increase with time
University of Sydney
!11
Analysis of GS algorithm
Prop.: Once a woman becomes engaged, she is never free again, and
the quality of her partner can only increase with time Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
University of Sydney
!11
Analysis of GS algorithm
Prop.: Once a woman becomes engaged, she is never free again, and
the quality of her partner can only increase with time Gale-Shapley(P)
w ⋯ m ⋯ m’ ⋯
M ← empty matching whilethereisafreemaninM
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
University of Sydney
!11
Analysis of GS algorithm
Prop.: Once a woman becomes engaged, she is never free again, and
the quality of her partner can only increase with time Gale-Shapley(P)
w ⋯ m ⋯ m’ ⋯
M ← empty matching whilethereisafreemaninM
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
University of Sydney
!11
Analysis of GS algorithm
Prop.: Once a woman becomes engaged, she is never free again, and
the quality of her partner can only increase with time Gale-Shapley(P)
w ⋯ m ⋯ m’ ⋯
M ← empty matching whilethereisafreemaninM
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
University of Sydney
!11
Analysis of GS algorithm
Prop.: Once a woman becomes engaged, she is never free again, and
the quality of her partner can only increase with time Gale-Shapley(P)
w ⋯ m ⋯ m’ ⋯
M ← empty matching whilethereisafreemaninM
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
University of Sydney
!11
Analysis of GS algorithm
Prop.: Once a woman becomes engaged, she is never free again, and
the quality of her partner can only increase with time
Prop.: Quality of a man’s partner can only decrease with time
Gale-Shapley(P)
M ← empty matching whilethereisafreemaninM
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w ⋯ m ⋯ m’ ⋯
University of Sydney
!11
Analysis of GS algorithm
Prop.: Once a woman becomes engaged, she is never free again, and
the quality of her partner can only increase with time
Prop.: Quality of a man’s partner can only decrease with time
Gale-Shapley(P)
M ← empty matching whilethereisafreemaninM
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w ⋯ m ⋯ m’ ⋯
University of Sydney
!11
Analysis of GS algorithm
Prop.: Once a woman becomes engaged, she is never free again, and
the quality of her partner can only increase with time
Prop.: Quality of a man’s partner can only decrease with time
Gale-Shapley(P)
M ← empty matching whilethereisafreemaninM
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w ⋯ m ⋯ m’ ⋯
University of Sydney
!11
Analysis of GS algorithm
Prop.: Once a woman becomes engaged, she is never free again, and
the quality of her partner can only increase with time
Prop.: Quality of a man’s partner can only decrease with time
Gale-Shapley(P)
M ← empty matching whilethereisafreemaninM
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w ⋯ m ⋯ m’ ⋯
University of Sydney
!11
Analysis of GS algorithm
Prop.: Once a woman becomes engaged, she is never free again, and
the quality of her partner can only increase with time
Prop.: Quality of a man’s partner can only decrease with time
Gale-Shapley(P)
M ← empty matching whilethereisafreemaninM
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
w ⋯ m ⋯ m’ ⋯
Prop.: GS algo always terminates and returns a perfect matching
University of Sydney
!11
Analysis of GS algorithm
Prop.:The GS algorithm runs for at most n2 iterations
Each iteration, a man proposes to a woman he has never proposed to
Each man has n women in his list and there are n men, so there are n2 entries in total.Thus at most n2 iterations
University of Sydney
!12
Analysis of GS algorithm
Prop.: The GS algorithm returns a stable matching
University of Sydney
!13
Analysis of GS algorithm
Prop.: The GS algorithm returns a stable matching
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
University of Sydney
!13
Analysis of GS algorithm
Prop.: The GS algorithm returns a stable matching
Suppose GS returns a perfect matching M and that
(m, w) blocks M :
– m prefers w to w’ = M(m) – w prefers m to m’ = M(w)
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
University of Sydney
!13
Analysis of GS algorithm
Prop.: The GS algorithm returns a stable matching
Suppose GS returns a perfect matching M and that
(m, w) blocks M :
– m prefers w to w’ = M(m) – w prefers m to m’ = M(w)
m ⋯ w ⋯ w’ ⋯
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
University of Sydney
!13
Analysis of GS algorithm
Prop.: The GS algorithm returns a stable matching
Suppose GS returns a perfect matching M and that
(m, w) blocks M :
– m prefers w to w’ = M(m) – w prefers m to m’ = M(w)
m ⋯ w ⋯ w’ ⋯ w ⋯ m ⋯ m’ ⋯
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
University of Sydney
!13
Analysis of GS algorithm
Prop.: The GS algorithm returns a stable matching
Suppose GS returns a perfect matching M and that
(m, w) blocks M :
– m prefers w to w’ = M(m) – w prefers m to m’ = M(w)
m ⋯ w ⋯ w’ ⋯ w ⋯ m ⋯ m’ ⋯
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
University of Sydney
!13
Analysis of GS algorithm
Prop.: The GS algorithm returns a stable matching
Suppose GS returns a perfect matching M and that
(m, w) blocks M :
– m prefers w to w’ = M(m) – w prefers m to m’ = M(w)
m ⋯ w ⋯ w’ ⋯ w ⋯ m ⋯ m’ ⋯
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
University of Sydney
!13
Analysis of GS algorithm
Prop.: The GS algorithm returns a stable matching
Suppose GS returns a perfect matching M and that
(m, w) blocks M :
– m prefers w to w’ = M(m) – w prefers m to m’ = M(w)
m ⋯ w ⋯ w’ ⋯ w ⋯ m ⋯ m’ ⋯
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
University of Sydney
!13
Analysis of GS algorithm
Prop.: The GS algorithm returns a stable matching
Suppose GS returns a perfect matching M and that
(m, w) blocks M :
– m prefers w to w’ = M(m) – w prefers m to m’ = M(w)
m ⋯ w ⋯ w’ ⋯ w ⋯ m ⋯ m’ ⋯
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
University of Sydney
!13
Analysis of GS algorithm
Prop.: The GS algorithm returns a stable matching
Suppose GS returns a perfect matching M and that
(m, w) blocks M :
– m prefers w to w’ = M(m) – w prefers m to m’ = M(w)
m ⋯ w ⋯ w’ ⋯ w ⋯ m ⋯ m’ ⋯
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
University of Sydney
!13
Analysis of GS algorithm
Prop.: The GS algorithm returns a stable matching
Suppose GS returns a perfect matching M and that
(m, w) blocks M :
– m prefers w to w’ = M(m) – w prefers m to m’ = M(w)
m ⋯ w ⋯ w’ ⋯ w ⋯ m ⋯ m’ ⋯
Contradiction!
Gale-Shapley(P)
M ← empty matching
while there is a free man in M
m ← some free man
w ← most desired woman by m not yet proposed if w is free
add (m,w) to M
if w is not free, but prefers m to m’=M(w)
remove (m’,w) from M
add (m,w) to M
return M
University of Sydney
!13
Properties of GS
Thm.: The GS algorithm produces a stable matching where each man
gets his best “stable partner” and each woman gets her worst “stable partner”
University of Sydney
!14
Properties of GS
Thm.: The GS algorithm produces a stable matching where each man
gets his best “stable partner” and each woman gets her worst “stable partner”
Example
University of Sydney
!14
Properties of GS
Thm.: The GS algorithm produces a stable matching where each man
gets his best “stable partner” and each woman gets her worst “stable partner”
Example
University of Sydney
!14
Properties of GS
Thm.: The GS algorithm produces a stable matching where each man
gets his best “stable partner” and each woman gets her worst “stable partner”
Example
m1 w1 w2 w3 m2 w2 w3 w1 m3 w3 w2 w1
University of Sydney
!14
Properties of GS
Thm.: The GS algorithm produces a stable matching where each man
gets his best “stable partner” and each woman gets her worst “stable partner”
Example
m1 w1 w2 w3 m2 w2 w3 w1 m3 w3 w2 w1
w1 m3 m2 m1 w2 m1 m3 m2 w3 m2 m1 m3
University of Sydney
!14
Properties of GS
Thm.: The GS algorithm produces a stable matching where each man
gets his best “stable partner” and each woman gets her worst “stable partner”
Example
m1 w1 w2 w3 m2 w2 w3 w1 m3 w3 w2 w1
w1 m3 m2 m1 w2 m1 m3 m2 w3 m2 m1 m3
University of Sydney
!14
Properties of GS
Thm.: The GS algorithm produces a stable matching where each man
gets his best “stable partner” and each woman gets her worst “stable partner”
Example
m1 w1 w2 w3 m2 w2 w3 w1 m3 w3 w2 w1
w1 m3 m2 m1 w2 m1 m3 m2 w3 m2 m1 m3
University of Sydney
!14
Properties of GS
Thm.: The GS algorithm produces a stable matching where each man
gets his best “stable partner” and each woman gets her worst “stable partner”
Example
m1 w1 w2 w3 m2 w2 w3 w1 m3 w3 w2 w1
w1 m3 m2 m1 w2 m1 m3 m2 w3 m2 m1 m3
University of Sydney
!14
Beyond the basic setup
Preference are typically not complete
Hospital usually have several positions
Preferences are usually not strict
Applicants are not necessarily independent
Can people cheat by misrepresenting their true preferences?
Shapley won the 2011 Nobel prize in Economics for his work on Stable Matchings
University of Sydney
!15