ag_two_exact
theoremverifiedoriginal
Exact answer for two strategies. For anonymous games with s = 2 strategies the best possible pure approximation is exactly 2λ = sλ: every λ-Lipschitz game has a pure 2λ-equilibrium, and (normalised, 1/2-Lipschitz) matching pennies has no pure ε-equilibrium with ε < 2λ.
Statement
theorem ag_two_exact :
(∀ (n : ℕ) (G : AGGame n 2) (lam : ℚ), 0 ≤ lam → G.Lipschitz lam →
∃ σ : Fin n → Fin 2, G.PureNE (2 * lam) σ) ∧
(∃ G : AGGame 2 2, G.Normalized ∧ G.Lipschitz (1 / 2) ∧
∀ ε : ℚ, ε < 2 * (1 / 2) → ∀ σ : Fin 2 → Fin 2, ¬ 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 9
- 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.
- ag_two_upperUpper bound for two strategies. Every λ-Lipschitz anonymous game with two strategies (any number of players) has a 2λ-approximate pure…
- agMPMatching pennies as a 2-player, 2-strategy anonymous game: player 0 wants to match the other player, player 1 wants to mismatch.
- agMP_normalizedMatching pennies, written as a 2-player 2-strategy anonymous game, has payoffs in [0,1].
- agMP_lipschitzMatching pennies, as an anonymous game, is 1/2-Lipschitz in the l1 norm on count vectors.
- agMP_no_pureNEIn matching pennies every pure profile leaves a player with regret 1 = 2λ.
Lean source view module on GitHub
/-- **Exact answer for two strategies.** For anonymous games with `s = 2` strategies the best possible pure approximation is exactly `2λ = sλ`: every `λ`-Lipschitz game has a pure `2λ`-equilibrium, and (normalised, `1/2`-Lipschitz) matching pennies has no pure `ε`-equilibrium with `ε < 2λ`. -/ theorem ag_two_exact : (∀ (n : ℕ) (G : AGGame n 2) (lam : ℚ), 0 ≤ lam → G.Lipschitz lam → ∃ σ : Fin n → Fin 2, G.PureNE (2 * lam) σ) ∧ (∃ G : AGGame 2 2, G.Normalized ∧ G.Lipschitz (1 / 2) ∧ ∀ ε : ℚ, ε < 2 * (1 / 2) → ∀ σ : Fin 2 → Fin 2, ¬ G.PureNE ε σ) := ⟨fun _ G lam hlam hL => ag_two_upper G lam hlam hL, ⟨agMP, agMP_normalized, agMP_lipschitz, agMP_no_pureNE⟩⟩