[Math] Construct a game with only pure strategy nash equilibrium.

game theory

I'm trying to construct a normal-form game with $2$ players such that the game has exactly $4$ Nash Equilibria

From the above properties, I know the game has to be a $4 \times 4$ matrix game, and it has $4$ pure strategy Nash Equilibrium with no mixed strategy Nash Equilibrium. This means there's no corresponding probability such that the players are indifferent to choose. Could someone find an example of this kind of matrix? And briefly explain how you construct it? Thanks a lot.

Best Answer

This requires degeneracy, since any non-degenerate game has an odd number of equilibria.

As a warmup let's do an example of a $2 \times 2$ game with exactly two (pure) equilibria:

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

The game has exactly two pure Nash equilibria: (top, left) and (bottom, right). The reason that no mixture is possible is that as soon as player 1 puts any positive probability on bottom, the unique best response is right. Likewise, by symmetry, as soon as player 2 puts positive probability on right, the unique best response is bottom. The game is degenerate because against left, a pure strategy, i.e., a mixed strategy with support size $1$, there are $2$ ($2>1$) best responses. This is a game where bottom and right are weakly dominant strategies for players 1 and 2 respectively.

Now I generalize this idea to a 4x4 game:

$$ \begin{align} A & = \left(\begin{array}{cccc} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 2 & 0 \\ 0 & 1 & 2 & 3 \end{array}\right)\\ B=A^\top & = \left(\begin{array}{cccc} 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 2 & 2 \\ 0 & 0 & 0 & 3 \end{array}\right) \end{align} $$

The four pure equilibria are the diagonal cells. No mixing is possible for similar reasons to the 2x2 case. To check the answer, you can use my online game solver http://banach.lse.ac.uk.

This idea clearly generalizes to a construction of symmetric $n \times n$ games with exactly $n$ symmetric pure equilibria.