AFTD Auto-Formalizing Theoretical Domains

woman_cutoff_tanking_is_stable_of_ge

theoremverified

In a marriage market where woman w's preferences are transitive, any matching μ stable after t-cutoff tanking by w that assigns w a partner weakly preferred to t is also stable in the original market.

Statement

theorem woman_cutoff_tanking_is_stable_of_ge {M W : Type*}
    (market : MarriageMarket M W) (w : W) (t : M)
    (hw_trans : ∀ a b c : M, market.pref_w w a b → market.pref_w w b c → market.pref_w w a c)
    (μ : M ≃ W)
    (h_tank_stable : is_stable_matching (woman_cutoff_tanking market w t) μ)
    (h_ge : ¬ market.pref_w w t (μ.symm w)) :
    is_stable_matching market μ
Source
arXiv:2610.42105 Appendix A.2
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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…
  • 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…
  • 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…
  • 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,…
  • 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…
Used by 1
  • exact_cutoff_filteringIn 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…

Read back from the Lean

For any types M and W, let market be a marriage market on men M and women W (with men's preference relations pref_m and women's preference relations pref_w), let w : W be a woman, and let t : M be a man. Assume: 1. hw_trans: woman w's preference relation is transitive, meaning for all a, b, c : M, if market.pref_w w a b and market.pref_w w b c, then market.pref_w w a c. 2. μ : M ≃ W is a bijection between M and W. 3. h_tank_stable: μ is a stable matching in the modified market woman_cutoff_tanking market w t, where women's preferences are unchanged, and each man m for whom woman w prefers t over m (market.pref_w w t m) has woman w moved to the bottom of his preferences (never preferred to any woman, and any other woman is preferred to her), while other men's preferences are unchanged. 4. h_ge: woman w does not prefer t to her partner under μ (that is, ¬ market.pref_w w t (μ.symm w)). Then μ is a stable matching in the original market (there are no blocking pairs).

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

The proof, explained

We prove stability by contradiction: assume (m', w') is a blocking pair in the original market. Since μ is stable in the cutoff-tanked market and women's preferences are completely unchanged, (m', w') could only fail to block the tanked market if m' no longer prefers w' to μ(m'), which requires w to prefer cutoff t to m' and m''s preferences to have been modified. If w' = w, transitivity forces w to prefer t to μ⁻¹(w), contradicting the hypothesis that w weakly prefers her partner to t. In all other cases (w' ≠ w or m' unmodified), moving w to the bottom preserves or forces m''s preference for w' over μ(m'), ensuring (m', w') blocks the tanked market and reaching a contradiction.

  1. To establish stability of μ in the original market, it suffices to show that any hypothetical blocking pair (m', w') would also have m' preferring w' over μ(m') in the cutoff-tanked market.

    Suppose for contradiction that (m', w') is a blocking pair in the original market, so m' prefers w' to μ(m') and w' prefers m' to μ⁻¹(w'). Because μ is assumed stable in the cutoff-tanked market, (m', w') cannot be a blocking pair there. Cutoff tanking leaves all women's preference relations unchanged, so w' still prefers m' to μ⁻¹(w') in the modified market. Hence, showing that m' prefers w' to μ(m') in the modified market is sufficient to produce a blocking pair there and obtain a contradiction.

    lines 9–13

      intro m' w' h_bp
      have h_tank_not_bp := h_tank_stable m' w'
      rcases h_bp with ⟨h_m_pref, h_w_pref⟩
      apply h_tank_not_bp
      refine ⟨?_, h_w_pref⟩
  2. In the case where woman w prefers t over m', the subcase w' = w is ruled out because it contradicts the hypothesis that w weakly prefers μ⁻¹(w) to t.

    Unfolding the definition of cutoff tanking, when woman w prefers cutoff t over m', man m''s preference ordering is modified by moving w to the very bottom. If w' = w, m' preferring w over anything evaluates to false under this modified ranking. This contradiction is confirmed by w's preferences: w prefers t over m', and because (m', w') blocked the original matching, w prefers m' over μ⁻¹(w). Transitivity of w's preferences (hw_trans) implies that w prefers t over μ⁻¹(w), directly contradicting the assumption h_ge.

    lines 14–21

    uses if_pos, False.elim

      dsimp [woman_cutoff_tanking]
      by_cases h1 : market.pref_w w t m'
      · rw [if_pos h1]
        dsimp [move_to_bottom]
        by_cases h2 : w' = w
        · rw [if_pos h2]
          rw [h2] at h_w_pref
          exact False.elim (h_ge (hw_trans t m' (μ.symm w) h1 h_w_pref))
  3. In the case where woman w prefers t over m' and w' ≠ w, man m' still prefers w' over μ(m') in the cutoff-tanked market.

    Since w' ≠ w and w was moved to the very bottom of m''s ranking, we split on whether m''s matched partner is w: if μ(m') = w, m' prefers w' over w automatically since w is at the bottom; if μ(m') ≠ w, neither w' nor μ(m') is w, so m''s relative preference between them is unchanged from the original market, where m' prefers w' over μ(m') by assumption.

    lines 22–27

    uses if_pos, if_neg

        · rw [if_neg h2]
          by_cases h3 : μ m' = w
          · rw [if_pos h3]
            trivial
          · rw [if_neg h3]
            exact h_m_pref
  4. In the case where woman w does not prefer t over m', man m' still prefers w' over μ(m') in the cutoff-tanked market, completing the stability proof.

    When w does not prefer t over m', m''s preference ordering is not modified by cutoff tanking. Therefore, m''s ranking of w' relative to μ(m') is identical to that in the original market, where m' prefers w' over μ(m') by the blocking-pair hypothesis.

    lines 28–29

    uses if_neg

      · rw [if_neg h1]
        exact h_m_pref
if_pos
If a proposition c holds, the conditional expression (if c then t else e) evaluates to t.
if_neg
If a proposition c is false (¬c), the conditional expression (if c then t else e) evaluates to e.
False.elim
From a contradiction (a proof of False), any conclusion follows (ex falso quodlibet).

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- A matching stable after t-cutoff tanking by w that assigns w at least t is stable in the original market. -/theorem woman_cutoff_tanking_is_stable_of_ge {M W : Type*}    (market : MarriageMarket M W) (w : W) (t : M)    (hw_trans : ∀ a b c : M, market.pref_w w a b → market.pref_w w b c → market.pref_w w a c)    (μ : M ≃ W)    (h_tank_stable : is_stable_matching (woman_cutoff_tanking market w t) μ)    (h_ge : ¬ market.pref_w w t (μ.symm w)) :    is_stable_matching market μ := by  intro m' w' h_bp  have h_tank_not_bp := h_tank_stable m' w'  rcases h_bp with ⟨h_m_pref, h_w_pref⟩  apply h_tank_not_bp  refine ⟨?_, h_w_pref⟩  dsimp [woman_cutoff_tanking]  by_cases h1 : market.pref_w w t m'  · rw [if_pos h1]    dsimp [move_to_bottom]    by_cases h2 : w' = w    · rw [if_pos h2]      rw [h2] at h_w_pref      exact False.elim (h_ge (hw_trans t m' (μ.symm w) h1 h_w_pref))    · rw [if_neg h2]      by_cases h3 : μ m' = w      · rw [if_pos h3]        trivial      · rw [if_neg h3]        exact h_m_pref  · rw [if_neg h1]    exact h_m_pref
See it in the graphDiscuss this resultChallenge it