AFTD Auto-Formalizing Theoretical Domains

agCyc_lipschitz

theoremverified

The cyclic game is 1/8-Lipschitz (for at least two strategies).

Statement

open Finset in
theorem agCyc_lipschitz (n s : ℕ) [NeZero s] (hs : 2 ≤ s) : (agCyc n s).Lipschitz (1 / 8)
Source
step towards ag_two_exact / ag_three_lower / ag_four_lower (Computing Equilibria in Anonymous Games, FOCS 2007 (arXiv:0710.5582), concluding conjecture that s*lambda is a lower bound)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • AGGame.Lipschitzλ-Lipschitz utilities: |u(x) − u(y)| ≤ λ ‖x − y‖₁ for all partitions x, y of the other n − 1 players.
  • agCycThe cyclic game u_i(y) = (y_{i+1} + min(y_i, 2)) / 4: a player on strategy i gains from others on the "next" strategy i+1 and from company…
  • ag_abs_auxElementary inequality behind the Lipschitz bound.
  • ag_min_auxFor rationals X, Y, the difference min(X,2) - min(Y,2) lies between 0 and X - Y.
Used by 2
  • ag_four_lowerFour strategies: the lower bound sλ is attained. The 5-player, 4-strategy cyclic game is normalised and λ = 1/8-Lipschitz, yet has no pure…
  • ag_three_lowerThree strategies: the lower bound exceeds sλ. The 5-player, 3-strategy cyclic game is normalised and λ = 1/8-Lipschitz, yet has no pure…

Lean source view module on GitHub

open Finset in/-- The cyclic game is `1/8`-Lipschitz (for at least two strategies). -/theorem agCyc_lipschitz (n s : ℕ) [NeZero s] (hs : 2 ≤ s) : (agCyc n s).Lipschitz (1 / 8) := by  intro p i x y hx hy  have hi : i + 1 ≠ i := by    intro h    have h' := congrArg Fin.val h    rw [Fin.val_add] at h'    have : (1 : Fin s).val = 1 := by      rw [Fin.val_one']; exact Nat.mod_eq_of_lt (by omega)    rw [this] at h'    have hi := i.isLt    rcases Nat.lt_or_ge (i.val + 1) s with h2 | h2    · rw [Nat.mod_eq_of_lt h2] at h'; omega    · have : i.val + 1 = s := by omega      rw [this, Nat.mod_self] at h'; omega  set D : Fin s → ℚ := fun j => (x j : ℚ) - (y j : ℚ) with hD  have hsum0 : ∑ j, D j = 0 := by    simp only [hD, Finset.sum_sub_distrib]    have hx' : ∑ j, (x j : ℚ) = ((n - 1 : ℕ) : ℚ) := by exact_mod_cast hx    have hy' : ∑ j, (y j : ℚ) = ((n - 1 : ℕ) : ℚ) := by exact_mod_cast hy    rw [hx', hy', sub_self]  -- split the sums at `i` and `i + 1`  have hmem : i + 1 ∈ (Finset.univ : Finset (Fin s)).erase i := Finset.mem_erase.2 ⟨hi, mem_univ _⟩  have split : ∀ f : Fin s → ℚ, ∑ j, f j =      f i + f (i + 1) + ∑ j ∈ ((Finset.univ.erase i).erase (i + 1)), f j := by    intro f    rw [← Finset.add_sum_erase _ _ (mem_univ i), ← Finset.add_sum_erase _ _ hmem]    ring  have hrest : ∑ j ∈ ((Finset.univ.erase i).erase (i + 1)), D j = -(D (i + 1) + D i) := by    have := split D; rw [hsum0] at this; linarith  have habs : |D (i + 1) + D i| ≤ ∑ j ∈ ((Finset.univ.erase i).erase (i + 1)), |D j| := by    rw [← abs_neg, ← hrest]; exact Finset.abs_sum_le_sum_abs _ _  have htot : |D (i + 1)| + |D i| + |D (i + 1) + D i| ≤ ∑ j, |D j| := by    rw [split (fun j => |D j|)]; linarith  have key := ag_abs_aux (D (i + 1)) (min (x i : ℚ) 2 - min (y i : ℚ) 2) (D i)    (ag_min_aux (x i) (y i))  simp only [agCyc]  have : ((x (i + 1) : ℚ) + min (x i : ℚ) 2) / 4 - ((y (i + 1) : ℚ) + min (y i : ℚ) 2) / 4      = (D (i + 1) + (min (x i : ℚ) 2 - min (y i : ℚ) 2)) / 4 := by    simp only [hD]; ring  rw [this, abs_div, show |(4 : ℚ)| = 4 by norm_num]  show _ ≤ 1 / 8 * ∑ j, |D j|  linarith
See it in the graphDiscuss this resultChallenge it