AFTD Auto-Formalizing Theoretical Domains

ag_three_lower

theoremverifiedoriginal

Three strategies: the lower bound exceeds sλ. The 5-player, 3-strategy cyclic game is normalised and λ = 1/8-Lipschitz, yet has no pure ε-equilibrium for any ε < 4λ (and 4λ > 3λ = sλ).

Statement

open Finset in
theorem ag_three_lower :
    ∃ G : AGGame 5 3, G.Normalized ∧ G.Lipschitz (1 / 8) ∧
      ∀ ε : ℚ, ε < 4 * (1 / 8) → ∀ σ : Fin 5 → Fin 3, ¬ 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.
  • agCyc3_checkFinite check for three strategies and five players (totals a + b + d = 5).
  • agCyc_regretFrom a regret-2 certificate on the totals to a player with regret 1/2.

Lean source view module on GitHub

open Finset in/-- **Three strategies: the lower bound exceeds `sλ`.** The 5-player, 3-strategy cyclic game is normalised and `λ = 1/8`-Lipschitz, yet has no pure `ε`-equilibrium for any `ε < 4λ` (and `4λ > 3λ = sλ`). -/theorem ag_three_lower :    ∃ G : AGGame 5 3, G.Normalized ∧ G.Lipschitz (1 / 8) ∧      ∀ ε : ℚ, ε < 4 * (1 / 8) → ∀ σ : Fin 5 → Fin 3, ¬ G.PureNE ε σ := by  refine ⟨agCyc 5 3, agCyc_normalized 3 (by norm_num), agCyc_lipschitz 5 3 (by norm_num), ?_⟩  intro ε hε σ hNE  have hsum := agTot_sum σ  rw [Fin.sum_univ_three] at hsum  have hc : agTot σ = ![agTot σ 0, agTot σ 1, agTot σ 2] := by    funext k; fin_cases k <;> rfl  obtain ⟨i, j, hpos, hreg⟩ := agCyc3_check ⟨agTot σ 0, by omega⟩ ⟨agTot σ 1, by omega⟩    ⟨agTot σ 2, 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
See it in the graphDiscuss this resultChallenge it