AFTD Auto-Formalizing Theoretical Domains

agCnt_eq

theoremverified

The count of other players on strategy j seen by player p is the total count on j minus one if p plays j.

Statement

open Finset in
theorem agCnt_eq {n s : ℕ} (σ : Fin n → Fin s) (p : Fin n) (j : Fin s) :
    agCnt σ p j = agTot σ j - (if σ p = j then 1 else 0)
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 2
  • agCntNumber of players other than p using strategy j in the pure profile σ.
  • agTotTotal number of players on each strategy.
Used by 1
  • agCyc_regretFrom a regret-2 certificate on the totals to a player with regret 1/2.

Lean source view module on GitHub

open Finset intheorem agCnt_eq {n s : ℕ} (σ : Fin n → Fin s) (p : Fin n) (j : Fin s) :    agCnt σ p j = agTot σ j - (if σ p = j then 1 else 0) := by  unfold agCnt agTot  have : Finset.univ.filter (fun q => q ≠ p ∧ σ q = j) = (Finset.univ.filter (fun q => σ q = j)).erase p := by    ext q; simp [and_comm]  rw [this]  by_cases h : σ p = j  · rw [if_pos h, Finset.card_erase_of_mem (by simp [h])]  · rw [if_neg h, Finset.erase_eq_of_notMem (by simp [h])]; simp
See it in the graphDiscuss this resultChallenge it