AGGame.Lipschitz
def
λ-Lipschitz utilities: |u(x) − u(y)| ≤ λ ‖x − y‖₁ for all partitions x, y of the other n − 1 players.
Statement
open Finset in def AGGame.Lipschitz {n s : ℕ} (G : AGGame n s) (lam : ℚ) : 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 6
- ag_two_exactExact answer for two strategies. For anonymous games with s = 2 strategies the best possible pure approximation is exactly 2λ = sλ: every…
- agMP_lipschitzMatching pennies, as an anonymous game, is 1/2-Lipschitz in the l1 norm on count vectors.
- ag_two_upperUpper bound for two strategies. Every λ-Lipschitz anonymous game with two strategies (any number of players) has a 2λ-approximate pure…
- agCyc_lipschitzThe cyclic game is 1/8-Lipschitz (for at least two strategies).
- 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 /-- `λ`-Lipschitz utilities: `|u(x) − u(y)| ≤ λ ‖x − y‖₁` for all partitions `x, y` of the other `n − 1` players. -/ def AGGame.Lipschitz {n s : ℕ} (G : AGGame n s) (lam : ℚ) : Prop := ∀ p i (x y : Fin s → ℕ), ∑ j, x j = n - 1 → ∑ j, y j = n - 1 → |G.u p i x - G.u p i y| ≤ lam * ∑ j, |(x j : ℚ) - (y j : ℚ)|