Roth & Shapley (2012): The Economics of Matchmaking — From Marriage to Kidneys

Markets Without Prices

Not all markets use prices. You can’t buy your way into a marriage. You can’t purchase a kidney (legally). You can’t bid for a spot at a public school. Yet these are all allocation problems — scarce resources must be matched to people who want them.

How do you design a system that produces good matches when money can’t do the job? This is the problem of matching markets, and the 2012 Nobel Prize honored the theorist who solved it mathematically and the engineer who made it work in practice.

Lloyd Shapley, a mathematician, proved in 1962 that stable matchings always exist and designed an algorithm to find them. Alvin Roth, an economist, took Shapley’s theory off the blackboard and into the real world — redesigning the systems that match doctors to hospitals, students to schools, and kidney donors to recipients.

Shapley: The Theory of Stable Matching

In 1962, David Gale and Lloyd Shapley posed a deceptively simple question: can you always find a stable way to match men and women into couples?

A matching is stable if no two people would prefer to leave their current partners and match with each other instead. If such a pair exists, they have an incentive to break away — making the matching unstable.

The Gale-Shapley deferred acceptance algorithm:

1. Each man proposes to his top-choice woman
2. Each woman who receives multiple proposals keeps her favorite and rejects the rest
3. Rejected men propose to their next choice
4. The process repeats until everyone is matched

Gale and Shapley proved three remarkable results:

• Existence: The algorithm always terminates with a stable matching — no matter what the preferences are. A stable solution always exists
• Optimality: When men propose, the result is the best stable matching for men (and the worst for women). When women propose, the reverse. The proposing side gets the advantage
• Strategy-proofness: The proposing side has no incentive to misrepresent their preferences — honesty is the best strategy. But the receiving side might benefit from strategic behavior

These results were purely theoretical — Shapley was a mathematician interested in elegant proofs, not practical applications. It took Roth to see the real-world potential.

Roth: From Theory to Life-Saving Practice

Alvin Roth made a remarkable discovery: the National Resident Matching Program (NRMP), which had been matching medical graduates to hospital residencies since 1952, was essentially using the Gale-Shapley algorithm — without knowing it. The system had evolved toward stability through trial and error.

This insight launched Roth’s career as an economic engineer — someone who designs real markets using theoretical principles.

Redesigning the medical match:

• The original NRMP algorithm was hospital-proposing, favoring hospitals over doctors
• Roth redesigned it in 1995 to be doctor-proposing, making it strategy-proof for doctors
• He also solved the “couples problem” — when two married doctors need positions in the same city, the standard algorithm can fail. Roth developed extensions that handle couples

School choice:

• In many cities, students are assigned to public schools through chaotic systems that reward gaming and manipulation
• Roth (with Atila Abdulkadiroglu) redesigned school choice systems in New York City (2003) and Boston (2005) using variants of the deferred acceptance algorithm
• The new systems are strategy-proof — families can honestly rank their preferred schools without worrying about gaming the system
• Result: better matches, less stress, and more equitable access to good schools

Kidney exchange — Roth’s most dramatic application:

• Many kidney patients have a willing donor whose kidney is incompatible. Patient A needs a kidney that donor B has, and patient B needs a kidney that donor A has — but they don’t know each other
• Roth designed kidney exchange programs that find these complementary pairs and arrange simultaneous swaps. He extended this to chains of three, four, or more pairs
• The New England Program for Kidney Exchange, which Roth helped create, has saved thousands of lives
• This is market design at its most profound — using economic theory to literally keep people alive

Why Matching Markets Are Special

Matching markets differ from ordinary markets in fundamental ways:

• No prices: You can’t buy a spouse, a school seat, or a kidney. Allocation must happen through other mechanisms
• Two-sided choice: Both sides must agree. A school can’t force a student to attend, and a student can’t force a school to accept them
• Preferences matter: Unlike commodity markets where one unit is as good as another, matching markets involve heterogeneous goods — each doctor-hospital pair has a unique value
• Thickness, congestion, and safety: Roth identified three requirements for well-functioning matching markets — enough participants (thickness), enough time to evaluate options (managing congestion), and safety to reveal true preferences (strategy-proofness)

Their 2012 Nobel Prize was awarded “for the theory of stable allocations and the practice of market design.”

Explain It to a Child

Imagine your class is picking teams for a science project. Everyone writes down who they want to work with. The problem: your first choice might not pick you back. And if people just pair up randomly, some kids will be unhappy and try to switch — causing chaos. Shapley invented a clever system: everyone takes turns proposing partners, and you can always trade up if someone better asks you, but you’re never left without a partner. No pair of kids ends up wishing they were together instead — that’s a “stable” match. Then Roth took this idea and used it for real life. He helped match doctors to hospitals, kids to schools, and — most amazingly — he helped people who need kidney transplants find donors. His matching system has saved thousands of lives, all based on the math of picking the right partner.