AFTD Auto-Formalizing Theoretical Domains

agCyc_regret

theoremverified

From a regret-2 certificate on the totals to a player with regret 1/2.

Statement

open Finset in
theorem agCyc_regret {s : ℕ} [NeZero s] (σ : Fin 5 → Fin s) (i j : Fin s)
    (hpos : 0 < agTot σ i)
    (hreg : agCycV i (agSub (agTot σ) i) + 2 ≤ agCycV j (agSub (agTot σ) i)) :
    ∃ p : Fin 5, (agCyc 5 s).u p (σ p) (agCnt σ p) + 1 / 2 ≤ (agCyc 5 s).u p j (agCnt σ p)
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 7
  • agCntNumber of players other than p using strategy j in the pure profile σ.
  • agCycThe cyclic game u_i(y) = (y_{i+1} + min(y_i, 2)) / 4: a player on strategy i gains from others on the "next" strategy i+1 and from company…
  • agCycVInteger numerator of the cyclic game's payoff.
  • agCyc_u_eqThe payoff of the cyclic anonymous game is the integer table agCycV divided by 4.
  • agTotTotal number of players on each strategy.
  • agCnt_eqThe count of other players on strategy j seen by player p is the total count on j minus one if p plays j.
  • agSubCount vector seen by a player on strategy i when the totals are c.
Used by 2
  • 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/-- From a regret-2 certificate on the totals to a player with regret `1/2`. -/theorem agCyc_regret {s : ℕ} [NeZero s] (σ : Fin 5 → Fin s) (i j : Fin s)    (hpos : 0 < agTot σ i)    (hreg : agCycV i (agSub (agTot σ) i) + 2 ≤ agCycV j (agSub (agTot σ) i)) :    ∃ p : Fin 5, (agCyc 5 s).u p (σ p) (agCnt σ p) + 1 / 2 ≤ (agCyc 5 s).u p j (agCnt σ p) := by  obtain ⟨p, hp⟩ := Finset.card_pos.1 hpos  simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp  refine ⟨p, ?_⟩  have hc : agCnt σ p = agSub (agTot σ) i := by    funext k    rw [agCnt_eq, hp]    unfold agSub    by_cases h : i = k    · subst h; simp    · rw [if_neg h, if_neg (Ne.symm h)]  rw [hc, hp, agCyc_u_eq, agCyc_u_eq]  have : ((agCycV i (agSub (agTot σ) i) + 2 : ℕ) : ℚ) ≤ (agCycV j (agSub (agTot σ) i) : ℚ) := by    exact_mod_cast hreg  push_cast at this  linarith
See it in the graphDiscuss this resultChallenge it