Game Theory
Correlated Equilibrium
Nash equilibrium requires independent actions. But what if players can coordinate through an external device - a traffic light, an arbiter, a random signal? Aumann's correlated equilibrium formalizes this idea and opens a space of efficient agreements unavailable under independent play.
- **Online advertising:** Google AdWords auctions use CE-based mechanisms for allocating ad impressions among advertisers
- **Traffic lights:** a traffic light schedule at an intersection is a CE in the drivers' game: the correlator recommends (go, stop) or (stop, go)
- **FCC spectrum auctions:** combinatorial auctions use CE-based approaches for efficient spectrum allocation
- **Multi-agent learning:** no-regret algorithms automatically converge to CE without centralized coordination
Предварительные знания
- Nash equilibrium
- Mixed strategies
- Basics of linear programming
Definition of correlated equilibrium
Robert Aumann in 1974 defined correlated equilibrium (CE), a concept broader than Nash equilibrium. In the Chicken game, the unique symmetric Nash equilibrium in mixed strategies yields expected payoff 0 to each player, while a CE that uses a fair coin - recommending (S,T) or (T,S) with equal probability - yields payoff 2 to each. Google AdWords in 2016 earned $79.4 billion under CE-based pricing theory. CE can be computed in polynomial time via linear programming, unlike the PPAD-hard problem of finding Nash equilibria.
How does correlated equilibrium differ from Nash equilibrium?
Aumann (1974): CE is a distribution mu over action profiles. A mediator samples a profile (a_1, ..., a_n) ~ mu and privately tells each player a_i. Equilibrium condition: upon seeing a_i, player i prefers not to deviate, given the conditional mu(a_{-i} | a_i). Every Nash equilibrium is the special case where mu is a product.
Computation: LP and no-regret learning
In the Chicken game: actions S (straight - do not yield) and T (turn - yield). Payoffs: (S,S) = (-10,-10), (S,T) = (5,-1), (T,S) = (-1,5), (T,T) = (0,0). Two pure Nash equilibria: (S,T) and (T,S). Symmetric mixed Nash: each plays S with probability 1/6. Expected payoff under mixed Nash: 0. CE with equal probability on (S,T) and (T,S): expected payoff 2 each.
What is the complexity of computing a correlated equilibrium in a game with n players and k actions?
CE is defined by linear constraints: for all i and s_i, s_i' ∈ A_i: sum_{a_{-i}} mu(s_i, a_{-i}) * [u_i(s_i, a_{-i}) - u_i(s_i', a_{-i})] >= 0. An LP of size O(n*k^n). Existence is trivial (every NE gives a CE). Unlike Nash (PPAD-complete), CE is polynomial in the input size.
Comparison with Nash and applications
Practical use of CE: in multi-item Vickrey auctions, Nash equilibria are hard to compute, but the welfare-optimal CE is found via LP. This underpins combinatorial auction mechanisms used by Google, Facebook, and the FCC spectrum auctions.
Which example shows that CE can be strictly better than any Nash equilibrium?
Chicken (Hawk-Dove) has three Nash equilibria: two pure asymmetric and one mixed. The mixed NE yields (3.5, 3.5) with positive crash risk. A CE via a traffic-light mediator (50/50 who goes first) yields (5.5, 5.5) - coordination without crashes. This is the canonical model of traffic regulation and priority systems.
Connections to other fields
Correlated equilibrium connects classical game theory with online learning, auction theory, and algorithmic game theory.
- Nash Equilibrium — Correlated equilibrium convexifies Nash via a public signal mediator
- Algorithmic Game Theory: Price of Anarchy — Correlated equilibria are reachable by no-regret dynamics and bound the price of anarchy
- Signaling Games — Both rely on asymmetric information and public versus private signals
Итоги
- CE is a distribution sigma over action profiles: each player, given a recommendation, has no incentive to deviate assuming others follow theirs
- The CE set is a convex polytope containing all Nash equilibria and their convex combinations
- Computational advantage: the optimal CE is polynomial-time solvable via LP (unlike PPAD-hard Nash)
- Multiplicative Weights with sublinear regret guarantees convergence of the empirical distribution to CE
- CE underpins online auction mechanisms, traffic control, and multi-agent systems with a centralized correlator
Вопросы для размышления
- Why does a traffic light at an intersection implement a correlated equilibrium rather than just a convention between drivers?
- How are no-regret online learning algorithms related to convergence to CE?
- In which situations does CE yield a strictly better total payoff than the best Nash equilibrium?