Coarse correlated equilibrium is too lax

The concept of equilibrium in Game Theory intends to predict the outcome of a game. Sometimes, the equilibrium shoul be thought of the strategy profile that players get to play after knowing the game very well. To know the game well, they must have played the game, so there are natural interpretations of equilibria in repeated games. Also, there is Evolutionary Game Theory, which tries to identify equilibria that a population of agents would arrive to, if given enough time.

In Learning Theory (and before), there is the concept of “Coarse correlated equilibrium”, which is defined as follows.

$ \newcommand{\PP}{\mathbb{P}} \newcommand{\RR}{\mathbb{R}} \newcommand{\EE}{\mathbb{E}} \newcommand{\eps}{\varepsilon} \newcommand{\defas}{≔} % {\coloneqq} $

Consider a multi-player normal form game $(I, A, u \colon A^I \to \RR^I)$, where $I$ is the set of players, $A$ the set of actions for each player, and $u$ the payoff function in vector form. A distribution over strategy profiles $\mu \in \Delta(A^I)$ is said to be a coarse correlated equilibrium if, for every player $i \in I$ and every action $a \in A$,

𝔼 σ ∼ μ ( u i ( σ ) ) ≥ 𝔼 σ ∼ μ ( u i ( σ − i , a ) ) . \mathbb{E}_{\sigma \sim \mu}( u_i(\sigma) ) \ge \mathbb{E}_{\sigma \sim \mu}( u_i(\sigma_{-i}, a) ) \,.

In other words, every player is better in expectation if they play according to $\mu$ than if they unilaterally and without disturbing the other players change their actions by a fix action all the time.

The best interpretation of this equilibrium concept I know if is as follows.

  • Imagine the coordinator send a closed envelop to every player.
  • Each envelop contains an action for them to play.
  • The distribution over action profiles is commonly known and follows $\mu$.
  • Once the player receives the envelop can choose between: open the envelop and play that action; or never open the envelop and do what they want. Under this dynamic, coarse correlated equilibrium is a usual Nash equilibrium. Sounds good, right? We will see that there are very strong assumptions in this dynamic.

Example

The following example is a variation of a game that appeared in No-regret dynamics and fictitious play. The game has tow players and four actions per player. The payoff function is given by the following table.

Table 1
Action 1 Action 2 Action 3 Action 4
Action 1 3, 3 3, 2 0, 0 0, -1
Action 2 2, 3 2, 2 -1, 0 -1, -1
Action 3 0, 0 0, -1 3, 3 3, 2
Action 4 -1, 0 -1, -1 2, 3 2, 2

Actions 2 and 4 are strictly dominated for both players by actions 1 and 3 respectively. Basically, players should never play them. But there is a coarse correlated equilibrium that is supported only on these actions: $1/2$ action $(2, 2)$ and $1/2$ action $(4, 4)$ is a coarse correlated equilibrium.

I can only explain this equilibria as follows: given that you know that the other player will play irraltionally actions $2$ and $4$ uniformely, your best option is to play as they do… and their action is given inside the envelop of the coarse correlated equilibrium.