AFTD Auto-Formalizing Theoretical Domains

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

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)
See it in the graphDiscuss this resultChallenge it