woman_cutoff_tanking_is_stable_of_ge
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.
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.
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⟩
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.
uses
if_pos,False.elimdsimp [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))
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.
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
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.
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).
- The hypothesis ¬ market.pref_w w t (μ.symm w) formally expresses that woman w weakly prefers her partner μ⁻¹(w) to the cutoff t, phrased as the negation of strict preference because preferences in MarriageMarket are given by strict binary relations.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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