Let \(\sigma \) be a joint distribution on \(\mathrm{Fin}\, M \times \mathrm{Fin}\, N\), so \(\sigma _{ij} \ge 0\) for all \(i,j\) and \(\sum _{i,j} \sigma _{ij} = 1\). Then for every row action \(i\) the row marginal \(\sigma ^{\mathrm{row}}_i = \sum _{j} \sigma _{ij}\) satisfies \(\sigma ^{\mathrm{row}}_i \ge 0\).

Let \(\sigma \) be a joint distribution on \(\mathrm{Fin}\, M \times \mathrm{Fin}\, N\), and let \(j\) be a column action. Then the column marginal \(\sigma ^{\mathrm{col}}_j = \sum _{i} \sigma _{ij}\) satisfies \(\sigma ^{\mathrm{col}}_j \ge 0\).

Let \(\sigma \) be a joint distribution over \(\mathrm{Fin}\, M \times \mathrm{Fin}\, N\), and for each row action \(i\) let \(\sigma ^{\mathrm{row}}_i = \sum _{j} \sigma _{ij}\) denote its row marginal. Then the row marginals sum to one:

Let \(\sigma \) be a joint distribution on \(\mathrm{Fin}\, M \times \mathrm{Fin}\, N\). Then the column marginals sum to one: \(\sum _{j} \sigma ^{\mathrm{col}}_j = 1\).

Let \(G\) be a finite two-player game with \(M\) row actions and \(N\) column actions, and let \(\sigma \) be a joint distribution over the action profiles \((i,j)\) that is a coarse correlated equilibrium of \(G\); that is, neither player can increase their expected utility under \(\sigma \) by committing in advance to a fixed pure action, so that for every row action \(i'\) the row player’s utility from deviating to \(i'\) (against the column marginal of \(\sigma \)) is at most their expected utility under \(\sigma \), and likewise the column player’s utility from deviating to any fixed action \(j'\) (against the row marginal of \(\sigma \)) is at most their expected utility under \(\sigma \). Then for every real \(\varepsilon \ge 0\), the distribution \(\sigma \) is an \(\varepsilon \)-coarse correlated equilibrium of \(G\): each player’s gain from any such unilateral pure deviation exceeds zero by at most \(\varepsilon \).

Let \(p\) be a mixed strategy for the row player over \(M\) actions and \(q\) a mixed strategy for the column player over \(N\) actions, and let \(\sigma \) be their product distribution, so that \(\sigma _{ij} = p_i q_j\) for every profile \((i,j)\). Then for each row action \(i\) the row marginal of \(\sigma \) equals the corresponding weight of \(p\), that is, \(\sum _{j} p_i q_j = p_i\).

Let \(p\) be a mixed strategy over \(M\) actions for the row player and \(q\) a mixed strategy over \(N\) actions for the column player, and let \(\sigma \) be their product distribution, which assigns probability \(p_i\, q_j\) to each pure profile \((i,j)\). Then for every column action \(j\), the column marginal of \(\sigma \) at \(j\) equals \(q_j\); that is, \(\sum _{i} p_i\, q_j = q_j\).

Fix \(T \ge 1\) rounds of play in which the row player uses mixed strategies \(p_1,\dots ,p_T\) over \(M\) actions and the column player uses mixed strategies \(q_1,\dots ,q_T\) over \(N\) actions, 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 for every row action \(i\), the row marginal \(\sigma ^{\mathrm{row}}_i = \sum _{j} \sigma _{ij}\) equals the time-average of the row player’s weight on \(i\):

Consider \(T \gt 0\) rounds of play between a row player with \(M\) actions and a column player with \(N\) actions, where in round \(t\) the row player uses the mixed strategy \(p_t\) over the row actions and the column player uses the mixed strategy \(q_t\) over the column actions. Form the empirical joint distribution \(\sigma \) assigning to each profile \((i,j)\) the time-averaged probability \(\frac{1}{T}\sum _{t=1}^{T} (p_t)_i (q_t)_j\). Then for each column action \(j\), the column marginal \(\sigma ^{\mathrm{col}}_j = \sum _i \sigma _{ij}\) equals the time-average of the column player’s weights on \(j\),

Fix \(T \gt 0\) rounds of play in which, in round \(t\), the row player uses a mixed strategy \(p_t\) over \(\mathrm{Fin}\, M\) and the column player a mixed strategy \(q_t\) over \(\mathrm{Fin}\, N\); write \((p_t)_i\) and \((q_t)_j\) for the weights placed on actions \(i\) and \(j\). Let \(\sigma \) be the empirical joint distribution, whose value at each profile \((i,j)\) is the time average \(\sigma _{ij} = \frac{1}{T}\sum _{t=1}^{T} (p_t)_i\, (q_t)_j\). Then for every function \(f : \mathrm{Fin}\, M \times \mathrm{Fin}\, N \to \mathbb {R}\),

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 \gt 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:

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:

Let \(G\) be a finite two-player game with \(M\) row actions and \(N\) column actions, and let \(u_r(i,j)\) denote the row player’s utility. Fix an integer \(T \ge 1\), and suppose that in each round \(t \in \{ 1,\dots ,T\} \) the row player plays the mixed strategy \(p_t\) over the \(M\) row actions and the column player plays the mixed strategy \(q_t\) over the \(N\) column actions, giving rise to the empirical joint distribution \(\sigma \) with \(\sigma _{ij} = \tfrac {1}{T}\sum _{t=1}^{T} (p_t)_i\, (q_t)_j\). Then for every pure row action \(i'\), the row player’s deviation utility under \(\sigma \) equals the time average of the expected utilities of playing \(i'\) against each round’s column strategy:

Let \(G\) be a finite two-player game with \(M\) row actions and \(N\) column actions and column utility \(u_c(i,j)\), and fix a number of rounds \(T \ge 1\). Suppose that in each round \(t \in \{ 1,\dots ,T\} \) the row player plays a mixed strategy \(p_t\) over the \(M\) row actions and the column player plays a mixed strategy \(q_t\) over the \(N\) column actions, and let \(\sigma \) be the empirical joint distribution that assigns mass \(\frac{1}{T}\sum _{t=1}^{T} (p_t)_i\, (q_t)_j\) to each action profile \((i,j)\). Then, for every column action \(j'\), the column player’s expected utility from deviating to the pure action \(j'\) against the row marginal \(\sigma ^{\mathrm{row}}_i = \sum _{j} \sigma _{ij}\) is the time average of the round-by-round deviation utilities:

Let \(G\) be a finite two-player game with row utility \(u_r\) over \(M\) row actions and \(N\) column actions, and consider \(T \gt 0\) rounds of play in which the row player uses the mixed strategy \(p_t\) and the column player the mixed strategy \(q_t\) at round \(t\). Fix \(\varepsilon \in \mathbb {R}\) and a pure row action \(i'\), and suppose the row player’s cumulative external regret against always playing \(i'\) is at most \(\varepsilon T\):

Then in the empirical joint distribution \(\sigma \) of the play, deviating to \(i'\) gains at most \(\varepsilon \) over the expected utility: \(\mathrm{rowDevUtil}(\sigma , G, i') \le \mathrm{rowExpUtil}(\sigma , G) + \varepsilon \). This is the row half of empiricalJoint_isApproxCCE.

Let \(G\) be a finite two-player game with column utility \(u_c\) over \(M\) row actions and \(N\) column actions, and consider \(T \gt 0\) rounds of play in which the row player uses the mixed strategy \(p_t\) and the column player the mixed strategy \(q_t\) at round \(t\). Fix \(\varepsilon \in \mathbb {R}\) and a pure column action \(j'\), and suppose the column player’s cumulative external regret against always playing \(j'\) is at most \(\varepsilon T\):

Then in the empirical joint distribution \(\sigma \) of the play, deviating to \(j'\) gains at most \(\varepsilon \) over the expected utility: \(\mathrm{colDevUtil}(\sigma , G, j') \le \mathrm{colExpUtil}(\sigma , G) + \varepsilon \). This is the column half of empiricalJoint_isApproxCCE, mirroring empiricalJoint_row_deviation_le.