# CS代考程序代写 algorithm COMP3927: Algorithm Design

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

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

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

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

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

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

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