The stable matching problem asks for a pairing between two equally sized groups in which no two participants would both rather be matched with each other than with their assigned partners. It was posed and solved by Gale and Shapley in 1962 in the context of college admissions and marriage (Gale–Shapley 1962). Their deferred acceptance algorithm underlies centralized clearinghouses such as the assignment of graduating medical students to hospital residencies, and the theory of stable allocations was recognized by the 2012 Nobel Memorial Prize in Economic Sciences awarded to Shapley and Roth.
Timeline of the results targeted here:
Fix . There are men and women, both indexed by . Each man ranks all women strictly: is the position of in 's list, position being most preferred; symmetrically each woman has . Both are bijections. A matching is a bijection from men to women. A pair blocks if and ; is stable if no pair blocks it.
The Gale–Shapley algorithm runs in rounds. A state records, for every man, how many women he has proposed to so far, and for every woman, her current provisional fiancé (if any). In each round every unengaged man proposes to the most preferred woman he has not yet proposed to, and every woman keeps the most preferred among her current fiancé and this round's suitors, rejecting the others. The Gale–Shapley outcome is the matching read off from the state after rounds.
This contains termination (all men are engaged after rounds), the fact that the final engagements form a bijection, and stability.
Existence of stable matchings is the foundation of two-sided matching theory, and the algorithmic proof is constructive. Man-optimality and woman-pessimality show that the proposing side is systematically favored, which is the reason the choice of proposing side matters in practice, as in the 1995 redesign of the residency match. The incentive results (milestones 5–8) explain why participants on the proposing side can safely report their true preferences while the receiving side cannot, and the lattice structure underlies efficient algorithms for enumerating and optimizing over stable matchings.
All results in this mission are classical and proved in the literature. The work here is formalization: a precise model of the round-based algorithm, machine-checked proofs of its correctness and optimality, and the incentive properties, which are usually argued informally.
The goal requires reasoning about an iterated state transformer rather than an abstract existence statement. The step that is usually waved away is the invariant that an unengaged man still has a woman left to propose to, which is what makes the bound and the bijectivity of the final engagements work. Man-optimality needs the invariant that no man is ever rejected by a woman who is his partner in some stable matching, which is not visible from the output alone. Group strategy-proofness is substantially harder than individual truthfulness: the known proofs go through a "blocking lemma" about matchings that are weakly preferred by all men.
Men and women are Fin n; preferences are strict total orders given as rank bijections Fin n ≃ Fin n; matchings are bijections Fin n ≃ Fin n. The algorithm is the round-based version described in the source: all unengaged men propose simultaneously in each round. The algorithm's output is fixed as the state after exactly rounds; termination within that bound is itself a milestone, so a wrong bound would make the goal false rather than vacuous. The case is included and is trivial. Incentive results compare Gale–Shapley outcomes of two instances that differ only in the lists of the deviating participants, with gains measured by the deviators' true lists.
The definitions are reusable for further missions on the same article (rural hospitals theorem, hospitals/residents problem). Contributions welcome: invariants of the algorithm, the blocking lemma, and alternative proofs of existence.
namespace StableMatching
theorem galeShapley_stable {n : ℕ} (I : Instance n) :
∃ μ : Matching n, I.IsGSOutcome μ ∧ I.IsStable μ := by sorry
end StableMatching
For every instance with men and women (strict preference lists), the Gale–Shapley (men-proposing deferred acceptance) algorithm is guaranteed to produce a stable matching: there is a bijection from men to women such that, after the algorithm's rounds, every man is engaged to , and has no blocking pair, i.e. there are no with preferring to and preferring to .
No open leaves. Every sub-goal is proved or awaiting decomposition.