PRIVATE ONE-ON-ONE TUITION · ONLINE WORLDWIDE

Matching Markets and the Gale–Shapley Algorithm, with Five Mistakes to Avoid from a San Diego Microeconomics Tutor

Microeconomics · Macroeconomics · Econometrics & Finance

Some markets have no prices to clear them. Junior doctors cannot bid for residency slots, and schools cannot auction their places, so something else has to decide who goes where. If you are taking intermediate micro or market design at UC San Diego, San Diego State or the University of San Diego, this Gale–Shapley lesson from a San Diego microeconomics tutor works through one small market from start to finish. It is organised around the five mistakes that cost the most marks, and each one is corrected with the argument a grader wants to see.

One market, twenty-four ways to fill it

Four junior doctors, A, B, C and D, apply to four hospitals, W, X, Y and Z. Each hospital has one slot. Everyone ranks everyone on the other side, most preferred first.

Doctor Ranking of hospitals Hospital Ranking of doctors
A Y, X, W, Z W A, B, D, C
B Y, X, W, Z X C, A, D, B
C W, Z, X, Y Y D, B, C, A
D X, W, Z, Y Z B, C, D, A

A matching pairs each doctor with one hospital. There are 4 × 3 × 2 × 1 = 24 of them. A doctor and a hospital form a blocking pair if each prefers the other to the partner the matching gave them. A matching is stable if it has no blocking pair. With partial lists you would also need individual rationality, nobody matched to someone they find unacceptable, but here every option is acceptable.

Stability matters because a blocking pair has every reason to break the match and make a side deal. A clearinghouse whose outcomes invite side deals tends to unravel. Check all 24 matchings in this market and exactly three are stable:

  • A–X, B–Y, C–Z, D–W
  • A–X, B–W, C–Z, D–Y
  • A–W, B–Z, C–X, D–Y

Mistake 1: reading “stable” as “everyone got a top choice”

A and B both rank Y first. Only one of them can have it, so no matching, stable or not, gives every doctor a first choice. Stability is a much weaker promise. It says nobody can find a willing partner they prefer, not that anybody is happy.

Nor is there one stable matching that is best for everyone. Each of the three is Pareto efficient: any matching that made someone better off would hand that person and their new partner a reason to block. But they rank differently for the two sides, and moving between them helps one side only by hurting the other. (The converse fails: a Pareto efficient matching need not be stable.) If you need the welfare vocabulary, Pareto efficiency and the welfare theorems set it out.

Mistake 2: accepting offers on the spot

Gale and Shapley’s 1962 paper in the American Mathematical Monthly gave a procedure that always finds a stable matching. Its key word is deferred. Here it is with doctors proposing.

  1. Every unmatched doctor applies to the best hospital that has not yet rejected them.
  2. Each hospital looks at everyone who has applied this round, plus the doctor it is already holding, keeps the best, and rejects the rest.
  3. Nothing is final until no doctor is rejected. Then every held offer becomes a match.

Run it on the market above.

Round Applications Held after the round What happened
1 A and B to Y; C to W; D to X W holds C, X holds D, Y holds B Y prefers B to A, so A is rejected
2 A to X W holds C, X holds A, Y holds B X prefers A to D, so it drops D
3 D to W W holds D, X holds A, Y holds B W prefers D to C, so it drops C
4 C to Z W holds D, X holds A, Y holds B, Z holds C nobody is rejected; stop

The result is A–X, B–Y, C–Z, D–W, the first stable matching on the list. Twice a hospital let go of a doctor it had been holding. Those two displacements are the whole point. A hospital that accepted D on the spot in round 1 would have had no room for A in round 2.

That is exactly what immediate acceptance does. In round k, each unmatched doctor applies to their k-th choice, and each hospital that is still open accepts its best applicant for good. Here, round 1 fills W with C, X with D and Y with B, permanently. A’s second and third choices, X and W, are already full when A reaches them, so A ends at Z. The outcome A–Z, B–Y, C–W, D–X is blocked twice: A and W prefer each other, and so do A and X.

Immediate acceptance also punishes honesty. If A lists X first instead of Y, A wins X in round 1, beating D, and ends with their true second choice instead of their fourth. A mechanism that rewards strategic ranking is one where your safest list is not your true one. Under doctor-proposing deferred acceptance no doctor can ever gain by misreporting. In this market that can be checked by trying every possible list, all 64 of them, from a single hospital up to a full ranking.

Mistake 3: assuming it does not matter who proposes

Run the algorithm again with hospitals proposing. W applies to A, X to C, Y to D and Z to B. Every doctor receives exactly one offer, so it ends after one round: A–W, B–Z, C–X, D–Y. That is the third stable matching, and it is a different one.

Doctors propose Hospitals propose
A gets X (2nd choice) W (3rd)
B gets Y (1st) Z (4th)
C gets Z (2nd) X (3rd)
D gets W (2nd) Y (4th)
Hospitals get W its 3rd; X, Y, Z their 2nd every hospital its 1st

This is a theorem, not a quirk of the example. The proposing side gets its best stable partner, and every one of its members agrees. Each member of the other side gets their worst stable partner. Every doctor weakly prefers the doctor-proposing outcome to every stable matching, and every hospital weakly prefers the hospital-proposing one. The middle matching, A–X, B–W, C–Z, D–Y, sits between them. So “run Gale–Shapley” is not a complete instruction. A good answer always says which side proposes, and why that side was chosen.

Mistake 4: treating truth-telling as safe for both sides

Proposers are safe. Dubins and Freedman (1981, American Mathematical Monthly) and Roth (1982, Mathematics of Operations Research) showed that truthful ranking is a dominant strategy for the proposing side under deferred acceptance. Students often stretch this to both sides. It does not stretch.

Take the doctor-proposing run, where W ends with D, its third choice. Suppose W instead declares only A and B acceptable. Then W rejects C in round 1 and D when D arrives. The rejected doctors cascade through the other hospitals until B, displaced from Y by D and turned down by X, applies to W. The new outcome is A–X, B–W, C–Z, D–Y. W now has B, its second choice, by hiding the truth about C and D. Notice that the outcome is the middle stable matching, which is stable under everyone’s true preferences. The lie did not break stability. It moved the market along the set of stable matchings toward W.

Roth’s 1982 paper shows this is unavoidable: no mechanism that always produces a stable matching makes truth-telling a dominant strategy for everyone. If you have met dominant strategies in game theory, this is the same concept applied to the reports people submit. It is also the bridge to auction theory and mechanism design, where incentives to report truthfully are the whole subject.

Mistake 5: carrying the existence result to one-sided markets

Gale and Shapley proved a stable matching always exists when the market has two sides. In the same paper they showed the guarantee fails when everyone can match with everyone, the roommates problem.

Four students, K, L, M and N, must split into two pairs. K ranks L, M, N; L ranks M, K, N; M ranks K, L, N; N, everyone’s last choice, ranks K, L, M. There are three ways to pair them. Pair K with L, and M and N are together: then L and M block, since L prefers M to K and M prefers L to N. Pair K with M: then K and L block. Pair K with N: then K and M block. Every pairing is blocked, so no stable outcome exists. The deferred-acceptance proof leans on the two-sided structure, and without it the argument has nowhere to stand.

Where deferred acceptance runs for real

The American market for new doctors, the National Resident Matching Program, already ran a hospital-proposing version of deferred acceptance. Its late-1990s redesign switched to applicants proposing, exactly the choice Mistake 3 is about; Roth and Peranson (1999, American Economic Review) describe the redesign. Several large public school systems have replaced immediate acceptance with deferred acceptance for the same reasons that appear above. In 2012 Alvin Roth and Lloyd Shapley shared the Nobel memorial prize in economics for the theory of stable allocations and the practice of market design.

Three exercises with answers

Exercise 1. In the market above, is A–W, B–Y, C–X, D–Z stable? If not, find every blocking pair.

Answer. It is not. Go doctor by doctor. A holds W and prefers Y and X, but Y holds B and X holds C, both ranked above A. B already has a first choice. C holds X and prefers W and Z. W holds A, its favourite, but Z holds D and ranks C above D. D holds Z and prefers X and W, both of which hold their first choices. The only blocking pair is C–Z.

Exercise 2. Three doctors, E, F and G, apply to three clinics, P, Q and R. E ranks R, P, Q; F ranks R, P, Q; G ranks P, R, Q. Clinic P ranks F, E, G; Q ranks E, F, G; R ranks F, E, G. Run deferred acceptance with each side proposing. How many stable matchings are there?

Answer. Both runs take four rounds and end at E–P, F–R, G–Q, the only stable matching. When the two proposing directions agree, the stable matching is unique, because every stable matching lies between them.

Exercise 3. Back in the four-hospital market, Z withdraws and Y adds a second slot. Both of Y’s slots use Y’s original ranking. Run deferred acceptance with doctors proposing and with hospitals proposing. (Hint: treat Y’s two slots as two copies of Y with the same preferences, and let every doctor rank the copies one after the other.)

Answer. Doctors proposing: A–Y, B–Y, C–W, D–X, so every doctor gets their first choice among the three hospitals still open. Hospitals proposing: A–W, B–Y, C–X, D–Y, so W gets A, X gets C and Y gets D and B, each hospital’s top choices. The proposing side wins again, even in a many-to-one market.

If you are taking market design or intermediate micro at UC San Diego, San Diego State or the University of San Diego, matching questions reward careful bookkeeping more than clever ideas. One-on-one microeconomics tutoring for UC San Diego students can run your own problem-set markets round by round until the blocking-pair checks become routine. See how a session is set up.

Book a micro tutor in San Diego for your market-design problem sets

Send the problem set or the lecture slides that are causing trouble, and you will be matched with a PhD tutor for sessions online. Working with a micro tutor in San Diego hours, you can take your matching, auction and mechanism-design questions in the order your course meets them. Start with the booking form, or use the WhatsApp button at the top of the page.

Get Started

See the #1 economics
mentoring platform in action