Nobel Prize in Economics 2012: Stable Matching and Market Design

This note covers the Nobel Prize in Economics 2012: who won it, what "matching theory" and "market design" mean, how the Gale-Shapley algorithm pairs people fairly without using prices, how the idea travelled from pure mathematics to real hospitals, schools and kidney transplants, how the discovery unfolded over five decades, why it matters and quick facts for exams.

What was the Nobel Prize in Economics 2012 awarded for?

The prize was given jointly to Alvin E. Roth and Lloyd S. Shapley "for the theory of stable allocations and the practice of market design".

This is the official citation of the Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012, the formal name of the award that is widely called the Nobel Prize in Economics.

In plain words, the prize rewards work on a very common problem: how do you pair up people or things fairly when you cannot simply let prices decide? A school place, a hospital internship or a donated kidney cannot be sold to the highest bidder, yet someone still has to be matched with someone else.

The laureates built the mathematical theory behind such matching, and then turned that theory into working systems used in real markets.

Shapley supplied the abstract mathematics of stable allocations, developed mainly in the 1950s and 1960s. Roth later showed that this theory explained why some real matching systems worked well and others failed, and he helped redesign several of them.

The press release called this combination "an outstanding example of economic engineering", attributed to the Royal Swedish Academy of Sciences.

Who are the laureates?

Alvin E. Roth

Alvin E. Roth was born on 18 December 1951 in New York, NY, USA. At the time of the award he was affiliated with Harvard University, Cambridge, MA, USA, and Harvard Business School, Boston, MA, USA. He received one half of the prize.

Roth took Shapley's abstract theory and tested it against the real world. Beginning in the 1980s he used empirical studies and laboratory experiments to show that stability was the key reason some matching systems succeeded while others broke down.

He went on to help redesign the system that matches new doctors with hospitals in the United States, the system that matches schoolchildren with schools in New York City, and systems that match organ donors with patients.

Lloyd S. Shapley

Lloyd S. Shapley was born on 2 June 1923 in Cambridge, MA, USA, and died on 12 March 2016 in Tucson, AZ, USA.

At the time of the award he was a professor emeritus at the University of California, Los Angeles (UCLA), CA, USA. He also received one half of the prize.

From the 1960s onward, Shapley used cooperative game theory to study and compare different ways of matching agents.

With the mathematician David Gale, he proved in 1962 that a simple algorithm could always produce a stable matching in two-sided problems such as pairing men and women, or students and schools.

He later solved a related one-sided problem about swapping houses, which fed directly into later work on exchanging kidneys.

What problem does matching theory solve?

Ordinary economics assumes that when something is scarce, its price rises until supply equals demand, and the market sorts itself out. This works for most goods, but it breaks down whenever prices cannot be used at all.

Universities are often not allowed to auction off places to the richest applicants. Human organs for transplant cannot legally be bought and sold. Hospital internships are not sold to the highest-paying trainee doctor.

Yet in every one of these situations, someone still has to decide who gets matched with whom. This is the problem of allocation without prices, and it needed its own branch of economics to be understood properly.

The laureates' answer rested on a single powerful idea: a matching should be stable. A matching is stable if no two agents on opposite sides would both prefer to abandon their current partners and pair up with each other instead.

If such a pair exists, the system is unstable, because those two agents have every incentive to break the rules and match privately.

Stability, not price, became the test of whether a matching system would actually survive contact with real people trying to get the best outcome for themselves.

How does the Gale-Shapley algorithm work?

In 1962, David Gale and Lloyd Shapley published a short paper asking a seemingly simple question: if ten women and ten men each have their own ranking of who they would like to marry, is there always a way to pair everyone up so that the result is stable? They answered yes, and they gave an exact method for finding such a pairing, now called the Gale-Shapley "deferred acceptance" algorithm.

One version of the algorithm, where women propose to men, works like this:

1. Each woman proposes to the man she likes best among those she has not yet proposed to.
2. Each man looks at all the proposals he has received so far, provisionally holds the one he likes most, and rejects the rest.
3. Every woman who was rejected proposes again, this time to her next-favourite man who has not already rejected her.
4. Each man again compares his new proposal with the one he is currently holding, keeps the better one, and rejects the other.
5. Steps 3 and 4 repeat until no woman has any further proposal left to make.
6. Every man then finally accepts the proposal he is holding, which completes a stable matching.

Gale and Shapley proved mathematically that this process always ends in a stable matching. They also showed something less obvious: whichever side is allowed to propose ends up with the better outcome, while the side that only responds gets the worst stable matching possible.

Draw three hospitals labelled a, b and c, and three doctors labelled 1, 2 and 3.

Show all three doctors first offering themselves to hospital a, which can only keep its favourite, doctor 1. Then show doctor 2 offering to hospital b and doctor 3 offering to hospital c, giving a stable match.

Beside it, draw the same doctors and hospitals but with hospitals making the offers instead, to show that the match that results is different and favours the hospitals.

How did Roth turn theory into practice?

Alvin Roth's contribution was to show that Shapley's abstract mathematics explained real markets that already existed, and then to use that understanding to fix markets that were broken.

He studied several matching systems in detail and found a common pattern: systems that produced stable matches tended to survive and grow, while systems that produced unstable matches tended to be abandoned by the people using them.

Three of his best documented projects are summarised below.

Roth also ran laboratory experiments that tested how real people behave inside different matching rules, confirming in a controlled setting what his field studies had already suggested about stability.

What is the top trading cycle for organ matching?

Not every matching problem has two active sides. In kidney exchange, patients and their willing donors want a transplant, but an organ itself does not "choose" anything; the exchange is effectively one-sided.

Shapley and his colleagues had already solved an abstract version of this problem in the 1970s, in a puzzle about people who each own a house and want to swap for a better one.

Their solution, known as the top trading cycle, starts from an initial allocation and lets participants swap in cycles until nobody can improve further without someone else losing out.

Decades later, Roth built directly on this result when designing chains of kidney exchange: if a donor is not compatible with their own intended recipient, their kidney can go to a stranger, whose own incompatible donor passes a kidney further along the chain, and so on.

The presentation speech by Professor Torsten Persson described one such case from 2011, where a chain beginning with an altruistic donor in California eventually linked together 60 coordinated transplant operations across the United States, ending with a 30th patient, a man in Chicago, resuming a normal life four days before Christmas Eve after a year of dialysis. These chains are now used across a number of U.S. states.

How did the discovery unfold?

The idea behind the 2012 prize grew over exactly fifty years, moving from a letter between mathematicians to systems now used by tens of thousands of people every year.

Why does this prize matter?

The work honoured in 2012 matters because it solves a problem that ordinary supply-and-demand economics cannot: deciding who gets what when prices are legally or ethically off the table.

Schools, hospital training positions and human organs all have to be allocated somehow, and the laureates' theory gives a mathematically sound and ethically acceptable way to do it.

The practical impact is large and measurable. The redesigned doctor-matching system now places over 20,000 positions a year, the New York City school admissions redesign cut unwanted placements by 90 percent, and kidney exchange chains built on these ideas have let patients receive transplants from donors who were never a direct match for them.

The Royal Swedish Academy of Sciences said the two laureates had "generated a flourishing field of research and improved the performance of many markets", even though Roth and Shapley never worked together directly.

The field continues to grow. Researchers have since extended matching theory to settings where prices do play some part, such as auctions for online advertising space, showing that the underlying mathematics of stable matching connects to a much wider range of markets than the original marriage and school examples suggested.

How does this connect to what you study?

Matching theory sits at the point where mathematics, economics and computer science meet, and the ideas show up in school-level topics in more than one way.

The Gale-Shapley algorithm is a clear example of a step-by-step procedure (algorithm), the kind of logical, repeatable process studied in computer science and mathematics, where a fixed set of rules is guaranteed to reach a correct answer.

In economics, the prize is a good illustration of why the simple idea that "prices always balance supply and demand" has important exceptions.

Wherever ethical or legal rules rule out buying and selling something directly, such as organs or school places, a different kind of reasoning, based on fairness and stability rather than price, becomes necessary.

This is a useful case study for anyone learning how economic theory is tested against real evidence and then used to redesign real institutions, which is exactly what game theory and market design courses at university level build on.

Quick facts for exams

The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel for 2012, popularly called the Nobel Prize in Economics, was announced on 15 October 2012 by the Royal Swedish Academy of Sciences.

It was awarded jointly, one half each, to Alvin E. Roth of Harvard University and Harvard Business School, USA, and Lloyd S.

Shapley of the University of California, Los Angeles, USA, "for the theory of stable allocations and the practice of market design". Shapley supplied the mathematical theory of stable matching from the 1950s and 1960s, especially the Gale-Shapley algorithm;

Roth later used empirical studies, laboratory experiments and real-world redesign to apply this theory to markets such as doctor placement, school admissions and kidney exchange, where prices cannot be used to allocate resources. The total prize amount was 8,000,000 Swedish kronor.

Note: Source. The prize facts in this note are from the Nobel Prize's official site, nobelprize.org.

Glossary

• Matching — pairing up members of one group with members of another group, such as students with schools or patients with donors.
• Stable allocation — a matching in which no two agents on opposite sides would both prefer to leave their current partners and pair with each other instead.
• Market design — the practical work of building or fixing the rules of a market so that it produces good, workable outcomes.
• Cooperative game theory — the branch of mathematics that studies how rational individuals might jointly agree on an outcome, such as a stable match.
• Gale-Shapley algorithm — the specific step-by-step method, also called deferred acceptance, that always produces a stable two-sided matching.
• Deferred acceptance — the feature of the algorithm where an offer is held provisionally, not accepted immediately, so it can be replaced by a better one later.
• Two-sided matching — a matching problem where both groups, such as students and schools, actively rank their preferences.
• One-sided matching — a matching problem where only one side has active preferences, such as people swapping houses or kidneys.
• Top trading cycle — an algorithm for one-sided matching that lets participants swap in cycles starting from an initial allocation.
• Clearinghouse — a centralised system that collects preferences from both sides of a market and computes a matching for everyone at once.
• National Resident Matching Program (NRMP) — the U.S. system that matches new doctors with hospital internships.
• Kidney exchange chain — a sequence of paired kidney donations in which each incompatible donor passes a kidney further along the chain.
• Economic engineering — a phrase used by the prize committee for the practical redesign of real markets using economic theory.

Common errors and misconceptions

• Misconception: Roth and Shapley worked together as a team. Correct: the sources state they worked independently, decades apart; the prize rewards the combination of Shapley's theory with Roth's later empirical and practical work.
• Misconception: the Gale-Shapley algorithm only applies to marriage matching. Correct: it has been used for doctors and hospitals and for students and schools; organ exchange instead uses a related but distinct algorithm, the top trading cycle.
• Misconception: stable matching means everyone gets their first choice. Correct: stability only means no pair would both prefer to swap away from their current match; some agents may still get a lower-ranked choice.
• Misconception: whichever side proposes in the algorithm does not affect the outcome. Correct: the proposing side systematically gets a better outcome than the responding side.
• Misconception: kidney exchange chains involve direct payment to donors. Correct: the design specifically rules out monetary side payments for ethical reasons.
• Misconception: this prize is purely abstract mathematics with no real-world use. Correct: it has been used to redesign actual systems, including U.S. doctor placement and New York City school admissions.
• Misconception: the "Nobel Prize in Economics" has exactly the same name as the other Nobel Prizes. Correct: its official name is the Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel.

Exam-style questions with model answers

Q1. In which year was the Nobel Prize in Economics 2012 announced? [1 mark]

1. It was announced on 15 October 2012 by the Royal Swedish Academy of Sciences.

Q2. State the official citation for the 2012 prize. [2 marks]

1. The citation reads "for the theory of stable allocations and the practice of market design", awarded jointly to Alvin E. Roth and Lloyd S. Shapley.

Q3. Explain what a "stable allocation" means in matching theory. [3 marks]

1. A stable allocation is a matching where no two agents on opposite sides, for example a student and a school, would both prefer to break their current pairing and match with each other instead.
2. If such a pair exists, the matching is unstable because those two agents have a clear incentive to abandon the rules and pair up privately.
3. Stability therefore became the central test economists used to judge whether a real matching system, such as a hospital-doctor clearinghouse, would hold together in practice.

Q4. Describe the main steps of the Gale-Shapley algorithm. [4 marks]

1. Each person on the proposing side offers themselves to their most-preferred partner who has not yet rejected them.
2. Each person on the receiving side provisionally holds the best offer received so far and rejects all others.
3. Anyone who is rejected proposes again to their next-favourite option.
4. This process of proposing, holding and rejecting repeats until nobody has an unmade proposal left.
5. The algorithm always ends in a stable matching, as proved mathematically by Gale and Shapley.

Q5. Why could prices not be used to solve the matching problems studied by Roth and Shapley? [3 marks]

1. In several of the markets they studied, using prices was either illegal or considered unethical, such as paying for human organs.
2. Schools and universities are often not allowed to charge for places, so money cannot be used to decide who is admitted.
3. Because price could not balance supply and demand, a different method, based on stable matching rather than money, was needed to allocate places fairly.

Q6. Discuss how Alvin Roth applied Lloyd Shapley's theoretical work to real markets, giving at least two examples. [5 marks]

1. Lloyd Shapley had developed the abstract theory of stable matching and the Gale-Shapley algorithm in the 1950s and 1960s, long before it was applied anywhere.
2. Beginning in the 1980s, Alvin Roth used empirical studies to show that real matching systems which produced stable matches tended to succeed, while unstable ones tended to collapse.
3. In the mid-1990s, Roth was asked to help redesign the U.S. National Resident Matching Program, which paired new doctors with hospitals; he and Elliott Peranson built a new applicant-proposing algorithm, adopted in 1997, that also accommodated dual-doctor couples.
4. In 2003, Roth and colleagues redesigned the New York City high-school admissions process using a similar applicant-proposing Gale-Shapley algorithm, cutting the number of students assigned to unlisted schools by 90 percent.
5. Roth also co-founded the New England Program for Kidney Exchange and helped design chains of kidney donations, building on a one-sided matching result Shapley had proved decades earlier.
6. Across all these cases, Roth combined Shapley's theory with field evidence, laboratory experiments and direct institutional redesign, which the prize committee described as "economic engineering".

Q7. What distributional consequence did Gale and Shapley identify about who is allowed to "propose" in their algorithm? [3 marks]

1. Gale and Shapley showed that the side allowed to make proposals ends up with a better outcome than the side that only responds to offers.
2. If women propose, the resulting match is the best possible stable match for women and the worst possible stable match for men, and the reverse is true if men propose.
3. This mattered practically, because real systems such as the original doctor-matching clearinghouse gave the proposing role to hospitals, which systematically favoured hospitals over students.

Q8. Briefly describe the kidney-exchange case mentioned in the award ceremony speech. [2 marks]

1. A chain that began with an altruistic donor in California eventually linked 60 coordinated kidney transplant operations across the United States.
2. The chain's 30th patient, a man in Chicago, received a kidney shortly before Christmas.

Key takeaways

• The 2012 Economics prize went jointly to Alvin E. Roth and Lloyd S. Shapley for the theory of stable allocations and the practice of market design.
• Shapley built the mathematical theory of stable matching, including the Gale-Shapley algorithm, mainly in the 1950s and 1960s.
• Roth showed empirically that stability explained the success or failure of real matching systems, then helped redesign several of them.
• A stable match means no two agents on opposite sides would both rather swap partners than keep their current match.
• The Gale-Shapley "deferred acceptance" algorithm always produces a stable match, but favours whichever side is allowed to propose.
• Roth's redesigns include the U.S. doctor-hospital matching system, New York City school admissions, and kidney exchange chains.
• The Royal Swedish Academy of Sciences called the combined work "an outstanding example of economic engineering".
• Matching theory matters most where prices cannot legally or ethically be used to allocate scarce resources.

Test yourself

Who were the two laureates of the Nobel Prize in Economics 2012?

Alvin E. Roth of Harvard University and Lloyd S. Shapley of the University of California, Los Angeles, shared the prize equally.

What was the official citation for the prize?

The citation reads "for the theory of stable allocations and the practice of market design".

What makes a matching "stable"?

A matching is stable when no two agents on opposite sides would both prefer to abandon their current partners for each other.

Who originally developed the deferred acceptance algorithm with Shapley?

The mathematician David Gale co-authored the 1962 paper with Lloyd Shapley that introduced the algorithm.

Name one real-world system Alvin Roth helped redesign.

Roth helped redesign the U.S. National Resident Matching Program, which pairs new doctors with hospital internships, in 1995 to 1997.

Why can prices not be used to allocate human organs?

Monetary payment for human organs is ruled out on ethical and legal grounds, so a non-price matching method is needed instead.

What algorithm did Shapley develop for one-sided matching problems like house swapping?

Shapley developed the top trading cycle algorithm, which lets participants swap allocations in cycles until no further improvement is possible.

How much did the New York City school admissions redesign reduce unwanted placements by?

The redesign led to a 90 percent reduction in the number of students assigned to schools they had not listed.