empiricalJoint_colDeviationUtility
Column deviation utility of the empirical joint distribution. Let $G$ be a finite two-player game with $M$ row actions and $N$ column actions and column utility $u_c(i,j)$, and fix a number of rounds $T \ge 1$. Suppose that in each round $t \in \{1,\dots,T\}$ the row player plays a mixed strategy $p_t$ over the $M$ row actions and the column player plays a mixed strategy $q_t$ over the $N$ column actions, and let $\sigma$ be the empirical joint distribution that assigns mass $\frac{1}{T}\sum_{t=1}^{T} (p_t)_i\,(q_t)_j$ to each action profile $(i,j)$. Then, for every column action $j'$, the column player's expected utility from deviating to the pure action $j'$ against the row marginal $\sigma^{\mathrm{row}}_i = \sum_{j} \sigma_{ij}$ is the time average of the round-by-round deviation utilities: \[ \sum_{i} \sigma^{\mathrm{row}}_i\, u_c(i,j') = \frac{1}{T}\sum_{t=1}^{T}\sum_{i} (p_t)_i\, u_c(i,j'). \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Finset BigOperators in lemma empiricalJoint_colDeviationUtility {M N T : ℕ} (hT : 0 < T) (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) (G : Game M N) (j' : Fin N) : (empiricalJoint hT p q).colDeviationUtility G j' = (∑ t : Fin T, ∑ i : Fin M, (p t).weights i * G.colUtility i j') / T
- Source
- TCSlib, `empiricalJoint_colDeviationUtility`
- 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.empiricalJoint_colDeviationUtility← empiricalJoint_colDeviationUtility (TCSlib/LearningTheory/Minimax/CCE.lean:380): verbatim
- 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…
- JointDistribution.colDeviationUtilityThe column player's expected utility from unilaterally deviating to the fixed pure action $j'$, while the row player keeps $\sigma$'s row…
- 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…
- Used by 1
- empiricalJoint_col_deviation_leColumn regret bound gives column deviation bound. Let $G$ be a finite two-player game with column utility $u_c$ over $M$ row actions and…
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.
set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Finset BigOperators in/-- The column player's deviation utility in the empirical joint distribution is the time average `(1/T) Σ_t Σ_i p_t(i) v(i, j')` of the utility of always playing the fixed column action `j'` against the row strategies actually played. -/lemma empiricalJoint_colDeviationUtility {M N T : ℕ} (hT : 0 < T) (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) (G : Game M N) (j' : Fin N) : (empiricalJoint hT p q).colDeviationUtility G j' = (∑ t : Fin T, ∑ i : Fin M, (p t).weights i * G.colUtility i j') / T := by unfold JointDistribution.colDeviationUtility simp_rw [empiricalJoint_rowMarginal] have hStep : ∀ i : Fin M, (∑ t : Fin T, (p t).weights i) / (T : ℝ) * G.colUtility i j' = (∑ t : Fin T, (p t).weights i * G.colUtility i j') / (T : ℝ) := by intro i rw [div_mul_eq_mul_div, ← Finset.sum_mul] simp_rw [hStep] rw [← Finset.sum_div, Finset.sum_comm]