Matching theory

What Is Matching Theory?

Matching theory is a field within economics and game theory that studies how agents or entities are paired when monetary prices alone do not fully determine the allocation. It focuses on processes where individuals or organizations express preferences over potential partners, aiming to create stable and mutually beneficial pairings. Unlike traditional markets where supply and demand are balanced primarily through price adjustments, matching theory addresses scenarios where qualitative preferences, indivisibilities, and other frictions play a significant role in resource allocation.

Matching theory is particularly relevant in "two-sided" markets, involving two distinct sets of participants, each seeking to be matched with members of the other set. Examples include students applying to schools, doctors seeking residencies, or organ donors matched with recipients. The core objective is often to achieve a stable matching, meaning no two unmatched participants would prefer to be matched with each other over their current assignments, and no individual prefers to remain unmatched over their assigned partner.

History and Origin

The foundational work in matching theory was laid by mathematicians David Gale and Lloyd Shapley in their 1962 paper, "College Admissions and the Stability of Marriage." They introduced the concept of a stable marriage problem and proposed an algorithm, known as the Gale-Shapley deferred acceptance algorithm, to solve it. This algorithm demonstrates that a stable matching always exists for any set of preferences.¹⁴

While Gale and Shapley developed the theoretical underpinnings, it was economist Alvin E. Roth who, starting in the 1980s, brought matching theory into widespread practical application and empirical study. Roth investigated existing matching markets, such as the market for U.S. medical residents, discovering that successful real-world systems often employed variations of stable matching algorithms.¹³ His work, alongside Shapley's theoretical contributions, earned them the Nobel Memorial Prize in Economic Sciences in 2012 for "the theory of stable allocations and the practice of market design."¹² Roth's research focused on diagnosing market failures in these contexts and designing new rules to improve their efficiency, particularly where monetary prices are not used or are ethically constrained, such as in the allocation of human organs for transplant.¹¹

Key Takeaways

• Matching theory examines how agents are paired when preferences, rather than just prices, dictate outcomes.
• It primarily deals with "two-sided" markets where participants from two groups seek mutually agreeable matches.
• A central concept is "stable matching," where no pair of unmatched individuals would prefer to be together over their current assignments.
• The Gale-Shapley deferred acceptance algorithm guarantees the existence of a stable matching.
• Pioneers Lloyd Shapley and Alvin Roth were awarded the Nobel Prize for their contributions to this field.

Formula and Calculation

Matching theory does not typically involve a single universal formula like those found in corporate finance or investment analysis. Instead, it relies on algorithms to facilitate pairing based on stated or inferred preferences. The most famous of these is the Gale-Shapley Deferred Acceptance Algorithm.

Consider a simplified scenario with two groups: (M) (men) and (W) (women), each with ordered preference lists for members of the opposite group. The algorithm works as follows (men proposing):

1. Proposals: Each man proposes to the woman he ranks highest on his preference list who has not yet rejected him.
2. Responses: Each woman considers all proposals she has received. She tentatively accepts the proposal from the man she prefers most among those who have proposed to her, and she rejects all other proposals. If she has no proposals, she remains unengaged.
3. Iteration: This process repeats. In each round, unengaged men propose to the next woman on their list they haven't yet proposed to. Women always keep their current best tentative offer and reject new offers that are worse. If a woman receives a better offer than her current tentative match, she rejects her current tentative match and accepts the new, better offer.
4. Termination: The algorithm terminates when no man wishes to make any more proposals. At this point, all men and women who are tentatively matched form their final, stable pairs.

This iterative process ensures that eventually, a stable matching is achieved. The "proposing" side receives their most preferred stable matching, while the "receiving" side receives their least preferred stable matching among all stable outcomes.

Interpreting Matching Theory

Interpreting matching theory involves understanding that successful allocations in certain markets do not solely depend on price mechanisms. Instead, outcomes are shaped by the structure of preferences, the rules governing interactions, and the stability of the resulting pairings. A key insight is that an allocation is "stable" if no participants have an incentive to deviate from their assigned match.¹⁰ This concept of stability is crucial for the long-term viability and efficiency of these markets.

For example, in a medical residency match, if an intern and a hospital could unilaterally improve their situation by breaking their current match and forming a new one, the system would be unstable. Matching theory aims to design systems that prevent such "blocking pairs." The interpretation of a successful matching system often revolves around whether it yields stable outcomes, promotes economic efficiency, and discourages strategic manipulation, where participants might misrepresent their true preferences to achieve a better outcome.

Hypothetical Example

Consider a small city where four recent medical school graduates (A, B, C, D) are seeking residency positions at four hospitals (Hospital 1, Hospital 2, Hospital 3, Hospital 4). Each graduate has ranked their preferred hospitals, and each hospital has ranked its preferred graduates.

Graduate Preferences:

• A: H1 > H2 > H3 > H4
• B: H2 > H1 > H4 > H3
• C: H3 > H4 > H1 > H2
• D: H1 > H4 > H2 > H3

Hospital Preferences:

• H1: A > D > B > C
• H2: B > A > C > D
• H3: C > A > D > B
• H4: D > B > A > C

Using a simplified deferred acceptance algorithm where graduates propose:

Round 1:

• A proposes to H1.
• B proposes to H2.
• C proposes to H3.
• D proposes to H1.

Hospital Responses (tentative accepts in bold):

• H1: Receives proposals from A and D. Prefers A over D. H1 tentatively accepts A, rejects D.
• H2: Receives proposal from B. H2 tentatively accepts B.
• H3: Receives proposal from C. H3 tentatively accepts C.
• H4: Receives no proposals.

Round 2:

• D (rejected by H1) proposes to his next choice, H4.

Hospital Responses:

• H1: A is still tentatively accepted.
• H2: B is still tentatively accepted.
• H3: C is still tentatively accepted.
• H4: Receives proposal from D. H4 tentatively accepts D.

All graduates are now matched, and no one has been rejected. The algorithm terminates.

Final Stable Matching:

• A - H1
• B - H2
• C - H3
• D - H4

This outcome is a stable matching because no graduate and hospital, currently unmatched with each other, would both prefer to switch partners. For instance, A and H1 are matched. If A were with H2 and H1 were with D, they would both prefer to be with each other, indicating instability. The algorithm prevents such situations by ensuring that once a proposal is rejected, it's not reconsidered unless a better option for the receiver becomes available.

Practical Applications

Matching theory has numerous practical applications, particularly in contexts where monetary prices are not the primary mechanism for allocation or where goods are indivisible and heterogeneous. Some key areas include:

• Labor Markets: One of the earliest and most impactful applications is the National Resident Matching Program (NRMP) for medical residents in the U.S. This system uses a sophisticated matching algorithm to pair graduating medical students with hospital residency programs, accounting for preferences from both sides. Similar systems exist for other specialized labor markets.⁹
• School Choice Systems: Many public school districts, including those in New York City and Boston, employ matching algorithms to assign students to schools based on student preferences and school capacities/priorities. This helps ensure equitable resource allocation and student satisfaction.⁸
• Kidney Exchange Programs: Matching theory has been instrumental in designing systems for kidney donations. Since blood types and other factors often lead to incompatibility between a donor and their intended recipient, exchange programs use algorithms to find chains or cycles of donors and recipients who can exchange kidneys, enabling life-saving transplants that would otherwise not be possible.⁷ This highlights how market design can overcome significant real-world challenges where direct monetary transactions are ethically prohibited.
• Online Dating and Ride-Sharing Platforms: Although less formal than the previous examples, the underlying principles of matching theory can be observed in platforms like Uber or Airbnb, which efficiently match drivers with riders or hosts with guests based on proximity, preferences, and availability, even if explicit "preference lists" aren't exchanged in the same way.⁶

These diverse applications demonstrate the power of matching theory in addressing complex coordination problems and improving economic efficiency in various sectors.

Limitations and Criticisms

While matching theory has proven highly effective in many domains, it is not without limitations and criticisms. One significant challenge arises in situations where participants might engage in strategic manipulation, misrepresenting their true preferences to try and achieve a more favorable match. While the Gale-Shapley algorithm is "truth-telling" for the proposing side (meaning proposers have no incentive to lie about their preferences), the receiving side may have incentives to misrepresent their preferences, which can complicate the design of truly robust matching systems.⁵

Another critique concerns the information requirements of matching algorithms. Effective matching often requires participants to submit comprehensive and accurate preference lists, which can be burdensome or even impossible in large, complex markets. Furthermore, the privacy implications of collecting and processing such sensitive preference data are a growing concern, as existing algorithms may inadvertently reveal private information about participants' preferences or the history of negotiations.⁴

From a broader macroeconomics perspective, some economists argue that while matching theory accurately describes the process of forming relationships, standard models, particularly in labor economics, sometimes struggle to quantitatively explain large fluctuations in unemployment rates over the business cycle. This suggests that while the theoretical framework is sound, its predictive power in certain dynamic, real-world scenarios might be limited without further refinements. Despite these challenges, ongoing research in market design continues to explore ways to enhance robustness, privacy, and quantitative accuracy in matching models.

Matching Theory vs. Search Theory

Matching theory and search theory are related but distinct branches of economics. Both deal with the formation of relationships and address market frictions that prevent instantaneous, frictionless transactions. However, their primary focus and methodological approaches differ.

While search theory often examines the individual's decision to continue searching or accept an offer, matching theory then steps in to analyze how these searchers are ultimately paired in a collective system, especially when their preferences on the "other side" must be considered simultaneously. In essence, search theory explains how individuals find potential matches, while matching theory explains how the final matches are formed and sustained.

FAQs

What is a "stable" matching in matching theory?

A stable matching is one where no two individuals who are not currently matched with each other would both prefer to be matched with each other over their assigned partners. Additionally, no individual would prefer to remain unmatched over their current partner. This stability ensures that the chosen pairings are resilient to unilateral deviations.³

Why are prices not always sufficient in matching markets?

In many matching markets, the "goods" being exchanged are heterogeneous and indivisible, such as a specific job position, a school slot, or a human organ. Preferences extend beyond just monetary value, encompassing factors like location, culture, specific skills, or ethical considerations. In such cases, a simple price adjustment cannot clear the market efficiently, leading to the need for preference-based allocation mechanisms.²

What is the Gale-Shapley algorithm?

The Gale-Shapley algorithm is a deferred acceptance procedure that guarantees a stable matching can always be found in two-sided matching markets. It involves one side proposing to the other, and the receiving side provisionally accepting or rejecting proposals based on their preferences. This iterative process continues until a stable set of matches is achieved.

How does matching theory relate to market design?

Matching theory is a core component of market design. Market design is an applied field of economics that uses theoretical insights from matching theory (and game theory more broadly) to create or improve the rules and institutions of real-world markets, especially those where traditional price mechanisms fail. The goal is to design mechanisms that lead to efficient, stable, and fair outcomes.¹