Stable Matching with Gale–Shapley, Explained

After reading this you can pair two ranked groups so that no couple would rather abandon their assignments for each other, run the algorithm by hand on small cases, and see exactly which side the method favors.

What a stable matching is

You have two groups of equal size. Each person on one side ranks everyone on the other side, best first. A matching pairs each person with exactly one partner from the other group. The matching is stable when no two people who are not paired together would both prefer each other over their current partners.

That pair, if it existed, is called a blocking pair. Suppose Adam is matched to Xena but he prefers Yara, and Yara is matched to Carl but she prefers Adam. Then Adam and Yara would both walk away and pair up. A stable matching has no such pair. Nobody can honestly complain that a partner they preferred also preferred them back.

The Gale–Shapley algorithm, published in 1962, always finds such a matching. It never gets stuck, it never loops, and it finishes in a predictable number of steps. That combination of guarantees is rare, which is why the same procedure runs medical residency matches for tens of thousands of doctors every year.

When to use it, and when not to

Reach for stable matching when both sides have genuine preferences over each other and you want a result nobody can undermine by side deals. Mentors and mentees, applicants and departments, students and project slots: all fit.

Do not use it when only one side has preferences. If rooms do not care who sleeps in them, you are not matching two ranked groups; you are assigning, and a simpler cost minimization is the right model. Also skip it when partners can hold more than one match at once with quotas larger than one, unless you extend the algorithm to the hospitals-residents variant. The plain version here assumes one partner each.

The algorithm and why it works

One side proposes, the other reviews. The procedure runs in rounds:

1. Every unmatched proposer proposes to the highest-ranked reviewer who has not yet rejected them.
2. Each reviewer who receives proposals keeps the one they rank highest (tentatively) and rejects the rest.
3. Rejected proposers move down their list and propose again next round.
4. Stop when no proposer is unmatched. The tentative pairings become final.

The key fact: a reviewer's tentative partner only ever improves. Once Yara holds a proposal from Ben, she will only trade up to someone she ranks higher, never down. Proposers, by contrast, only ever move down their own lists. Those two monotone directions are what make the process finish.

Here R is the number of proposals made across the whole run and n is the size of each group. Each proposer can propose to at most n reviewers, and at least one proposer stays fixed, so with n = 3 you get at most 3^2 - 3 + 1 = 7 proposals. Small instances resolve in a handful of rounds.

Worked example with three proposers

Reading both directions

Because the proposing side is favored, the tool also runs the algorithm with the roles flipped, letting the reviewers propose. On this instance the reviewer-proposing run produces Xena-Ben, Yara-Carl, Zoe-Adam, which gives every reviewer her 1st choice and every proposer his best too. Both sides get their top pick in that direction.

So this instance has (at least) two different stable matchings. When the two runs disagree, you are looking at a real trade-off: one side's best stable outcome is the other side's worst. When the two runs agree, the stable matching is unique and no argument about which side proposes can change it.

Explore the bias yourself

Common mistakes

The errors below cause wrong or misleading results more often than any subtlety of the algorithm itself.

Incomplete lists

Every proposer must rank every reviewer and vice versa. If Adam lists only Yara and Xena, and both reject him, the algorithm has nowhere to send him. Rank the whole other side.

Confusing stable with optimal total happiness

Adding up ranks and picking the lowest sum can produce a matching that is not stable. Stability is a per-pair guarantee, not a sum. In the demo, the proposer run scores 1+1+1+3+3+3 = 12 and the reviewer run scores the same 12, yet both are stable and neither is chosen for its total.

Assuming the result is unique

If you only run one direction, you never learn there was a second stable matching favoring the other side. Always compare both.

Unequal group sizes

The plain algorithm needs the two sides to be the same size. If you have 6 mentees and 4 mentors, add dummy partners or use a quota-based variant before matching.

Related tools

Matching pairs two ranked groups. Two neighboring problems on this site look similar but need different methods. If you are building a weekly roster around who is unavailable rather than who prefers whom, use the Shift Rota Builder. If your problem is ordering stops rather than pairing people, the Errand Route Optimizer finds the shortest tour, exact for up to 12 stops.

Related tools

Errand Route Optimizer

Best order for your stops — exact for up to 12, smart beyond.

Shift Rota Builder

A fair weekly rota around everyone’s unavailable days.

Round-Robin Schedule Generator

Everyone plays everyone: fixtures by the circle method, byes included.

Seating Chart Optimizer

Assign guests to tables around keep-together and keep-apart rules.

Secret Santa Generator

Draw gift-exchange pairs with exclusions, no self-draws guaranteed.

Voting Methods Lab

Drag candidates on an opinion map and watch plurality, runoff, Borda and Condorcet crown different winners.