Stable Matching and Gale-Shapley

The problem: you have two equal-sized groups — say, job candidates and firms, or residents and hospitals — and each side has ranked every member of the other side by preference. You want to pair everyone up one-to-one. A matching is unstable if some candidate and some firm, who aren't paired with each other, would both prefer to be paired with each other over their current assignments — that pair has an incentive to break the match and pair up privately. Can you always find a matching where no such pair exists?

The algorithm: deferred acceptance

Yes, and the Gale-Shapley algorithm constructs one directly. Run it in rounds: every unmatched candidate on the proposing side proposes to their most-preferred firm they haven't already proposed to. Each firm, if it receives one or more proposals, tentatively holds onto its favorite among the proposals it's received so far (including any it's already holding from a previous round) and rejects the rest. Rejected candidates cross that firm off their list and propose to their next choice in the following round. Repeat until every candidate is held by some firm. This always terminates with a stable matching, because no candidate ever proposes to the same firm twice, so the process can't loop forever, and a careful induction shows the final pairing has no unstable pair.

Worked example: three candidates, three firms

Candidates 1, 2, 3 rank firms; firms rank candidates:

Candidate	Preference (best to worst)
1	A, B, C
2	B, A, C
3	A, B, C

Firm	Preference (best to worst)
A	2, 1, 3
B	1, 2, 3
C	1, 2, 3

Round 1: Candidate 1 proposes to A (top choice). Candidate 2 proposes to B. Candidate 3 proposes to A. Firm A has two proposals (1 and 3); A prefers 2 over 1 over 3, but only 1 and 3 proposed — A prefers 1 over 3, so A holds 1 and rejects 3. Firm B has one proposal (2), holds it.

Round 2: Candidate 3, rejected by A, proposes to their next choice, B. Firm B now has proposals from 2 (held) and 3 (new); B prefers 1 over 2 over 3, and between its actual proposers 2 and 3, B prefers 2 — B keeps holding 2, rejects 3.

Round 3: Candidate 3, rejected by B, proposes to their last choice, C. Firm C has one proposal (3), holds it.

No one is unmatched and no candidate has firms left to propose to, so the algorithm ends: 1–A, 2–B, 3–C. Check for instability: does any pair prefer each other over their current match? Candidate 1 got their top choice, so no complaint there. Candidate 2 got their top choice too. Candidate 3 got their bottom choice — but 3 would need a firm that prefers 3 over its current match to form an unstable pair, and both A and B already hold candidates (1 and 2) they prefer over 3. So the matching is stable.

What this means in practice

Gale-Shapley runs real-world systems: US medical residency matching, some school-choice and course-allocation systems, and any two-sided marketplace pairing problem where you want no side-deals to be tempting. It's also the standard model for thinking about why the proposing side tends to do at least as well as possible under any stable matching, while the side being proposed to does no better than its worst stable outcome — a well-known asymmetry: whoever proposes has a structural advantage, which is why which side "proposes" in a real matching system is a genuine design choice, not a detail.