Matching Theory: A Mathematical Journey from Stable Marriage to the Nobel Prize

Every September, hundreds of thousands of high school graduates enter universities through centralized admission systems; every March, tens of thousands of medical school graduates are placed in teaching hospitals through the National Resident Matching Program (NRMP); in the United States, thousands of kidney failure patients receive new lives each year through kidney exchange programs. These seemingly disparate systems share a common mathematical foundation: Stable Matching Theory. This mathematical problem, first posed in 1962, was ultimately recognized with the 2012 Nobel Prize in Economics, becoming one of the most elegant examples of how mathematics can improve social institutions.

I. The Stable Marriage Problem: When "Defection" Becomes a Threat

In 1962, American mathematicians David Gale and Lloyd Shapley published a paper of just 9 pages in The American Mathematical Monthly, titled "College Admissions and the Stability of Marriage." This seemingly modest paper would go on to establish the entire field of matching theory.^[1]

The problem they posed was remarkably concise: suppose there are n men and n women, and each person has a preference ranking over all members of the opposite sex (from most preferred to least preferred). Our task is to pair everyone into n couples such that the resulting matching is "stable." But what does "stable" mean?

Definition: A matching is unstable if and only if there exists a man-woman pair (say, John and Mary) who are not matched together, but who would both prefer to leave their current partners and be with each other. Such a pair is called a "blocking pair." A stable matching is one in which no blocking pair exists.

In plain terms, a stable matching means: no one can "defect" to a better partner, because that better partner would not accept them. This sounds like a kind of "everyone in their place" social order -- each person may not end up with their top choice, but at least no pair of elopers will disrupt the entire system.

Gale and Shapley posed a crucial question: Does a stable matching always exist? They not only proved that the answer is yes, but also provided an elegant algorithm to find one.

II. The Deferred Acceptance Algorithm: Mathematical Elegance

The Gale-Shapley algorithm, also known as the "Deferred Acceptance Algorithm," is the cornerstone of matching theory. Here is how it works:

The Man-Proposing Version

1. Round 1: Each man proposes to the woman ranked highest on his preference list.
2. Each woman reviews all proposals she has received, tentatively "holds" her most preferred suitor (but does not yet permanently accept), and rejects the rest.
3. Subsequent rounds: Rejected men propose to the next woman on their preference list. A woman may "trade up" -- if a new proposer is preferable to the one she is currently holding, she releases her current hold and holds the new proposer instead.
4. Termination: The algorithm terminates when every man is either matched (or has been rejected by every woman), at which point each woman permanently accepts the man she is holding.

The algorithm is called "Deferred Acceptance" because women never immediately accept a proposal; instead, they keep their options open, waiting for potentially better suitors. This "comparison shopping" strategy is precisely what enables the algorithm to achieve a stable matching.

Proof of Existence

Why does this algorithm always produce a stable matching? The proof hinges on a contradiction argument:

Suppose the final matching contains a blocking pair (John, Mary), meaning both John and Mary would prefer to be with each other. This implies:

• John prefers Mary over his final match.
• Mary prefers John over her final match.

But according to the algorithm, John must have proposed to Mary at some point during the process (since he proposes in order of preference, and he prefers Mary). Given that John proposed to Mary, why didn't Mary end up with him? Only two possibilities exist:

1. Mary rejected John at that point because she was already holding someone she preferred more.
2. Mary later "traded up," releasing John in favor of a better suitor.

In either case, Mary's final match must be someone she prefers over John (since women only trade up, never down). This contradicts the assumption that "Mary prefers John." Therefore, no blocking pair can exist, and the matching is necessarily stable.^[2]

Man-Optimal vs. Woman-Optimal

There is a crucial asymmetry here: when men propose, the algorithm produces the man-optimal stable matching, meaning every man receives the best possible partner he could attain in any stable matching. Simultaneously, this matching is also woman-pessimal, the worst outcome for every woman across all stable matchings.

Conversely, if women propose and men hold, the result is woman-optimal and man-pessimal. This finding reveals a profound truth: the design choices of an algorithm implicitly determine the distribution of power. Who proposes and who waits determines who wins. This is not merely a mathematical theorem; it is the political economy of market design -- a fundamental choice within any decision-making framework.^[3]

III. The Story of Two Mathematicians

David Gale (1921-2008) was a mathematician at the University of California, Berkeley, renowned for his work in game theory and linear programming. Lloyd Shapley (1923-2016) was a mathematician and economist at the University of California, Los Angeles, widely recognized as one of the founders of game theory.

Their collaboration began with a simple question: could the college admissions system be designed more fairly? At the time, American college admissions were chaotic -- schools issued acceptance letters on different timelines, students were forced to make decisions without complete information, and the result was rampant "reneging" and "broken commitments." Gale and Shapley realized that this was fundamentally a matching problem.

Interestingly, although the paper's title mentions "College Admissions," almost the entire text discusses "the Stability of Marriage." This was Shapley's style -- he loved using simple metaphors to illuminate deep mathematical structures. The name "Stable Marriage" became the hallmark of this field from then on.^[4]

Shapley's other major contribution was the "Shapley Value" -- a method for fairly distributing the gains from cooperative games. If stable matching solves the problem of "how to match," the Shapley Value solves the problem of "how to divide." Together, these two bodies of work laid the mathematical foundation for modern market design.

IV. Alvin Roth: Bridging Theory and Practice

If Gale and Shapley created the theory, then Alvin Roth was the person who brought it into the real world. Roth, an economist at Harvard University (now at Stanford University), made his mark by discovering that many seemingly unrelated real-world institutions are in fact matching problems -- and can be analyzed and improved using the Gale-Shapley framework.

The U.S. Resident Matching System (NRMP)

One of Roth's most famous discoveries concerned the American resident matching system. In the 1950s, American medical education faced a serious problem: medical students were being snapped up by hospitals well before graduation, with some receiving offers as early as their second year. This "early recruitment arms race" left both sides without adequate information to make good decisions, generating widespread dissatisfaction.

In 1952, the National Resident Matching Program (NRMP) was established, adopting a centralized matching mechanism. Remarkably, Roth proved in 1984 that the algorithm used by the NRMP was essentially a variant of the Gale-Shapley algorithm -- even though the designers of the NRMP were unaware of Gale and Shapley's paper! This is a striking case of independent discovery.^[5]

However, Roth also identified a problem with the NRMP: the original design was the "hospital-proposing" version, meaning the outcome was optimal for hospitals and worst for students. In the 1990s, Roth redesigned the NRMP to a "student-proposing" version, producing outcomes more favorable to students. This reform remains in operation today, matching over 40,000 residents each year.^[6]

The New York City High School Admissions System

In 2003, Roth was invited to redesign the New York City high school admissions system. The existing system was a "chaotic market": students could apply to only 5 schools, and schools could strategically prioritize applicants who listed them as their first choice. The result: over 30,000 students were assigned each year to schools they had never applied to.

Roth's team introduced the Deferred Acceptance Algorithm, allowing students to rank up to 12 choices (later expanded to unlimited), while schools could no longer see where they ranked on a student's preference list. This design had two key advantages:

1. Strategy-proofness: Students had no need to strategically conceal their true preferences; honest reporting was the optimal strategy.
2. Stability: No student-school pair existed where both sides would prefer to "defect" from their assigned match.

After the reform, the number of students unmatched to any of their listed choices dropped from 30,000 to roughly 3,000. This stands as a classic case of market design improving public policy.^[7]

Kidney Exchange Matching

Roth's most humanitarian contribution may well be the kidney exchange program. Suppose Alice is willing to donate a kidney to her husband Bob, but they are blood-type incompatible. Meanwhile, Carol is willing to donate a kidney to her brother Dan, but they are also incompatible. If Alice's kidney is compatible with Dan, and Carol's kidney is compatible with Bob, they can "exchange" -- Alice donates to Dan, Carol donates to Bob, and all four benefit.

Roth and his collaborators designed an algorithm capable of finding such "exchange chains" on a national scale. This is not a standard stable matching problem (because kidney exchange involves a "simultaneity" constraint -- all surgeries must be performed at the same time, lest someone renege), but Roth creatively adapted the theoretical framework to solve it.

To date, this system has saved thousands of lives. It is perhaps one of the most direct examples of mathematics saving human lives.^[8]

V. The 2012 Nobel Prize in Economics

In 2012, the Royal Swedish Academy of Sciences awarded the Nobel Prize in Economics to Lloyd Shapley and Alvin Roth for "the theory of stable allocations and the practice of market design." This was the highest honor for matching theory and the formal establishment of "Market Design" as a recognized field.^[9]

The award citation specifically emphasized what makes this research unique: it is not about traditional price-based markets, but about "markets without prices." In college admissions, resident matching, and organ donation, we cannot use money to buy and sell positions or organs (it would be both immoral and illegal). Yet matching problems persist, and they equally require effective mechanisms to resolve them. The Gale-Shapley framework provides exactly such a tool.

It is worth noting that David Gale passed away in 2008, never witnessing this honor. The Nobel Prize is not awarded posthumously, but everyone acknowledges his pioneering contribution.

VI. Mathematical Depth: Three Theorems

For readers wishing to understand matching theory at a deeper level, here are three core theorems:

Theorem 1: Existence of Stable Matchings

Theorem: For any finite two-sided matching problem, a stable matching always exists.

Proof: The Gale-Shapley algorithm terminates in a finite number of steps and produces a stable matching (as demonstrated above). Since the algorithm is constructive, this simultaneously proves existence.

Theorem 2: Proposer-Optimality

Theorem: The Deferred Acceptance Algorithm (with men as proposers) produces a matching that is optimal for every man among all stable matchings; simultaneously, it is the worst for every woman among all stable matchings.

The implication of this theorem is: stable matchings are generally not unique (there are usually many), but the Deferred Acceptance Algorithm selects the one most favorable to the proposing side.^[10]

Theorem 3: Strategy-Proofness

Theorem: In the Deferred Acceptance Algorithm, truthful preference reporting is a dominant strategy for the proposing side. That is, regardless of what others report, proposers have no incentive to misrepresent their preferences.

This is the gold standard of market design: a good mechanism should allow participants to succeed without "gaming the system" -- honesty is the best strategy. However, this theorem comes with an important caveat: the receiving side does not enjoy strategy-proofness. Women can sometimes obtain better outcomes by strategically modifying their preference lists, which is why real-world matching system designs require careful handling.^[11]

VII. Extensions: Beyond One-to-One Matching

Real-world matching problems are often more complex than the "Stable Marriage" setting. Here are several important extensions:

Many-to-One Matching: School Admissions

In college admissions, a school can admit multiple students, but each student can attend only one school. This is a "many-to-one matching" problem. The Gale-Shapley algorithm generalizes directly: we simply give each school a "quota" and allow it to hold up to that number of applicants during the algorithm. The definition of stability is adjusted accordingly: no student-school pair both wish to "swap" their current assignment.

Matching with Couples

A special challenge in resident matching is "couples matching": two medical students who are married wish to be assigned to hospitals in the same city. This greatly increases the complexity of the problem, and may even cause stable matchings to cease to exist. Roth and his colleagues developed specialized algorithms to handle such cases, but they must accept "approximate stability" rather than perfect stability.^[12]

The Special Nature of Kidney Exchange

Kidney exchange is not a standard two-sided matching but instead involves "exchange cycles." A 3-way exchange means three donor-recipient pairs swap simultaneously; longer chains can help more people, but the requirement that all surgeries occur simultaneously becomes increasingly difficult to satisfy. One of Roth's innovations was introducing a "non-directed donor" -- a stranger willing to selflessly donate a kidney -- as the starting point of an exchange chain, dramatically increasing the number of possible matches.

VIII. Applications and Lessons for Taiwan

Taiwan's centralized university admission system is, at its core, a matching problem. The current system uses a "student-priority" preference-based allocation (similar to the student-proposing version of Deferred Acceptance), which is relatively favorable to students. However, Taiwan's system has its own particularities:

• Exam scores as the sole ranking criterion: Unlike the holistic review process in the United States, Taiwan has traditionally determined admissions based on exam scores alone. This simplifies schools' "preferences" but sacrifices other considerations.
• Star Plan and Individual Application: These channels introduce more elements of "bilateral choice," bringing the system closer to the Gale-Shapley framework.
• Strategic behavior: Students still engage in strategic considerations when filling out their preferences (e.g., "score-cutoff analysis"), indicating that the system has not yet achieved full strategy-proofness.

From the perspective of matching theory, Taiwan's higher education admissions system still has room for improvement -- particularly in enabling students to express their preferences more honestly and reducing the anxiety of "gambling on school choices."

IX. Conclusion: How Mathematics Can Improve Social Institutions

The story of matching theory is a model of the perfect union between mathematics and social science. A pure mathematics problem from 1962, developed over decades, ultimately changed the life trajectories of millions -- from entering the school of their dreams to receiving life-saving organs.

This story offers several profound lessons:

1. Good institutional design can reduce "rat races": When the rules are clear and honest reporting is the optimal strategy, participants need not expend energy gaming the system and can focus on what truly matters.
2. Mathematics is not just computation; it is a design tool: The Gale-Shapley algorithm does more than solve a problem -- it reveals which problems are solvable, what properties solutions possess, and what consequences design choices entail.
3. Bridging theory and practice requires someone to build the bridge: Shapley created the theory; Roth brought it into reality. The value of academic research often depends on such "translators" to be realized.

Looking back on this history, perhaps the most moving insight is this: when we design institutions thoughtfully, mathematics can become an instrument of justice. In markets without prices, stable matching provides a form of fairness -- everyone receives the best outcome the system can offer them, and no one is unfairly left behind.

This is the core conviction of the field of "Market Design": we need not passively accept existing institutions. Using the tools of mathematics and economics, we can design better rules of the game.