AFTD Auto-Formalizing Theoretical Domains

da_run

def

One run of men-proposing deferred acceptance with a step budget: each step the first free man with proposals left proposes to his next woman, who keeps whichever of him and her current man she ranks better.

Statement

def da_run {nm nw : ℕ} (rm : Fin nm → Fin nw → Fin nw) (rw : Fin nw → Fin nm → Fin nm)
    (fuel : ℕ) (hold : Fin nw → Option (Fin nm)) (nxt : 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
Used by 2
  • deferred_acceptanceMen-proposing deferred acceptance (Gale-Shapley): the man each woman ends up with, given each man's ranking of the women and each woman's…
  • Polynomial.physHermiteThe physicist's Hermite polynomials are defined as polynomials over ℤ in X recursively with physHermite 0 = 1 and…

Lean source view module on GitHub

/-- One run of men-proposing deferred acceptance with a step budget. `rm m w` is the rank man `m` gives woman `w` and `rw w m` the rank woman `w` gives man `m` (0 = best). `hold w` is the man woman `w` currently holds and `nxt m` how many proposals man `m` has made. Each step, the first free man with proposals left proposes to the woman he ranks `nxt m`; she keeps whichever of him and her current man she ranks better. -/
def da_run {nm nw : ℕ} (rm : Fin nm → Fin nw → Fin nw) (rw : Fin nw → Fin nm → Fin nm)
    (fuel : ℕ) (hold : Fin nw → Option (Fin nm)) (nxt : Fin nm → ℕ) : Fin nw → Option (Fin nm) :=
  match fuel with
  | 0 => hold
  | fuel + 1 =>
    match (List.finRange nm).find? (fun m =>
        decide (nxt m < nw) && (List.finRange nw).all (fun w => hold w != some m)) with
    | none => hold
    | some m =>
      match (List.finRange nw).find? (fun w => ((rm m w : ℕ) == nxt m)) with
      | none => hold
      | some w =>
        let nxt' := Function.update nxt m (nxt m + 1)
        match hold w with
        | none => da_run rm rw fuel (Function.update hold w (some m)) nxt'
        | some m' =>
          if rw w m < rw w m' then da_run rm rw fuel (Function.update hold w (some m)) nxt'
          else da_run rm rw fuel hold nxt'
See it in the graphDiscuss this resultChallenge it