JInv
JInv (Proposed → Held): once man i has proposed to woman p in some prior step, p is currently held by *someone* (possibly i, possibly someone better). Formally: every p in the prefix (m.prefs i).take (s.nextChoice i) of i's preference list — i.e., every woman i has already proposed to — has s.holding p = some _. This is the "once proposed-to, always held" invariant: a woman who has ever received a proposal can never go back to being unmatched. It is the dual of [HoldInv] (every currently-held woman is in her holder's proposed prefix), which gives the converse direction. Together JInv and HoldInv pin down a bidirectional correspondence between the per-man cursors and the per-woman holdings, which the stability proof needs in both directions.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open List Finset in open GS in variable {n : ℕ} [NeZero n] in def JInv (m : Preferences n) (s : DAState n) : Prop
- Defined in
- EconCSLib, `JInv`
- 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← JInv (EconCSLib/MarketDesign/Matching/GaleShapley.lean:476): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 2
- 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.
- Used by 10
- nc_le_n_run
nextChoice i ≤ noverdaRun. - jinv_step
JInvis preserved by onedaStep. - rsinv_runRSInv over daRun.
- not_free_of_nc_ge
nextChoice i ≥ n+ injectivity +JInv→ maniis not free. - nc_sum_le_nn
∑ nextChoice ≤ n * nis preserved overdaRun. - finalState_no_free_menAt termination, every man is held (no free man remains). Proof: if a free man remained,
nc_sum_growswould given*n + 1 ≤ n*n,… - nc_sum_growsAfter
fuelrounds ending with free men,∑ nextChoicegrew by ≥fuel. - jinv_initjinv_init
- jinv_run
JInvoverdaRun. - daStep_nc_le_n
nextChoice i ≤ nfordaStep.
- nc_le_n_run
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open List Finset in open GS in variable {n : ℕ} [NeZero n] in /-- **JInv** (Proposed → Held): once man `i` has proposed to woman `p` in some prior step, `p` is currently held by *someone* (possibly `i`, possibly someone better). Formally: every `p` in the prefix `(m.prefs i).take (s.nextChoice i)` of `i`'s preference list — i.e., every woman `i` has already proposed to — has `s.holding p = some _`. This is the **"once proposed-to, always held"** invariant: a woman who has ever received a proposal can never go back to being unmatched. It is the dual of [`HoldInv`] (every currently-held woman is in her holder's proposed prefix), which gives the converse direction. Together `JInv` and `HoldInv` pin down a bidirectional correspondence between the per-man cursors and the per-woman holdings, which the stability proof needs in both directions. -/ def JInv (m : Preferences n) (s : DAState n) : Prop := ∀ i p : Fin n, p ∈ (m.prefs i).take (s.nextChoice i) → ∃ h : Fin n, s.holding p = some h