What's the difference between a Nash, Correlated, and Extreme equilibrium?

Question

As the title states, what's the difference? As I understand it:

• The Nash Equilbirum (NE) is a solution concept in non-cooperative games where no player has incentive to unilaterally deviate from a given strategy.
• The Correlated Equilibrium (CE) is a generalization of the NE where players have no incentive to unilaterally deviate given that all other players play according to a public signal.
• The Extreme Equilibrium (EE) I'm having a hard time understanding this concept. There exist several algorithms for enumerating all EEs (e.g. the EEE algorithm and the improved EEE algorithm), but what exactly are they and how are they different from NEs or CEs?

Answer 1

An extreme equilibrium $(x,y)$, where $x$ and $y$ are the mixed strategies of players 1 and 2, is a Nash equilibrium where for both players mixed strategies cannot be described as convex combinations of other mixed strategies that form equilibria.

Fact: There are always finitely many extreme equilibria.**

For a mixed strategy $x$, let the support of $x$ be defined as the set of pure strategies that $x$ uses with positive probability, i.e.,

$$\text{support}(x) := \{ i : x_i > 0 \}.$$

A game is called non-degenerate game if for all mixed strategies $x$, if $|\text{support}(x)| = k$ then the number of best responses against $x$ is at most $k$.

Fact: Every non-degenerate game has only extreme equilibria.

For a simple example of a game with non-extreme equilibria consider a $2\times 2$ game where both players get $0$ for all strategy profiles. In this case, all four pure profiles are extreme equilibria and all strict mixtures are non-extreme Nash equilibria. For a less trivial example, consider any $2 \times 2$ bimatrix game where there is no strict dominance for either player but exactly one of the players has a weakly dominant strategy. Then, the game is degenerate and the game will have infinitely many equilibria. As an example, consider the following game.

$$A = \left( \begin{array}{ccc} 1 & 0 \\ 0 & 1 \\ \end{array} \right) \quad B = \left( \begin{array}{ccc} 1 & 1 \\ 1 & 0 \\ \end{array} \right) $$

The game has exactly two extreme equilibria. Here is the output from the online game solver http://banach.lse.ac.uk, which shows these two extreme equilibria:

2 x 2 Payoff matrix A:

  1  0
  0  1

2 x 2 Payoff matrix B:

  1  1
  1  0

EE = Extreme Equilibrium, EP = Expected Payoff

Decimal Output

  EE  1  P1:  (1)  1.0  0.0  EP=  1.0  P2:  (1)  1.0  0.0  EP=  1.0
  EE  2  P1:  (1)  1.0  0.0  EP=  0.5  P2:  (2)  0.5  0.5  EP=  1.0

Rational Output

  EE  1  P1:  (1)  1  0  EP=    1  P2:  (1)    1    0  EP=  1
  EE  2  P1:  (1)  1  0  EP=  1/2  P2:  (2)  1/2  1/2  EP=  1

Connected component 1:
{1}  x  {1, 2}

The final line of this output shows that against the unique equilibrium strategy of player 1 (top row), player 2 can play any convex combination of $(1,0)$ and $(1/2,1/2)$.

For a thorough technical exposition, which covers both finding extreme equilibria and then from these all equilibria of bimatrix games, see, e.g.,

David Avis, Gabriel D. Rosenberg, Rahul Savani, and Bernhard von Stengel (2010).
Enumeration of Nash equilibria for two-player games.
Economic Theory, 42:9–37.

On the relationship between correlated equilibria and Nash equilibria:

Fact:: The set of correlated equilibrium distributions of an $n$-player noncooperative game is a convex polytope that includes all the Nash equilibrium distributions. In fact, the Nash equilibria all lie on the boundary of the polytope.

See:

Robert Nau, Sabrina Gomez Canovas, and Pierre Hansen (2004).
On the geometry of Nash equilibria and correlated equilibria.
International Journal of Game Theory 32: 443-453.