AFTD Auto-Formalizing Theoretical Domains

empiricalJoint

defimported Lean

Given $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 distribution assigns to each profile $(i,j)$ the time-averaged probability $\frac{1}{T}\sum_{t=1}^{T} (p_t)_i \cdot (q_t)_j$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Finset BigOperators in
noncomputable def empiricalJoint {M N T : ℕ} (hT : 0 < T)
    (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) :
    JointDistribution M N
Defined in
TCSlib, `empiricalJoint`
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
none listed
Built on 2
  • MixedStrategyA mixed strategy over $n$ actions is a record consisting of a weight function $w : \mathrm{Fin}\,n \to \mathbb{R}$ together with…
  • JointDistributionA joint distribution $\sigma$ on $\mathrm{Fin}\,M \times \mathrm{Fin}\,N$ is a nonnegative function $\sigma_{ij} \ge 0$ satisfying…
Used by 10
  • empiricalJoint_isApproxCCENo-regret play yields an approximate coarse correlated equilibrium. Let $G$ be a finite two-player game with row utility $u_r$ and column…
  • 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_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…
  • 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_rowDeviationUtilityEmpirical row deviation utility as a time average. Let $G$ be a finite two-player game with $M$ row actions and $N$ column actions, and…
  • empiricalJoint_rowExpectedUtilityRow expected utility of the empirical joint distribution. Fix a finite two-player game with $M$ row actions and $N$ column actions, and…
  • empiricalJoint_rowMarginalRow marginal of the empirical joint distribution. Fix $T \ge 1$ rounds of play in which the row player uses mixed strategies…
  • empiricalJoint_colExpectedUtilityColumn utility of the empirical joint distribution. Consider a finite two-player game with $M$ row actions and $N$ column actions, whose…
  • empiricalJoint_colDeviationUtilityColumn deviation utility of the empirical joint distribution. Let $G$ be a finite two-player game with $M$ row actions and $N$ column…
  • 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 empirical joint distribution of `T > 0` rounds in which the row player plays the mixed strategy `p t` and the column player plays the mixed strategy `q t`, drawing their actions independently: the profile `(i, j)` has probability `(1/T) Σ_t p_t(i) · q_t(j)`. [Rou13-L17, §3 (time-averaged history `σ`)]. **Proof sketch** (that the mass is one). Each round contributes a product distribution of total mass one (`h_round_sum`, by summing out `q t` and then `p t`); pull the division by `T` out of the double sum (`hPullDiv`), swap the time sum to the outside (`hSwap`), and the total is `T · 1 / T = 1`. -/
noncomputable def empiricalJoint {M N T : ℕ} (hT : 0 < T)
    (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N) :
    JointDistribution M N where
  prob i j := (∑ t : Fin T, (p t).weights i * (q t).weights j) / T
  nonneg i j := div_nonneg
    (Finset.sum_nonneg fun t _ => mul_nonneg ((p t).nonneg i) ((q t).nonneg j))
    (Nat.cast_nonneg T)
  sum_one := by
    -- Each round contributes a product distribution of total mass one, so the
    -- time average also has total mass one.
    have hT_ne : (T : ℝ) ≠ 0 := Nat.cast_ne_zero.mpr (Nat.pos_iff_ne_zero.mp hT)
    have h_round_sum : ∀ t : Fin T,
        ∑ i : Fin M, ∑ j : Fin N, (p t).weights i * (q t).weights j = 1 := by
      intro t
      calc ∑ i : Fin M, ∑ j : Fin N, (p t).weights i * (q t).weights j
          = ∑ i : Fin M, (p t).weights i * ∑ j : Fin N, (q t).weights j := by
            apply Finset.sum_congr rfl; intro i _
            rw [← Finset.mul_sum]
        _ = ∑ i : Fin M, (p t).weights i * 1 := by rw [(q t).sum_one]
        _ = 1 := by simp [(p t).sum_one]
    have hPullDiv :
        ∑ i : Fin M, ∑ j : Fin N,
            (∑ t : Fin T, (p t).weights i * (q t).weights j) / (T : ℝ) =
          (∑ i : Fin M, ∑ j : Fin N, ∑ t : Fin T,
              (p t).weights i * (q t).weights j) / (T : ℝ) := by
      rw [Finset.sum_div]
      apply Finset.sum_congr rfl; intro i _
      rw [Finset.sum_div]
    have hSwap :
        (∑ i : Fin M, ∑ j : Fin N, ∑ t : Fin T,
            (p t).weights i * (q t).weights j) =
          ∑ t : Fin T, ∑ i : Fin M, ∑ j : Fin N,
              (p t).weights i * (q t).weights j := by
      rw [show (∑ i : Fin M, ∑ j : Fin N, ∑ t : Fin T,
                (p t).weights i * (q t).weights j) =
            (∑ i : Fin M, ∑ t : Fin T, ∑ j : Fin N,
                (p t).weights i * (q t).weights j) from
            Finset.sum_congr rfl fun _ _ => Finset.sum_comm]
      exact Finset.sum_comm
    rw [hPullDiv, hSwap]
    simp_rw [h_round_sum]
    rw [Finset.sum_const, Finset.card_fin, nsmul_eq_mul, mul_one]
    exact div_self hT_ne
See it in the graphDiscuss this resultChallenge it