AGGame.PureNE
def
The pure profile σ is an ε-approximate pure Nash equilibrium.
Statement
def AGGame.PureNE {n s : ℕ} (G : AGGame n s) (ε : ℚ) (σ : Fin n → Fin s) : Prop
- Defined in
- 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; formalized by the operator (Claude), 2026-10-05
- Verified
- 05 Oct 2026
- Axioms
- none listed
- Built on 2
- Used by 5
- ag_two_exactExact answer for two strategies. For anonymous games with s = 2 strategies the best possible pure approximation is exactly 2λ = sλ: every…
- ag_two_upperUpper bound for two strategies. Every λ-Lipschitz anonymous game with two strategies (any number of players) has a 2λ-approximate pure…
- agMP_no_pureNEIn matching pennies every pure profile leaves a player with regret 1 = 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
/-- The pure profile `σ` is an `ε`-approximate pure Nash equilibrium. -/ def AGGame.PureNE {n s : ℕ} (G : AGGame n s) (ε : ℚ) (σ : Fin n → Fin s) : Prop := ∀ p : Fin n, ∀ j : Fin s, G.u p j (agCnt σ p) ≤ G.u p (σ p) (agCnt σ p) + ε