Correlated Equilibrium

A shared signal players may follow lets them coordinate better than independent Nash play, without any binding agreement.

A mediator draws one joint recommendation and whispers each player only their part, and no one gains by disobeying what they heard

Why Does This Exist?

Independent Nash play leaves money on the table in coordination games: drivers who randomize separately crash at intersections, while a traffic light (a shared correlating signal) fixes it. Aumann's correlated equilibrium (1974) formalizes the light. A mediator draws a joint action from a known distribution and privately recommends each player's part; the distribution is an equilibrium when following the recommendation beats deviating, given only your own recommendation.

The set contains every Nash equilibrium (independent signals are a special case) and more: higher-payoff, fairer points Nash cannot reach. It is also what no-regret learning actually finds: independent no-regret dynamics converge in average play to correlated equilibrium, not Nash. Pure Nash stays the independent special case; learning dynamics are under game-theoretic optimization.

The one idea you need first

Obedience constraints: for every player and every recommended action $a$ , following must beat any deviation $b$ in conditional expectation over the others' recommended actions. One inequality per $(a, b)$ pair per player.

Think of It Like This

A traffic light at a blind crossing

Two drivers approach a blind crossing. Without a light they guess: both go, both crash. With a light, each sees only their own color. Green means the other likely sees red, so going beats stopping; red means the other likely goes, so stopping beats going. Neither sees the other's light, yet both obey their own.

The light correlates without communicating: its joint distribution (green-red, red-green, never green-green) does the work. Nash without the light is guessing; obedience with it is coordination. The light needs no police (no enforcement), only that each color, once seen, is self-interested to obey.

How It Actually Works

For a joint distribution $\pi$ over action profiles, $\pi$ is a correlated equilibrium when for each player $i$ , recommendation $a_i$ , and deviation $b_i$ :

\sum_{a_{-i}} \pi(a_{-i} \mid a_i) \, u_i(a_i, a_{-i}) \ge \sum_{a_{-i}} \pi(a_{-i} \mid a_i) \, u_i(b_i, a_{-i})

In plain words: conditional on hearing $a_i$ , the expected payoff of obeying tops every deviation, where expectations use the mediator's distribution conditioned on your recommendation.

Worked example

Traffic-light game. Actions Go/Stop. Payoffs: both Go $(-10, -10)$ crash; one Goes $(5, 0)$ or $(0, 5)$ ; both Stop $(-1, -1)$ wait. Mediator recommends (Go, Stop) and (Stop, Go) each with $1/2$ . Hearing "Go": the other was told "Stop" for sure, so obeying pays $5$ vs deviating to Stop paying $-1$ : obey. Hearing "Stop": the other goes, so obeying pays $0$ vs deviating to Go paying $-10$ : obey. Expected payoff $(2.5, 2.5)$ . Best Nash without signals mixes and earns about $-0.5$ each (frequent crashes and waits). The signal gains $3$ points per player with zero enforcement.

Code

1def obey_value(rec: str, others: dict[str, float], pay: dict) -> float:2    return sum(p * pay[(rec, o)] for o, p in others.items())  # obey payoff3
4
5# Hearing Go: other Stops for sure.6print(obey_value("Go", {"Stop": 1.0}, {("Go", "Stop"): 5, ("Stop", "Stop"): -1}))  # -> 5.07# Deviating to Stop while other Stops:8print(obey_value("Stop", {"Stop": 1.0}, {("Stop", "Stop"): -1, ("Go", "Stop"): 5}))  # -> -1.09# Hearing Stop: other Goes for sure; obey 0.0 beats deviate -10.0.10print(0.0, -10.0)  # -> 0.0 -10.0

Obedience wins both recommendations: $5 > -1$ and $0 > -10$ .

Watch Out For

Assuming the mediator must be trusted or powerful

The mediator needs no secrecy beyond private recommendations and no enforcement at all: obedience is self-interested given the distribution. Teams that build heavyweight trusted coordinators for a problem a public random signal solves (a shared seed, a clock) over-engineer. Publish the distribution, keep recommendations private, done.

Reading correlation as communication or collusion

Players learn nothing beyond their own recommendation and cannot use the signal to conspire: deviations are evaluated unilaterally. Regulators sometimes mistake correlated play for collusion; the test is whether anyone gains by solo deviation given their signal. If not, it is equilibrium, not conspiracy.

The Quick Version

A mediator draws joint actions and privately recommends each part.
Obedience constraints require following to beat every deviation conditionally.
The light's $(1/2, 1/2)$ mix on the two one-goes profiles pays $(2.5, 2.5)$ vs Nash near $-0.5$ .
Every Nash is a correlated equilibrium; the reverse fails usefully.
No-regret independent learning converges to correlated equilibrium in average play.
Signals need privacy of recommendations, never enforcement.