AFTD Auto-Formalizing Theoretical Domains

empiricalJoint_isApproxCCE

theoremverifiedformalizationimported Lean

No-regret play yields an approximate coarse correlated equilibrium. Let $G$ be a finite two-player game with row utility $u_r$ and column utility $u_c$ over $M$ row actions and $N$ column actions, and consider $T > 0$ rounds of play in which the row player uses the mixed strategy $p_t$ and the column player uses the mixed strategy $q_t$ at round $t$. Fix $\varepsilon \in \bbr$, and suppose that for every pure row deviation $i'$, \[ \sum_{t=1}^{T}\sum_{j}(q_t)_j\, u_r(i',j) \;-\; \sum_{t=1}^{T}\sum_{i,j}(p_t)_i (q_t)_j\, u_r(i,j) \;\le\; \varepsilon T, \] and for every pure column deviation $j'$, \[ \sum_{t=1}^{T}\sum_{i}(p_t)_i\, u_c(i,j') \;-\; \sum_{t=1}^{T}\sum_{i,j}(p_t)_i (q_t)_j\, u_c(i,j) \;\le\; \varepsilon T. \] Then the empirical joint distribution of the play, which assigns to each profile $(i,j)$ the probability $\frac{1}{T}\sum_{t=1}^{T}(p_t)_i (q_t)_j$, is an $\varepsilon$-coarse correlated equilibrium of $G$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Finset BigOperators in
theorem empiricalJoint_isApproxCCE {M N T : ℕ} (hT : 0 < T)
    (G : Game M N)
    (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N)
    (ε : ℝ)
    (hRow : ∀ i' : Fin M,
      (∑ t : Fin T, ∑ j : Fin N, (q t).weights j * G.rowUtility i' j) -
        (∑ t : Fin T, ∑ i : Fin M, ∑ j : Fin N,
          (p t).weights i * (q t).weights j * G.rowUtility i j) ≤ ε * T)
    (hCol : ∀ j' : Fin N,
      (∑ t : Fin T, ∑ i : Fin M, (p t).weights i * G.colUtility i j') -
        (∑ t : Fin T, ∑ i : Fin M, ∑ j : Fin N,
          (p t).weights i * (q t).weights j * G.colUtility i j) ≤ ε * T) :
    IsApproxCoarseCorrelatedEquilibrium G (empiricalJoint hT p q) ε
Formalizes
No-regret play yields an approximate coarse correlated equilibrium, as formalized in TCSlib (`empiricalJoint_isApproxCCE`)
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 12
  • 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_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_rowMarginalRow marginal of the empirical joint distribution. Fix $T \ge 1$ rounds of play in which the row player uses mixed strategies…
  • IsApproxCoarseCorrelatedEquilibriumA joint distribution $\sigma$ is an $\varepsilon$-coarse correlated equilibrium ($\varepsilon$-CCE) of game $G$ if each player's…
  • 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…
  • GameA finite two-player game with $M$ row actions and $N$ column actions, specified by a row utility function…
  • JointDistribution.colDeviationUtilityThe column player's expected utility from unilaterally deviating to the fixed pure action $j'$, while the row player keeps $\sigma$'s row…
  • JointDistribution.colExpectedUtilityThe column player's expected utility under $\sigma$ in game $G$ is $\sum_{i,j} \sigma_{ij} \cdot u_c(i,j)$.
  • JointDistribution.rowDeviationUtilityThe row player's expected utility from unilaterally deviating to the fixed pure action $i'$, while the column player keeps $\sigma$'s…
  • JointDistribution.rowExpectedUtilityThe row player's expected utility under $\sigma$ in game $G$ is $\sum_{i,j} \sigma_{ij} \cdot u_r(i,j)$.

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Finset BigOperators in
/-- No-regret dynamics yield a coarse correlated equilibrium: if over `T > 0` rounds of mixed play `p t`, `q t` both players have cumulative external regret at most `ε · T` against every fixed pure deviation (i.e. average regret at most `ε`), then the empirical joint distribution of their play is an `ε`-coarse correlated equilibrium of `G`. [Rou13-L17, Prop. 3.1 (no-regret dynamics converge to CCE)]; [CBL06, §7.4]. Deviation: stated for two players, with the regret hypotheses given as cumulative bounds `ε · T` for each player (the source's Proposition 3.1 states the hypothesis as time-averaged regret at most `ε` for every player and deviation; here it is written as the equivalent cumulative bound `ε · T`). **Proof sketch.** The proof is the term `⟨row, col⟩`: the row half is `empiricalJoint_row_deviation_le` applied to the row regret hypothesis at each deviation `i'`, and the column half is `empiricalJoint_col_deviation_le` applied to the column regret hypothesis at each deviation `j'`. Each half rewrites both sides as time averages, puts them over the common denominator `T`, clears `T`, and reads off the regret bound. -/
theorem empiricalJoint_isApproxCCE {M N T : ℕ} (hT : 0 < T)
    (G : Game M N)
    (p : Fin T → MixedStrategy M) (q : Fin T → MixedStrategy N)
    (ε : ℝ)
    (hRow : ∀ i' : Fin M,
      (∑ t : Fin T, ∑ j : Fin N, (q t).weights j * G.rowUtility i' j) -
        (∑ t : Fin T, ∑ i : Fin M, ∑ j : Fin N,
          (p t).weights i * (q t).weights j * G.rowUtility i j) ≤ ε * T)
    (hCol : ∀ j' : Fin N,
      (∑ t : Fin T, ∑ i : Fin M, (p t).weights i * G.colUtility i j') -
        (∑ t : Fin T, ∑ i : Fin M, ∑ j : Fin N,
          (p t).weights i * (q t).weights j * G.colUtility i j) ≤ ε * T) :
    IsApproxCoarseCorrelatedEquilibrium G (empiricalJoint hT p q) ε :=
  -- Step 1: row half.  Step 2: column half.
  ⟨fun i' => empiricalJoint_row_deviation_le hT G p q ε i' (hRow i'),
   fun j' => empiricalJoint_col_deviation_le hT G p q ε j' (hCol j')⟩
See it in the graphDiscuss this resultChallenge it