AFTD Auto-Formalizing Theoretical Domains

GS.StableMatching.gsStable_greatest

theoremverifiedformalizationimported Lean

The GS output is the greatest stable matching in the men-preference order: every man weakly prefers his GS partner to his partner in any other stable matching. This is galeShapley_isProposingOptimal packaged as the lattice maximum (⊤-like greatest element).

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open GS GS.StableMatching in
open GS in
variable {n : ℕ} (w m : Preferences n) in
variable {w m} in
variable (μ ν : Matching (Fin n) (Fin n))
  (hμ : Matching.IsStable (MatchingMarket.ofEquivData w m) μ)
  (hν : Matching.IsStable (MatchingMarket.ofEquivData w m) ν) in
theorem GS.StableMatching.gsStable_greatest [NeZero n] (μ : StableMatching w m) : μ ≤ gsStable w m
Formalizes
EconCSLib, `GS.StableMatching.gsStable_greatest`
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
Classical.choiceQuot.soundpropext
Built on 17
Used by 1

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen GS GS.StableMatching inopen GS invariable {n : ℕ} (w m : Preferences n) invariable {w m} invariable (μ ν : Matching (Fin n) (Fin n))  (hμ : Matching.IsStable (MatchingMarket.ofEquivData w m) μ)  (hν : Matching.IsStable (MatchingMarket.ofEquivData w m) ν) in/-- **The GS output is the greatest stable matching** in the men-preference order: every man weakly prefers his GS partner to his partner in any other stable matching. This is `galeShapley_isProposingOptimal` packaged as the lattice maximum (`⊤`-like greatest element). -/theorem GS.StableMatching.gsStable_greatest [NeZero n] (μ : StableMatching w m) : μ ≤ gsStable w m := by  intro j  show (m.prefs j).idxOf ((gsStable w m).partner j) ≤ (m.prefs j).idxOf (μ.partner j)  have hg : (gsStable w m).partner j      = (Equiv.ofBijective (gs w m) (gs_bijective w m)).symm j := rfl  rw [hg]  exact galeShapley_isProposingOptimal w m μ.1 μ.2 j (μ.partner j) (matchW_partner μ j)
See it in the graphDiscuss this resultChallenge it