Gale–Shapley algorithm

Gale–Shapley algorithm
Name	Gale–Shapley algorithm
Class	Stable matching
Data	Preference lists
Time	$O(n^2)$
Space	$O(n^2)$
Authors	David Gale and Lloyd Shapley
Year	1962
Journal	The American Mathematical Monthly

Gale–Shapley algorithm. The Gale–Shapley algorithm, also known as the deferred acceptance algorithm, is a seminal procedure in game theory and computer science for solving the stable matching problem. First published in 1962 by mathematicians David Gale and Lloyd Shapley in The American Mathematical Monthly, it guarantees to find a stable marriage for two equally sized sets of participants given their ranked preferences. Its profound theoretical guarantees and practical efficiency have led to its widespread adoption in real-world systems, most notably the National Resident Matching Program which places medical graduates into hospital residencies.

Overview

The algorithm addresses the classic stable marriage problem formulated by David Gale and Lloyd Shapley. The problem involves two disjoint sets, such as an equal number of men and women, where each individual ranks all members of the opposite set in strict order of preference. A matching is considered stable if there is no pair who would both prefer each other to their current assigned partners. The Gale–Shapley algorithm is proven to always terminate with such a stable matching. Its operation is often framed in a proposal-and-response paradigm, where one set (traditionally termed the proposers) sequentially makes offers to the other set (the reviewers). The algorithm's deterministic nature and polynomial-time complexity distinguish it from more computationally difficult problems in combinatorial optimization.

Algorithm description

The procedure executes in discrete rounds. One group is designated as the proposers (e.g., suitors) and the other as the reviewers (e.g., reviewers). Each proposer begins free and has a list of all reviewers in order of preference. Similarly, each reviewer has a ranked list of all proposers. In each round, every free proposer proposes to their most-preferred reviewer to whom they have not yet proposed. Each reviewer then considers all current proposals, temporarily accepts the one from their highest-ranked proposer, and rejects all others, leaving those proposers free for the next round. A reviewer who is already tentatively engaged will reject any new proposal from a proposer they rank lower than their current tentative match. This process repeats until no proposer is free, at which point all tentative acceptances become final. The resulting bijection is the algorithm's output matching.

Properties and correctness

The Gale–Shapley algorithm possesses several important mathematical properties. First, it is guaranteed to terminate within $O(n^2)$ steps for $n$ participants per group. Second, it always produces a stable matching, a fact proven by Lloyd Shapley and David Gale using an invariant argument. Third, the matching is proposer-optimal, meaning it is stable and every proposer gets the best possible partner they could have in any stable matching. Conversely, it is reviewer-pessimal, meaning each reviewer receives the worst partner they could have in any stable matching. This optimality property is a direct consequence of the asymmetric roles in the procedure. The proof of correctness often employs techniques from discrete mathematics and is a standard topic in courses on algorithm design.

Applications

The most famous real-world implementation is the National Resident Matching Program, which uses a version of the algorithm to match medical school graduates with residency programs at teaching hospitals. Similar systems are used for assigning students to schools in New York City and Boston public school choice programs. The algorithm is also employed in matching donor kidneys to recipients through paired kidney exchange programs. In technology, it underpins mechanisms for assigning users to servers in distributed systems and for forming stable pairs in certain online dating platforms. The Nobel Memorial Prize in Economic Sciences awarded to Lloyd Shapley and Alvin E. Roth in 2012 highlighted the algorithm's immense practical impact in market design.

Variants and extensions

Many extensions of the classical problem have been studied. The hospital/resident problem allows one side (hospitals) to have multiple positions, a model directly used by the National Resident Matching Program. The stable roommates problem involves a single set where each agent ranks all others, which does not always admit a stable solution. Researchers like Alvin E. Roth have explored versions with incomplete lists and ties in preferences. The college admissions problem is another generalization. Work by Donald Knuth and Robert W. Irving has further analyzed its structural properties. Algorithmic variants also consider different optimization goals, such as finding the egalitarian stable matching or minimizing regret, leading to active research areas in theoretical computer science.

History and impact

The algorithm was first described in the 1962 paper "College Admissions and the Stability of Marriage" by David Gale and Lloyd Shapley. While initially a theoretical contribution in mathematical economics, its practical potential was recognized decades later by Alvin E. Roth, who successfully redesigned the National Resident Matching Program based on its principles. This application demonstrated the power of game theory to solve concrete societal problems, a field now known as market design. The 2012 Nobel Memorial Prize in Economic Sciences jointly awarded to Lloyd Shapley and Alvin E. Roth cemented the algorithm's status as one of the most influential ideas in both economics and computer science. Its study remains central in courses at institutions like Stanford University and the Massachusetts Institute of Technology.

Category:Algorithms Category:Game theory Category:Matching theory