Correlated Equilibrium

Two cars reach an intersection at the same time. Each driver wants to go, but if both go at once there is a crash. If both wait, nothing happens. The best outcome is to take turns — but how do they coordinate without talking?

Enter the traffic light. It privately tells each driver whether to go or wait. A driver following the signal never wants to deviate: if the light says "go," the other driver is stopped, so going is best; if the light says "wait," the other driver is going, so waiting avoids a crash. No phone call needed — just a shared, trusted signal.

This is a correlated equilibrium, a concept introduced by economist Robert Aumann in 1974. A mediator draws a joint action profile from a probability distribution and whispers each player their own recommendation. The key property: given what you know (just your own recommendation), you never gain by ignoring it.

Aumann proved this concept is at least as general as Nash equilibrium — every Nash equilibrium is a correlated equilibrium, but not vice versa. Better yet, while computing a Nash equilibrium is PPAD-complete and believed to require exponential time in the worst case, computing a correlated equilibrium is a linear program solvable in polynomial time. The solution that seemed richer turns out to be easier to find.

The table below shows the payoff matrix for two drivers at an intersection. Go earns a big reward if the other waits but causes a crash if both go; Wait is safe but slow. A traffic light acts as mediator and recommends each driver an action.

Click Run mediator to let the traffic light draw a joint recommendation and tell each driver privately. Then check whether either driver would gain by deviating — the Check equilibrium button verifies the condition for you.

<p class="hint">{{hint}}</p>

<div class="payoff-wrap">
  <table class="payoff" id="payoffTable">
    <thead>
      <tr><th></th><th>{{th_b_go}}</th><th>{{th_b_wait}}</th></tr>
    </thead>
    <tbody>
      <tr>
        <th>{{th_a_go}}</th>
        <td id="c-gg" class="cell">(−5, −5)</td>
        <td id="c-gw" class="cell">(4, 0)</td>
      </tr>
      <tr>
        <th>{{th_a_wait}}</th>
        <td id="c-wg" class="cell">(0, 4)</td>
        <td id="c-ww" class="cell">(1, 1)</td>
      </tr>
    </tbody>
  </table>
</div>

<div class="signal-row" id="signalRow" style="display:none">
  <div class="signal-box" id="sigA"></div>
  <div class="signal-box" id="sigB"></div>
</div>

<div class="status" id="status">{{press_run}}</div>

<div class="btns">
  <button id="btnRun" type="button">{{btn_run}}</button>
  <button id="btnCheck" type="button" disabled>{{btn_check}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>

<div class="detail" id="detail"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.payoff-wrap { overflow-x: auto; margin-bottom: .8rem; }
.payoff { border-collapse: collapse; font-size: .92rem; min-width: 300px; }
.payoff th { background: #e8eef3; color: #1d3557; padding: .45rem .7rem;
             text-align: center; font-weight: 700; border: 1px solid #cdd9e3; }
.payoff td { padding: .45rem .7rem; text-align: center; border: 1px solid #cdd9e3;
             transition: background .25s; }
.cell.highlight { background: #d4ecd4; font-weight: 700; }
.signal-row { display: flex; gap: 1rem; margin: .6rem 0; flex-wrap: wrap; }
.signal-box { border-radius: 10px; padding: .55rem 1rem; font-size: .92rem;
              font-weight: 600; border: 1px solid #cdd9e3; background: #f5f7fa;
              min-width: 180px; opacity: 0; transition: opacity .4s; }
.signal-box.shown { opacity: 1; }
.signal-box.go { background: #d4ecd4; border-color: #5aab6e; color: #1a5c2a; }
.signal-box.wait { background: #fde8c8; border-color: #d4843a; color: #7a430a; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.5em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .4; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
.detail { font-size: .84rem; color: #555; margin-top: .7rem; line-height: 1.6; }

// Code not found

Notice: the mediator never recommends (Go, Go) — that would be a crash. It splits time between (Go, Wait) and (Wait, Go), so on average each driver gets through half the time. Neither driver wants to deviate because the recommendation already accounts for what the other driver is doing.

The computational gap between Nash and correlated equilibrium is dramatic.

• Nash equilibrium is PPAD-complete — proven by Daskalakis, Goldberg, and Papadimitriou in 2006. No polynomial-time algorithm is known for finding one in a general game, and it is widely believed none exists.
• Correlated equilibrium is a linear program. The constraints are linear inequalities (no-deviation conditions), and linear programs can be solved in polynomial time. The celebrated ellipsoid method and interior-point methods both apply directly.
• Every Nash equilibrium induces a correlated equilibrium — just take the product distribution over Nash strategies. The reverse is not true: correlated equilibria can achieve outcomes (like the traffic-light 50/50 split) that no Nash equilibrium reaches.
• No mediator is really needed for computation: the set of all correlated equilibria is a convex polytope described by linear constraints, so we can enumerate, optimise, or even sample from it efficiently.

The punchline: Aumann's concept is strictly more general than Nash but strictly easier to compute. In computational game theory this is rare — richer structure usually means harder computation. Here the mediator's extra freedom actually simplifies the maths.

Status: solved — the existence of a correlated equilibrium in every finite game follows from Nash's theorem (1950), and polynomial-time computation was established via linear programming. There is no Millennium Prize here, just a beautifully tractable theory.

The moment you have multiple self-interested agents and a trusted coordinating signal, correlated equilibrium appears:

• Traffic systems: every signal — red, amber, green — is literally a mediator recommending actions. Modern adaptive traffic lights optimise the joint recommendation as a linear program, improving city-wide flow without any direct communication between drivers.
• Spectrum auctions: regulators act as mediators in multi-round auctions for radio frequencies. Correlated-equilibrium analysis guides bid strategies and reserve-price design.
• Online advertising: real-time ad auctions can be modelled as repeated games. No-regret learning algorithms — a practical way to reach correlated equilibria — are standard in modern ad exchanges.
• Mechanism design: protocol designers want to build systems where honest participation is each agent's best response. Correlated equilibrium is the solution concept most naturally achieved by cheap-talk protocols.
• Multi-agent reinforcement learning: when multiple AI agents interact, correlated equilibria emerge from no-regret learning and are easier to target than Nash. Systems like Google DeepMind's multi-agent frameworks exploit this tractability.

See also Nash Equilibrium for the solution concept that correlated equilibrium generalises, and Linear Programming for the algorithmic engine behind its computation.

Correlated equilibrium is one of those ideas that looks complicated until you see a traffic light: a trusted signal, private recommendations, and the assurance that following the advice is always your best move.

Robert Aumann's 1974 insight was to notice that coordination does not require Nash's strict independence. Players who share a common signal source can achieve outcomes Nash equilibrium cannot reach — and computing those outcomes reduces to a linear program that any laptop can solve.

In an era where Nash equilibrium dominates pop-science discussions of game theory, correlated equilibrium quietly powers the systems that actually coordinate millions of agents every day: the traffic grids, the ad exchanges, the spectrum auctions. Its tractability is not a lucky accident — it is the reward for letting the mediator's signal carry the coordination burden that players would otherwise struggle to achieve on their own.