Stable Matching: Who Pairs With Whom?

What’s going on

Four blues and four ambers have to pair up, one blue with one amber. Everyone has ranked the people in the other group, from favourite to least favourite. In the scene, each ranking sits next to its owner, favourite first, nearest the name.

Not every pairing will hold. Look at the one in the scene when it opens: Cy is paired with Ned and Leo with Ada, yet Cy and Leo are each other’s first choice. Both would happily leave their partners for each other. Such a pair is called a blocking pair, and the scene draws it as a red dashed line.

A pairing with no blocking pair is called stable. Nobody can find someone who would also rather switch, so nothing breaks apart. Try making one by hand: click a blue, then an amber, to pair them. With four people on each side there are 24 possible pairings, and finding a stable one by trial and error is surprisingly fiddly.

The algorithm

In 1962 David Gale and Lloyd Shapley described a simple procedure that always finds a stable pairing. Press Run Gale–Shapley:

1. A blue who is not paired proposes to the favourite amber they have not asked yet.
2. An amber who gets a proposal compares it with the offer they are holding, if any. They keep the better one for now and turn the other down.
3. Repeat until everyone is paired.

Ambers can trade up: Leo first holds Ada’s offer, then drops her when Cy, Leo’s favourite, proposes. A blue who is turned down simply moves to the next name on their list.

The result is always stable. Suppose blue X and amber Y would both rather be together. X ended up with someone X likes less than Y, so X must have proposed to Y earlier. Y either refused X or dropped X later, and both happen only for someone Y likes more. Ambers only ever trade up, so Y ends with someone better than X. So Y does not want X after all.

Who proposes matters

Switch Who proposes to Ambers and run it again. With these rankings the result changes: every amber now gets their first choice, while Ada and Dot drop from their third and second choices to their last.

This is no accident. The proposing side always gets the best partner it could have in any stable pairing, and the side that waits gets the worst. The rules look fair, but the side that asks has the advantage.

This problem is traditionally called the stable marriage problem, because Gale and Shapley described it with brides and grooms. Today the same procedure pairs students with schools and young doctors with hospitals.

Try it yourself

1. Everyone agrees

All four blues rank the ambers in the same order: Kim, Leo, Mia, Ned. All four ambers rank the blues the same way: Ada, Ben, Cy, Dot. How many stable pairings are there?

Answer

Exactly one: Ada–Kim, Ben–Leo, Cy–Mia, Dot–Ned. Ada and Kim are everybody's favourites, so if they were not together, they would form a blocking pair. With them paired, the same argument applies to Ben and Leo among the rest, and so on.

2. One group only

Now there is a single group of four sharing two-person rooms. A likes B best, then C. B likes C best, then A. C likes A best, then B. Everyone likes D least. Is there a stable way to make two pairs?

Answer

No. Whoever shares with D wants out. If A is with D, then C (with B) prefers A, and A prefers C to D. If B is with D, then A prefers B, and B prefers A to D. If C is with D, then B prefers C, and C prefers B to D. Every pairing has a blocking pair. With two separate groups this can never happen, and that is what the Gale–Shapley argument proves.

3. Why does it stop?

Could the proposals go on forever? Find a limit on how many there can be with n people on each side.

Answer

Nobody proposes to the same person twice, because each blue works down their own list. So there are at most n × n proposals, and in fact at most n × n − n + 1. Also, once an amber has an offer, they hold one for the rest of the run, so nobody can be left out at the end.

Go deeper

• In 2012 Lloyd Shapley and Alvin Roth received the Nobel Memorial Prize in Economic Sciences for the theory of stable matching and its use in practice. David Gale had died in 2008.
• Roth helped redesign the systems that place young doctors in American hospitals and pupils in New York City high schools, both based on proposals of this kind.