Correlated Equilibrium

From Theory

Notes for CS 8803 - Game Theory and Computer Science. Spring 2008

Scribe:

1 The setting
2 Definition
3 Stop Light Example
4 Theorem
5 Proof
6 Corollary
7 Theorem 2
8 epsilon-correlated equilibrium

The setting

A correlated equilibrium is a solution concept that is more general than Nash equilibrium. It was first discussed by Robert Aumann (1974). The idea is that each player chooses her action according to her observation of the value of some correlation device. This device could be a car's navigation system or a traffic light. A strategy assigns an action to every possible observation a player can make. If no player would want to deviate from the recommended strategy (assuming the others don't deviate), the distribution is called a correlated equilibrium. These equilibrium are very easy to compute and alwasy exist. Yea!

Correlation Device gives advice/suggestions $(a_1, a_2, ...,a_N) \in A$ , where $A=A_1\times\ldots\times A_N$ is the set of action profiles.

There is a probability distribution, $π$ , over suggestions. (cells in the game)

$π(a)$ is the probability of $a \in A$

[edit]

Definition

$π$ is a correlated equilibrium if:

$\forall i \leq N$

$\forall a_i, \bar a_i \in A_i$

$\sum \pi(a_i,a_{-i})(u_i(a_i,a_{-i}) - u_i(\bar a_i, a_{-i}))\geq 0$

(How much you will gain from switching from $a i$ to $\bar a_i$ )

[edit]

Stop Light Example

	Stop	Go
Stop	0, 0	0,30
Go	30, 0	-10, -10
Stop Light

A correlated equilibrium here is a 50-50 distribution over the cells (GO,STOP) and (STOP,GO). You are told to play GO with probability 1/2. If you switch GO's to STOP's you lose 30. Same if you switch from STOP to GO.

[edit]

Theorem

If $σ$ is a NE then $\pi(a) = \prod_{i=j}^{N} \sigma_i(a_i)$ is a correlated equilibrium.

[edit]

Proof

Show $\forall_i \leq N$ and $\forall a_i, \bar a_i$

$\sum_{a_{-i}\in A_{-i}} (\pi(a_i,a_{-i})(u_i(a_i,a_{-i})) - u_i(\bar a_i, a_{-i})) = \sigma_i(a_i) \left( \sum_{a_{-i}\in A_{-i}} \prod_{j\neq i} \sigma_j(a_j)u_i(a) - \sum_{a_{-i}\in A_{-i}} \prod_{j \neq i} \sigma_j(a_j) u_i(\bar a_i, a_{-i}) \right) \geq 0$

$\sum_{a_{-i}\in A_{-i}} \prod_{j\neq i} \sigma_j(a_j)u_i(a) = u(a_i,\sigma)$ , and

$\sum_{a_{-i}\in A_{-i}} \prod_{j\neq i} \sigma_j(a_j)u_i(\bar a_i,a_{-i}) = u(a_{-i},\sigma)$ .

Hence,

$\sum_{a_{-i}\in A_{-i}} (\pi(a_i,a_{-i})(u_i(a_i,a_{-i})) - u_i(\bar a_i, a_{-i})) = \sigma_i(a_i) (u(a_i,\sigma)-u(\bar a_i,\sigma)).$

This holds trivially for all $a i$ such that $σ i (a i) = 0$ . On the other hand, since $σ$ is a NE, if $σ i (a i) > 0$ , then as we have shown earlier, we must have that $u(a_i,\sigma_{-i}) \geq u(\bar a_i,\sigma_{-i}).$ (Otherwise, we could take all the mass off of $a i$ and move it to $\bar a_i$ to get a better response.) Hence, in either case, the above quantity is non-negative, as desired.

Q.E.D.

[edit]

Corollary

At least one Correlated Equilibrium exists for any finite game.

[edit]

Theorem 2

The Set of Correlated Equilibrium is a convex set.

Suppose $A i = (1,2,... n i)$

$\pi \in \reals^{n_1 \times n_2 \times \ldots \times n_N}$

$π$ is a Correlated Equilibrium iff $\pi(a_1,a_2,...,a_n)\geq 0, \sum_{a \in A} \pi(a) = 1,$ and

$\forall i, \leq N \forall a_i, \bar a_i \in A_i \sum \pi(a_i,a_{-i})(u_i(a_i,a_{-i}) - u_i(\bar a_i, a_{-i}))\geq 0$

[edit]

epsilon-correlated equilibrium

$π$ is an $ε$ -correlated equilibrium ( $\epsilon\geq 0$ ) if:

$\forall i \leq N ~\sum_{a_i \in A_i} \max_{\bar a_i \in A_i} \sum_{a_{-i} \in A_{-i}} \pi(a_i,a_{-i})(u_i(\bar a_i,a_{-i}) - u_i(a_i, a_{-i}))\leq \epsilon.$