AFTD Auto-Formalizing Theoretical Domains

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)
See it in the graphDiscuss this resultChallenge it