108 Learning Theory — CCE
108.1 Overview
This module develops the theory of coarse correlated equilibria (CCE) for finite two-player games. It introduces joint distributions over action profiles, defines (approximate) CCE in terms of one-sided deviation utilities, constructs the empirical joint distribution from a sequence of mixed-strategy plays, and proves the main result: if both players run no-regret algorithms with per-round external regret at most \(\varepsilon \), then their empirical joint distribution is an \(\varepsilon \)-CCE.
108.2 Declarations
A finite two-player game with \(M\) row actions and \(N\) column actions, specified by a row utility function \(u_r : \mathrm{Fin}\, M \times \mathrm{Fin}\, N \to \mathbb {R}\) and a column utility function \(u_c : \mathrm{Fin}\, M \times \mathrm{Fin}\, N \to \mathbb {R}\). Both players are utility maximizers.
Given a zero-sum game \(G\) with payoff matrix \(A\), this embeds it into the general two-player framework by setting the row utility to \(A\) and the column utility to \(-A\), so that both players are maximizers of their respective utilities.
A joint distribution \(\sigma \) on \(\mathrm{Fin}\, M \times \mathrm{Fin}\, N\) is a nonnegative function \(\sigma _{ij} \ge 0\) satisfying \(\sum _{i,j} \sigma _{ij} = 1\). It represents a correlated distribution over pure action profiles of the two players.
The row marginal of \(\sigma \) at row action \(i\) is \(\sigma ^{\mathrm{row}}_i = \sum _{j} \sigma _{ij}\), i.e. the probability that the row player plays \(i\) under \(\sigma \).
The column marginal of \(\sigma \) at column action \(j\) is \(\sigma ^{\mathrm{col}}_j = \sum _{i} \sigma _{ij}\), i.e. the probability that the column player plays \(j\) under \(\sigma \).
For any joint distribution \(\sigma \) and row action \(i\), \(\sigma ^{\mathrm{row}}_i \ge 0\).
For any joint distribution \(\sigma \) and column action \(j\), \(\sigma ^{\mathrm{col}}_j \ge 0\).
The row marginals form a valid probability distribution: \(\sum _{i} \sigma ^{\mathrm{row}}_i = 1\).
The column marginals form a valid probability distribution: \(\sum _{j} \sigma ^{\mathrm{col}}_j = 1\).
The row player’s expected utility under \(\sigma \) in game \(G\) is \(\sum _{i,j} \sigma _{ij} \cdot u_r(i,j)\).
The column player’s expected utility under \(\sigma \) in game \(G\) is \(\sum _{i,j} \sigma _{ij} \cdot u_c(i,j)\).
The row player’s expected utility from unilaterally deviating to the fixed pure action \(i'\), while the column player keeps \(\sigma \)’s column marginal: \(\sum _{j} \sigma ^{\mathrm{col}}_j \cdot u_r(i', j)\).
The column player’s expected utility from unilaterally deviating to the fixed pure action \(j'\), while the row player keeps \(\sigma \)’s row marginal: \(\sum _{i} \sigma ^{\mathrm{row}}_i \cdot u_c(i, j')\).
Given mixed strategies \(p\) for the row player and \(q\) for the column player, the product (independent) joint distribution assigns to each profile \((i,j)\) the probability \(p_i \cdot q_j\).
For the product distribution of \(p\) and \(q\), the row marginal at \(i\) equals \(p_i\) (the original row mixed-strategy weight).
For the product distribution of \(p\) and \(q\), the column marginal at \(j\) equals \(q_j\) (the original column mixed-strategy weight).
Given \(T \gt 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\).
The row marginal of the empirical joint distribution at action \(i\) equals the time-average of the row player’s mixed-strategy weights: \((1/T)\sum _{t} (p_t)_i\).
The column marginal of the empirical joint distribution at action \(j\) equals the time-average of the column player’s mixed-strategy weights: \((1/T)\sum _{t} (q_t)_j\).
For any function \(f : \mathrm{Fin}\, M \to \mathrm{Fin}\, N \to \mathbb {R}\), the sum \(\sum _{i,j} \sigma _{ij} \cdot f(i,j)\) over the empirical joint distribution equals the time-average \((1/T)\sum _{t}\sum _{i,j}(p_t)_i(q_t)_j f(i,j)\).
The row player’s expected utility under the empirical joint distribution equals the time-average of the per-round bilinear utilities:
The column player’s expected utility under the empirical joint distribution equals the time-average of the per-round bilinear column utilities:
The row player’s deviation utility for pure action \(i'\) in the empirical distribution equals the time-average utility of always playing \(i'\):
The column player’s deviation utility for pure action \(j'\) in the empirical distribution equals the time-average utility of always playing \(j'\):
Let \(G\) be a two-player game, \(T \gt 0\), and let \(p_t\), \(q_t\) be the mixed strategies played at round \(t\) by the row and column players respectively. Suppose that for every pure row deviation \(i'\),
and similarly for every column deviation \(j'\) using \(u_c\). Then the empirical joint distribution is an \(\varepsilon \)-CCE of \(G\).