College admissions and the stability of marriage¶
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. American Mathematical Monthly, 69(1), 9-15.
Cited by¶
3 citations across 3 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.
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:1025004a91fd · see in the full table