is_blocking_pair
def
In 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 w to his assigned partner μ m, and w strictly prefers m to her assigned partner μ.symm w.
Statement
def is_blocking_pair {M W : Type*} (market : MarriageMarket M W) (μ : M ≃ W) (m : M) (w : W) : Prop
- Defined in
- College Admissions and the Stability of Marriage (1962): blocking pair of a matching in the marriage market; standard textbook definition (matching markets)
- Verified
- 06 Oct 2026
- Axioms
- none listed
- 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…
- 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…
- opposed_latin_blocking_sum_eqLet n >= 2 and let L be an n x n Latin square with symbols 0,...,n-1 (every row and every column of L is a permutation). In the opposed…
- 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…
- 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,…
- 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…
- hollow_shell_blocking_pairs_ncard_leThe upper half of the Shield-Core conjecture (arXiv:2609.17418, open): in the cyclic Hollow-Shell market C_n, every complete matching has…
Lean source view module on GitHub
/-- `m` and `w` block the matching `μ`: each strictly prefers the other to their assigned partner. -/ def is_blocking_pair {M W : Type*} (market : MarriageMarket M W) (μ : M ≃ W) (m : M) (w : W) : Prop := market.pref_m m w (μ m) ∧ market.pref_w w m (μ.symm w)