ag_two_upper
theoremverifiedoriginal
Upper bound for two strategies. Every λ-Lipschitz anonymous game with two strategies (any number of players) has a 2λ-approximate pure Nash equilibrium.
Statement
open Finset in theorem ag_two_upper {n : ℕ} (G : AGGame n 2) (lam : ℚ) (hlam : 0 ≤ lam) (hL : G.Lipschitz lam) : ∃ σ : Fin n → Fin 2, G.PureNE (2 * lam) σ
- 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 6
- AGGameAn anonymous game with n players and s strategies (setting of arXiv 0710.5582, "Computing equilibria in anonymous games", Section 2): the…
- AGGame.Lipschitzλ-Lipschitz utilities: |u(x) − u(y)| ≤ λ ‖x − y‖₁ for all partitions x, y of the other n − 1 players.
- agCntNumber of players other than p using strategy j in the pure profile σ.
- AGGame.PureNEThe pure profile σ is an ε-approximate pure Nash equilibrium.
- agCnt_sumThe counts of the others always form a partition of n − 1.
- agY2Two-strategy count vector with k others on strategy 1.
- Used by 1
- ag_two_exactExact answer for two strategies. For anonymous games with s = 2 strategies the best possible pure approximation is exactly 2λ = sλ: every…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finset in/-- **Upper bound for two strategies.** Every `λ`-Lipschitz anonymous game with two strategies (any number of players) has a `2λ`-approximate pure Nash equilibrium. -/theorem ag_two_upper {n : ℕ} (G : AGGame n 2) (lam : ℚ) (hlam : 0 ≤ lam) (hL : G.Lipschitz lam) : ∃ σ : Fin n → Fin 2, G.PureNE (2 * lam) σ := by -- payoff advantage of strategy 1 when `k` others play 1 set d : Fin n → ℕ → ℚ := fun p k => G.u p 1 (agY2 n k) - G.u p 0 (agY2 n k) with hd have hsumY : ∀ k, k ≤ n - 1 → ∑ j, agY2 n k j = n - 1 := by intro k hk simp [agY2, Fin.sum_univ_two]; omega -- one step of `k` moves each payoff by at most `2λ` have hstep : ∀ p i k, k + 1 ≤ n - 1 → |G.u p i (agY2 n (k + 1)) - G.u p i (agY2 n k)| ≤ 2 * lam := by intro p i k hk have := hL p i (agY2 n (k + 1)) (agY2 n k) (hsumY _ hk) (hsumY _ (by omega)) have hl1 : ∑ j, |((agY2 n (k + 1) j : ℕ) : ℚ) - (agY2 n k j : ℚ)| = 2 := by simp only [Fin.sum_univ_two, agY2] simp only [show (0 : Fin 2) ≠ 1 by decide, if_false, if_true] have h1 : ((n - 1 - (k + 1) : ℕ) : ℚ) = (n : ℚ) - 1 - k - 1 := by rw [Nat.cast_sub (by omega), Nat.cast_sub (by omega)]; push_cast; ring have h2 : ((n - 1 - k : ℕ) : ℚ) = (n : ℚ) - 1 - k := by rw [Nat.cast_sub (by omega), Nat.cast_sub (by omega)]; push_cast; ring rw [h1, h2]; push_cast rw [show (n : ℚ) - 1 - k - 1 - (n - 1 - k) = -1 by ring, show ((k : ℚ) + 1 - k) = 1 by ring] norm_num rw [hl1] at this; linarith set A : ℕ → Finset (Fin n) := fun m => Finset.univ.filter (fun p => m < n ∧ 2 * lam < d p m) with hA set B : ℕ → Finset (Fin n) := fun m => Finset.univ.filter (fun p => 0 < m ∧ d p (m - 1) < -(2 * lam)) with hB have hex : ∃ m, (A m).card ≤ m := ⟨n, by have : A n = ∅ := by ext p; simp [hA] rw [this]; simp⟩ classical set m := Nat.find hex with hm have hmA : (A m).card ≤ m := Nat.find_spec hex have hmn : m ≤ n := Nat.find_min' hex (by have : A n = ∅ := by ext p; simp [hA] rw [this]; simp) have hB_le : (B m).card ≤ n - m := by by_cases h0 : m = 0 · have : B m = ∅ := by ext p; simp [hB, h0] rw [this]; simp · have hlt : ¬ (A (m - 1)).card ≤ m - 1 := Nat.find_min hex (by omega) have hdisj : Disjoint (A (m - 1)) (B m) := by rw [Finset.disjoint_filter] intro p _ h1 h2 linarith [h1.2, h2.2] have := Finset.card_union_of_disjoint hdisj have := Finset.card_le_univ (A (m - 1) ∪ B m) simp only [Fintype.card_fin] at this omega have hAB : Disjoint (A m) (B m) := by rw [Finset.disjoint_filter] intro p _ h1 h2 have hm1 : m - 1 + 1 = m := by omega have := hstep p 1 (m - 1) (by omega) have h0 := hstep p 0 (m - 1) (by omega) rw [hm1] at this h0 have e1 := (abs_le.1 this).2 have e2 := (abs_le.1 h0).1 have : d p m - d p (m - 1) ≤ 4 * lam := by simp only [hd]; linarith linarith [h1.2, h2.2] -- choose the set `S` of players on strategy 1 have hsub : A m ⊆ Finset.univ \ B m := by intro p hp simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] exact Finset.disjoint_left.1 hAB hp have hcardt : m ≤ (Finset.univ \ B m).card := by rw [Finset.card_sdiff_of_subset (Finset.subset_univ _), Finset.card_univ, Fintype.card_fin] omega obtain ⟨S, hAS, hSB, hScard⟩ := Finset.exists_subsuperset_card_eq hsub hmA hcardt refine ⟨fun p => if p ∈ S then 1 else 0, ?_⟩ intro p j -- the count vector seen by `p` have hc1 : agCnt (fun q => if q ∈ S then (1 : Fin 2) else 0) p 1 = (S.erase p).card := by unfold agCnt; congr 1; ext q; by_cases hq : q ∈ S <;> simp [hq, and_comm] have hsum := agCnt_sum (fun q => if q ∈ S then (1 : Fin 2) else 0) p rw [Fin.sum_univ_two] at hsum by_cases hp : p ∈ S · have hk : (S.erase p).card = m - 1 := by rw [Finset.card_erase_of_mem hp, hScard] have hm0 : 0 < m := by rw [← hScard]; exact Finset.card_pos.2 ⟨p, hp⟩ have hcnt : agCnt (fun q => if q ∈ S then (1 : Fin 2) else 0) p = agY2 n (m - 1) := by funext i fin_cases i · simp [agY2]; rw [hc1, hk] at hsum; omega · simp [agY2]; rw [hc1, hk] have hpB : p ∉ B m := fun h => (Finset.mem_sdiff.1 (hSB hp)).2 h simp only [hB, Finset.mem_filter, Finset.mem_univ, true_and, not_and, not_lt] at hpB have := hpB hm0 simp only [hp, if_true, hcnt] fin_cases j · simp only [hd] at this; simp; linarith · simp; linarith · have hk : (S.erase p).card = m := by rw [Finset.erase_eq_of_notMem hp, hScard] have hmlt : m < n := by have : S ⊆ Finset.univ.erase p := fun q hq => Finset.mem_erase.2 ⟨fun e => hp (e ▸ hq), mem_univ _⟩ have hle := Finset.card_le_card this rw [Finset.card_erase_of_mem (mem_univ _), Finset.card_univ, Fintype.card_fin, hScard] at hle have := p.isLt omega have hcnt : agCnt (fun q => if q ∈ S then (1 : Fin 2) else 0) p = agY2 n m := by funext i fin_cases i · simp [agY2]; rw [hc1, hk] at hsum; omega · simp [agY2]; rw [hc1, hk] have hpA : p ∉ A m := fun h => hp (hAS h) simp only [hA, Finset.mem_filter, Finset.mem_univ, true_and, not_and, not_lt] at hpA have := hpA hmlt simp only [hp, if_false, hcnt] fin_cases j · simp; linarith · simp only [hd] at this; simp; linarith