AFTD Auto-Formalizing Theoretical Domains

GS.DAState

structureimported Lean

DA state: per-man proposal cursor + per-woman tentative hold.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open List Finset in
structure GS.DAState (n : ℕ)
Defined in
EconCSLib, `GS.DAState`
Lean proof
By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at 1a88f809b538 (Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.
Verified
08 Oct 2026
Axioms
none listed
Used by 54
  • holding_injective_runOver daRun, holding remains injective.
  • proposal_rank_boundWhen free man j proposes to woman i in daStep, the resulting hold has rank ≤ j.
  • holdinv_stepHoldInv is preserved by one DA step. Proof structure: case-analyze on the pair (s.holding p, bestNew p) that drives daStep's…
  • GS.daStepOne step of standard men-proposing DA. All free men propose; women pick the best of {held, new proposers} by rank; free men advance their…
  • nc_le_n_runnextChoice i ≤ n over daRun.
  • GS.daRunRun DA for at most fuel steps, stopping early if no free men remain.
  • GS.freeMenSetThe finset of all free men in s.
  • GS.daRun_NoAchievableRejectionNoAchievableRejection is preserved by daRun (threading HoldInv and holding-injectivity, both also preserved by daStep).
  • GS.daStep_holdingOne step of DA: woman p's new holding, expanded once. This is the workhorse rewrite for any proof that needs to case-split on what…
  • nc_sum_increase∑ nextChoice strictly increases when free men exist.
  • jinv_stepJInv is preserved by one daStep.
  • pl_free_propsHelper: membership in the proposerList implies freedom and proposal target.
  • GS.gsThe Gale-Shapley function: woman j's partner at termination.
  • GS.daStep_nc_heldGS.daStep_nc_held
  • holdinv_runholdinv_run
  • rsinv_runRSInv over daRun.
  • holding_rank_mono_runRank-mono over any daRun.
  • final_holding_injectivefinalState holding is injective.
  • not_free_of_nc_genextChoice i ≥ n + injectivity + JInv → man i is not free.
  • GS.daStep_nc_freeGS.daStep_nc_free
  • GS.NoAchievableRejectionRun-state invariant for proposer optimality. NoAchievableRejection w m s says: at state s, for every achievable pair (j, wj), if man…
  • GS.daStep_NoAchievableRejectionInductive step (KEY LEMMA). NoAchievableRejection is preserved by one daStep. Also threads HoldInv (for the old-holder index…
  • GS.initState_NoAchievableRejectionThe invariant holds vacuously at initState: no man has proposed yet.
  • nc_sum_le_nn∑ nextChoice ≤ n * n is preserved over daRun.
  • finalState_no_free_menAt termination, every man is held (no free man remains). Proof: if a free man remained, nc_sum_grows would give n*n + 1 ≤ n*n,…
  • finalState_rank_boundAt termination: if man j proposed to woman i at some round (j was free, i was his nc-th choice at state s, and the rest of the run reaches…
  • initState_injectiveinitState has trivially injective holding (all none).
  • rsinv_stabilityIf j strictly prefers i over his final partner, i's final partner has rank ≤ j.
  • GS.isFreeMan i is free in s iff no woman holds him.
  • GS.mem_freeMenSetGS.mem_freeMenSet
  • final_all_women_holdAt termination, every woman holds some man.
  • nc_sum_growsAfter fuel rounds ending with free men, ∑ nextChoice grew by ≥ fuel.
  • final_all_men_heldAt termination, every man is held by some woman.
  • jinv_initjinv_init
  • jinv_runJInv over daRun.
  • holdinv_initholdinv_init
  • daStep_nc_le_nnextChoice i ≤ n for daStep.
  • GS.initStateInitial state: all women free, all men start at proposal index 0.
  • gs_injectivegs w m is injective.
  • GS.isFree_iffGS.isFree_iff
  • GS.finalStatefinalState: run daRun with fuel n*n + 1 from initState.
  • JInvJInv (Proposed → Held): once man i has proposed to woman p in some prior step, p is currently held by *someone* (possibly i,…
  • daStep_held_of_free_propFree man i proposing to woman p makes her held in daStep.
  • proposal_rank_bound_runOver a daRun, if man j proposed to woman i at the first step, woman i's final partner has rank ≤ j's rank in w.prefs i.
  • RSInvRSInv (the deferred-acceptance rank invariant — the engine of the stability proof): for every man j and every woman i that j has…
  • holding_rank_mono_stepAfter one daStep, woman j's held man's rank can only decrease (she only upgrades).
  • galeShapley_isStableGale-Shapley stability: the DA output has no blocking pair. The statement is in the *market* frame (IsBlocking … (i : M) (j : W)).…
  • rsinv_initrsinv_init
  • HoldInvHoldInv (Held → Proposed): if woman p currently holds man j, then j must already have proposed to p — i.e., p is in the…
  • holding_injective_stepIn daStep, holding remains injective.
  • held_preserved_runOnce held, always held over daRun.
  • rsinv_stepRSInv is preserved by one daStep.
  • GS.galeShapley_isProposingOptimalMen-optimal stable matching (Gale–Shapley 1962, [MSZ 22.10]): in the men-proposing DA, every man's GS partner is at least as preferred…
  • GS.not_isFree_iffGS.not_isFree_iff

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open List Finset in
/-- DA state: per-man proposal cursor + per-woman tentative hold. -/
structure GS.DAState (n : ℕ) where
  nextChoice : Fin n → ℕ
  holding    : Fin n → Option (Fin n)
See it in the graphDiscuss this resultChallenge it