The Gale-Shapley Stable Matching Algorithm

The problem it solves: stable marriage

Suppose you have n proposers and n receivers, and every agent has ranked everyone on the other side from most to least preferred. A matching pairs each proposer with exactly one receiver. The matching is stable if it contains no blocking pair: a proposer p and receiver r who are not matched together but who each prefer the other to their current partner. A blocking pair is a latent instability — those two agents could ditch their assignments and both be better off, so the matching would not survive contact with self-interested agents.

David Gale and Lloyd Shapley posed and answered two questions in their 1962 paper College Admissions and the Stability of Marriage: does a stable matching always exist, and can we compute one efficiently? The surprising answer to both is yes — and the constructive proof is the algorithm.

How deferred acceptance works

The mechanism is called deferred acceptance because receivers never commit — they only tentatively hold their best offer so far, deferring the final decision until the process settles. It runs in rounds:

• Every proposer who is currently free proposes to the highest-ranked receiver on their list to whom they have not yet proposed.
• Each receiver looks at all proposals they hold plus any new ones, keeps their single most-preferred proposer (tentatively engaged), and rejects every other.
• A rejected proposer is free again and, next round, proposes to their next choice down the list.
• Repeat until no free proposer has anyone left to propose to. The tentative engagements become the final matching.

The two invariants that make it work:

• Proposers go down. A proposer only ever proposes in decreasing order of preference, and never proposes twice to the same receiver.
• Receivers only trade up. Once a receiver is engaged, any partner they later accept is strictly better than the one they held. A receiver's partner quality is monotonically non-decreasing over time.

These two facts are the entire correctness argument, and we unpack them below.

Why it always terminates — and always produces a stable matching

Termination. Each proposal is to a receiver the proposer has never proposed to before. There are only n receivers, so a single proposer can make at most n proposals. Across n proposers, the total number of proposals is at most n² — the loop cannot run forever, giving the O(n²) bound directly.

Everyone ends up matched (complete lists). Suppose some proposer p is free at the end. Then p has proposed to every receiver and been rejected by all. But a receiver only rejects when she already holds someone better — and she never lets go of an engagement. So every receiver is engaged, which means all n receivers are matched to n distinct proposers, so all proposers are matched. Contradiction. Hence the matching is perfect.

Stability. Suppose for contradiction that (p, r) is a blocking pair: p prefers r to his assigned partner, and r prefers p to hers. Because p prefers r, and proposers descend their list, p must have proposed to r earlier and been rejected (or dumped) in favor of someone r ranked higher. Since receivers only trade up, r's final partner is at least as good as that one — so r prefers her final partner to p. That contradicts the assumption that r prefers p. No blocking pair can exist.

Proposer-optimal, receiver-pessimal

A stable matching is rarely unique — a given instance can have many. Gale-Shapley does not return an arbitrary one. It returns the proposer-optimal stable matching: every proposer receives the best partner they could get in any stable matching, simultaneously. That is a strong and non-obvious statement — you might expect proposers to compete and force trade-offs, but it turns out all their best-case stable outcomes are mutually compatible.

The dual is uncomfortable: the same matching is receiver-optimal's opposite — receiver-pessimal. Every receiver gets the worst partner they could have in any stable matching. Running the algorithm with the sides swapped (receivers propose) produces a generally different matching that flips the advantage. So the choice of which side proposes is a substantive policy lever, not a formality. In the medical match, that debate is why the NRMP moved to an applicant-proposing algorithm.

The proof of proposer-optimality is by induction: no proposer is ever rejected by a receiver who is a valid partner (i.e. a partner in some stable matching). The first such rejection would create a blocking pair in that stable matching, so it can't happen — every rejection is by a receiver who prefers a stable partner, meaning proposers only lose receivers they could never have kept stably anyway.

The catch: you can lie — but only from one side

Since proposers get their best possible stable outcome, they have no incentive to misreport: proposer-optimal deferred acceptance is strategy-proof for proposers. Telling the truth is a dominant strategy. Receivers are not so lucky. A receiver can sometimes reject a proposal she'd actually accept under truth-telling, triggering a chain of rejections that ultimately lands her a better partner. Alvin Roth's impossibility result is the punchline: no stable matching mechanism can be strategy-proof for both sides at once. Someone always has a potential incentive to game the system — which is exactly why the identity of the proposing side is chosen with care in real markets.

Gale-Shapley vs related assignment algorithms

	Gale-Shapley	Hungarian algorithm	Hopcroft-Karp
Problem	Stable matching (ranked prefs)	Min-cost assignment (cost matrix)	Max cardinality bipartite matching
Objective	No blocking pair (stability)	Minimize total cost / maximize weight	Match as many pairs as possible
Input	Two ranked preference lists	n×n numeric cost matrix	Bipartite adjacency (no weights)
Time	O(n²)	O(n³)	O(E·√V)
Output	Proposer-optimal stable matching	Globally minimum-cost perfect matching	One maximum matching
Guarantees fairness?	Stable, but skewed to proposers	Optimal by total cost, not stability	N/A — no preferences

A key distinction: Gale-Shapley optimizes stability, not total welfare. The Hungarian algorithm minimizes a global cost but can (and often does) leave blocking pairs. A stable matching is not necessarily the one that maximizes the sum of everyone's satisfaction — stability and total welfare are different objectives that can pull in opposite directions.

How it works in Python

def gale_shapley(proposer_prefs, receiver_prefs):
    """
    proposer_prefs[p] = list of receivers, best first.
    receiver_prefs[r] = list of proposers, best first.
    Returns dict: receiver -> matched proposer (proposer-optimal).
    """
    n = len(proposer_prefs)

    # rank[r][p] = receiver r's ranking of proposer p (lower = better) -> O(1) compare
    rank = {r: {p: i for i, p in enumerate(prefs)}
            for r, prefs in receiver_prefs.items()}

    free = list(proposer_prefs)             # all proposers start free
    next_choice = {p: 0 for p in proposer_prefs}  # index of next receiver to try
    engaged = {}                            # receiver -> proposer

    while free:
        p = free.pop()
        r = proposer_prefs[p][next_choice[p]]  # p's best not-yet-tried receiver
        next_choice[p] += 1

        if r not in engaged:                # r is free -> tentatively engage
            engaged[r] = p
        elif rank[r][p] < rank[r][engaged[r]]:  # r prefers p -> trade up
            free.append(engaged[r])         # old partner becomes free
            engaged[r] = p
        else:                               # r keeps current partner -> p rejected
            free.append(p)

    return engaged

The trick that keeps each proposal O(1) is the precomputed rank table: comparing two proposers from a receiver's point of view becomes a single integer comparison instead of a linear scan of her list. Building rank costs O(n²), which matches the algorithm's overall bound. The total number of iterations of the while loop is the number of proposals — at most n².

A worked example (n = 3)

Proposers A, B, C and receivers X, Y, Z. Proposer preferences: A: X>Y>Z, B: X>Z>Y, C: X>Y>Z. Receiver preferences: X: B>A>C, Y: A>B>C, Z: A>B>C.

1. A proposes to X. X is free → X holds A.
2. B proposes to X. X ranks B (best) above A → X drops A, holds B. A is free again.
3. A proposes to Y (next choice). Y is free → Y holds A.
4. C proposes to X. X holds B and prefers B over C → C rejected. C is free.
5. C proposes to Y. Y holds A and prefers A over C → C rejected. C is free.
6. C proposes to Z. Z is free → Z holds C.

Final stable matching: A–Y, B–X, C–Z. Notice that X — the receiver everyone ranked first — ends with B, the proposer X liked most, illustrating how popular receivers do well while proposers may settle lower. Every proposer here got their proposer-optimal stable partner.

Common misconceptions and pitfalls

• "It maximizes total happiness." No — it maximizes stability. There can be a different matching with higher aggregate satisfaction that contains a blocking pair. Stability and social welfare are distinct goals.
• "The result is fair to both sides." It is proposer-optimal and receiver-pessimal. Whoever proposes is systematically advantaged. Fairness is a design choice made by picking the proposing side.
• "Any stable matching algorithm gives the same answer." An instance can have many stable matchings; Gale-Shapley returns a specific extreme (proposer-optimal), not a random one.
• "Both sides should just report honestly." Only the proposing side is guaranteed nothing to gain from lying. Receivers can sometimes benefit from strategic misreporting.
• "Incomplete or unequal lists break it." They don't — with unacceptable partners or unequal sides, the matching may be incomplete, but it is still stable. Just mark unlisted partners as unacceptable and stop proposing past them.
• "Ties in preferences are handled the same way." Strict preferences guarantee a stable matching and O(n²). With ties, definitions branch (weak vs strong vs super stability) and some variants become NP-hard.

History and the 2012 Nobel Prize

Gale and Shapley published the algorithm in The American Mathematical Monthly in 1962 as an elegant existence proof. For decades it looked like a pretty piece of combinatorics. Then Alvin Roth showed in the 1980s that the National Resident Matching Program — the clearinghouse that had matched U.S. medical graduates to residencies since 1952 — had independently converged on essentially a deferred-acceptance mechanism, and that markets which lacked such a stable mechanism tended to unravel. In the 1990s Roth led a redesign of the NRMP to an applicant-proposing algorithm that also handled couples and specialty constraints; today it matches on the order of 40,000 applicants per year.

Roth and colleagues went on to apply the same theory to public-school assignment in New York City and Boston and to kidney-exchange chains that save lives by matching incompatible donor-patient pairs. In 2012 Lloyd Shapley and Alvin Roth shared the Nobel Memorial Prize in Economic Sciences "for the theory of stable allocations and the practice of market design." (David Gale had died in 2008; the Nobel is not awarded posthumously.)