cyclic_latin_market
For 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 L_a(i,j), and woman j ranks man i by decreasing rank L_a(i,j), where L_a(i,j) is the index r with i + j = a_r.
Statement
def cyclic_latin_market (n : ℕ) (a : Fin n ≃ ZMod n) :
MarriageMarket (ZMod n) (ZMod n)- Defined in
- Benjamin, Converse, Krieger (1995)
- Verified
- 10 Nov 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 3
- 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:…
- 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…
- 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…
Read back from the Lean
cyclic_latin_market defines a MarriageMarket (ZMod n) (ZMod n) parameterized by a natural number n and an equivalence a : Fin n ≃ ZMod n. In this market, both the set of men and the set of women are ZMod n:
- Man i prefers woman j over woman j' (pref_m i j j') if and only if (a.symm (i + j) : ℕ) < (a.symm (i + j') : ℕ).
- Woman j prefers man i over man i' (pref_w j i i') if and only if (a.symm (i' + j) : ℕ) < (a.symm (i + j) : ℕ).
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
/-- The opposed cyclic Latin marriage market associated with an ordering a of Z/nZ. -/ def cyclic_latin_market (n : ℕ) (a : Fin n ≃ ZMod n) : MarriageMarket (ZMod n) (ZMod n) where pref_m i j j' := (a.symm (i + j) : ℕ) < (a.symm (i + j') : ℕ) pref_w j i i' := (a.symm (i' + j) : ℕ) < (a.symm (i + j) : ℕ)