Gale-Shapley Algorithm
Gale-Shapley Stable Marriage Algorithm · Also known as: Stable Marriage Problem, Deferred Acceptance, Two-Sided Matching
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.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
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.
Strengths & limitations
- 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
- 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
Frequently asked
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.
Sources
- Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15. DOI: 10.1080/00029890.1962.11989827 ↗
- Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628. DOI: 10.1287/moor.7.4.617 ↗
How to cite this page
ScholarGate. (2026, June 3). Gale-Shapley Stable Marriage Algorithm. ScholarGate. https://scholargate.app/en/game-theory/gale-shapley-algorithm
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Bayesian Nash EquilibriumGame Theory↔ compare
- Principal-Agent ModelGame Theory↔ compare
- Top Trading CyclesGame Theory↔ compare
- VCG MechanismGame Theory↔ compare