Gale-Shapley Algorithm
- Introduced by
- David Gale, Lloyd Shapley
- Year
- 1962
- Type
- algorithm
- Family
- Game-theoretic
What does it do?
The Gale-Shapley algorithm solves the stable marriage problem: how to match two groups (e.g., medical residents to hospitals, students to schools) such that no pair prefers each other to their assigned partners.
Introduced by David Gale and Lloyd Shapley in 1962, the algorithm guarantees a stable matching in polynomial time through a deferred acceptance process where one side proposes sequentially and the other side responds, revising choices as better options arrive.
The intuition behind the method
Imagine matching doctors to hospitals. The algorithm works like a game of musical chairs: each doctor proposes to their most-preferred hospital; each hospital tentatively accepts the best doctor available. As hospitals receive better proposals, they revise their choices, potentially rejecting earlier acceptances. Doctors who are rejected propose to their next-preferred hospital. The process continues until no doctor wants to propose further and no hospital wants to trade their current match. The result is stable: no doctor-hospital pair would both prefer to be matched to each other rather than their assigned partners.
History
David Gale and Lloyd Shapley published their solution to the stable marriage problem in 1962, proving that stable matchings always exist for two-sided markets. Their algorithm spawned a vast literature on matching theory with applications spanning medicine, education, and labor markets. In 2012, Alvin Roth won the Nobel Prize in Economics for his experimental and theoretical work applying matching theory to real market design, validating the practical importance of the Gale-Shapley framework.
When to use it
Apply the Gale-Shapley algorithm when matching two-sided markets where stability is crucial: medical resident placement, student-to-school assignment, kidney exchange, labor market matching, or online dating markets. Use when there is a risk of matching instability (blocking pairs) that could unravel a matching after assignment. The algorithm is ideal when one side can move first with a strategic advantage.
Limitations and considerations
- Not Pareto optimal: the matching may not maximize total welfare; blocked pairs may exist that could all benefit from trading partners
- Strategic vulnerability: the proposing side can gain by misrepresenting preferences, while the responding side is truthful
- Asymmetry: outcomes depend heavily on which side proposes first
- Does not handle constraints: difficult to incorporate complex preferences (e.g., couples, regional preferences) without algorithmic modification
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Guaranteed stability: no blocking pairs exist in the final matching
- Polynomial time: O(n^2) complexity, making it efficient for large populations
- Simple implementation: easy to execute in practice with transparent preference collection
- Strategic incentives: the proposing side has a strategic advantage, preferring early proposals to later ones
- Universally applicable: works for any preference profiles without assuming convexity or transitivity
Applications
- Medical residency matching: pairing medical school graduates to hospital residency programs via NRMP
- School choice: assigning students to public schools based on preferences and capacity constraints
- Kidney exchange: matching organ donors and recipients to maximize compatible transplants
- Job market matching: connecting job seekers with employers in two-sided labor markets
- Online dating: matching users in dating platforms to improve match stability and user satisfaction
How it works
How it works
Create preference lists for all individuals in both groups, representing their ranking of the other side.
In each round, each unmatched person on the proposing side proposes to the highest-ranked person on the other side to whom they have not yet proposed.
Each person on the receiving side tentatively accepts the proposal if they are unmatched, or if the proposer ranks higher than their current partner, in which case they revoke the previous engagement.
The algorithm halts when every person is matched and no further proposals occur, yielding a stable matching.
Common pitfalls
- Assuming stability alone is sufficient for fairness or welfare; stable matchings can be highly skewed toward one side
- Confusing stability with optimality; a stable matching is not necessarily welfare-maximizing
- Overlooking the proposing side's strategic advantage: the proposing side's members tend to match to higher-ranked partners
- Forgetting that the algorithm assumes complete preference lists; incomplete preferences require modification
Frequently asked questions
Why is stability important in matching?
Without stability, matched pairs might later discover they prefer each other to their assigned partners, creating incentive to break the matching. Stable matchings prevent such blocking pairs, ensuring the matching persists without renegotiation.
Does the Gale-Shapley algorithm always produce the same matching?
No. Different preference lists or proposal orders can yield different stable matchings. However, there is always a 'man-optimal' stable matching (best for all proposers) and a 'woman-optimal' stable matching (best for all responders).
How does Gale-Shapley handle preferences over groups (e.g., couples)?
The standard algorithm does not directly handle couples or other constraints. Extensions like the couples algorithm exist but are more complex and may not guarantee stability for all preference profiles.
Related methods
Sources
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
Open DOI referenceCopied.Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.
Open DOI referenceCopied.