deferred_acceptance
def
Men-proposing deferred acceptance (Gale-Shapley): the man each woman ends up with, given each man's ranking of the women and each woman's ranking of the men (0 = best).
Statement
def deferred_acceptance {nm nw : ℕ} (rm : Fin nm → Fin nw → Fin nw) (rw : Fin nw → Fin nm → Fin nm) : Fin nw → Option (Fin nm)
- Defined in
- College Admissions and the Stability of Marriage (1962), men-proposing deferred acceptance; It's Not All Black and White: Degree of Truthfulness for Risk-Avoiding Agents, arXiv:2502.18805 v3, Def. 3.1 and Sec. 8.1
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Built on 1
- da_runOne run of men-proposing deferred acceptance with a step budget: each step the first free man with proposals left proposes to his next…
- Used by 2
- da_woman_k_known_safely_manipulableIn men-proposing deferred acceptance with nm men, nw women and complete rankings (no truncation), some woman who knows the rankings of k…
- da_three_by_three_three_known_safely_manipulableIn the 3x3 market with complete rankings, a woman who knows three agents can safely and profitably manipulate men-proposing deferred…
Lean source view module on GitHub
/-- Men-proposing deferred acceptance (Gale-Shapley): the man each woman ends up with. With complete rankings every man makes at most `nw` proposals, so `nm * nw` steps suffice. -/ def deferred_acceptance {nm nw : ℕ} (rm : Fin nm → Fin nw → Fin nw) (rw : Fin nw → Fin nm → Fin nm) : Fin nw → Option (Fin nm) := da_run rm rw (nm * nw + 1) (fun _ => none) (fun _ => 0)