College Admissions and the Stability of Marriage¶
Gale, D., & Shapley, L. S. (1962). College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69(1), 9-15.
Cited by¶
4 citations across 4 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Incentive Compatibility
- The Vickrey-Clarke-Groves (VCG) mechanism — Vickrey (1961), Clarke (1971), Groves (1973) — the second-price sealed-bid auction, the Deferred Acceptance algorithm (Gale-Shapley 1962)
This sourceFoundational stable-marriage paper: proves via the deferred-acceptance algorithm that a stable matching always exists for any preference profile on two sides and can be found constructively in polynomial time, covering instances from doctors-to-hospitals to abstract bipartite matching.
- The Vickrey-Clarke-Groves (VCG) mechanism — Vickrey (1961), Clarke (1971), Groves (1973) — the second-price sealed-bid auction, the Deferred Acceptance algorithm (Gale-Shapley 1962)
- Mechanism Design
- The Deferred Acceptance algorithm is elegant precisely because it is a mechanism — agents state preferences, the algorithm computes stable allocations, and truth-telling is an equilibrium strategy without need for external enforcement.
This sourceFoundational stable-marriage paper: proves via the deferred-acceptance algorithm that a stable matching always exists for any preference profile on two sides and can be found constructively in polynomial time, covering instances from doctors-to-hospitals to abstract bipartite matching.
- The Deferred Acceptance algorithm is elegant precisely because it is a mechanism — agents state preferences, the algorithm computes stable allocations, and truth-telling is an equilibrium strategy without need for external enforcement.
- Two-Sided Matching
- The pattern was first made precise by Gale and Shapley (1962) in their stable marriage problem, which proved that for any set of preference rankings on two sides a stable matching always exists and can be found constructively.
This sourceFoundational stable-marriage paper: proves via the deferred-acceptance algorithm that a stable matching always exists for any preference profile on two sides and can be found constructively in polynomial time, covering instances from doctors-to-hospitals to abstract bipartite matching.
- The pattern was first made precise by Gale and Shapley (1962) in their stable marriage problem, which proved that for any set of preference rankings on two sides a stable matching always exists and can be found constructively.
Mechanisms¶
- Two-Sided or Multi-Sided Matching
- Then it collects ranked lists from both sides and runs deferred acceptance — students propose to their top labs, labs tentatively hold their most-preferred applicants up to capacity and reject the rest, and rejected students propose down their lists, iterating until no proposals remain.
This sourceSpecifies the deferred-acceptance procedure using both sides’ rankings, tentative capacity-limited holds, rejections, and repeated proposals until the process terminates.
- Then it collects ranked lists from both sides and runs deferred acceptance — students propose to their top labs, labs tentatively hold their most-preferred applicants up to capacity and reject the rest, and rejected students propose down their lists, iterating until no proposals remain.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Not recorded. Neither this nor any other of the 4 citations of this work carries a recorded support check.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:b71d47f6e4f9 · see in the full table