How can a shared signal make two selfish drivers both better off?
Topics 11 to 15 asked who gains when several players choose. These nine go further: what changes when the moves come in turns (25), when players hold secrets (26), when they meet again (27), when they learn as they go (28), when a shared signal is allowed (29), when each chooses a route (30), when the question is how hard an equilibrium is to find (31), the one place where quantum physics changes a game's value (32), and then a market you design and attack yourself (33).
Two drivers speed towards each other. Each can swerve or dare. If both dare they crash (0 each); if one dares and the other swerves, the dare wins big (7 against 2); if both swerve, both are fine (6 each). This is the game of Chicken.
It has two pure equilibria, (dare, swerve) and (swerve, dare), each good for one driver and bad for the other, and a mixed one in which each dares with probability 1/3. The mixed one is poor: each driver expects only 14/3, and the cell where both dare turns up with chance 1/9.
Robert Aumann (1974) noticed that real drivers have something the equilibria leave out: a signal they both can see. A traffic light is a device that makes the two drivers' choices correlated. If the light tells each driver what to do, and neither gains by disobeying, the recommendation is itself an equilibrium. It is called a correlated equilibrium, and a traffic light is the standard picture of it.
In this game the light does better than the mixed equilibrium for both drivers, because it removes the crash cell altogether while still announcing the lopsided cells, where one driver wins big, often.
A correlated equilibrium is a probability distribution x over the four cells such that, whenever a player is told a move, doing as told is a best reply given what the told move reveals about the other player's. For row, told a and tempted by b:
Σc x(a, c) · [ urow(b, c) − urow(a, c) ] ≤ 0
and the same for column. That is four linear inequalities in the four unknowns, plus x ≥ 0 and Σx = 1: the set of correlated equilibria is a polytope, so a linear program (topic 03) can optimise over it. Every Nash equilibrium is a correlated one; the converse is false.
Checking the traffic light, x = (0, 1/3, 1/3, 1/3). Told dare, row is certain the other was told swerve (only cell “dare, swerve” has a dare for row): dare pays 7, swerve pays 6, so row obeys. Told swerve, row sees “swerve, dare” and “swerve, swerve” equally likely: swerve pays (2 + 6)/2 = 4, dare would pay (0 + 7)/2 = 3.5, so row obeys. Column is symmetric. Both are paid 5.
The best correlated equilibrium for total payoff puts weights (0, 1/4, 1/4, 1/2), which pays 21/4 each: better than the light above, and better than any Nash equilibrium. The four candidates:
| Outcome | Payoffs | Total |
|---|---|---|
| Pure Nash (dare, swerve) | 7, 2 | 9 |
| Mixed Nash | 14/3, 14/3 | 28/3 |
| Traffic light, 1/3 each | 5, 5 | 10 |
| Best correlated equilibrium | 21/4, 21/4 | 21/2 |
Link to topic 28. Learners that keep regret records do not, in general, converge to a Nash equilibrium. A variant of regret matching that tracks "what if I had played b whenever I played a" converges to the set of correlated equilibria (Hart and Mas-Colell, 2000), so a traffic light is the kind of thing a pair of such learners can end up following without ever talking.
Move the four sliders to choose how often the light announces each cell. The page checks the four obedience conditions, shows both payoffs and says whether you have a correlated equilibrium. Use the preset buttons to compare the pure, mixed and correlated answers.
Traffic itself A navigation app that tells each driver a route is a signal of the same kind as the light: drivers may follow it or ignore it, and whether following is an equilibrium depends on whether any driver gains by ignoring it. That is exactly the condition the four inequalities above state.
Why it is tractable Computing a Nash equilibrium is believed to be hard in general (topic 31). A correlated equilibrium is the solution of a linear program, so it can be found in polynomial time for any game given as a table. This is one reason correlated equilibrium is the notion used in practical algorithms.
The sources Aumann, Journal of Mathematical Economics 1, 67 (1974), doi:10.1016/0304-4068(74)90037-8; and, for the Bayesian reading, Aumann, Econometrica 55, 1 (1987), doi:10.2307/1911154.
No quantum link is claimed for this topic.
Check yourself
In the game of Chicken, a referee tells each driver only their own move, drawn so that each of three cells (dare-swerve, swerve-dare, swerve-swerve) has chance 1/3. Why does a driver told to swerve obey?
Told to swerve, a driver sees the cells swerve-dare and swerve-swerve as equally likely. Swerving pays (2 + 6)/2 = 4; daring would pay (0 + 7)/2 = 3.5. So obeying is a best reply, which is what makes the light a correlated equilibrium.