AFTD Auto-Formalizing Theoretical Domains

empiricalJoint_rowDeviationUtility

theoremverifiedimported Lean

Empirical row deviation utility as a time average. Let $G$ be a finite two-player game with $M$ row actions and $N$ column actions, and let $u_r(i,j)$ denote the row player's utility. Fix an integer $T \ge 1$, and suppose that in each round $t \in \{1,\dots,T\}$ the row player plays the mixed strategy $p_t$ over the $M$ row actions and the column player plays the mixed strategy $q_t$ over the $N$ column actions, giving rise to the empirical joint distribution $\sigma$ with $\sigma_{ij} = \tfrac{1}{T}\sum_{t=1}^{T} (p_t)_i\,(q_t)_j$. Then for every pure row action $i'$, the row player's deviation utility under $\sigma$ equals the time average of the expected utilities of playing $i'$ against each round's column strategy: \[ \sum_{j} \sigma^{\mathrm{col}}_j\, u_r(i',j) = \frac{1}{T}\sum_{t=1}^{T}\sum_{j} (q_t)_j\, u_r(i',j). \]

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Finset BigOperators in
lemma empiricalJoint_rowDeviationUtility {M N T : ℕ} (hT : 0 < T)
    (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) (G : Game M N)
    (i' : Fin M) :
    (empiricalJoint hT p q).rowDeviationUtility G i' =
      (∑ t : Fin T, ∑ j : Fin N, (q t).weights j * G.rowUtility i' j) / T
Source
TCSlib, `empiricalJoint_rowDeviationUtility`
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 6
  • empiricalJointGiven $T > 0$ rounds of play in which the row player uses mixed strategy $p_t$ and the column player uses $q_t$, the empirical joint…
  • MixedStrategyA mixed strategy over $n$ actions is a record consisting of a weight function $w : \mathrm{Fin}\,n \to \mathbb{R}$ together with…
  • empiricalJoint_colMarginalColumn marginal of the empirical joint distribution. Consider $T > 0$ rounds of play between a row player with $M$ actions and a column…
  • empiricalJoint_rowMarginalRow marginal of the empirical joint distribution. Fix $T \ge 1$ rounds of play in which the row player uses mixed strategies…
  • GameA finite two-player game with $M$ row actions and $N$ column actions, specified by a row utility function…
  • JointDistribution.rowDeviationUtilityThe row player's expected utility from unilaterally deviating to the fixed pure action $i'$, while the column player keeps $\sigma$'s…
Used by 1
  • empiricalJoint_row_deviation_leRow regret bound gives row deviation bound. Let $G$ be a finite two-player game with row utility $u_r$ over $M$ row actions and $N$ column…

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Finset BigOperators in/-- The row player's deviation utility in the empirical joint distribution is the time average `(1/T) Σ_t Σ_j q_t(j) u(i', j)` of the utility of always playing the fixed row action `i'` against the column strategies actually played. -/lemma empiricalJoint_rowDeviationUtility {M N T : ℕ} (hT : 0 < T)    (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) (G : Game M N)    (i' : Fin M) :    (empiricalJoint hT p q).rowDeviationUtility G i' =      (∑ t : Fin T, ∑ j : Fin N, (q t).weights j * G.rowUtility i' j) / T := by  unfold JointDistribution.rowDeviationUtility  simp_rw [empiricalJoint_colMarginal]  have hStep : ∀ j : Fin N,      (∑ t : Fin T, (q t).weights j) / (T : ℝ) * G.rowUtility i' j =        (∑ t : Fin T, (q t).weights j * G.rowUtility i' j) / (T : ℝ) := by    intro j    rw [div_mul_eq_mul_div, ← Finset.sum_mul]  simp_rw [hStep]  rw [← Finset.sum_div, Finset.sum_comm]
See it in the graphDiscuss this resultChallenge it