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
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.
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