rsinv_step
theoremverifiedformalizationimported Lean
RSInv is preserved by one daStep.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open List Finset in open GS in variable {n : ℕ} [NeZero n] in lemma rsinv_step (w m : Preferences n) (s : DAState n) (hrs : RSInv w m s) (hnc0 : ∀ k : Fin n, s.nextChoice k ≤ n) : RSInv w m (daStep w m s)
- Formalizes
- EconCSLib, `rsinv_step`
- 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.rsinv_step← rsinv_step (EconCSLib/MarketDesign/Matching/GaleShapley.lean:742): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- proposal_rank_boundWhen free man
jproposes to womaniindaStep, the resulting hold has rank ≤ j. - 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…
- GS.daStep_nc_heldGS.daStep_nc_held
- GS.daStep_nc_freeGS.daStep_nc_free
- GS.propTargetThe woman man
iproposes to at cursor indexk(none if out of bounds). - GS.isFreeMan
iis free insiff no woman holds him. - GS.DAStateDA state: per-man proposal cursor + per-woman tentative hold.
- GS.PreferencesList-based preferences:
prefs iis a full permutation ofFin n, ordered from most to least preferred. - RSInvRSInv (the deferred-acceptance rank invariant — the engine of the stability proof): for every man
jand every womanithatjhas… - holding_rank_mono_stepAfter one
daStep, womanj's held man's rank can only decrease (she only upgrades).
- proposal_rank_boundWhen free man
- Used by 1
- rsinv_runRSInv over daRun.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen List Finset inopen GS invariable {n : ℕ} [NeZero n] in/-- RSInv is preserved by one daStep. -/lemma rsinv_step (w m : Preferences n) (s : DAState n) (hrs : RSInv w m s) (hnc0 : ∀ k : Fin n, s.nextChoice k ≤ n) : RSInv w m (daStep w m s) := by intro j i hi by_cases hfj : isFree s j = true · rw [daStep_nc_free hfj] at hi rcases lt_or_ge (s.nextChoice j) n with hnc_lt | h_ge · -- nc < n: take (nc+1) = take nc ++ [proposal] rw [List.take_succ_eq_append_getElem (by rwa [(m.valid j).2])] at hi simp only [List.mem_append, List.mem_singleton] at hi rcases hi with hi_old | hi_eq · -- i was in the old take — rank already good; use rank_mono_step obtain ⟨h, hh, hrk⟩ := hrs j i hi_old obtain ⟨h', hh', hrk'⟩ := holding_rank_mono_step w m s i hh exact ⟨h', hh', Nat.le_trans hrk' hrk⟩ · -- i = (m.prefs j)[nc] = the new proposal; use proposal_rank_bound have hpt : propTarget m j (s.nextChoice j) = some i := by simp [propTarget, List.getElem?_eq_getElem (by rwa [(m.valid j).2]), hi_eq] exact proposal_rank_bound w m s j i hfj hpt · -- nc ≥ n: take (nc+1) = take nc = full list have hmem_take : i ∈ (m.prefs j).take (s.nextChoice j) := by rw [List.take_of_length_le (by rw [(m.valid j).2]; exact h_ge)] rw [List.take_of_length_le (by rw [(m.valid j).2]; omega)] at hi; exact hi obtain ⟨h, hh, hrk⟩ := hrs j i hmem_take obtain ⟨h', hh', hrk'⟩ := holding_rank_mono_step w m s i hh exact ⟨h', hh', Nat.le_trans hrk' hrk⟩ · -- j not free: nc unchanged simp only [Bool.not_eq_true] at hfj rw [daStep_nc_held hfj] at hi obtain ⟨h, hh, hrk⟩ := hrs j i hi obtain ⟨h', hh', hrk'⟩ := holding_rank_mono_step w m s i hh exact ⟨h', hh', Nat.le_trans hrk' hrk⟩