Motivation
A two-player zero-sum game has a minimax value, and no-regret play can approximate optimal strategies. In a general multiplayer game there need not be one common value or a single opponent. Nevertheless, if every player has low regret against fixed actions, the joint empirical distribution of play obeys a useful equilibrium condition.
The resulting object is a coarse correlated equilibrium. A mediator samples a joint action profile and privately recommends one action to each player. No player gains much by committing in advance to one fixed alternative action. The mediator may correlate recommendations across players; the result is not automatically a Nash equilibrium or an equilibrium against deviations that depend on the recommendation.
Definitions and theorem
Definition 2.2.1
(Coarse correlated equilibrium)
There are players. Player has a nonempty finite action set and payoff for each action profile. A joint distribution is an -coarse correlated equilibrium if, for every player and fixed alternative ,
The alternative may depend on the known distribution but not on the realized recommendation. Here denotes the actions of all other players.
Theorem 2.2.2
(Full-information no-regret construction)
For any , the simultaneous multiplicative-weights procedure below constructs an -coarse correlated equilibrium of every finite game with payoffs in . It is a uniform mixture of product distributions, with
where is a positive integer and logarithms are natural. If , one round suffices.
Theorem 2.2.3
(A full-information regret bound)
For actions, any sequence of loss vectors , and , exponential weights with , and satisfies, for every fixed action ,
The loss vectors may be chosen after seeing the current distribution; the inequality is deterministic once the sequence is fixed. We assume exact real arithmetic for exponential weights and expectations. Finite-precision and sampling guarantees require separate analysis.
Proving the regret bound
Proof
(A single potential bounds every fixed action)
Let . For and , the elementary inequality gives
Using for and summing over rounds yields
For any fixed action , its final weight is , so is at least that value. Since , comparing the logarithmic lower and upper bounds and rearranging proves the displayed regret inequality. No independence between rounds was used.
Proof X-ray
One potential bounds every fixed deviation
The total weight bounds the learner's accumulated expected loss from above, while the weight of any one action bounds the same total from below. Comparing the two bounds gives a guarantee for that fixed action; the algebra holds simultaneously for every action.
From no regret to a joint distribution
Proof
(Averaging the round product distributions)
At round , each player has an exponential-weights distribution over . For each possible action , define its full-information loss by averaging over the other players' current product distribution:
These losses lie in . Each player updates all action weights using its loss vector. This is a deterministic procedure over exact real distributions; it does not need to sample actions to define its updates. Let be the uniform mixture over rounds of the joint product distributions .
For player , the expected loss actually incurred under round 's product distribution is . Applying the regret theorem to any fixed and converting loss back to payoff gives
Take and an integer . Both terms are then at most , proving the coarse correlated inequalities for every player and every fixed deviation. When , there is no alternative action for any player and the unique profile is exact in one round.
What the mediator reveals
A sample from can be generated by choosing a round index uniformly and then independently sampling each player's action from that round's distribution. The recommendation to each player is its sampled action. The coarse correlated guarantee compares against a fixed alternative chosen before receiving a recommendation; it does not guarantee that the player cannot improve by conditioning a deviation on its recommendation or on the hidden round index.
Counterexample mode
A mixture of products is not its product of marginals
Choose or with equal probability. This distribution is a mixture of two product distributions, but its marginals are both uniform and their product also gives positive probability to and . Replacing the joint mixture by the product of averaged marginals changes the distribution and is not justified by the proof.
The definition of keeps the round mixture intact. It is compactly described by lists of player distributions, even though the full joint table can be large. If the mediator publicly reveals the round index, a player can choose an alternative depending on that extra information; the fixed-action bound above does not automatically cover that stronger deviation.
Worked examples
Worked example 2.2.4
(A one-action game)
If every player has exactly one action, the unique joint profile has no distinct unilateral alternative. Its point-mass distribution is an exact coarse correlated equilibrium. The special case avoids a zero-round interpretation of the logarithmic bound.
Worked example 2.2.5
(A correlated coordination outcome)
Two players receive payoff one when their binary actions agree and zero otherwise. The distribution assigning probability one half to each of and gives each player expected payoff one. No fixed deviation can improve on one, so it is an exact coarse correlated equilibrium. Its recommendations are correlated.
Worked example 2.2.6
(A round budget)
For at most four actions per player and , choose and . Since , the theorem applies. The explicit regret bound is per round.
Worked example 2.2.7
(A fixed loss sequence)
For two actions and two rounds, let the losses be in round one and in round two. The regret bound applies to either fixed action even though the best action changes between rounds. It does not compare the learner with a comparator allowed to switch freely after seeing each loss vector.
Common mistakes
Common mistake
(Changing the deviation from round to round)
The same fixed deviation must be used on every round when applying the displayed regret inequality. A player who sees the sampled round or recommendation may choose a different deviation in different circumstances; that is a stronger benchmark. Coarse correlated equilibrium is defined precisely to match the fixed-action comparison.
The product distribution within one round assumes independent sampling by players conditional on that round. The mixture over rounds can create correlation. Taking products before averaging and taking products after averaging are different operations, as the counterexample shows.
Common mistake
(An approximate coarse correlated equilibrium is not a Nash equilibrium)
The proof constructs an approximate coarse correlated equilibrium, not necessarily a Nash equilibrium or a recommendation-dependent correlated equilibrium. In zero-sum two-player games, additional arguments can extract approximate minimax strategies; arbitrary multiplayer payoffs require their own conclusions.
Computation and representation
For an explicitly listed normal-form game, each round's loss vectors can be computed by summing over the payoff table and the current product probabilities. This takes a polynomial number of arithmetic operations in the size of that explicit table per round, and the stated number of rounds is polynomial in and the logarithm of the largest action count. If the game is given only by a succinct circuit or oracle, computing these expectations may have a different cost.
The theorem assumes exact real arithmetic for exponentials and probabilities. It therefore gives an arithmetic-operation count and an exact mathematical distribution, not a certified polynomial bit-time implementation. A finite-precision implementation must bound accumulated errors and their effect on every deviation inequality. A sampled-play version must also account for sampling error; neither issue is hidden inside the deterministic expected-payoff proof.
The number of players may be arbitrary, but the explicit payoff table itself has one entry for every joint action profile and player. An operation count polynomial in that table size can still be exponential in the number of players when each has multiple actions. This is an input-representation distinction, not a contradiction of the finite-round bound.
Expanding the payoff comparison
For a fixed player and round, substitute the loss definition into the learner's expected loss. Because the player's own mixed action is independent of the other players conditional on the round, the result is one minus the expected payoff under the full product distribution. The loss of a fixed alternative is one minus the expected payoff obtained by replacing only that player's component. Subtracting cancels the two ones. Averaging the resulting inequalities over rounds is exactly the definition of expectation under .
The simultaneous updates do not create a circular choice. At the beginning of a round, every distribution is determined by weights from previous rounds. The procedure computes all expected loss vectors from those current distributions, then updates all weights for the next round. A loss vector may depend on the player's present distribution through the other players' choices, but the potential proof holds for every vector once it is specified. It does not require an independent adversary or independent losses across rounds.
Exact existence as a limit
The finite-horizon construction also gives an existence argument for an exact coarse correlated equilibrium. Choose a sequence tending to zero and construct a corresponding distribution for each value. All joint distributions lie in a finite-dimensional probability simplex, which is compact, so some subsequence converges to a distribution . For every player and fixed alternative, the coarse correlated inequality is linear and continuous in the joint distribution. Passing to the limit along that subsequence removes the error and shows that is exact.
This argument proves that at least one limit point works. It does not say that the entire sequence of distributions converges, nor does it provide a finite-time exact rational representation. The approximate construction and its finite round budget remain the algorithmic result established above.
A deviation check in a small game
In the binary coordination example, a player who commits to always playing zero receives payoff one against the other player's recommendation zero and payoff zero against recommendation one. Its expected deviation payoff is therefore one half, while following the recommendation gives payoff one. The same calculation holds for always playing one. Checking both fixed actions is enough because any fixed mixed deviation is a convex combination of their payoffs.
That last observation generalizes: to verify a coarse correlated equilibrium against all fixed mixed deviations, it suffices to check every fixed pure action. The payoff from a mixed deviation is the weighted average of the corresponding pure-deviation payoffs. It cannot exceed the largest pure-deviation payoff. This finite list of inequalities is exactly the list controlled by the regret bound.
Concept lensGeometric
The equilibria form a polytope
Fix a game and write for the simplex of distributions on joint action profiles. Each pure alternative contributes one linear inequality in , namely the displayed condition. The -coarse correlated equilibria are therefore the intersection of with closed half-spaces: a convex polytope, nonempty by the construction above. Mixtures of equilibria are equilibria, and finding one in an explicit table is a linear feasibility problem.
Summary
Exponential weights bounds each player's regret against every fixed action. Applying that bound to expected full-information losses and averaging the round product distributions produces an approximate coarse correlated equilibrium. The mediator's information, the joint mixture, and the exact-arithmetic assumption are part of the guarantee.
Exercises
Quick check
(Why does the regret theorem allow the loss vector to depend on the current action distribution?)
Look at where the potential proof uses .
Solution · Answer
The potential inequality holds for each realized loss vector in and does not use independence from the current distribution. Summing those pointwise inequalities gives the bound.
Quick check
(If all players have one action, why does one round produce an exact equilibrium?)
What alternative action could a player consider?
Solution · Answer
There is no different unilateral action, so every coarse correlated inequality holds with equality for the unique profile.
Quick check
(In the binary coordination example, what is the expected payoff of either player under the diagonal mixture?)
Compute the payoff at each of the two profiles in the support.
Solution · Answer
It is one: both profiles in the support have matching actions and payoff one.
Quick check
(Why does a fixed-deviation guarantee not automatically cover a deviation that depends on the sampled recommendation?)
Compare a deviation fixed in advance with one chosen after seeing the recommendation.
Solution · Answer
Such a deviation can choose different alternatives in different recommendation cases. The theorem compares only with one action fixed across all rounds and recommendations.