AFTD Auto-Formalizing Theoretical Domains

MarriageMarket

structure

A 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 relation pref_w : W → M → M → Prop representing women's preferences over men.

Statement

structure MarriageMarket (M W : Type*)
Defined in
Roth & Sotomayor (1990), Two-Sided Matching, Section 2.1; Gale & Shapley (1962), Section 2
Verified
01 Oct 2026
Axioms
none listed
Used by 17
  • 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…
  • man_cutoff_tankingIn a marriage market, the profile obtained by t-cutoff tanking by man m: man m is moved to the bottom of the preference list of every…
  • 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…
  • 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…
  • 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…
  • 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…
  • stable_matching_not_pref_of_prefIn a marriage market market with agent types M and W, if a matching equivalence μ : M ≃ W has no blocking pairs (that is, for all m : M…
  • opposed_latin_marketThe strict opposed Latin marriage market associated with an n × n Latin square L: man i ranks woman j at position L(i,j)+1, and woman j…
  • stable_matching_of_all_women_top_choiceIn 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…
  • cyclic_latin_marketFor an ordering a of Z/nZ, the opposed cyclic Latin marriage market has men and women Z/nZ where man i ranks woman j by increasing rank…
  • 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…
  • stable_matching_of_subsingletonIn a marriage market market with agent types M and W where M is a subsingleton (Subsingleton M), if men's preferences are irreflexive (∀…
  • 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…
  • stable_matching_of_all_men_top_choiceIn a marriage market market with agent types M and W, if every man m : M is matched under equivalence μ : M ≃ W to a woman μ m such that…
  • hollow_shell_marketThe cyclic Hollow-Shell marriage market C_n on n men and n women indexed by Z/nZ: man g ranks woman h at ((h - g) mod n) + 1 and woman h…

Read back from the Lean

A structure MarriageMarket parameterized by types M and W, consisting of: 1. pref_m: for each element $m : M$, a binary relation on $W$ (M → W → W → Prop), and 2. pref_w: for each element $w : W$, a binary relation on $M$ (W → M → M → Prop).

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 two-sided marriage market with agent types M and W and preference relations. -/
structure MarriageMarket (M W : Type*) where
  pref_m : M → W → W → Prop
  pref_w : W → M → M → Prop
See it in the graphDiscuss this resultChallenge it