AFTD Auto-Formalizing Theoretical Domains

agCyc_normalized

theoremverified

The cyclic game with n = 5 players has payoffs in [0, 1].

Statement

open Finset in
theorem agCyc_normalized (s : ℕ) [NeZero s] (hs : 2 ≤ s) : (agCyc 5 s).Normalized
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.NormalizedPayoffs lie in [0, 1] (the normalisation of arXiv 0710.5582) on all partitions 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…
  • agCycVInteger numerator of the cyclic game's payoff.
  • agCyc_u_eqThe payoff of the cyclic anonymous game is the integer table agCycV divided by 4.
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 with `n = 5` players has payoffs in `[0, 1]`. -/theorem agCyc_normalized (s : ℕ) [NeZero s] (hs : 2 ≤ s) : (agCyc 5 s).Normalized := by  intro p i y 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  have h2 : y (i + 1) + y i ≤ 4 := by    have := Finset.sum_le_sum_of_subset (f := y) (Finset.subset_univ {i + 1, i})    rw [Finset.sum_pair hi, hy] at this    simpa using this  rw [agCyc_u_eq]  simp only [agCycV]  constructor  · positivity  · have : y (i + 1) + min (y i) 2 ≤ 4 := by omega    have : ((y (i + 1) + min (y i) 2 : ℕ) : ℚ) ≤ 4 := by exact_mod_cast this    linarith
See it in the graphDiscuss this resultChallenge it