agCnt_sum
theoremverified
The counts of the others always form a partition of n − 1.
Statement
open Finset in theorem agCnt_sum {n s : ℕ} (σ : Fin n → Fin s) (p : Fin n) : ∑ j, agCnt σ p j = n - 1
- Source
- step towards ag_two_exact / ag_three_lower / ag_four_lower (Computing Equilibria in Anonymous Games, FOCS 2007 (arXiv:0710.5582), concluding conjecture that s*lambda is a lower bound)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- agCntNumber of players other than p using strategy j in the pure profile σ.
- Used by 1
- ag_two_upperUpper bound for two strategies. Every λ-Lipschitz anonymous game with two strategies (any number of players) has a 2λ-approximate pure…
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/-- The counts of the others always form a partition of `n − 1`. -/theorem agCnt_sum {n s : ℕ} (σ : Fin n → Fin s) (p : Fin n) : ∑ j, agCnt σ p j = n - 1 := by unfold agCnt rw [← Finset.card_biUnion] · have : (Finset.univ.biUnion fun j => Finset.univ.filter (fun q => q ≠ p ∧ σ q = j)) = Finset.univ.erase p := by ext q; simp [and_comm] rw [this, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin] · intro i _ j _ hij simp only [Function.onFun] rw [Finset.disjoint_filter] intro q _ h1 h2 exact hij (h1.2.symm.trans h2.2)