💞

Every year thousands of new doctors are matched to hospitals by an algorithm, not a market. It has to produce assignments that no doctor and hospital would both rather undo. Gale and Shapley showed such a matching always exists, and how to find it.

Stable matching

Match two sides with preferences, medical residents to hospitals, students to schools, and you want stability: no pair who would both prefer each other to their assigned partners. Deferred acceptance always reaches a stable matching, and it quietly favours whichever side does the proposing.

From earlier lessons

Two quick ones before we start.

A matching is unstable if there is a pair who both prefer...

An algorithm is strategy-proof if no one gains by...

Predict, then play

Three men and three women, with cyclic preferences designed to make the sides clash. Run deferred acceptance, then swap which side proposes.

Why did that happen?

Take a guess, then reveal the reason

Proposers get to try their top choice first and only move down when rejected, so they end up as high on their own list as stability allows. Receivers can only accept or reject what comes to them, so they end up as low as stability allows. The result is stable either way: no pair wants to defect. But the two runs produce different stable matchings, one best for each side, which is why the question of who proposes is a real design choice, not a technicality.

The math

Definition, deferred acceptance and stability

A matching is stable if no unmatched pair prefer each other to their assigned partners (no blocking pair). In deferred acceptance, each member of the proposing side proposes down its list; each receiver tentatively holds its best proposer so far and rejects the rest; rejected proposers try their next choice. The process ends with a stable matching, and it is proposer-optimal: every proposer gets the best partner it could have in any stable matching, and every receiver the worst.

In the cyclic instance, man-proposing round 1 has $m_1 \to w_1$ , $m_2 \to w_2$ , $m_3 \to w_3$ , and every woman receives exactly one proposal, so all are held and the algorithm stops. Each man gets his first choice; each woman ( $w_1$ ranks $m_2 > m_3 > m_1$ , and so on) gets her last. Checking stability: every man already has his top choice, so no man would leave, and therefore no blocking pair exists. Woman-proposing produces the mirror image, best for the women.

Work it out

Run it, then check for blocking pairs

Man-proposing: in round 1 each man proposes to his first choice, $m_1 \to w_1$ , $m_2 \to w_2$ , $m_3 \to w_3$ . No woman gets two proposals, so each holds hers and the algorithm ends immediately. Every man has his first choice; every woman her last.

Now hunt for a blocking pair. Take $w_1$ , who got $m_1$ (her least favourite) and would prefer $m_2$ . But $m_2$ has $w_2$ , his first choice, and prefers her to $w_1$ . So $(m_2, w_1)$ is not a blocking pair. The same holds everywhere: every man has his top choice and will not stray. No blocking pair exists, so the matching is stable, even though every woman is matched to her worst option.

Key idea

Deferred acceptance always yields a stable matching, and it is best for the proposing side and worst for the receiving side. Stability does not pin down a unique matching, so who proposes is a genuine design decision.

Check yourself

Check yourselfapply

Under man-proposing deferred acceptance in this game, what do the women get?

Check yourselfanalyse

Both man-proposing and woman-proposing give stable matchings, and they differ. What does that tell you?

Check yourselfbrings back: dominant strategy

For the proposing side, deferred acceptance is strategy-proof. What does that mean here?

Sources

Gale, D., and Shapley, L. S. (1962). College admissions and the stability of marriage. American Mathematical Monthly, 69(1), 9-15.