AFTD Auto-Formalizing Theoretical Domains

pureVsPayoff_empiricalStrategy

theoremverifiedimported Lean

Pure-row payoff against the empirical column strategy. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N \ge 1$ column actions, and payoff matrix $A$. Fix a row action $i$ and a sequence of column actions $a_0, \dots, a_{T-1}$ with $T > 0$, and let $\hat{q}$ be the associated empirical column strategy. Then the expected payoff of row $i$ against $\hat{q}$ equals the average payoff over the sequence: \[ \sum_{j} A_{ij}\,\hat{q}_j \;=\; \frac{1}{T}\sum_{t=0}^{T-1} A_{i,\,a_t}. \]

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
lemma pureVsPayoff_empiricalStrategy {M N T : ℕ} [NeZero N] (G : ZeroSumGame M N)
    (hT : 0 < T) (actions : Fin T → Fin N) (i : Fin M) :
    pureVsPayoff G i (empiricalStrategy hT actions) =
      (∑ t : Fin T, G.payoff i (actions t)) / T
Source
TCSlib, `pureVsPayoff_empiricalStrategy`
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
Classical.choiceQuot.soundpropext
Built on 3
  • pureVsPayoffGiven a game $G$, a pure row $i$, and a mixed column strategy $q$, the expected payoff of row $i$ against $q$ is…
  • ZeroSumGameA finite two-player zero-sum game with $M$ row actions and $N$ column actions is a record consisting of a payoff matrix…
  • empiricalStrategyGiven $T > 0$ pure actions $a_0, \dots, a_{T-1} \in \mathrm{Fin}\,n$, the empirical strategy is the mixed strategy assigning to…
Used by 1
  • 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 inset_option autoImplicit false inopen Real Finset BigOperators in/-- The payoff of a pure row `i` against the empirical column strategy of a sequence of played columns equals the time average `(1/T) Σ_t A(i, j_t)` of the payoffs of `i` against the columns actually played. [FS99, §5]. **Proof sketch.** A four-step `calc`: unfold the empirical weights and push the payoff `A(i, x)` inside the indicator sum for each column `x`; pull the division by `T` out of the outer sum; swap the order of summation so time is outermost; for each round `t` collapse the indicator sum over columns `x` to the single term `x = j_t`. -/lemma pureVsPayoff_empiricalStrategy {M N T : ℕ} [NeZero N] (G : ZeroSumGame M N)    (hT : 0 < T) (actions : Fin T → Fin N) (i : Fin M) :    pureVsPayoff G i (empiricalStrategy hT actions) =      (∑ t : Fin T, G.payoff i (actions t)) / T := by  simp only [pureVsPayoff, empiricalStrategy]  calc ∑ x : Fin N, G.payoff i x * ((∑ t : Fin T, if actions t = x then 1 else 0) / ↑T)      -- Step 1: push the payoff inside the indicator sum.      = ∑ x : Fin N, (∑ t : Fin T, G.payoff i x *            (if actions t = x then 1 else 0)) / ↑T := by          congr 1          ext x          rw [← Finset.mul_sum]          ring      -- Step 2: pull the division by `T` out of the column sum.    _ = (∑ x : Fin N, ∑ t : Fin T, G.payoff i x *            (if actions t = x then 1 else 0)) / ↑T := by          rw [Finset.sum_div]      -- Step 3: swap the order of summation.    _ = (∑ t : Fin T, ∑ x : Fin N, G.payoff i x *            (if actions t = x then 1 else 0)) / ↑T := by          rw [Finset.sum_comm]      -- Step 4: collapse each indicator sum to the played column.    _ = (∑ t : Fin T, G.payoff i (actions t)) / ↑T := by          congr 1          apply Finset.sum_congr rfl          intro t _          rw [Finset.sum_eq_single (actions t)]          · simp          · intro b _ hb            simp [hb.symm]          · intro h            exact False.elim (h (Finset.mem_univ _))
See it in the graphDiscuss this resultChallenge it