AFTD Auto-Formalizing Theoretical Domains

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

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)
See it in the graphDiscuss this resultChallenge it