AFTD Auto-Formalizing Theoretical Domains

RSInv

defimported Lean

RSInv (the deferred-acceptance rank invariant — the engine of the stability proof): for every man j and every woman i that j has already proposed to, i currently holds *some* man whom she prefers at least as much as j. Formally: for every i ∈ (m.prefs j).take (s.nextChoice j) (the prefix of j's preference list j has cycled through), there exists h such that s.holding i = some h and (w.prefs i).idxOf h ≤ (w.prefs i).idxOf j (smaller index = higher preference). Why this is the stability lever: at termination, if (i, j) *were* a blocking pair — i and j mutually prefer each other to their final partners — then j would have proposed to i at some point, so RSInv at termination would say i holds someone she likes at least as much as j. That someone is i's eventual partner (by holding_rank_mono_run), giving i no incentive to defect. Contradiction with the blocking-pair assumption. The invariant is preserved by every daStep (rsinv_step) and trivially holds at initState (rsinv_init); see also rsinv_finalState for the terminal form used in the stability proof.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open List Finset in
open GS in
variable {n : ℕ} [NeZero n] in
def RSInv (w m : Preferences n) (s : DAState n) : Prop
Defined in
EconCSLib, `RSInv`
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
Built on 2
  • GS.DAStateDA state: per-man proposal cursor + per-woman tentative hold.
  • GS.PreferencesList-based preferences: prefs i is a full permutation of Fin n, ordered from most to least preferred.
Used by 4

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
/-- **RSInv** (the deferred-acceptance rank invariant — the engine of the stability proof): for every man `j` and every woman `i` that `j` has already proposed to, `i` currently holds *some* man whom she prefers at least as much as `j`. Formally: for every `i ∈ (m.prefs j).take (s.nextChoice j)` (the prefix of `j`'s preference list `j` has cycled through), there exists `h` such that `s.holding i = some h` **and** `(w.prefs i).idxOf h ≤ (w.prefs i).idxOf j` (smaller index = higher preference). Why this is the stability lever: at termination, if `(i, j)` *were* a blocking pair — `i` and `j` mutually prefer each other to their final partners — then `j` would have proposed to `i` at some point, so `RSInv` at termination would say `i` holds someone she likes at least as much as `j`. That someone is `i`'s eventual partner (by `holding_rank_mono_run`), giving `i` no incentive to defect. Contradiction with the blocking-pair assumption. The invariant is preserved by every `daStep` (`rsinv_step`) and trivially holds at `initState` (`rsinv_init`); see also `rsinv_finalState` for the terminal form used in the stability proof. -/
def RSInv (w m : Preferences n) (s : DAState n) : Prop :=
  ∀ j i : Fin n, i ∈ (m.prefs j).take (s.nextChoice j) →
    ∃ h : Fin n, s.holding i = some h ∧ (w.prefs i).idxOf h ≤ (w.prefs i).idxOf j
See it in the graphDiscuss this resultChallenge it