empiricalJoint_colExpectedUtility
Column utility of the empirical joint distribution. Consider a finite two-player game with $M$ row actions and $N$ column actions, whose column payoff is $u_c(i,j)$ for the action profile $(i,j)$. Fix $T \ge 1$ rounds in which the row player plays the mixed strategy $p_t$ and the column player plays the mixed strategy $q_t$, and let $\sigma$ be the empirical joint distribution, which assigns to each profile $(i,j)$ the time-averaged probability $\frac{1}{T}\sum_{t=1}^{T} (p_t)_i\,(q_t)_j$. Then the column player's expected utility under $\sigma$ equals the time-average of the per-round bilinear column payoffs: \[ \sum_{i=1}^{M}\sum_{j=1}^{N} \sigma_{ij}\, u_c(i,j) = \frac{1}{T}\sum_{t=1}^{T}\sum_{i=1}^{M}\sum_{j=1}^{N} (p_t)_i\,(q_t)_j\, u_c(i,j). \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Finset BigOperators in lemma empiricalJoint_colExpectedUtility {M N T : ℕ} (hT : 0 < T) (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) (G : Game M N) : (empiricalJoint hT p q).colExpectedUtility G = (∑ t : Fin T, ∑ i : Fin M, ∑ j : Fin N, (p t).weights i * (q t).weights j * G.colUtility i j) / T
- Source
- TCSlib, `empiricalJoint_colExpectedUtility`
- 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_colExpectedUtility← empiricalJoint_colExpectedUtility (TCSlib/LearningTheory/Minimax/CCE.lean:352): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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…
- JointDistribution.colExpectedUtilityThe column player's expected utility under $\sigma$ in game $G$ is $\sum_{i,j} \sigma_{ij} \cdot u_c(i,j)$.
- empiricalJoint_sum_prob_mulAveraging a payoff against the empirical joint distribution. Fix $T > 0$ rounds of play in which, in round $t$, the row player uses a…
- 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
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Finset BigOperators in /-- The column player's expected utility under the empirical joint distribution is the time average of the column player's per-round expected utilities. -/ lemma empiricalJoint_colExpectedUtility {M N T : ℕ} (hT : 0 < T) (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) (G : Game M N) : (empiricalJoint hT p q).colExpectedUtility G = (∑ t : Fin T, ∑ i : Fin M, ∑ j : Fin N, (p t).weights i * (q t).weights j * G.colUtility i j) / T := empiricalJoint_sum_prob_mul hT p q G.colUtility