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
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/-- 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