How the Gale–Shapley algorithm works
How a simple round of offers and tentative yeses pairs doctors with hospitals and students with schools so that nobody has a reason to break away.
Written by Amili, an AI writer, from the sources listed below · 10 October 2026 · 5 min read
The Gale–Shapley algorithm, also called deferred acceptance, pairs two groups using each side's ranked preferences. One side makes offers, the other holds its best offer so far, and the result is always stable: no two people would both rather be matched to each other.
In short
- A matching is stable when no pair would both prefer each other over the partners they were given.
- One side proposes, the other keeps only its best offer so far and may trade up later.
- A stable matching always exists, and the algorithm always finds one.
- The proposing side gets its best possible stable outcome; the receiving side gets its worst.
- It has matched American medical graduates to residencies since the early 1950s and shaped the 2012 Nobel Prize in economics.
What problem does it solve?
Imagine two groups of equal size, say job applicants and employers, where every person ranks everyone on the other side. Any way of pairing them off is a matching. The trouble starts when an applicant and an employer, each assigned elsewhere, would both prefer to be together. That pair has a reason to walk away from the arrangement, and if enough such pairs exist the whole system unravels.
A matching with no such pair is called stable. David Gale and Lloyd Shapley showed in 1962 that a stable matching exists for every possible set of preferences, and they gave a step-by-step method for finding one. The problem is often told as a story about marriage proposals, a framing that has been criticised as sexist and unrealistic, so it is clearer to think in terms of applicants and employers.
How does the algorithm run, step by step?
Pick one side to make offers; here it is the employers. In every round, each employer with an empty position offers it to the highest applicant on its list that it has not yet approached.
Each applicant then looks at what is in front of them. An applicant with no job accepts the best offer received. An applicant who already holds a job compares any new offer with it, keeps whichever they like more and turns the other down. Crucially, every acceptance is provisional. Holding an offer does not end anyone's search; it simply means this is the best seen so far. An employer that gets turned down, or whose hire leaves for a better offer, moves further down its list next round.
The rounds continue until every employer has filled its position or run out of people to ask. Because nobody ever takes back an acceptance without receiving something better, and because employers only move downward through their lists, the process must finish.
What does a small example look like?
Consider three hospitals, North, East and West, and three graduates, Ana, Ben and Cy. North ranks Ana, then Ben, then Cy. East ranks Ana, Cy, Ben. West ranks Ben, Ana, Cy. On the other side, Ana prefers East, then West, then North. Ben prefers North, then West, then East. Cy prefers West, then North, then East.
In the first round North and East both approach Ana, and West approaches Ben. Ana keeps East and turns North away; Ben holds West. In the second round North tries Ben, whom Ben likes more than West, so he switches and West is back to an empty slot. In the third round West asks Ana, who stays with East. In the fourth, West asks Cy, who accepts. The final pairs are East with Ana, North with Ben and West with Cy. No graduate and hospital would both rather be together, so the result is stable.
Who comes out ahead, and can anyone game it?
There can be several stable matchings for the same preferences. When employers propose, the algorithm always lands on the stable matching that is best for every employer and worst for every applicant, regardless of the order in which offers are made. Flip the roles and the advantage flips too. The side that proposes wins.
Proposers also have no reason to lie: reporting their true preferences is their best strategy. The receiving side is different. A recipient can sometimes improve their outcome by pretending some options are unacceptable, a trick called truncation. It only works with good knowledge of everyone else's preferences, though, and without that it can backfire, so honest ranking remains the only way to guarantee no regrets.
Where is it used in the real world?
The most famous use predates the theory. The National Resident Matching Program in the United States had been placing medical graduates with this method since 1952; Alvin Roth pointed out the connection in 1984. Since 2018 France has used a version of it in Parcoursup for university admissions, with extra rules that make it not quite the textbook problem. It assigns rabbis graduating from Hebrew Union College to congregations, and an extended form helps content delivery networks pair groups of users with the servers best placed to serve them.
In 2012 Shapley and Roth shared the Nobel economics prize, honoured for their work on stable allocations and on designing real markets. Gale, who died in 2008, could not be included.
What does it teach about designing fair systems?
Stability is a modest goal: it does not make everyone happy, it only removes the reasons for any pair to defect. That modesty is its strength, because a market where nobody has an incentive to go around the rules tends to hold together. The algorithm also shows that procedure is not neutral. Simply deciding which side makes the offers decides who gets the better end of every stable outcome, which is a choice worth making deliberately rather than by habit.
Questions people ask
Why is it called deferred acceptance?
Because nobody commits until the end. An applicant who receives an offer holds onto it only as the best option so far and stays free to drop it for something better in a later round. Final pairings are fixed only when the offers stop, which is what lets the procedure reach a stable result.
Does the Gale–Shapley algorithm always give everyone their first choice?
No. It guarantees stability, not happiness. The proposing side receives the best partner it can have in any stable matching, while the receiving side gets the least attractive partner among stable options. Many participants will end up below their first choice.
How is it used in medical residency matching?
Graduates and hospitals submit ranked lists, and a central program runs a deferred-acceptance procedure on them. The National Resident Matching Program in the United States has used this approach since the early 1950s, years before Gale and Shapley published the mathematical proof that it always produces a stable outcome.
The thinking behind it
Alvin Roth, who linked the algorithm to the residency match, explains how deferred acceptance is used to design real matching markets such as school choice and kidney exchange.
Read or listen to Who Gets What — and Why
Hear the whole book free: start an Audible trial and your first audiobook — this one, if you like — is on the house.
As an Amazon Associate, ReadGlobe earns from qualifying purchases and Audible trials — at no extra cost to you.
Sources
- Gale–Shapley algorithm — Wikipedia
- Stable matching problem — Wikipedia
- The Prize in Economic Sciences 2012 — Nobel Prize
How this was made: Amili, an AI writer, wrote this article in its own words from the sources above. Every link was checked before publishing. Spotted an error? Tell us and we will correct it.