Market Design: Matching Theory & Gale-Shapley
Learning Goal: Apply market design and matching theory principles to analyze resource allocation in markets without prices, evaluating the efficiency and fairness of mechanisms such as the Gale-Shapley algorithm in school choice, kidney exchange networks, and medical residency matching.
- Prerequisites: Basic mathematical logic and introductory game theory concepts (recommended but not required).
- Estimated Total Study Time: 10 Hours
Module 1: Introduction to Market Design and Price-Free Markets
Module Overview
In standard economics, prices act as the invisible hand coordinating supply and demand. However, in many of society's most critical arenas—such as assigning children to public schools, allocating human organs for transplant, or matching doctors to residencies—using monetary prices is either legally banned, ethically repugnant, or practically impossible. This module introduces the field of Market Design, explaining how economists act as engineers to build rules and pathways for these price-free matching markets.
Recommended Videos
Why this video
Presented by Nobel laureate Alvin Roth, this comprehensive lecture is the definitive introduction to market design. It lays out the three essential components of any successful matching market: establishing thickness (attracting a critical mass of participants), overcoming congestion (allowing enough time or structural capacity to process offers), and ensuring safety (making it in participants' best interests to act truthfully).
Why this video
This brief interview offers an accessible real-world summary of how matching markets function. It helps transition the student's mindset from abstract economic theory to the human-centric focus of matchmaking, where outcomes depend on mutual choice rather than simple buying power.
Knowledge Checkpoint
- Understand the fundamental difference between commodity markets (where price determines allocation) and matching markets (where transactions require mutual consent).
- Define "thickness" and "congestion" in the context of design-driven markets.
- Explain why standard price-based mechanisms cannot be used to allocate scarce goods like kidneys or public school seats.
Module 2: Two-Sided Matching & The Gale-Shapley Algorithm
Module Overview
Two-sided matching involves pairing two distinct groups (such as men and women, or applicants and employers) where both sides have preferences over the other. The benchmark of success in these markets is stability—an allocation where no pair of participants would both prefer to break their current assignments to match with each other. This module unpacks the mathematics of the Stable Marriage Problem and masterfully breaks down the mechanics of the Nobel-winning Gale-Shapley Deferred-Acceptance Algorithm.
Recommended Videos
Why this video
This video uses a clean, intuitive visual walkthrough to demonstrate step-by-step how the Gale-Shapley algorithm reaches a stable matching. It traces proposals, tentative holds (deferred acceptance), and rejections across a set of sample preferences, making it easy to see how the algorithm guarantees a stable state.
Why this video
An excellent, formal lecture from MIT OpenCourseWare that translates the physical concept of the "matching ritual" into algorithmic steps. It details the exact mathematical proofs of why the algorithm must terminate, why the final matching is stable, and how the proposing side always achieves their best possible stable matching (optimal outcomes).
Why this video
In this segment, legendary computer scientist Richard Karp discusses the computer science and computational complexity perspectives of the stable marriage problem. This conversation bridges the gap between economic game theory and computer science, showing how matching theory sits at the intersection of both fields.
Knowledge Checkpoint
- Define a "blocking pair" and write the formal mathematical criteria for a matching to be considered stable.
- Manually execute the Gale-Shapley algorithm given two sets of ranked preferences.
- Explain the concept of "proposer-optimality" and identify who benefits most when the algorithm is run.
- Prove why the Gale-Shapley algorithm is guaranteed to terminate and always yield a stable matching.
Module 3: School Choice Systems and Mechanism Design
Module Overview
How should public school districts assign thousands of children to schools when some institutions are heavily oversubscribed? Historically, many cities used the Boston Mechanism (Immediate Acceptance), which frequently penalized families for being honest about their preferences. In this module, we examine how market design revolutionized school admissions by shifting cities toward Strategy-Proof Deferred Acceptance systems, ensuring no family is punished for listing their true dream school first.
Recommended Videos
Why this video
Led by MIT economist Parag Pathak, one of the primary architects of school choice design in New York and Boston, this academic lecture explains the direct application of matching models to school systems. It explores the critical nuances of one-sided vs. two-sided markets, single-tie-breaking vs. multiple-tie-breaking for priority lists, and the practical policy trade-offs between stability and efficiency.
Why this video
This short, impactful video features Alvin Roth describing the specific real-world transition of the Boston school system. He outlines how the old system forced parents to play complex strategic games, whereas the new deferred-acceptance system made revealing true preferences a "dominant strategy" (safe for everyone).
Why this video
A very brief but mathematically targeted abstract presentation that highlights the theoretical disadvantages of the Boston mechanism, reinforcing why immediate-acceptance mechanisms fail the test of strategy-proofness.
Curriculum Gap Bridge: The Boston Mechanism vs. Deferred Acceptance
Because the available video pool contains limited step-by-step tutorials comparing these two school choice systems, study this comparative breakdown carefully:
HOW CHOICES ARE PROCESSED IN SCHOOL ASSIGNMENTS
[ Family Submits Ranked List: 1st Choice, 2nd Choice, 3rd Choice... ] │ ┌────────────────────────┴────────────────────────┐ ▼ ▼ 【 BOSTON / IMMEDIATE ACCEPTANCE 】 【 DEFERRED ACCEPTANCE (DA) 】
- Priority: 1st-choice applicants processed - Priority: Evaluated round-by-round. first. - "Holds": Schools hold top applicants
- Immediate Match: If a school has seats, temporarily (deferred acceptance). it permanently matches immediately. - Safety: If rejected in Round 2, you
- Penalty: If rejected, your 2nd choice can still compete for your 2nd choice is likely already full of people who on equal footing with those who ranked ranked it 1st. You are displaced. it 1st.
- Strategy: Must lie and rank a "safe" - Strategy: Strategy-proof. Safe to rank school first to avoid disaster. your absolute favorite school first.
Detailed Example:
Imagine School A has 1 seat. School B has 1 seat.
-
Student 1 ranks: (1) School A, (2) School B
-
Student 2 ranks: (1) School A, (2) School B
-
Student 3 ranks: (1) School B, (2) School A
-
School Priorities: Both schools prefer Student 2, then Student 1, then Student 3.
-
Under Boston (Immediate Acceptance):
- Round 1: Students 1 and 2 apply to School A. Since Student 2 has higher priority, Student 2 gets the seat permanently. Student 3 applies to School B and gets the seat permanently.
- Round 2: Student 1 is rejected from School A and now looks at their second choice, School B. But School B's seat is already permanently taken by Student 3. Student 1 is left unassigned, even though School B would have preferred Student 1 over Student 3!
-
Under Deferred Acceptance (Gale-Shapley):
- Round 1: Students 1 and 2 apply to School A. School A tentatively holds Student 2 and rejects Student 1. Student 3 applies to School B; School B tentatively holds Student 3.
- Round 2: Rejected Student 1 applies to School B. School B compares Student 1 to their tentative hold (Student 3). Since School B prefers Student 1, School B rejects Student 3 and tentatively holds Student 1.
- Round 3: Rejected Student 3 applies to School A. School A compares Student 3 to their tentative hold (Student 2). School A prefers Student 2, so School A rejects Student 3.
- Outcome: Matches become permanent. Student 2 gets School A; Student 1 gets School B. This is stable and fair.
Knowledge Checkpoint
- Explain why the Boston Mechanism incentivizes families to "strategize" and misrepresent their true preferences.
- Define the term "strategy-proofness" (or dominant-strategy incentive compatibility).
- Contrast how priority tie-breaking (single lottery vs. multiple lotteries) influences equity and efficiency in student placement.
Module 4: Kidney Exchange Networks and Cycle Matching
Module Overview
Organ transplantation presents a unique matching challenge. A patient with renal failure may have a willing donor (such as a spouse or sibling) who is biologically incompatible. Using a monetary market to purchase kidneys is illegal globally (except in Iran). Economists solved this using market design by building networks that arrange kidney exchanges. This module analyzes how multi-pair cycles and altruistic donor chains, powered by the Top Trading Cycles (TTC) algorithm, optimize life-saving resource allocation.
Recommended Videos
Why this video
This lecture segment explicitly models and visualizes Herbert Scarf's and David Gale's Top Trading Cycles (TTC) algorithm. Pathak illustrates how cycles are formed by mapping directed graphs where agents "point" to their most-preferred items, demonstrating why TTC is Pareto-efficient, strategy-proof, and individually rational.
Why this video
Professor Tim Roughgarden breaks down the elegant graph theory behind TTC. In this concise walkthrough, you will see how pointing to owners of preferred houses (or kidneys) guarantees the existence of at least one cycle, which is then executed, leading to optimal Pareto-efficient trades.
Why this video
This documentary-style video provides the real-world application of matching theory to live organ donation. It explains how economists set up donor-recipient pairs and coordinated altruistic chains to bypass biological incompatibility.
Curriculum Gap Bridge: Mechanics of Top Trading Cycles (TTC)
Because the math of TTC is highly abstract, review this step-by-step logic used to allocate kidneys or houses:
THE TOP TRADING CYCLES (TTC) LOOP
┌────────────────────────────────────────────────────────┐
│ │
▼ │
[ Step 1: Every remaining patient points to their ] │ [ favorite kidney (or house) remaining. ] │ │ │ ▼ │ [ Step 2: Every kidney/house owner points back to ] │ [ the patient they brought to the market. ] │ │ │ ▼ │ [ Step 3: Identify the resulting directed cycles. ] │ [ (Graph theory guarantees ≥1 cycle exists) ] │ │ │ ▼ │ [ Step 4: Execute the trades in the cycles. ] │ [ Assigned patients & kidneys leave. ] │ │ │ └───────────────── No more items left? ──────────────────┘ │ Yes ▼ [ Terminate Match ]
Why TTC is unique:
Unlike Gale-Shapley, which focuses on stability (no blocking pairs), TTC focuses on Pareto efficiency. In house allocation or kidney markets where agents start with an initial endowment (their own house or their incompatible donor), TTC ensures that no group of people can trade among themselves to achieve a better outcome than the algorithm's final allocation.
Knowledge Checkpoint
- Draw a directed graph representing a 3-pair kidney exchange cycle and identify the trading loops.
- Explain why altruistic donor chains (non-directed chains starting with an un-paired donor) do not have to be closed loops and why this drastically increases matching flexibility.
- Define the "Core" of a housing market and explain why the Top Trading Cycles algorithm uniquely produces the core allocation.
Module 5: Medical Residency Matching & Market Unraveling
Module Overview
The National Resident Matching Program (NRMP) in the United States is one of the oldest and largest running matching markets in the world, matching tens of thousands of medical graduates to hospital residencies annually. Before a centralized matching clearinghouse was introduced in the 1950s, this market suffered from a destructive phenomenon known as market unraveling. This module investigates why decentralized matching systems collapse over time and details how modern algorithms accommodate complex structural requirements, such as matching dual-career couples.
Recommended Videos
Why this video
This is the official animated guide produced by the NRMP explaining their resident-proposing matching algorithm. It demonstrates how student and hospital rank lists are combined using a deferred-acceptance system to produce a legally binding match, emphasizing that the system is optimized for applicants.
Why this video
This deep-dive analysis critiques the existing Roth-Peranson algorithm (the variant of Gale-Shapley used by the NRMP). The video explains the historical context of the match, examines how the algorithm functions, and discusses modern debates surrounding equity, geographic constraints, and potential alternative algorithms.
Why this video
One of the most complex algorithmic challenges in matching theory is the "couples match." Because couples coordinate their rankings to secure placements in the same geographic region, their preferences are interdependent. This video provides a practical explanation of how the NRMP coordinates these joint-rank lists, highlighting why couples matching threatens the existence of a stable matching.
Curriculum Gap Bridge: The Theory of Market Unraveling
Decentralized matching markets often suffer from a competitive failure called market unraveling. To understand this concept, review the historical progression:
CHRONOLOGY OF MARKET UNRAVELING
[ Stage 1: Balanced Recruiting ]
Hospitals hire medical students near the end of senior year.
│
▼
[ Stage 2: Pre-emptive Offers ]
To beat competitors to top talent, Hospital A offers a job
to a junior. Hospital B responds by offering jobs to sophomores.
│
▼
[ Stage 3: Extreme Congestion / Exploding Offers ]
Offers are made years before graduation with "exploding" deadlines
(e.g., "accept in 24 hours or the offer is revoked").
│
▼
[ Stage 4: Market Collapse ]
Hospitals must hire based on highly incomplete academic records.
Students are forced to accept early, sub-optimal offers out of fear.
- The Solution: A centralized clearinghouse (like the NRMP) establishes a unified timeline. No offers can be made early, and all preferences are processed simultaneously using the Gale-Shapley algorithm, eliminating the incentive to jump the gun.
Knowledge Checkpoint
- Define "market unraveling" and identify the incentives that cause decentralized matching markets to recruit earlier over time.
- Explain why the presence of "couples" (interdependent preferences) means a stable matching is mathematically no longer guaranteed to exist, and how the Roth-Peranson algorithm handles this in practice.
- Contrast applicant-proposing vs. employer-proposing algorithms and explain who benefits from each setup.
Course Map
Key People Index
- David Gale & Lloyd Shapley: Mathematicians who co-authored the seminal 1962 paper "College Admissions and the Stability of Marriage," proving that stable matchings always exist and formulating the Deferred-Acceptance algorithm. Shapley was awarded the 2012 Nobel Prize in Economic Sciences.
- Alvin E. Roth: Economist and Nobel laureate (2012) who applied Gale and Shapley's theoretical models to design real-world institutions, including the reorganization of the National Resident Matching Program (NRMP), school choice systems in New York City and Boston, and the creation of regional kidney exchange networks.
- Parag Pathak: MIT economist and key researcher in market design. Pathak worked directly alongside Al Roth to reform urban public school matching systems and is a primary expert on the application of matching algorithms to public policy.
- Herbert Scarf: Mathematician who developed the core concepts of indivisible goods allocation, laying the foundational mathematics that Gale later used to construct the Top Trading Cycles (TTC) algorithm.
Final Self-Assessment
Test your mastery of matching theory and market design by verifying you can answer or perform each of the following:
- I can explain why some markets must operate without prices and list at least three distinct real-world examples.
- I can define a "stable matching" and mathematically identify whether an arbitrary set of matched pairs is stable or contains blocking pairs.
- I can write out the steps of the Gale-Shapley algorithm and execute it by hand using preference lists for five agents on each side.
- I can explain why proposer-proposing deferred acceptance is strategy-proof for the proposing side but not necessarily for the receiving side.
- I can explain the mechanics of the Boston school choice mechanism and demonstrate exactly how it penalizes families who are honest about their school preferences.
- I can explain the step-by-step logic of the Top Trading Cycles (TTC) algorithm and trace cycles on a directed graph.
- I can describe how an altruistic kidney donor chain works and why it is less constrained than a standard closed kidney exchange cycle.
- I can explain "market unraveling," including how pre-emptive and exploding offers degrade market efficiency.
- I can explain why the inclusion of couples with joint preferences complicates the residency match algorithm and why a stable matching is not guaranteed under these conditions.