Gale-Shapley, Proved and Traced

Gale-Shapley, Proved and Traced

Five lines of pseudocode can pair two sides so that no couple would ever defect — and you can prove it. This film takes Gale-Shapley deferred acceptance all the way down: the algorithm built line-group by line-group, the three correctness proofs in plain language with every step genuinely valid (termination in at most n-squared proposals, everyone matched, no blocking pair), the proposer-optimality theorem stated honestly, and one complete trace — every proposal, both broken engagements, the rejection — read back through the proof that predicted it.

Chapters: 0:00 Two questions one algorithm must answer 0:29 Part One — The Algorithm 1:41 Part Two — Correctness 3:08 Part Three — A Full Trace 4:28 Verdict 4:45 Your turn 5:03 Outro

YOUR TURN — paste this into Claude:

Run Gale-Shapley on these tables twice — first with students proposing, then with schools proposing. Trace every proposal in both runs, compare the two final matchings, and name the theorem that predicted exactly who got happier.

Students' preferences: S1: C1 then C2 S2: C2 then C1

Schools' preferences: C1: S2 then S1 C2: S1 then S2

(Both runs produce a stable matching. They are not the same matching. That difference is the point.)

Every factual claim in this video was checked against primary sources before rendering.

youtube.com/@NikBearBrown

▶ The full series playlist — Brutalist https://www.youtube.com/playlist?list=PLG9H-C6rp5RU

What this video covers

• 0:00 — Two questions one algorithm must answer
• 0:29 — Part One — The Algorithm
• 1:41 — Part Two — Correctness
• 3:08 — Part Three — A Full Trace
• 4:28 — Verdict
• 4:45 — Your turn
• 5:03 — Outro

Transcript

A lightly formatted transcript of the video, with timestamps so you can jump to any section on YouTube.

Two questions one algorithm must answer

[0:00] Mulvaney, this is Liam in for Bear. Ask for matching algorithm and you get five lines of pseudo code. Ask whether those five lines can ever strand two people who would both rather leave their partners. That takes a proof. This is Gale-Shapley all the way down, the code, the correctness, and one complete run. Here is the whole plan typed slowly. One algorithm, three questions. What do the five lines actually say? Why is the result guaranteed, not observed, guaranteed? And what does one complete run look like decision by decision?

Part One — The Algorithm

[0:29] Part one, the algorithm. The setup, two sides of equal size. Every student ranks every school, every school ranks every student, no ties. The job is not just to pair everyone, it is to pair them so the pairing holds. First, the one definition everything hangs on. A matching pairs everyone. It is stable when no student and school both prefer each other to what they got. Such a pair is called blocking, and a single blocking pair is fatal because those two would simply leave and the whole assignment unravels. Here is the engine, two lines at a time. While any student is free, he proposes to the next school on his list. Next, never the same school

Twice, never a school he skipped. His pointer only moves down. Hold on to that word, down. The school side is three cases and only three. If she is free, they engage. If she prefers the newcomer to her current match, she trades up and her old partner goes back to the free pool. Otherwise, she rejects and the proposer moves on. Notice what she never does. She never trades down. And that is the whole license, two directions, both one way. Proposers walk down finite lists and never back up. Receivers only ever trade upward. Engagements are deferred, not final. Nothing is a promise until everything stops. Every proof in part two is just these two arrows cashed in.

Part Two — Correctness

[1:41] Part two, correctness. Three claims to earn in order. The loop stops. When it stops, everyone is matched and the matching it leaves has no blocking pair. Each proof is short, plain-spoken, and genuinely valid. No hand-waving dressed up as rigor. Claim one, it stops. Every pass through the loop, some student proposes and burns one entry of his preference list forever because pointers never back up. N students and entries each N squared entries in the whole system. The loop cannot run longer than that. Termination proved by counting. Claim two, nobody is left out. Suppose some student ends free, then he proposed to all N schools and struck out everywhere, but watch the receivers. Once a school gets any proposal at all, she's engaged from that moment on. She trades partners. She never returns to free. So, all N schools end engaged, which takes N students.

He cannot be free. Contradiction. Claim three, the one the algorithm exists for. Suppose the final matching hides a blocking pair. Student S prefers school C to his own match. His pointer only moves down, so on the way to worse school he must have proposed to C. She turned him away then or dropped him later. Either way, only for someone she ranked higher, and she never traded down afterward. So, her final partner beats S on her list. She does not prefer S. The pair was never blocking. One more theorem, stated honestly rather than proved. The full case analysis lives in the text. Among all stable matchings, the proposing side gets the best partners it can ever have, and the receiving side gets the worst. Same algorithm, same stability guarantee, but who proposes is not a detail. It decides who the outcome favors. Part three, one

Part Three — A Full Trace

[3:09] Complete run, nothing skipped. Three students, three schools, full preference tables on screen the whole way. Watch exactly two things. Student pointers moving down and school choices trading up. The instance S1 and S2 both want C1 first, a collision. S3 wants C2. On the other side, C1 ranks S2 highest and C2 ranks S1 highest. So, somebody's first engagement is not going to survive. The pseudo code rides along on the right, and the active line lights up as each decision fires. Proposal one, S1 to C1. She is free. The engaged line fires. They pair. Proposal two, S2 to C1. She already holds S1, so stop. Her list reads S2 above S1. Before it resolves, commit, keep, or trade,

She trades up. S1 is back in the pool, and his pointer has already moved past C1 forever. Proposal three, S3 to C2 free, engaged. Proposal four, S1 out of the pool tries a second choice, C2. Her list ranks S1 above S3, so she trades up to. S3 is freed. And look at the board, both one-way directions live. S1 slid down his list, C2 climbed hers. Proposal five, S3 freed tries C1. She holds S2, her favorite, rejected flat. The else branch finally on screen. Proposal six, S3 moves down to his last entry, C3 free, engaged. No student is free. The loop exits after six proposals, comfortably under the nine that claim one guaranteed. Now read the result back

Verdict

[4:29] Through claim three. The tempting pair is S1 and C1. He genuinely prefers her to his match, but she holds S2, whom she ranks higher, which is exactly what the stability proof said must be true wherever a preference points elsewhere. Check every pair, nothing blocks, not luck. The invariant cashed in. The

Your turn

[4:45] Verdict, five lines of pseudo code. Students propose down their lists, schools trade up theirs. It stops within n squared proposals by counting. It matches everyone a proposed to school never frees again. It leaves no blocking pair. Every refusal was for someone ranked higher. And it favors whichever side does the proposing. Proved, not promised. Your turn. Open a Claude

Outro

[5:04] Session and paste this. Run Gale-Shapley on the two-by-two tables in the description, first with students proposing, then with schools proposing. Trace every proposal in both runs, compare the two final matchings, and name the theorem from this film that predicted exactly who got happier. The full prompt tables included is in the description. Gale-Shapley proved and traced, now you know. Lay 'em in for bare.