AFTD Auto-Formalizing Theoretical Domains

exact_cutoff_filtering

theoremverifiedformalization

In a finite marriage market with strict complete preference profile Q, for every agent (woman w with stable partner t in M, or man m with stable partner t in W), the set of stable matchings of the profile obtained by t-cutoff tanking by that agent equals the set of stable matchings in S(Q) that assign that agent a partner ranked weakly above t.

Statement

theorem exact_cutoff_filtering {M W : Type*} [Fintype M] [Fintype W]
    (market : MarriageMarket M W)
    (h_m_strict : ∀ m, IsStrictTotalOrder W (market.pref_m m))
    (h_w_strict : ∀ w, IsStrictTotalOrder M (market.pref_w w)) :
    (∀ (w : W) (t : M) (_ : ∃ μ : M ≃ W, is_stable_matching market μ ∧ μ.symm w = t),
      {μ : M ≃ W | is_stable_matching (woman_cutoff_tanking market w t) μ} =
      {μ : M ≃ W | is_stable_matching market μ ∧ ¬ market.pref_w w t (μ.symm w)}) ∧
    (∀ (m : M) (t : W) (_ : ∃ μ : M ≃ W, is_stable_matching market μ ∧ μ m = t),
      {μ : M ≃ W | is_stable_matching (man_cutoff_tanking market m t) μ} =
      {μ : M ≃ W | is_stable_matching market μ ∧ ¬ market.pref_m m t (μ m)})
Formalizes
arXiv:2610.42105 Theorem 4.3
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • woman_cutoff_tankingIn a marriage market, the profile obtained by t-cutoff tanking by woman w: woman w is moved to the bottom of the preference list of every…
  • man_cutoff_tankingIn a marriage market, the profile obtained by t-cutoff tanking by man m: man m is moved to the bottom of the preference list of every…
  • woman_cutoff_tanking_ge_subsetIn a marriage market, any matching μ stable in market that assigns woman w a partner weakly preferred to t (that is, ¬ market.pref_w w t…
  • woman_cutoff_tanking_is_stable_of_geIn a marriage market where woman w's preferences are transitive, any matching μ stable after t-cutoff tanking by w that assigns w a…
  • is_blocking_pairIn a marriage market with agent types M and W and a matching μ : M ≃ W, a man m and a woman w form a blocking pair when m strictly prefers…
  • move_to_bottomThe relation obtained from a binary relation r on α by moving an element bot_elt to the bottom: bot_elt is not preferred to anything, any…
  • MarriageMarketA marriage market with types M and W consists of a relation pref_m : M → W → W → Prop representing men's preferences over women, and a…
  • is_stable_matchingIn a marriage market with agent types M and W, a matching μ : M ≃ W is stable when no man m and woman w form a blocking pair, that is,…

Read back from the Lean

Let $M$ and $W$ be finite types, and let market be a marriage market on $M$ and $W$ with men's preference relations market.pref_m and women's preference relations market.pref_w. Assume that for every $m \in M$, market.pref_m m is a strict total order on $W$, and for every $w \in W$, market.pref_w w is a strict total order on $M$. Then both of the following hold: 1. For every woman $w \in W$ and man $t \in M$, if there exists a bijection $\mu : M \simeq W$ that is a stable matching in market such that $\mu^{-1}(w) = t$, then: The set of bijections $\mu : M \simeq W$ that are stable matchings in the market woman_cutoff_tanking market w t equals the set of bijections $\mu : M \simeq W$ that are stable matchings in market and satisfy $\neg market.pref_w(w, t, \mu^{-1}(w))$ (i.e., $w$ does not strictly prefer $t$ to her partner $\mu^{-1}(w)$). 2. For every man $m \in M$ and woman $t \in W$, if there exists a bijection $\mu : M \simeq W$ that is a stable matching in market such that $\mu(m) = t$, then: The set of bijections $\mu : M \simeq W$ that are stable matchings in the market man_cutoff_tanking market m t equals the set of bijections $\mu : M \simeq W$ that are stable matchings in market and satisfy $\neg market.pref_m(m, t, \mu(m))$ (i.e., $m$ does not strictly prefer $t$ to his partner $\mu(m)$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

open Classicallemma exact_cutoff_filtering_pref_m_tanked_irrefl {M W : Type*} (market : MarriageMarket M W)    (h_m_strict : ∀ m, IsStrictTotalOrder W (market.pref_m m))    (w : W) (t : M) (m : M) (x : W) :    ¬ (woman_cutoff_tanking market w t).pref_m m x x := by  dsimp [woman_cutoff_tanking]  split_ifs  · dsimp [move_to_bottom]    split_ifs with h1    · trivial    · exact (h_m_strict m).irrefl x  · exact (h_m_strict m).irrefl xlemma exact_cutoff_filtering_pref_m_tanked_of_market {M W : Type*} (market : MarriageMarket M W)    (h_w_strict : ∀ w, IsStrictTotalOrder M (market.pref_w w))    (w : W) (t : M) (μ ν : M ≃ W) (h_nu_t : ν t = w)    (m' : M) (h : market.pref_m m' (ν m') (μ m')) :    (woman_cutoff_tanking market w t).pref_m m' (ν m') (μ m') := by  dsimp [woman_cutoff_tanking]  split_ifs with hwt  · dsimp [move_to_bottom]    have h_m'_ne_t : m' ≠ t := by      intro heq      have := (h_w_strict w).irrefl t      rw [heq] at hwt      exact this hwt    have h_nu_ne_w : ν m' ≠ w := by      intro heq      have : ν m' = ν t := by rw [heq, h_nu_t]      exact h_m'_ne_t (ν.injective this)    rw [if_neg h_nu_ne_w]    by_cases hmu : μ m' = w    · rw [if_pos hmu]      trivial    · rw [if_neg hmu]      exact h  · exact hlemma exact_cutoff_filtering_step_w {M W : Type*} (market : MarriageMarket M W)    (h_m_strict : ∀ m, IsStrictTotalOrder W (market.pref_m m))    (h_w_strict : ∀ w, IsStrictTotalOrder M (market.pref_w w))    (w : W) (t : M) (μ ν : M ≃ W)    (h_mu_stable : is_stable_matching (woman_cutoff_tanking market w t) μ)    (m : M)    (h_m_step : (woman_cutoff_tanking market w t).pref_m m (ν m) (μ m)) :    market.pref_w (ν m) (μ.symm (ν m)) m := by  have h_not_bp := h_mu_stable m (ν m)  dsimp [is_blocking_pair] at h_not_bp  have h_not_w : ¬ (woman_cutoff_tanking market w t).pref_w (ν m) m (μ.symm (ν m)) := by    intro hw    exact h_not_bp ⟨h_m_step, hw⟩  dsimp [woman_cutoff_tanking] at h_not_w  have := h_w_strict (ν m)  rcases trichotomous_of (market.pref_w (ν m)) (μ.symm (ν m)) m with h1 | h2 | h3  · exact h1  · exfalso    have : ν m = μ m := by      have h_eq : μ (μ.symm (ν m)) = μ m := by rw [h2]      rw [μ.apply_symm_apply] at h_eq      exact h_eq    rw [this] at h_m_step    exact exact_cutoff_filtering_pref_m_tanked_irrefl market h_m_strict w t m (μ m) h_m_step  · exfalso    exact h_not_w h3lemma exact_cutoff_filtering_step_m {M W : Type*} (market : MarriageMarket M W)    (h_m_strict : ∀ m, IsStrictTotalOrder W (market.pref_m m))    (h_w_strict : ∀ w, IsStrictTotalOrder M (market.pref_w w))    (μ ν : M ≃ W)    (h_nu_stable : is_stable_matching market ν)    (m : M)    (hw : market.pref_w (ν m) (μ.symm (ν m)) m) :    market.pref_m (μ.symm (ν m)) (ν (μ.symm (ν m))) (μ (μ.symm (ν m))) := by  let m' := μ.symm (ν m)  have h_not_bp := h_nu_stable m' (ν m)  dsimp [is_blocking_pair] at h_not_bp  have h_not_m : ¬ market.pref_m m' (ν m) (ν m') := by    intro hm    have hw_sub : market.pref_w (ν m) m' (ν.symm (ν m)) := by      rw [ν.symm_apply_apply]      exact hw    exact h_not_bp ⟨hm, hw_sub⟩  have := h_m_strict m'  have h_w_eq : ν m = μ m' := by    dsimp [m']    rw [μ.apply_symm_apply]  rcases trichotomous_of (market.pref_m m') (ν m') (μ m') with h1 | h2 | h3  · exact h1  · exfalso    have h_eq : ν m' = ν m := by rw [h2, h_w_eq]    have h_m'_eq : m' = m := ν.injective h_eq    have hw' : market.pref_w (ν m) m' m := hw    rw [h_m'_eq] at hw'    exact (h_w_strict (ν m)).irrefl m hw'  · exfalso    rw [← h_w_eq] at h3    exact h_not_m h3lemma exact_cutoff_filtering_base_step {M W : Type*} (market : MarriageMarket M W)    (h_w_strict : ∀ w, IsStrictTotalOrder M (market.pref_w w))    (w : W) (t : M) (μ ν : M ≃ W) (h_nu_t : ν t = w)    (h_w_pref : market.pref_w w t (μ.symm w)) :    (woman_cutoff_tanking market w t).pref_m (μ.symm w) (ν (μ.symm w)) (μ (μ.symm w)) := by  dsimp [woman_cutoff_tanking]  rw [if_pos h_w_pref]  dsimp [move_to_bottom]  have h_ne_t : μ.symm w ≠ t := by    intro heq    have := (h_w_strict w).irrefl t    rw [heq] at h_w_pref    exact this h_w_pref  have h_nu_ne_w : ν (μ.symm w) ≠ w := by    intro heq    have : ν (μ.symm w) = ν t := by rw [heq, h_nu_t]    exact h_ne_t (ν.injective this)  rw [if_neg h_nu_ne_w]  rw [if_pos (μ.apply_symm_apply w)]  triviallemma exact_cutoff_filtering_woman_ge_of_stable {M W : Type*} [Fintype M] [Fintype W]    (market : MarriageMarket M W)    (h_m_strict : ∀ m, IsStrictTotalOrder W (market.pref_m m))    (h_w_strict : ∀ w, IsStrictTotalOrder M (market.pref_w w))    (w : W) (t : M) (ν : M ≃ W)    (h_nu_stable : is_stable_matching market ν)    (h_nu_t : ν.symm w = t)    (μ : M ≃ W)    (h_mu_stable : is_stable_matching (woman_cutoff_tanking market w t) μ) :    ¬ market.pref_w w t (μ.symm w) := by  intro h_w_pref  have h_nu_t_apply : ν t = w := by    rw [← h_nu_t, ν.apply_symm_apply]  let f : Equiv.Perm M := ν.trans μ.symm  have h_f_t : f t = μ.symm w := by    dsimp [f]    rw [h_nu_t_apply]  let m₀ := μ.symm w  have h_base : (woman_cutoff_tanking market w t).pref_m m₀ (ν m₀) (μ m₀) :=    exact_cutoff_filtering_base_step market h_w_strict w t μ ν h_nu_t_apply h_w_pref  have h_ind_m : ∀ n : ℕ, (woman_cutoff_tanking market w t).pref_m ((f ^ n) m₀) (ν ((f ^ n) m₀)) (μ ((f ^ n) m₀)) := by    intro n    induction' n with n ih    · exact h_base    · rw [pow_succ', Equiv.Perm.coe_mul, Function.comp_apply]      have hw := exact_cutoff_filtering_step_w market h_m_strict h_w_strict w t μ ν h_mu_stable ((f ^ n) m₀) ih      have hm := exact_cutoff_filtering_step_m market h_m_strict h_w_strict μ ν h_nu_stable ((f ^ n) m₀) hw      change (woman_cutoff_tanking market w t).pref_m (f ((f ^ n) m₀)) (ν (f ((f ^ n) m₀))) (μ (f ((f ^ n) m₀)))      exact exact_cutoff_filtering_pref_m_tanked_of_market market h_w_strict w t μ ν h_nu_t_apply (f ((f ^ n) m₀)) hm  let k := orderOf f  have hk : 0 < k := orderOf_pos f  let N := k - 1  have h_eq_t : (f ^ N) m₀ = t := by    have h1 : (f ^ k) m₀ = m₀ := by rw [pow_orderOf_eq_one]; rfl    have h2 : k = N + 1 := (Nat.sub_add_cancel hk).symm    rw [h2, pow_succ', Equiv.Perm.coe_mul, Function.comp_apply] at h1    apply f.injective    rw [h_f_t]    exact h1  have hw_N := exact_cutoff_filtering_step_w market h_m_strict h_w_strict w t μ ν h_mu_stable ((f ^ N) m₀) (h_ind_m N)  rw [h_eq_t, h_nu_t_apply] at hw_N  have := (h_w_strict w).irrefl t (_root_.trans h_w_pref hw_N)  exact thisdef exact_cutoff_filtering_swap_market {M W : Type*} (market : MarriageMarket M W) : MarriageMarket W M :=  ⟨market.pref_w, market.pref_m⟩lemma exact_cutoff_filtering_is_stable_matching_swap {M W : Type*} (market : MarriageMarket M W) (μ : M ≃ W) :    is_stable_matching (exact_cutoff_filtering_swap_market market) μ.symm ↔ is_stable_matching market μ := by  dsimp [is_stable_matching, is_blocking_pair, exact_cutoff_filtering_swap_market]  constructor <;> intro h a b <;> have := h b a <;> tautolemma exact_cutoff_filtering_man_cutoff_tanking_swap {M W : Type*} (market : MarriageMarket M W) (m : M) (t : W) :    exact_cutoff_filtering_swap_market (man_cutoff_tanking market m t) = woman_cutoff_tanking (exact_cutoff_filtering_swap_market market) m t := by  rfl/-- Theorem 4.3 (Exact cutoff filtering): the set of stable matchings after t-cutoff tanking by an agent equals the stable matchings of the original profile assigning that agent a partner weakly preferred to t. -/theorem exact_cutoff_filtering {M W : Type*} [Fintype M] [Fintype W]    (market : MarriageMarket M W)    (h_m_strict : ∀ m, IsStrictTotalOrder W (market.pref_m m))    (h_w_strict : ∀ w, IsStrictTotalOrder M (market.pref_w w)) :    (∀ (w : W) (t : M) (_ : ∃ μ : M ≃ W, is_stable_matching market μ ∧ μ.symm w = t),      {μ : M ≃ W | is_stable_matching (woman_cutoff_tanking market w t) μ} =      {μ : M ≃ W | is_stable_matching market μ ∧ ¬ market.pref_w w t (μ.symm w)}) ∧    (∀ (m : M) (t : W) (_ : ∃ μ : M ≃ W, is_stable_matching market μ ∧ μ m = t),      {μ : M ≃ W | is_stable_matching (man_cutoff_tanking market m t) μ} =      {μ : M ≃ W | is_stable_matching market μ ∧ ¬ market.pref_m m t (μ m)}) := by  constructor  · intro w t ⟨ν, h_nu_stable, h_nu_t⟩    ext μ    simp only [Set.mem_setOf_eq]    constructor    · intro h_tank_stable      have h_ge := exact_cutoff_filtering_woman_ge_of_stable market h_m_strict h_w_strict w t ν h_nu_stable h_nu_t μ h_tank_stable      have hw_trans : ∀ a b c : M, market.pref_w w a b → market.pref_w w b c → market.pref_w w a c :=        fun a b c hab hbc => _root_.trans hab hbc      exact ⟨woman_cutoff_tanking_is_stable_of_ge market w t hw_trans μ h_tank_stable h_ge, h_ge⟩    · rintro ⟨h_stable, h_ge⟩      exact woman_cutoff_tanking_ge_subset market w t μ h_stable h_ge  · intro m t ⟨ν, h_nu_stable, h_nu_t⟩    ext μ    simp only [Set.mem_setOf_eq]    have h_w_strict_swap : ∀ (w : W), IsStrictTotalOrder M ((exact_cutoff_filtering_swap_market market).pref_m w) := h_w_strict    have h_m_strict_swap : ∀ (m : M), IsStrictTotalOrder W ((exact_cutoff_filtering_swap_market market).pref_w m) := h_m_strict    have h_nu_symm_m : ν.symm.symm m = t := h_nu_t    have h_nu_swap_stable : is_stable_matching (exact_cutoff_filtering_swap_market market) ν.symm := by      rw [exact_cutoff_filtering_is_stable_matching_swap]      exact h_nu_stable    constructor    · intro h_tank_stable      have h_tank_swap_stable : is_stable_matching (woman_cutoff_tanking (exact_cutoff_filtering_swap_market market) m t) μ.symm := by        rw [← exact_cutoff_filtering_man_cutoff_tanking_swap]        rw [exact_cutoff_filtering_is_stable_matching_swap]        exact h_tank_stable      have h_ge := exact_cutoff_filtering_woman_ge_of_stable (exact_cutoff_filtering_swap_market market) h_w_strict_swap h_m_strict_swap m t ν.symm h_nu_swap_stable h_nu_symm_m μ.symm h_tank_swap_stable      dsimp [exact_cutoff_filtering_swap_market] at h_ge      have hm_trans : ∀ a b c : W, market.pref_m m a b → market.pref_m m b c → market.pref_m m a c :=        fun a b c hab hbc => _root_.trans hab hbc      have h_orig_swap : is_stable_matching (exact_cutoff_filtering_swap_market market) μ.symm :=        woman_cutoff_tanking_is_stable_of_ge (exact_cutoff_filtering_swap_market market) m t hm_trans μ.symm h_tank_swap_stable h_ge      rw [exact_cutoff_filtering_is_stable_matching_swap] at h_orig_swap      exact ⟨h_orig_swap, h_ge⟩    · rintro ⟨h_stable, h_ge⟩      have h_swap_stable : is_stable_matching (exact_cutoff_filtering_swap_market market) μ.symm := by        rw [exact_cutoff_filtering_is_stable_matching_swap]        exact h_stable      have h_tank_swap : is_stable_matching (woman_cutoff_tanking (exact_cutoff_filtering_swap_market market) m t) μ.symm :=        woman_cutoff_tanking_ge_subset (exact_cutoff_filtering_swap_market market) m t μ.symm h_swap_stable h_ge      rw [← exact_cutoff_filtering_man_cutoff_tanking_swap] at h_tank_swap      rw [exact_cutoff_filtering_is_stable_matching_swap] at h_tank_swap      exact h_tank_swap
See it in the graphDiscuss this resultChallenge it