ag_four_lower
theoremverifiedoriginal
Four strategies: the lower bound sλ is attained. The 5-player, 4-strategy cyclic game is normalised and λ = 1/8-Lipschitz, yet has no pure ε-equilibrium for any ε < 4λ = sλ.
Statement
open Finset in theorem ag_four_lower : ∃ G : AGGame 5 4, G.Normalized ∧ G.Lipschitz (1 / 8) ∧ ∀ ε : ℚ, ε < 4 * (1 / 8) → ∀ σ : Fin 5 → Fin 4, ¬ G.PureNE ε σ
- Related work
- operator (Claude), 2026-10-05: small cases of the conjecture of Computing Equilibria in Anonymous Games, FOCS 2007 (arXiv:0710.5582), Sections 1-2 and the concluding conjecture that s*lambda is a lower bound for the approximation of pure Nash equilibria: for s = 2 the optimal pure approximation is exactly 2 lambda (greedy threshold argument plus matching pennies); for s = 3 and s = 4 a cyclic 5-player game with lambda = 1/8 has no pure epsilon-equilibrium for epsilon < 4 lambda; found by MILP/SMT search, checked by the Lean kernel (finite certificates via decide)
- Verified
- 05 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- AGGameAn anonymous game with n players and s strategies (setting of arXiv 0710.5582, "Computing equilibria in anonymous games", Section 2): the…
- AGGame.NormalizedPayoffs lie in [0, 1] (the normalisation of arXiv 0710.5582) on all partitions of the other n − 1 players.
- AGGame.Lipschitzλ-Lipschitz utilities: |u(x) − u(y)| ≤ λ ‖x − y‖₁ for all partitions x, y of the other n − 1 players.
- AGGame.PureNEThe pure profile σ is an ε-approximate pure Nash equilibrium.
- 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…
- agCyc_lipschitzThe cyclic game is 1/8-Lipschitz (for at least two strategies).
- agCyc_normalizedThe cyclic game with n = 5 players has payoffs in [0, 1].
- agTotTotal number of players on each strategy.
- agTot_sumThe total counts of a pure profile over all strategies sum to the number of players n.
- agCyc4_checkFinite check for four strategies and five players.
- agCyc_regretFrom a regret-2 certificate on the totals to a player with regret 1/2.
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/-- **Four strategies: the lower bound `sλ` is attained.** The 5-player, 4-strategy cyclic game is normalised and `λ = 1/8`-Lipschitz, yet has no pure `ε`-equilibrium for any `ε < 4λ = sλ`. -/theorem ag_four_lower : ∃ G : AGGame 5 4, G.Normalized ∧ G.Lipschitz (1 / 8) ∧ ∀ ε : ℚ, ε < 4 * (1 / 8) → ∀ σ : Fin 5 → Fin 4, ¬ G.PureNE ε σ := by refine ⟨agCyc 5 4, agCyc_normalized 4 (by norm_num), agCyc_lipschitz 5 4 (by norm_num), ?_⟩ intro ε hε σ hNE have hsum := agTot_sum σ rw [Fin.sum_univ_four] at hsum have hc : agTot σ = ![agTot σ 0, agTot σ 1, agTot σ 2, agTot σ 3] := by funext k; fin_cases k <;> rfl obtain ⟨i, j, hpos, hreg⟩ := agCyc4_check ⟨agTot σ 0, by omega⟩ ⟨agTot σ 1, by omega⟩ ⟨agTot σ 2, by omega⟩ ⟨agTot σ 3, by omega⟩ (by simpa using hsum) simp only at hpos hreg rw [← hc] at hpos hreg obtain ⟨p, hp⟩ := agCyc_regret σ i j hpos hreg have := hNE p j linarith