Gale–Shapley algorithm

Gale–Shapley algorithm is an algorithm for producing a stable matching between two equal-sized sets of agents based on ranked preferences. It was introduced by David Gale and Lloyd Shapley and formalized the concept of stability in two-sided matching, influencing research in economics, computer science, and operations research. The procedure, often called deferred acceptance in applied settings, underpins mechanisms used by institutions and markets for assigning positions and resources.

History

The algorithm was published in a 1962 paper by David Gale and Lloyd Shapley that addressed the stable marriage problem and related issues in cooperative game theory. The result drew on antecedents in combinatorics and optimization studied by Paul Erdős, Ronald Fisher, and researchers at RAND Corporation, and it catalyzed later work by scholars including Alvin Roth, Marilda Sotomayor, and Alvin E. Roth's collaborators on market design at Harvard University and Stanford University. The 1990s and 2000s saw renewed interest after applications in the National Resident Matching Program and redesign efforts involving teams at Massachusetts General Hospital, New York City Department of Education, and research groups led by Alvin Roth and Elliott Lieb (note: collaborative networks included economists from University of Pittsburgh, University of Chicago, Princeton University, and Yale University). The theoretical foundations influenced later results such as the Shapley value and earned Lloyd Shapley a Nobel Memorial Prize in Economic Sciences jointly with Alvin Roth.

Algorithm

The procedure operates on two disjoint sets of participants, historically labeled proposers and reviewers, with strict preference lists. In the canonical description proposers iteratively propose to the highest-ranked reviewer who has not yet rejected them; reviewers tentatively accept the best proposal they have received and reject inferior ones. This iterated deferred acceptance continues until no proposer wishes to make further proposals, producing a stable matching. The algorithm is commonly presented in textbooks by authors from MIT Press, Princeton University Press, and Cambridge University Press and is implemented in software developed at institutions such as Microsoft Research, Google, and university departments including Stanford University Department of Computer Science and Harvard University Department of Economics.

Properties and correctness

Gale and Shapley proved that the algorithm always terminates with a stable matching and that the resulting matching is optimal for all proposers and pessimal for all reviewers under strict preferences. The proof uses invariants on proposal sequences and dominance relations studied in earlier work by Richard Bellman, John von Neumann, and Oskar Morgenstern on games and optimization. The algorithm is strategy-proof for proposers under certain informational assumptions, a result extended in mechanism design literature by researchers at University of Chicago and London School of Economics. Counterexamples demonstrating manipulability by reviewers or under incomplete preferences were explored by teams at University of California, Berkeley and University of Oxford.

Variants and extensions

Multiple variants extend the core idea to many-to-one and many-to-many settings, including versions used for hospital residency matches and school choice. Key extensions include the hospital/residents algorithm, ties and incomplete lists models, and versions with couples or complementarities, each analyzed by scholars at Johns Hopkins University, Columbia University, and Yale University. Computational complexity results relating to NP-hardness and approximation were developed in collaborations involving researchers from Bell Labs, IBM Research, and Carnegie Mellon University. Market-design adaptations incorporate monetary transfers, matching with contracts, and matching under uncertainty, studied by teams at Princeton University and Massachusetts Institute of Technology.

Applications

Practical deployments include the National Resident Matching Program in the United States, centralized student assignment systems in New York City, centralized school choice programs in Boston, centralized clearinghouses for organ exchange networks analyzed by groups at Harvard Medical School and University of Pennsylvania, and allocation mechanisms at Google, Facebook, and public sector agencies. The algorithm informs course allocation at universities such as University of Michigan and University of Cambridge, and has been used in spectrum allocation and labor market platforms influenced by research at Stanford Graduate School of Business and Wharton School.

Category:Algorithms Category:Matching theory