CSE 421 Section 1

Stable Matching

Administrivia & Introductions

Homework

• Submissions
• LaTeX (highly encouraged)
• overleaf.com
• template and LaTeX guide posted on course website!
• Word Editor that supports mathematical equations
• Handwritten (not preferred, but fine as long as clear)
• All homeworks will be turned in via Gradescope
• Homeworks due on Thursdays at 11.59pm

​

• You get 6 late days for the quarter, and can use a maximum of 3 on any HW

​

​

​

Announcements & Reminders

• Section Materials
• Handouts will be provided in at each section
• Worksheets and sample solutions will be available on the class website later this evening

​

• HW1
• Due Thursday 10/2 at 11.59pm

​

Stable Matching

Stable Matching

Gale-Shapley Algorithm

Algorithm to find a stable matching:

​

Initially all 𝑟 in 𝑅 and ℎ in 𝐻 are free

while there is a free 𝑟

Let ℎ be highest on 𝑟’s list that 𝑟 has not proposed to

if ℎ is free

match (𝑟,ℎ)

else //ℎ is not free

Let 𝑟′ be the current match of ℎ

if ℎ prefers 𝑟 to 𝑟′

unmatch (𝑟′,ℎ)

match (𝑟,ℎ)

​

​

Problem 1 – Gale-Shapley

1. Run the Gale-Shapley Algorithm with riders proposing on the instance above. When choosing which free rider to propose next, always choose the one with the smallest index (e.g., if r₁ and r₂ are both free, always choose r₁).

Consider the following stable matching instance:

​

r₁: h₃, h₁, h₂, h₄

r₂: h₂, h₁, h₄, h₃

r₃: h₂, h₃, h₁, h₄

r₄: h₃, h₄, h₁, h₂

​

h₁: r₄, r₁, r₃, r₂

h₂: r₁, r₃, r₂, r₄

h₃: r₁, r₃, r₄, r₂

h₄: r₃, r₁, r₂, r₄

Problem 1 – Gale-Shapley

1. Run the Gale-Shapley Algorithm with riders proposing on the instance above. When choosing which free rider to propose next, always choose the one with the smallest index (e.g., if r₁ and r₂ are both free, always choose r₁).

r₁ chooses h₃ (r₁, h₃)

​

r₁: h₃, h₁, h₂, h₄

r₂: h₂, h₁, h₄, h₃

r₃: h₂, h₃, h₁, h₄

r₄: h₃, h₄, h₁, h₂

​

h₁: r₄, r₁, r₃, r₂

h₂: r₁, r₃, r₂, r₄

h₃: r₁, r₃, r₄, r₂

h₄: r₃, r₁, r₂, r₄

Problem 1 – Gale-Shapley

1. Run the Gale-Shapley Algorithm with riders proposing on the instance above. When choosing which free rider to propose next, always choose the one with the smallest index (e.g., if r₁ and r₂ are both free, always choose r₁).

r₁ chooses h₃ (r₁, h₃)

​

r₂ chooses h₂ (r₁, h₃), (r₂, h₂)

r₁: h₃, h₁, h₂, h₄

r₂: h₂, h₁, h₄, h₃

r₃: h₂, h₃, h₁, h₄

r₄: h₃, h₄, h₁, h₂

​

h₁: r₄, r₁, r₃, r₂

h₂: r₁, r₃, r₂, r₄

h₃: r₁, r₃, r₄, r₂

h₄: r₃, r₁, r₂, r₄

Problem 1 – Gale-Shapley

1. Run the Gale-Shapley Algorithm with riders proposing on the instance above. When choosing which free rider to propose next, always choose the one with the smallest index (e.g., if r₁ and r₂ are both free, always choose r₁).

r₁ chooses h₃ (r₁, h₃)

r₂ chooses h₂ (r₁, h₃), (r₂, h₂)

​

r₃ chooses h₂ (r₁, h₃), (r₂, h₂), (r₃, h₂)

r₁: h₃, h₁, h₂, h₄

r₂: h₂, h₁, h₄, h₃

r₃: h₂, h₃, h₁, h₄

r₄: h₃, h₄, h₁, h₂

​

h₁: r₄, r₁, r₃, r₂

h₂: r₁, r₃, r₂, r₄

h₃: r₁, r₃, r₄, r₂

h₄: r₃, r₁, r₂, r₄

Problem 1 – Gale-Shapley

1. Run the Gale-Shapley Algorithm with riders proposing on the instance above. When choosing which free rider to propose next, always choose the one with the smallest index (e.g., if r₁ and r₂ are both free, always choose r₁).

r₁ chooses h₃ (r₁, h₃)

r₂ chooses h₂ (r₁, h₃), (r₂, h₂)

​

r₃ chooses h₂ (r₁, h₃), (r₂, h₂), (r₃, h₂)

r₁: h₃, h₁, h₂, h₄

r₂: h₂, h₁, h₄, h₃

r₃: h₂, h₃, h₁, h₄

r₄: h₃, h₄, h₁, h₂

​

h₁: r₄, r₁, r₃, r₂

h₂: r₁, r₃, r₂, r₄

h₃: r₁, r₃, r₄, r₂

h₄: r₃, r₁, r₂, r₄

Problem 1 – Gale-Shapley

1. Run the Gale-Shapley Algorithm with riders proposing on the instance above. When choosing which free rider to propose next, always choose the one with the smallest index (e.g., if r₁ and r₂ are both free, always choose r₁).

r₁ chooses h₃ (r₁, h₃)

r₂ chooses h₂ (r₁, h₃), (r₂, h₂)

r₃ chooses h₂ (r₁, h₃), (r₂, h₂), (r₃, h₂)

​

r₂ chooses h₁ (r₁, h₃), (r₂, h₁), (r₃, h₂)

r₁: h₃, h₁, h₂, h₄

r₂: h₂, h₁, h₄, h₃

r₃: h₂, h₃, h₁, h₄

r₄: h₃, h₄, h₁, h₂

​

h₁: r₄, r₁, r₃, r₂

h₂: r₁, r₃, r₂, r₄

h₃: r₁, r₃, r₄, r₂

h₄: r₃, r₁, r₂, r₄

Problem 1 – Gale-Shapley

1. Run the Gale-Shapley Algorithm with riders proposing on the instance above. When choosing which free rider to propose next, always choose the one with the smallest index (e.g., if r₁ and r₂ are both free, always choose r₁).

r₁ chooses h₃ (r₁, h₃)

r₂ chooses h₂ (r₁, h₃), (r₂, h₂)

r₃ chooses h₂ (r₁, h₃), (r₂, h₂), (r₃, h₂)

r₂ chooses h₁ (r₁, h₃), (r₂, h₁), (r₃, h₂)

​

r₄ chooses h₃ (r₁, h₃), (r₂, h₁), (r₃, h₂), (r₄, h₃)

r₁: h₃, h₁, h₂, h₄

r₂: h₂, h₁, h₄, h₃

r₃: h₂, h₃, h₁, h₄

r₄: h₃, h₄, h₁, h₂

​

h₁: r₄, r₁, r₃, r₂

h₂: r₁, r₃, r₂, r₄

h₃: r₁, r₃, r₄, r₂

h₄: r₃, r₁, r₂, r₄

Problem 1 – Gale-Shapley

1. Run the Gale-Shapley Algorithm with riders proposing on the instance above. When choosing which free rider to propose next, always choose the one with the smallest index (e.g., if r₁ and r₂ are both free, always choose r₁).

r₁ chooses h₃ (r₁, h₃)

r₂ chooses h₂ (r₁, h₃), (r₂, h₂)

r₃ chooses h₂ (r₁, h₃), (r₂, h₂), (r₃, h₂)

r₂ chooses h₁ (r₁, h₃), (r₂, h₁), (r₃, h₂)

​

r₄ chooses h₃ (r₁, h₃), (r₂, h₁), (r₃, h₂), (r₄, h₃)

r₁: h₃, h₁, h₂, h₄

r₂: h₂, h₁, h₄, h₃

r₃: h₂, h₃, h₁, h₄

r₄: h₃, h₄, h₁, h₂

​

h₁: r₄, r₁, r₃, r₂

h₂: r₁, r₃, r₂, r₄

h₃: r₁, r₃, r₄, r₂

h₄: r₃, r₁, r₂, r₄

Problem 1 – Gale-Shapley

1. Run the Gale-Shapley Algorithm with riders proposing on the instance above. When choosing which free rider to propose next, always choose the one with the smallest index (e.g., if r₁ and r₂ are both free, always choose r₁).

r₁ chooses h₃ (r₁, h₃)

r₂ chooses h₂ (r₁, h₃), (r₂, h₂)

r₃ chooses h₂ (r₁, h₃), (r₂, h₂), (r₃, h₂)

r₂ chooses h₁ (r₁, h₃), (r₂, h₁), (r₃, h₂)

r₄ chooses h₃ (r₁, h₃), (r₂, h₁), (r₃, h₂), (r₄, h₃)

​

r₄ chooses h₄ (r₁, h₃), (r₂, h₁), (r₃, h₂), (r₄, h₄)

r₁: h₃, h₁, h₂, h₄

r₂: h₂, h₁, h₄, h₃

r₃: h₂, h₃, h₁, h₄

r₄: h₃, h₄, h₁, h₂

​

h₁: r₄, r₁, r₃, r₂

h₂: r₁, r₃, r₂, r₄

h₃: r₁, r₃, r₄, r₂

h₄: r₃, r₁, r₂, r₄

Problem 1 – Gale-Shapley

1. Run the Gale-Shapley Algorithm with riders proposing on the instance above. When choosing which free rider to propose next, always choose the one with the smallest index (e.g., if r₁ and r₂ are both free, always choose r₁).

r₁ chooses h₃ (r₁, h₃)

r₂ chooses h₂ (r₁, h₃), (r₂, h₂)

r₃ chooses h₂ (r₁, h₃), (r₂, h₂), (r₃, h₂)

r₂ chooses h₁ (r₁, h₃), (r₂, h₁), (r₃, h₂)

r₄ chooses h₃ (r₁, h₃), (r₂, h₁), (r₃, h₂), (r₄, h₃)

r₄ chooses h₄ (r₁, h₃), (r₂, h₁), (r₃, h₂), (r₄, h₄)

(r₁, h₃), (r₂, h₁), (r₃, h₂), (r₄, h₄)

r₁: h₃, h₁, h₂, h₄

r₂: h₂, h₁, h₄, h₃

r₃: h₂, h₃, h₁, h₄

r₄: h₃, h₄, h₁, h₂

​

h₁: r₄, r₁, r₃, r₂

h₂: r₁, r₃, r₂, r₄

h₃: r₁, r₃, r₄, r₂

h₄: r₃, r₁, r₂, r₄

Problem 1 – Gale-Shapley

2. Run the Gale-Shapley Algorithm with riders proposing on the same instance. But now, when choosing which free rider to propose next, always choose the one with the largest index. Do you get the same result?

3. Now run the algorithm with horses proposing, breaking ties by taking the free horse with the smallest index. Do you get the same result?

r₁: h₃, h₁, h₂, h₄

r₂: h₂, h₁, h₄, h₃

r₃: h₂, h₃, h₁, h₄

r₄: h₃, h₄, h₁, h₂

​

h₁: r₄, r₁, r₃, r₂

h₂: r₁, r₃, r₂, r₄

h₃: r₁, r₃, r₄, r₂

h₄: r₃, r₁, r₂, r₄

Work on parts b and c of this problem with the people around you, and then we’ll go over it together!

Problem 1 – Gale-Shapley

2. Run the Gale-Shapley Algorithm with riders proposing on the same instance. But now, when choosing which free rider to propose next, always choose the one with the largest index. Do you get the same result?

r₁: h₃, h₁, h₂, h₄

r₂: h₂, h₁, h₄, h₃

r₃: h₂, h₃, h₁, h₄

r₄: h₃, h₄, h₁, h₂

​

h₁: r₄, r₁, r₃, r₂

h₂: r₁, r₃, r₂, r₄

h₃: r₁, r₃, r₄, r₂

h₄: r₃, r₁, r₂, r₄

Problem 1 – Gale-Shapley

2. Run the Gale-Shapley Algorithm with riders proposing on the same instance. But now, when choosing which free rider to propose next, always choose the one with the largest index. Do you get the same result?

r₁: h₃, h₁, h₂, h₄

r₂: h₂, h₁, h₄, h₃

r₃: h₂, h₃, h₁, h₄

r₄: h₃, h₄, h₁, h₂

​

h₁: r₄, r₁, r₃, r₂

h₂: r₁, r₃, r₂, r₄

h₃: r₁, r₃, r₄, r₂

h₄: r₃, r₁, r₂, r₄

The steps of the Gale-Shapley Algorithm with the rider with highest index proposing first:

​

r₄ chooses h₃ (r₄, h₃)

r₃ chooses h₂ (r₃, h₂),(r₄, h₃)

r₂ chooses h₂ (r₃, h₂),(r₄, h₃)

r₂ chooses h₁ (r₂, h₁),(r₃, h₂),(r₄, h₃)

r₁ chooses h₃ (r₁, h₃),(r₂, h₁),(r₃, h₂)

r₄ chooses h₄ (r₁, h₃),(r₂, h₁),(r₃, h₂),(r₄, h₄)

​

We ended up with the same result!

Problem 1 – Gale-Shapley

3. Now run the algorithm with horses proposing, breaking ties by taking the free horse with the smallest index. Do you get the same result?

r₁: h₃, h₁, h₂, h₄

r₂: h₂, h₁, h₄, h₃

r₃: h₂, h₃, h₁, h₄

r₄: h₃, h₄, h₁, h₂

​

h₁: r₄, r₁, r₃, r₂

h₂: r₁, r₃, r₂, r₄

h₃: r₁, r₃, r₄, r₂

h₄: r₃, r₁, r₂, r₄

Problem 1 – Gale-Shapley

3. Now run the algorithm with horses proposing, breaking ties by taking the free horse with the smallest index. Do you get the same result?

r₁: h₃, h₁, h₂, h₄

r₂: h₂, h₁, h₄, h₃

r₃: h₂, h₃, h₁, h₄

r₄: h₃, h₄, h₁, h₂

​

h₁: r₄, r₁, r₃, r₂

h₂: r₁, r₃, r₂, r₄

h₃: r₁, r₃, r₄, r₂

h₄: r₃, r₁, r₂, r₄

The steps of the Gale-Shapley Algorithm with horses proposing:

​

h₁ chooses r₄ (r₄, h₁)

h₂ chooses r₁ (r₁, h₂),(r₄, h₁)

h₃ chooses r₁ (r₁, h₃),(r₄, h₁)

h₂ chooses r₃ (r₁, h₃),(r₃, h₂),(r₄, h₁)

h₄ chooses r₃ (r₁, h₃),(r₃, h₂),(r₄, h₁)

h₄ chooses r₁ (r₁, h₃),(r₃, h₂),(r₄, h₁)

h₄ chooses r₂ (r₁, h₃),(r₂, h₄),(r₃, h₂),(r₄, h₁)

​

No, the result is different when we have the horses propose as opposed to the riders.

Induction

Induction

• You will be writing lots of induction proofs in this class in order to prove that your algorithms are correct.

​

• The style requirements for proofs in this class are less stringent than the style requirements from 311
• there is a style guide doc on the course website (here) about how 421 proofs are different than what you did in 311

Induction Template

Problem 3 – Induction Review

Problem 3 – Induction Review

Work on this problem with the people around you, and then we’ll go over it together!

Problem 3 – Induction Review

Problem 3 – Induction Review

KEY Induction Concept

Problem 3 – Induction Review

Work on this problem with the people around you, and then we’ll go over it together!

Problem 3 – Induction Review

2. Prove the claim by induction.

Problem 3 – Induction Review

2. Prove the claim by induction.

That’s All, Folks!

Thanks for coming to section this week!

Any questions?