AFTD Auto-Formalizing Theoretical Domains

AGGame.Normalized

def

Payoffs lie in [0, 1] (the normalisation of arXiv 0710.5582) on all partitions of the other n − 1 players.

Statement

open Finset in
def AGGame.Normalized {n s : ℕ} (G : AGGame n 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 1
  • AGGameAn anonymous game with n players and s strategies (setting of arXiv 0710.5582, "Computing equilibria in anonymous games", Section 2): the…
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…
  • agCyc_normalizedThe cyclic game with n = 5 players has payoffs in [0, 1].
  • agMP_normalizedMatching pennies, written as a 2-player 2-strategy anonymous game, has payoffs in [0,1].
  • 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

open Finset in
/-- Payoffs lie in `[0, 1]` (the normalisation of arXiv 0710.5582) on all partitions of the other `n − 1` players. -/
def AGGame.Normalized {n s : ℕ} (G : AGGame n s) : Prop :=
  ∀ p i (y : Fin s → ℕ), ∑ j, y j = n - 1 → 0 ≤ G.u p i y ∧ G.u p i y ≤ 1
See it in the graphDiscuss this resultChallenge it