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