Who asks matters

Pair off two equal groups, where everyone has ranked everyone on the other side. There is always a way to do it that nobody can break by running off together, and a simple ritual finds it. But the ritual has a direction: the side that does the asking gets the better end.

What "stable" means

Lehman, Leighton and Meyer tell it as marriages between n men and n women; below we use letters and numbers. A matching pairs each person with exactly one person on the other side. A rogue couple is two people who are not paired with each other but who each prefer the other to their own partner. They have every reason to walk out together. A matching is stable when it has no rogue couple at all.

That a stable matching always exists is not obvious, and it is not free. In the book's "buddy" version, where anyone may pair with anyone, some sets of preferences have no stable pairing whatsoever.

Why it matters

Real clearinghouses run on this. The book names the National Resident Matching Program, which places medical graduates in hospital residencies. Gale and Shapley published the ritual in 1962, but the NRMP had been running a similar algorithm about ten years earlier, unknown to them. Akamai uses a variant to send web requests to its servers, an online dating agency uses it, and Shapley was awarded the 2012 Nobel prize in economics for this and related work.

The ritual

Every man starts with his full ranked list of the women. Then each day has three parts. In the morning, every man goes to the woman at the top of his list and serenades her. In the afternoon, each woman with suitors tells her favourite to stay and tells the rest to go. In the evening, every rejected man crosses that woman off his list for good. The first morning on which no woman has more than one suitor is the last: each woman marries the one she has.

Why it works

It stops. A day that does not end the ritual has some woman with two or more suitors, so at least one name gets crossed off. The lists hold n² names in total and none is ever added back, so there are at most n² days.

Nobody is left over. The book's key fact is an invariant, a statement that stays true every day: if a woman is crossed off a man's list, she has a suitor she likes better than him. That holds because a woman never gives up her current favourite unless someone better arrives. Now suppose a man ends single. Then his list is empty, so every woman rejected him, so every woman has a suitor, so every woman is married. With equal numbers, that leaves no room for him.

No rogue couple. Take any man and woman who did not marry each other. If she is crossed off his list, the invariant says she has someone she prefers. If she is still on it, he worked down his list from the top and married someone he ranks higher. Either way, one of them would refuse.

Who the ritual favours

The women look powerful: they do all the rejecting, and their best suitor can only improve day by day. The book proves the opposite. Call someone a feasible partner of yours if some stable matching pairs you. The ritual gives every man his best feasible wife, and gives every woman her least-preferred feasible husband.

Stable matchings are often not unique, and the book notes that reversing the roles often yields a different one. Same preferences, different stable answer, and the proposing side does better in each. In the figure, flip who asks: nobody on the asking side ever does worse for having asked. Since both runs end in a stable matching, when the lists allow only one, both directions must reach it.

In short

A stable matching leaves no two people who would both rather have each other. The proposal ritual always finds one within n² days, and its invariant is the proof. Among all the stable answers, it hands the asking side its best and the answering side its worst.