AFTD Auto-Formalizing Theoretical Domains

AGGame

structure

An anonymous game with n players and s strategies (setting of arXiv 0710.5582, "Computing equilibria in anonymous games", Section 2): the payoff of player p for strategy i depends only on the vector y : Fin s → ℕ of counts of the *other* players on each strategy.

Statement

structure AGGame (n s : ℕ)
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
Used by 9
  • agMPMatching pennies as a 2-player, 2-strategy anonymous game: player 0 wants to match the other player, player 1 wants to mismatch.
  • AGGame.Lipschitzλ-Lipschitz utilities: |u(x) − u(y)| ≤ λ ‖x − y‖₁ for all partitions x, y of the other n − 1 players.
  • 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…
  • 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…
  • AGGame.PureNEThe pure profile σ is an ε-approximate pure Nash equilibrium.
  • AGGame.NormalizedPayoffs lie in [0, 1] (the normalisation of arXiv 0710.5582) on all partitions of the other n − 1 players.
  • 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

/-- An anonymous game with `n` players and `s` strategies (setting of arXiv 0710.5582, "Computing equilibria in anonymous games", Section 2): the payoff of player `p` for strategy `i` depends only on the vector `y : Fin s → ℕ` of counts of the *other* players on each strategy. -/
structure AGGame (n s : ℕ) where
  u : Fin n → Fin s → (Fin s → ℕ) → ℚ
See it in the graphDiscuss this resultChallenge it