jinv_step
theoremverifiedformalizationimported Lean
JInv 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 jinv_step (w m : Preferences n) (s : DAState n) (hj : JInv m s) : JInv m (daStep w m s)
- Formalizes
- EconCSLib, `jinv_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.jinv_step← jinv_step (EconCSLib/MarketDesign/Matching/GaleShapley.lean:502): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- 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.
- JInvJInv (Proposed → Held): once man
ihas proposed to womanpin some prior step,pis currently held by *someone* (possiblyi,… - GS.PreferencesList-based preferences:
prefs iis a full permutation ofFin n, ordered from most to least preferred. - daStep_held_of_free_propFree man
iproposing to womanpmakes her held indaStep. - holding_rank_mono_stepAfter one
daStep, womanj's held man's rank can only decrease (she only upgrades).
- Used by 5
- nc_le_n_run
nextChoice i ≤ noverdaRun. - rsinv_runRSInv over daRun.
- nc_sum_le_nn
∑ nextChoice ≤ n * nis preserved overdaRun. - nc_sum_growsAfter
fuelrounds ending with free men,∑ nextChoicegrew by ≥fuel. - jinv_run
JInvoverdaRun.
- nc_le_n_run
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/-- `JInv` is preserved by one `daStep`. -/lemma jinv_step (w m : Preferences n) (s : DAState n) (hj : JInv m s) : JInv m (daStep w m s) := by intro i p hp -- Helper: if s.holding p = some h, then (daStep s).holding p = some h' for some h'. have mono : ∀ h : Fin n, s.holding p = some h → ∃ h' : Fin n, (daStep w m s).holding p = some h' := fun h hh => (holding_rank_mono_step w m s p hh).imp fun h' ⟨heq, _⟩ => heq by_cases hfi : isFree s i = true · -- Man i was free: nc increases by 1, hp : p ∈ take (nc+1) (prefs i). rw [daStep_nc_free hfi] at hp rcases lt_or_ge (s.nextChoice i) n with hnc_lt | h_ge · -- nc < n: take (nc+1) = take nc ++ [(prefs i)[nc]]. rw [List.take_succ_eq_append_getElem (by rwa [(m.valid i).2])] at hp simp only [List.mem_append, List.mem_singleton] at hp rcases hp with hp_old | hp_eq · obtain ⟨h, hh⟩ := hj i p hp_old; exact mono h hh · -- p = (prefs i)[nc]: man i proposes to p this round. have hpt : propTarget m i (s.nextChoice i) = some p := by simp [propTarget, List.getElem?_eq_getElem (by rwa [(m.valid i).2]), hp_eq] exact daStep_held_of_free_prop w m s i p hfi hpt · -- nc ≥ n: take (nc+1) = take nc = prefs i (since length = n). have heq_full : (m.prefs i).take (s.nextChoice i) = m.prefs i := List.take_of_length_le (by rw [(m.valid i).2]; exact h_ge) have hmem_take : p ∈ (m.prefs i).take (s.nextChoice i) := by rw [heq_full] rw [List.take_of_length_le (by rw [(m.valid i).2]; omega)] at hp exact hp obtain ⟨h, hh⟩ := hj i p hmem_take; exact mono h hh · -- Man i was not free: nc unchanged. simp only [Bool.not_eq_true] at hfi rw [daStep_nc_held hfi] at hp obtain ⟨h, hh⟩ := hj i p hp; exact mono h hh