is_stable_matching
def
In 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, when for every m and every w it is not the case that m prefers w to μ m and w prefers m to μ.symm w.
Statement
def is_stable_matching {M W : Type*} (market : MarriageMarket M W) (μ : M ≃ W) : Prop
- Defined in
- College Admissions and the Stability of Marriage (1962): stable matching; standard textbook definition (matching markets)
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Built on 2
- 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…
- Used by 8
- cyclic_latin_stable_rank_polynomial_order_threeFor n = 3, any two ordering bijections a and b from Fin 3 to ZMod 3 have identical stable-matching rank polynomials:…
- 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…
- cyclic_latin_rank_matching_is_stableFor every natural number n, ordering bijection a : Fin n ≃ ZMod n, and rank r : Fin n, the matching cyclic_latin_rank_matching n a r is…
- 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…
- cyclic_latin_rank_polynomialGiven an order n with [NeZero n] and a bijection a : Fin n ≃ ZMod n, cyclic_latin_rank_polynomial n a is the polynomial in ℤ[X] defined by…
- not_is_stable_matching_of_universal_preferenceIn the marriage market on M and W whose two preference relations are identically true, so that every agent strictly prefers everyone to…
- 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…
- is_stable_matching_of_no_strict_preferenceIn the marriage market on M and W whose two preference relations are identically false, so that no agent strictly prefers anyone to…
Lean source view module on GitHub
/-- A matching is stable when no pair blocks it. -/ def is_stable_matching {M W : Type*} (market : MarriageMarket M W) (μ : M ≃ W) : Prop := ∀ (m : M) (w : W), ¬ is_blocking_pair market μ m w