Gale–Shapley Algorithm

Gale–Shapley algorithm (also known as the deferred-acceptance algorithm) is a polynomial-time combinatorial mechanism within computation and algorithms and algorithmic game theory that resolves the two-sided stable matching problem in O(n²) time. Introduced by mathematician David Gale and economist Lloyd S. Shapley in their landmark 1962 paper "College Admissions and the Stability of Marriage," the algorithm constructively proves that every two-sided market with complete, transitive ordinal preference rankings admits at least one stable matching—a bijection in which no unmatched pair of agents would both prefer each other over their assigned partners.

Through an iterative sequence of proposals from one side of the market (proposers) and tentative holds or rejections by the other side (reviewers), the deferred-acceptance mechanism converges in at most n² − n + 1 proposals. Beyond guaranteeing stability, the matching produced by the Gale–Shapley algorithm achieves an extremal algebraic position within the distributive lattice of all stable matchings: it is simultaneously proposer-optimal (assigning every proposer the highest-ranked partner attainable in any stable matching) and reviewer-pessimal, which induces dominant-strategy incentive compatibility (truthfulness) for the proposing side. For this foundational contribution to market design—which underpins the National Resident Matching Program (NRMP), public school choice systems, and kidney exchange clearinghouses—Lloyd Shapley and Alvin E. Roth were awarded the 2012 Nobel Memorial Prize in Economic Sciences.

Blocking Pairs and the Stable Matching Model

Consider two disjoint finite sets of agents of equal cardinality |P| = |R| = n: a set of proposers P = {p₁, p₂, …, p_n} and a set of reviewers R = {r₁, r₂, …, r_n}. Each proposer p ∈ P holds a strict, complete ordinal preference ordering >_p over all reviewers in R, and each reviewer r ∈ R holds a strict, complete ordinal preference ordering >_r over all proposers in P.

A matching μ : P ∪ R → P ∪ R is a one-to-one correspondence between P and R such that μ(p) = r if and only if μ(r) = p. A pair (p, r) ∈ P × R not matched to each other under μ (that is, μ(p) ≠ r) forms a blocking pair (or instability) if both agents prefer each other to their assigned partners under μ:

If a matching μ contains a blocking pair (p, r), both p and r have a mutual incentive to defect from the central clearinghouse assignment and match privately with each other, causing market unraveling. A matching μ is defined as stable if it contains zero blocking pairs.

Iterative Deferred-Acceptance Procedure

The proposer-proposing Gale–Shapley algorithm executes as follows:

1. Initialization: Every proposer p ∈ P and reviewer r ∈ R is initialized as unmatched (free), and each proposer maintains a pointer to the top unproposed reviewer on their preference list.
2. Proposal Step: While there exists a free proposer p who has not yet proposed to every reviewer, p proposes to the highest-ranked reviewer r on >_p to whom p has not previously proposed.
3. Deferred-Acceptance Evaluation:
   • If reviewer r is currently free, r tentatively accepts the proposal, creating a provisional engagement (p, r).
   • If reviewer r is currently engaged to another proposer p' and prefers the new proposer (p >_r p'), then r breaks the engagement with p' (returning p' to the free pool) and tentatively engages with p.
   • Otherwise (p' >_r p), reviewer r rejects p, who remains free and advances their preference pointer.
4. Termination: When no free proposers remain, all tentative engagements are finalized as the output matching μ_P.

Monotonicity Invariants and Quadratic Complexity Bound

Two structural monotonicity invariants govern the execution of the Gale–Shapley algorithm:

• Reviewer Improvement Invariant: Once a reviewer r receives their first proposal, r remains engaged for the rest of the algorithm, and the sequence of tentative partners held by r monotonically improves according to >_r.
• Proposer Deterioration Invariant: The sequence of reviewers to whom a proposer p proposes monotonically descends along >_p, because p never proposes to the same reviewer twice.

Because each of the n proposers can propose to at most n reviewers, the total number of proposals cannot exceed n² (more tightly, at most n(n − 1) + 1 proposals, since the moment n − 1 reviewers have received proposals, the final n-th reviewer must accept the very next proposal directed to them). By representing each proposer's preference list as an array and each reviewer's preference list as an inverse ranking array rank[r][p] ∈ {1, …, n}, each proposal and comparison executes in O(1) time, yielding Θ(n²) worst-case time and Θ(n²) space complexity.

Proof of Stability and Proposer-Optimality

Suppose for contradiction that the final matching μ_P contains a blocking pair (p, r) where r >_p μ_P(p) and p >_r μ_P(r). Because p proposes in decreasing order of preference and ended up matched to μ_P(p), proposer p must have proposed to r during some earlier iteration and been rejected by r in favor of some proposer p' with p' >_r p. By the reviewer improvement invariant, r's final partner satisfies μ_P(r) ≥_r p' >_r p, contradicting p >_r μ_P(r). Hence no blocking pair can exist.

Furthermore, a reviewer r is called a valid partner for p if some stable matching assigns p to r. Induction on the rejection sequence proves that no proposer is ever rejected by a valid partner during the proposer-proposing Gale–Shapley algorithm. Consequently, every proposer p is matched in μ_P to their highest-ranked valid partner across the entire distributive lattice of stable matchings (proposer-optimality), while simultaneously every reviewer r receives their lowest-ranked valid partner (reviewer-pessimal property).

Strategy-Proofness and the Impossibility Theorem

In mechanism design, Lester Dubins and David Freedman (1981) and Alvin Roth (1982) proved two foundational incentive theorems for the Gale–Shapley mechanism:

1. Truthfulness for Proposers: Under the proposer-proposing deferred-acceptance mechanism, reporting true preferences >_p is a weakly dominant strategy for every proposer p ∈ P; no unilateral misrepresentation of preferences by p can yield a partner strictly preferred to μ_P(p).
2. Roth's Impossibility Theorem: No stable matching mechanism exists for which truth-telling is a dominant strategy for both sides of the market simultaneously. Whenever the stable matching lattice contains more than one element (μ_P ≠ μ_R), at least one reviewer r can profitably truncate their preference list to force a better stable partner.

Medical Residency Clearinghouses, School Choice, and Content Delivery Networks

Since 1952, the National Resident Matching Program (NRMP) in the United States has matched over 40,000 graduating physicians annually to hospital residency programs using an algorithm mathematically equivalent to Gale–Shapley (redesigned by Roth and Elliott Peranson in 1997 to shift to applicant-proposing order and accommodate married couples). Public school districts in New York City, Boston, and Chicago adopted student-proposing deferred acceptance to eliminate strategic gaming by parents. In distributed computing and cloud infrastructure, Akamai Technologies deploys deferred-acceptance algorithms at the network edge to match billions of client DNS requests to globally distributed content delivery servers subject to latency rankings and server capacity quotas.

Does the order in which free proposers make proposals change the final matching?

No. Although the algorithm description allows any free proposer to be chosen at each step (such as via a first-in-first-out queue or a stack), the Gale–Shapley algorithm is order-independent: every execution order rejects the exact same set of impossible pairs and terminates at the identical unique proposer-optimal stable matching μ_P.

How can we test whether a given market instance has a unique stable matching?

Run the Gale–Shapley algorithm twice: once with proposers P proposing to reviewers R to obtain the proposer-optimal matching μ_P, and once with reviewers R proposing to proposers P to obtain the reviewer-optimal matching μ_R. Because the set of all stable matchings forms a distributive lattice under Conway's partial order with top element μ_P and bottom element μ_R, the market admits a unique stable matching if and only if μ_P = μ_R.

What happens when preference lists are incomplete or contain ties?

When agents are allowed to declare certain partners unacceptable (incomplete lists), a stable matching always exists and the Rural Hospitals Theorem (Roth, 1986) proves that the set of matched agents—and the number of filled positions in each under-subscribed hospital—is identical across every stable matching. When preference lists contain ties (indifferences), a weakly stable matching always exists via arbitrary tie-breaking, whereas deciding the existence of a super-stable or strongly stable matching requires specialized polyhedral and graph-matching methods.

1. Gale, D., & Shapley, L. S. (1962). "College admissions and the stability of marriage." The American Mathematical Monthly, 69(1), 9–15. https://doi.org/10.2307/2312726
2. Dubins, L. E., & Freedman, D. A. (1981). "Machiavelli and the Gale–Shapley algorithm." The American Mathematical Monthly, 88(7), 485–494. https://doi.org/10.2307/2321753
3. Roth, A. E. (1982). "The economics of matching: Stability and incentives." Mathematics of Operations Research, 7(4), 617–628. https://doi.org/10.1287/moor.7.4.617
4. Gusfield, D., & Irving, R. W. (1989). The Stable Marriage Problem: Structure and Algorithms. MIT Press. https://mitpress.mit.edu/9780262515528/the-stable-marriage-problem/
5. Roth, A. E., & Peranson, E. (1999). "The redesign of the matching market for American physicians: Some engineering aspects of economic design." American Economic Review, 89(4), 748–780. https://doi.org/10.1257/aer.89.4.748