AFTD Auto-Formalizing Theoretical Domains

woman_cutoff_tanking_ge_subset

theoremverified

In 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 (μ.symm w)) remains stable after t-cutoff tanking by w.

Statement

theorem woman_cutoff_tanking_ge_subset {M W : Type*}
    (market : MarriageMarket M W) (w : W) (t : M) (μ : M ≃ W)
    (h_stable : is_stable_matching market μ)
    (h_ge : ¬ market.pref_w w t (μ.symm w)) :
    is_stable_matching (woman_cutoff_tanking market w t) μ
Source
arXiv:2610.42105 Lemma 4.1
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…
  • 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,…
  • 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_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…
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 all types M and W, every marriage market market on M and W, every woman w : W, every man t : M, and every bijective matching μ : M ≃ W: If: 1. μ is a stable matching in market (that is, for every m : M and w' : W, it is not the case that m prefers w' to μ m and w' prefers m to μ.symm w'), and 2. woman w does not prefer t to her matched partner μ.symm w (that is, ¬ market.pref_w w t (μ.symm w)), Then: μ is a stable matching in woman_cutoff_tanking market w t, which is the market where women's preferences are unchanged and each man m for whom woman w prefers t to m (market.pref_w w t m) has woman w moved to the bottom of his preference ranking (so that he never prefers w to any other woman, and prefers any other woman to w), while men for whom this does not hold keep their original preferences.

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

To show that a stable matching μ remains stable after t-cutoff tanking by woman w, it suffices to show that any blocking pair in the tanked market would already have been a blocking pair in the original market. Cutoff tanking leaves women's preferences completely unchanged, so any woman in a putative blocking pair still prefers the blocking man. For men, tanking only demotes w to the bottom of the preference lists of men whom w prefers to t. Since w weakly prefers her own partner μ⁻¹(w) to t, neither a man's assigned partner nor his blocking partner can be w, meaning their relative ranking is unaffected. Because the original market admits no blocking pairs, the tanked market admits none either.

  1. To show that a blocking pair (m, w') in the tanked market is also a blocking pair in the original market, it suffices to show that m prefers w' over μ(m) in the original market.

    Let (m, w') be a blocking pair for μ in the tanked market, so m prefers w' over μ(m) and w' prefers m over μ⁻¹(w') under the tanked preferences. Cutoff tanking does not modify women's preferences, so w' already prefers m over μ⁻¹(w') in the original market. Thus, we only need to verify that m prefers w' over μ(m) in the original market.

    lines 9–11

      intro m w' hbp
      obtain ⟨h1, h2⟩ := hbp
      refine ⟨?_, h2⟩
  2. If woman w prefers t over m, then m's assigned partner μ(m) cannot be w.

    We split into cases based on whether w prefers t over m in the original market. In the positive case, suppose for contradiction that μ(m) = w. Applying μ⁻¹ gives μ⁻¹(w) = m, so the case hypothesis means that w prefers t over μ⁻¹(w). But this contradicts the assumption that w weakly prefers μ⁻¹(w) to t (h_ge). Therefore, μ(m) ≠ w.

    lines 12–17

      by_cases h : market.pref_w w t m
      · have hmw : μ m ≠ w := by
          intro heq
          apply h_ge
          have : μ.symm w = m := by rw [← heq]; simp
          rwa [this]
  3. When w prefers t over m, the blocking woman w' cannot be w.

    Continuing the case where w prefers t over m, suppose w' = w. In the tanked market, w is demoted to the very bottom of m's preference list (move_to_bottom). However, the assumption that (m, w') blocks μ in the tanked market means m prefers w' (which is w) over his assigned match μ(m). Because no candidate can be ranked below the bottom element, this yields an immediate contradiction, closing this subcase.

    lines 18–20

        by_cases hw' : w' = w
        · subst hw'
          simp [woman_cutoff_tanking, h, move_to_bottom] at h1
  4. When w prefers t over m and w' ≠ w, m prefers w' over μ(m) in the original market.

    Since w' ≠ w and μ(m) ≠ w, neither woman is the bottom element w. Thus, moving w to the bottom leaves the relative ranking of w' and μ(m) unchanged. Since m prefers w' over μ(m) in the tanked market, he also prefers w' over μ(m) in the original market.

    lines 21–22

        · simp [woman_cutoff_tanking, h, move_to_bottom, hmw, hw'] at h1
          exact h1
  5. When w does not prefer t over m, m prefers w' over μ(m) in the original market.

    If w does not prefer t over m, then by definition of cutoff tanking, m's preferences are not modified at all. Therefore, m's preference for w' over μ(m) in the tanked market directly implies the same preference in the original market.

    line 23

      · simpa [woman_cutoff_tanking, h] using h1
  6. The matching μ remains stable in the cutoff-tanked market.

    To show stability in the tanked market, suppose for contradiction that there is a blocking pair (m, w'). By the auxiliary lemma (woman_cutoff_tanking_ge_subset_aux), (m, w') must also be a blocking pair in the original market. This contradicts the stability of μ in the original market (h_stable).

    lines 31–32

    uses woman_cutoff_tanking_ge_subset_aux

      intro m w' hbp
      exact h_stable m w' (woman_cutoff_tanking_ge_subset_aux market w t μ h_ge m w' hbp)
woman_cutoff_tanking_ge_subset_aux
If woman w weakly prefers her assigned partner μ⁻¹(w) to t, then any pair that blocks μ in the t-cutoff tanked market is already a blocking pair in the original market.

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 blocking pair in the t-cutoff-tanked market, when `w` weakly prefers her ownpartner over `t`, is already a blocking pair in the original market. -/private theorem woman_cutoff_tanking_ge_subset_aux {M W : Type*}    (market : MarriageMarket M W) (w : W) (t : M) (μ : M ≃ W)    (h_ge : ¬ market.pref_w w t (μ.symm w)) :    ∀ (m : M) (w' : W),      is_blocking_pair (woman_cutoff_tanking market w t) μ m w' →      is_blocking_pair market μ m w' := by  intro m w' hbp  obtain ⟨h1, h2⟩ := hbp  refine ⟨?_, h2⟩  by_cases h : market.pref_w w t m  · have hmw : μ m ≠ w := by      intro heq      apply h_ge      have : μ.symm w = m := by rw [← heq]; simp      rwa [this]    by_cases hw' : w' = w    · subst hw'      simp [woman_cutoff_tanking, h, move_to_bottom] at h1    · simp [woman_cutoff_tanking, h, move_to_bottom, hmw, hw'] at h1      exact h1  · simpa [woman_cutoff_tanking, h] using h1/-- A stable matching assigning woman w at least t survives t-cutoff tanking by w. -/theorem woman_cutoff_tanking_ge_subset {M W : Type*}    (market : MarriageMarket M W) (w : W) (t : M) (μ : M ≃ W)    (h_stable : is_stable_matching market μ)    (h_ge : ¬ market.pref_w w t (μ.symm w)) :    is_stable_matching (woman_cutoff_tanking market w t) μ := by  intro m w' hbp  exact h_stable m w' (woman_cutoff_tanking_ge_subset_aux market w t μ h_ge m w' hbp)
See it in the graphDiscuss this resultChallenge it