stable_matching_of_all_women_top_choice
In a marriage market market with agent types M and W, if every woman w : W is matched under equivalence μ : M ≃ W to a man μ.symm w such that for all men m : M she does not strictly prefer m to μ.symm w (that is, ∀ (w : W) (m : M), ¬ market.pref_w w m (μ.symm w)), then the matching has no blocking pairs, meaning that for all m : M and w : W, ¬ (market.pref_m m w (μ m) ∧ market.pref_w w m (μ.symm w)).
Statement
theorem stable_matching_of_all_women_top_choice {M W : Type*} (market : MarriageMarket M W) (μ : M ≃ W) (h_top : ∀ (w : W) (m : M), ¬ market.pref_w w m (μ.symm w)) : ∀ (m : M) (w : W), ¬ (market.pref_m m w (μ m) ∧ market.pref_w w m (μ.symm w))
- Source
- Roth & Sotomayor 1990, Section 2.2
- Verified
- 07 Sep 2026
- Axioms
Quot.sound- Built on 1
- 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…
Read back from the Lean
For any two types $M$ and $W$, any market : MarriageMarket M W (providing preference relations pref_m : M → W → W → Prop and pref_w : W → M → M → Prop), and any bijection $\mu : M \simeq W$:
If for every woman $w : W$ and every man $m : M$, it is not the case that $w$ prefers $m$ over her assigned partner $\mu^{-1}(w)$ (¬ market.pref_w w m (μ.symm w)),
then for every man $m : M$ and woman $w : W$, it is not the case that both:
1. $m$ prefers $w$ over his assigned partner $\mu(m)$ (market.pref_m m w (μ m)), and
2. $w$ prefers $m$ over her assigned partner $\mu^{-1}(w)$ (market.pref_w w m (μ.symm w)).
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
/-- A matching in which every woman receives her top choice has no blocking pairs. -/ theorem stable_matching_of_all_women_top_choice {M W : Type*} (market : MarriageMarket M W) (μ : M ≃ W) (h_top : ∀ (w : W) (m : M), ¬ market.pref_w w m (μ.symm w)) : ∀ (m : M) (w : W), ¬ (market.pref_m m w (μ m) ∧ market.pref_w w m (μ.symm w)) := fun _ w ⟨_, hw⟩ => h_top w _ hw