cyclic_latin_rank_matching_is_stable
For 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 stable in cyclic_latin_market n a.
Statement
theorem cyclic_latin_rank_matching_is_stable (n : ℕ) (a : Fin n ≃ ZMod n) (r : Fin n) :
is_stable_matching (cyclic_latin_market n a) (cyclic_latin_rank_matching n a r)- Formalizes
- Benjamin, Converse, Krieger (1995)
- Verified
- 10 Nov 2026
- Axioms
Quot.soundpropext- Built on 5
- 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…
- cyclic_latin_rank_matchingGiven a natural number n, an ordering bijection a : Fin n ≃ ZMod n, and an index r : Fin n, cyclic_latin_rank_matching n a r is the…
- 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,…
- 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…
- 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…
- Used by 1
- 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:…
Read back from the Lean
For every natural number $n$, every bijection $a : \text{Fin } n \simeq \mathbb{Z}/n\mathbb{Z}$, and every $r \in \text{Fin } n$, the matching $\mu : \mathbb{Z}/n\mathbb{Z} \simeq \mathbb{Z}/n\mathbb{Z}$ defined by $\mu(i) = a(r) - i$ is a stable matching in the cyclic Latin marriage market associated to $(n, a)$. That is, there is no pair $(m, w) \in \mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ that blocks $\mu$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof argues by contradiction: suppose there exists a blocking pair (m, w). In the constant-rank matching π_r, every agent is matched so that the sum of the partners in ℤ/nℤ is identically a(r), meaning every agent's match has rank r. For man m to prefer w, the rank of m + w must be strictly less than r, but under the opposing preferences for women, for woman w to prefer m, the rank of m + w must be strictly greater than r; these two strict inequalities cannot both hold.
Assuming for contradiction that (m, w) is a blocking pair, their preference conditions translate to rank inequalities comparing the pair's sum m + w to the sums with their assigned partners.
By definition of stability, there can be no blocking pair (m, w). Assuming one exists gives hypotheses hm (m prefers w to his current match μ(m)) and hw (w prefers m to her current match μ⁻¹(w)). Expanding the definitions of the matching μ(i) = a(r) - i and the cyclic Latin market preferences, hm means a⁻¹(m + w) < a⁻¹(m + (a(r) - m)) and hw means a⁻¹((a(r) - w) + w) < a⁻¹(m + w).
intro m w ⟨hm, hw⟩ dsimp [cyclic_latin_market, cyclic_latin_rank_matching] at hm hw
The sum of each agent with their assigned match equals a(r).
In the additive group ℤ/nℤ, the sum of man m and his partner is m + (a(r) - m) = a(r) by add_sub_cancel. Similarly, woman w and her partner sum to (a(r) - w) + w = a(r) by sub_add_cancel.
uses
add_sub_cancel,sub_add_cancelhave hm_eq : m + (a r - m) = a r := add_sub_cancel m (a r) have hw_eq : (a r - w) + w = a r := sub_add_cancel (a r) w
The blocking conditions simplify to a⁻¹(m + w) < r and r < a⁻¹(m + w).
Substituting the partner sums into hm and hw, the assigned partner rank in each expression is a⁻¹(a(r)), which equals r by Equiv.symm_apply_apply. Thus, hm becomes a⁻¹(m + w) < r and hw becomes r < a⁻¹(m + w).
uses
Equiv.symm_apply_applyrw [hm_eq, Equiv.symm_apply_apply] at hm rw [hw_eq, Equiv.symm_apply_apply] at hw
Contradiction: no blocking pair can exist.
The inequalities require the natural number a⁻¹(m + w) to be both strictly less than r and strictly greater than r, which is impossible. The omega tactic closes the proof by linear arithmetic over ℕ.
omega
add_sub_cancel- In an additive commutative group, adding an element and then subtracting it cancels: a + (b - a) = b.
sub_add_cancel- In an additive group, subtracting an element and then adding it back cancels: (a - b) + b = a.
Equiv.symm_apply_apply- Applying the inverse of an equivalence to the image of an element yields the original element: e.symm (e x) = x.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Every constant-rank matching pi_r(i) = a_r - i is stable in the opposed cyclic Latin market. -/theorem cyclic_latin_rank_matching_is_stable (n : ℕ) (a : Fin n ≃ ZMod n) (r : Fin n) : is_stable_matching (cyclic_latin_market n a) (cyclic_latin_rank_matching n a r) := by intro m w ⟨hm, hw⟩ dsimp [cyclic_latin_market, cyclic_latin_rank_matching] at hm hw have hm_eq : m + (a r - m) = a r := add_sub_cancel m (a r) have hw_eq : (a r - w) + w = a r := sub_add_cancel (a r) w rw [hm_eq, Equiv.symm_apply_apply] at hm rw [hw_eq, Equiv.symm_apply_apply] at hw omega