AFTD Auto-Formalizing Theoretical Domains

empiricalJoint_rowExpectedUtility

theoremverifiedimported Lean

Row expected utility of the empirical joint distribution. Fix a finite two-player game with $M$ row actions and $N$ column actions, and write $u_r(i,j)$ for the row player's payoff at the pure profile $(i,j)$. Suppose that over $T > 0$ rounds the row player plays a mixed strategy $p_t$ and the column player a mixed strategy $q_t$ in each round $t$, and let $\sigma$ be the empirical joint distribution given by $\sigma_{ij} = \frac{1}{T}\sum_{t=1}^{T}(p_t)_i\,(q_t)_j$. Then the row player's expected utility under $\sigma$ equals the time-average of the per-round bilinear payoffs: \[ \sum_{i,j}\sigma_{ij}\,u_r(i,j) = \frac{1}{T}\sum_{t=1}^{T}\sum_{i,j}(p_t)_i\,(q_t)_j\,u_r(i,j). \]

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Finset BigOperators in
lemma empiricalJoint_rowExpectedUtility {M N T : ℕ} (hT : 0 < T)
    (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) (G : Game M N) :
    (empiricalJoint hT p q).rowExpectedUtility G =
      (∑ t : Fin T, ∑ i : Fin M, ∑ j : Fin N,
          (p t).weights i * (q t).weights j * G.rowUtility i j) / T
Source
TCSlib, `empiricalJoint_rowExpectedUtility`
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 7
  • JointDistribution.rowExpectedUtilityThe row player's expected utility under $\sigma$ in game $G$ is $\sum_{i,j} \sigma_{ij} \cdot u_r(i,j)$.
  • 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_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_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 in
set_option autoImplicit false in
open Finset BigOperators in
/-- The row player's expected utility under the empirical joint distribution is the time average of the row player's per-round expected utilities `Σ_i Σ_j p_t(i) q_t(j) u(i, j)`. -/
lemma empiricalJoint_rowExpectedUtility {M N T : ℕ} (hT : 0 < T)
    (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) (G : Game M N) :
    (empiricalJoint hT p q).rowExpectedUtility G =
      (∑ t : Fin T, ∑ i : Fin M, ∑ j : Fin N,
          (p t).weights i * (q t).weights j * G.rowUtility i j) / T :=
  empiricalJoint_sum_prob_mul hT p q G.rowUtility
See it in the graphDiscuss this resultChallenge it