How Matching Theory Shapes College Admissions, Residency, and Kidney Exchanges

What Is a Matching Market?

Traditional markets involve a seller offering a product and a buyer paying a price. In a matching market, both sides must choose each other; price is often irrelevant and the market must be sufficiently "thick" to give participants many options.

The core feature is two‑sided selection : each participant must be accepted by the other for a transaction to occur.

Three Key Elements of a Matching Market

Thickness – enough participants so that each agent has multiple potential matches.

Non‑congestion – participants have sufficient time and information to evaluate options.

Safety – agents can express true preferences without fear of penalty.

Mathematical Foundations of Matching Theory

Consider two finite sets: a set of men \(M\) and a set of women \(W\). Each man has a strict preference ordering over all women, and each woman has a strict ordering over all men.

A matching \(\mu\) is a function that pairs each man with at most one woman and each woman with at most one man. The matching is stable if there is no blocking pair \((m,w)\) such that both prefer each other to their current partners (or to being single).

Gale‑Shapley Deferred Acceptance Algorithm

In 1962, David Gale and Lloyd Shapley introduced the Deferred Acceptance (DA) algorithm, proving that a stable matching always exists.

Input: sets M (men) and W (women) with complete preference lists
Output: a stable matching μ

Initialize all agents as "free"
while there exists a free man m who has not been rejected by every woman:
    w = m's highest‑ranked woman who has not yet rejected him
    if w is free:
        w tentatively accepts m (engagement)
    else if w prefers m to her current fiancé m':
        w rejects m' and tentatively accepts m
        m' becomes free
    else:
        w rejects m
    remove w from m's preference list
return the set of engagements as μ

Algorithm Example

A 4‑by‑4 example (four men, four women) illustrates the dynamics. In each round, free men propose to their highest‑ranked woman who has not yet rejected them. Women tentatively accept the best proposal and reject the rest. The process continues until no free men remain, yielding a stable matching.

Current state after each round shows which agents are free and which are engaged.

Important Properties

Theorem 1 (Existence) : For any bipartite matching problem, the Gale‑Shapley algorithm terminates in a finite number of steps and produces a stable matching.

Theorem 2 (Optimality) : The matching produced by the proposing side (men in the example) is men‑optimal and women‑pessimal among all stable matchings.

Theorem 3 (Strategy‑proofness) : For the proposing side, truthfully reporting preferences is a dominant strategy and is group‑strategy‑proof; the receiving side may have incentives to misreport.

When Matching Markets Fail

Medical Residency Chaos

In the early 20th century U.S. medical residency market, hospitals began issuing offers earlier and earlier, creating a “market unraveling” where both hospitals and students faced severe information asymmetry and explosive‑deadline offers.

Solution: The National Resident Matching Program (NRMP)

Established in 1952, the NRMP uses a matching algorithm equivalent to Gale‑Shapley. Its design guarantees:

Stability – no blocking pairs.

Individual rationality – no participant receives a match worse than being single.

Strategy‑proofness for applicants – reporting true preferences is optimal.

Today over 40 000 graduates are placed annually, and the system has been refined to handle couples and other complexities.

Life‑Saving Matching Design

Kidney Exchange Model

Patients with willing but incompatible donors form pairs \((p_i, d_i)\). A compatibility matrix indicates which donor can give to which patient. The problem is modeled as a directed graph where vertices are pairs and an edge \(i\to j\) exists if donor \(d_i\) can donate to patient \(p_j\).

The objective is to select a collection of vertex‑disjoint cycles (often limited to length 3 or 4) that maximizes the number of transplanted kidneys. This is an NP‑hard problem, but integer‑programming approaches solve realistic instances efficiently.

Donation Chains

Introducing altruistic (non‑directed) donors creates chains that do not need to be executed simultaneously, allowing longer sequences and dramatically increasing the number of transplants.

Why Not Money?

Organ markets are deemed “repugnant” by society; ethical constraints prohibit buying kidneys, so market design must work within a no‑money framework.

School Choice Matching

Boston Mechanism Flaws

The Boston mechanism assigns students to schools by iteratively filling seats with first‑choice applicants, then second‑choice, etc. It is not strategy‑proof; families can gain by misreporting preferences, leading to inefficiency and inequity.

Reforms in New York and Boston

Both cities adopted the student‑optimal stable mechanism (the Gale‑Shapley student‑proposing version). Under this system, truthful reporting is a weakly dominant strategy for students, dramatically reducing the number of unassigned applicants and eliminating the “guess‑the‑game” pressure.

Takeaways

Increase market thickness – more options improve match quality.

Report preferences honestly – in well‑designed mechanisms this is strategically optimal.

Understand the other side’s criteria – matching is a two‑way process.

Allow sufficient decision time – avoid explosive‑deadline offers that force suboptimal choices.