Stable Matching

Gale–Shapley, worked both directions

Three ideas, before anything else

  • stable matching
  • deferred acceptance
  • proposer-optimal

Get these three straight now — the worked example runs on all three.

Stable matching

Six people pair off. It doesn’t have to make anyone thrilled — it just has to survive contact with temptation: no one currently paired should be able to find someone else who’d also rather be with them than their own current match.

That no-mutual-regret property is stability, and a matching that has it is a stable matching.

Deferred acceptance

When someone asks you out and you’re not sure, “yes, for now” is a reasonable answer — you’re free to trade up later if someone better asks, and whoever you’re currently seeing finds out by being the one who gets let go.

That’s exactly how this week’s algorithm works, and it has a name: deferred acceptance — every “yes” is provisional until nobody better shows up.

Proposer-optimal

Here’s the twist: whichever side does the asking, as a group, ends up with the best partner they could possibly get in any stable arrangement. Asking isn’t just brave — it’s structurally an advantage.

Economists call that result proposer-optimality, and it’s the sharpest claim this week’s theorem makes.

The preferences

Asker1st choice2nd choice3rd choice
RobinJordanCaseyMorgan
SamCaseyJordanMorgan
DrewJordanCaseyMorgan
Match1st choice2nd choice3rd choice
JordanSamRobinDrew
CaseyRobinSamDrew
MorganRobinSamDrew

Run 1: Askers propose

RoundProposalsWhat happens
1Robin→Jordan, Sam→Casey, Drew→JordanJordan prefers Robin to Drew — holds Robin, rejects Drew. Casey holds Sam.
2Drew→Casey (his next choice)Casey prefers Sam to Drew — keeps Sam, rejects Drew.
3Drew→Morgan (his last choice)Morgan’s only offer — holds Drew.

Result: Robin–Jordan, Sam–Casey, Drew–Morgan. Robin and Sam both got their first choice.

Run 2: Matches propose instead

Same six people, same preferences — just flip who does the asking.

RoundProposalsWhat happens
1Jordan→Sam, Casey→Robin, Morgan→RobinRobin prefers Casey to Morgan — holds Casey, rejects Morgan. Sam holds Jordan.
2Morgan→Sam (her next choice)Sam prefers Jordan to Morgan — keeps Jordan, rejects Morgan.
3Morgan→Drew (her last choice)Drew’s only offer — holds Morgan.

Result: Robin–Casey, Sam–Jordan, Drew–Morgan.

Same people, same preferences, different outcome

PersonAskers proposeMatches propose
RobinJordan (1st choice)Casey (2nd choice)
SamCasey (1st choice)Jordan (2nd choice)
JordanRobin (2nd choice)Sam (1st choice)
CaseySam (2nd choice)Robin (1st choice)
Drew / Morganmatched to each other, either waymatched to each other, either way

Both matchings are genuinely stable. Whoever proposes does better, as a group, than whoever receives — every single time.

Stable does not mean happy. It means nobody has an incentive to break the arrangement, given what everyone else is doing — and it means the side that asked got the better half of that arrangement.

What the theorem doesn’t say

  • nothing about proposer-optimal vs. receiver-optimal outcomes being equal
  • nothing about the surplus once matched — that’s week 9
  • nothing about what happens when preferences change after matching

What today doesn’t settle

The theorem proves the proposing side does better, but says nothing about how a real market decides who plays that role. Week 7 couldn’t explain who breaks a standoff; this week, whoever a market simply labels the proposer wins the same way, unearned.

Week 12 is where this, and every prior week’s gap, come back at once.

Congratulations

You found a stable match. Now decide who does the dishes.

Week 9: Household Bargaining