Game Theory
Matching Theory and the Gale-Shapley Algorithm
Every year thousands of medical students in the US don't know where they'll intern. Every year thousands of children in New York are assigned to a school. How to allocate them fairly and stably? The answer is an algorithm invented by mathematicians for a charming puzzle, and it now governs the lives of millions.
- **NRMP**: 50,000+ American medical residents are matched annually through the Gale-Shapley algorithm, in use since 1952
- **NYC Schools**: 90,000 New York 8th-graders receive school assignments each year through centralised matching
- **Kidney Exchange**: Alvin Roth created kidney exchange chains, matchings without money that save hundreds of lives annually
Предварительные знания
The Matching Problem
NRMP distributes 40,000 medical residents to US hospitals annually via Gale-Shapley , a stable matching is mathematically guaranteed, making it manipulation-proof since 1952. The matching problem is the assignment of agents from two groups into pairs, where each agent has **preferences** over agents from the other group. Unlike a standard market, there are no monetary transfers, only preferences.
What makes a matching 'good'? The answer is **stability**: the central concept of matching theory.
A matching M is called **stable** if there is no **blocking pair**: a pair (a, b) such that: • a prefers b to their current partner in M • b prefers a to their current partner in M If a blocking pair exists, a and b will leave their partners and pair up. Stability = no mutual desire to 'elope'.
Matching: Anna-Ivan, Kate-Peter. Anna prefers Peter, and Peter prefers Anna. Is this matching stable?
The Gale-Shapley Algorithm
David Gale and Lloyd Shapley (1962)
Mathematicians David Gale and Lloyd Shapley published 'College Admissions and the Stability of Marriage' in 1962. They proved that a stable matching exists for any set of preferences and gave a constructive algorithm to find it. Lloyd Shapley received the Nobel Prize in Economics in 2012 (shared with Alvin Roth). Gale passed away in 2008 before the prize was awarded.
The algorithm terminates in a finite number of steps (at most n² proposals) and is guaranteed to return a stable matching. Moreover, the algorithm is **optimal for the proposing side**: each man gets the best possible partner across all stable matchings.
In the Gale-Shapley algorithm a woman receives a proposal and already has a tentative partner. What does she do?
Properties and Limitations of the Algorithm
The Gale-Shapley algorithm has several remarkable properties but also an important limitation, the asymmetry of the result.
| Property | Description |
|---|---|
| Existence | A stable matching always exists for any preferences |
| Completeness | All agents are matched (when group sizes are equal) |
| Proposer optimality | Each proposer gets the BEST partner across ALL stable matchings |
| Receiver pessimality | Each receiver gets the WORST partner across all stable matchings |
| Strategy-proofness | Honest preference list is a dominant strategy for proposers |
| Manipulability | Receivers CAN benefit by misrepresenting their preferences |
The side that proposes wins. In real systems this matters: • NRMP (doctors - hospitals): for a long time hospitals proposed → hospitals benefited. After the 1995 reform, doctors propose → better for doctors. • Schools vs families: the side that proposes first has the advantage.
Why is the Gale-Shapley algorithm strategy-proof for proposers but not for receivers?
Applications: Markets Without Prices
Alvin Roth (Nobel Prize 2012) transformed matching theory into an applied science, **market design**. He built mechanisms for real markets where money doesn't work or is socially unacceptable.
Roth's lesson: **markets must be designed**. Markets that arise spontaneously are often unstable, not strategy-proof, and produce poor outcomes. Matching theory is a tool for improving them.
Why can't the kidney exchange market simply use monetary payments instead of a complex matching algorithm?
Key Ideas
- **Stable matching**: no blocking pair exists; neither partner in any pair mutually prefers someone else
- **Gale-Shapley (Deferred Acceptance)**: proposers offer in decreasing preference order; receivers hold the best proposer seen
- **Optimal for proposers**: each gets their best possible partner; **pessimal for receivers**
- **Strategy-proof for proposers**: honest list is a dominant strategy; receivers can manipulate
- **Market design (Roth)**: matching algorithms applied to schools, hospitals, kidney exchanges
Related Topics
Matching theory sits at the intersection of game theory and algorithms:
- Mechanism Design — Matching is an application of mechanism design: how to engineer rules for a desired outcome
- Auction Theory — Auctions are matching with money; Roth contrasts them with 'markets without prices'
- Algorithmic Game Theory — The GS algorithm runs in O(n²); computational complexity of matching problems
Вопросы для размышления
- In the university admissions system in the country, is it stable? Who proposes, who accepts?
- What happens if everyone knows that others can also manipulate their preferences? Will an equilibrium emerge?
- Roth talks about 'repugnant markets', markets society considers unethical. Where is the line between acceptable and unacceptable?