AFTD Auto-Formalizing Theoretical Domains

averageStrategy

defimported Lean

Given $T$ distributions $p_0, \dots, p_{T-1}$ over $\mathrm{Fin}\,n$ (each presented as non-negative weights summing to $1$) and $T > 0$, the average strategy is the mixed strategy with weights \[ \bar{p}_i \;=\; \frac{1}{T} \sum_{t=0}^{T-1} p_t(i). \]

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
noncomputable def averageStrategy {n T : ℕ} [NeZero n] (hT : 0 < T)
    (strategies : Fin T → Fin n → ℝ)
    (h_nonneg : ∀ t i, 0 ≤ strategies t i)
    (h_sum : ∀ t, ∑ i : Fin n, strategies t i = 1) : MixedStrategy n
Defined in
TCSlib, `averageStrategy`
Lean proof
By Karim Abdel Sadek, Mark Bedaywi, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Karim Abdel Sadek and Mark Bedaywi. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
none listed
Built on 1
  • MixedStrategyA mixed strategy over $n$ actions is a record consisting of a weight function $w : \mathrm{Fin}\,n \to \mathbb{R}$ together with…
Used by 2
  • payoffVsPure_averageStrategyAverage strategy's payoff against a pure column. Let $G$ be a finite two-player zero-sum game with $M \ge 1$ row actions and $N$ column…
  • hedge_constructionHedge yields an approximate minimax pair. Let $G$ be a finite two-player zero-sum game with $M \ge 2$ row actions and $N \ge 1$ column…

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
/-- The time average of `T > 0` probability distributions over `n` actions, as a mixed strategy: the weight of action `i` is `(1/T) Σ_t strategies t i`. This packages the averaged row strategy `P̄ = (1/T) Σ_t P_t` used after running Hedge for `T` rounds. [FS99, §5]. -/
noncomputable def averageStrategy {n T : ℕ} [NeZero n] (hT : 0 < T)
    (strategies : Fin T → Fin n → ℝ)
    (h_nonneg : ∀ t i, 0 ≤ strategies t i)
    (h_sum : ∀ t, ∑ i : Fin n, strategies t i = 1) : MixedStrategy n where
  weights i := (∑ t : Fin T, strategies t i) / T
  nonneg i := div_nonneg (Finset.sum_nonneg fun t _ => h_nonneg t i) (Nat.cast_nonneg T)
  sum_one := by
    rw [← Finset.sum_div, Finset.sum_comm]
    simp_rw [h_sum, Finset.sum_const, Finset.card_fin, nsmul_eq_mul, mul_one]
    exact div_self (Nat.cast_ne_zero.mpr (Nat.pos_iff_ne_zero.mp hT))
See it in the graphDiscuss this resultChallenge it