Finding Mixed Nash Equilibria in a $3\times 3$ Game

Question

I am tasked with finding all of the Nash Equilibria (pure or mixed) in the of the following game:

$$\begin{array} \\&L&C&R\\ T&2,2&2,3&1,2\\ M&0,3&3,2&1,1\\ B&3,1&0,2&0,3\end{array}$$

I have already deduced that there are no pure strategy equilibria here by using the "underline the best response" method. In order to find mixed strategies, I know that one must be indifferent to all of his own options given a probability distribution from the other player, i.e. the expected utility from any of his choices is the same given what his opponent might play.

To do this, I started by finding the expected utility of each of the pure strategies by assigning probabilities to each of their actions. For Player $1$, $T$, $M$, and $B$ got probabilities of $x$, $y$, and $1-x-y$, respectively; I did a similar thing for Player $2$, with $p$, $q$, and $1-p-q$. Then, I calculated each players' utility given that his opponent picked a pure strategy; for Player $1$:

$$U_1((x,y,1-x-y),L)=3-x-3y$$ $$U_1((x,y,1-x-y), C)=2x+3y$$ $$U_1((x,y,1-x-y), R)=x+y$$

and for Player $2$:

$$U_2(T, (p,q,1-p-q))=q+2$$ $$U_2(M, (p,q,1-p-q))=2p+q+1$$ $$U_2(B, (p,q,1-p-q))=3-2p-q$$

Using these, I hoped to be able to see whether or not any of the pure strategies was strictly dominated given some other mixed strategy (e.g. $M$ is strictly dominated by some combination of $t$ and $B$). However, I'm not confident that this is the best way of actually doing this problem. Any suggestions as to where to go/what method to employ would be sincerely appreciated. Cheers.

Answer 1

Assume the pure strategy $s_i$ is strictly dominated by $s_i'$. This means that $s_i$ is not a best response to any of the opponent's pure strategies. For whatever strategy the other player is playing, the strategy $s_i'$ would yield a larger payoff. Even if $s_i'$ is a mixed strategy, for any strategy the opponent is playing you can select a pure component of $s_i'$ with a larger payoff than $s_i$ as the payoff of $s_i'$ is the average of the payoffs of its pure components.

A reversal of this is that if a pure strategy is a best response to any pure strategy of the opponent, it cannot be strictly dominated.

From the "underline the best response" method you will see that all the strategies of all the players are best response to at least one strategy of the opponent, hence none of them are strictly dominated.

Unfortunately, this still does not tell you much about the mixed equilibria. With different supports it is possible to have more than one.

---

An example:

In the game $$ \begin{array} \\&L&C&R\\ T&1,1&0,0&0,0\\ M&0,0&1,1&0,0\\ B&0,0&0,0&1,1 \end{array} $$ the strategy profile where all strategies are mixed with probability $1/3$ is a mixed equilibrium, but the strategy profile where the Row player mixes $T$, $M$ while the Column player mixes $L$ and $C$ with probability $1/2$ is also a mixed equilibrium. (There are two other mixed equilibria and three pure ones.)

---

So there is no trivial method to find all the mixed equilibria, one usually has to use a trick or work through the different cases for all the supports.

Wilson's oddness theorem tells you that there are an odd number of equilibria, except in special "degenerate" cases.

Answer 2

The following method works if you already know or at least you may safely assume that the game is nondegenerate, i.e. all Nash equilibria (NE) are isolated:

(a) Check for pure NE. (None in your case.)

(b) Check for a completely mixed NE. This means solve the corresponding $3\times 3$ system of equations. (None in your case.)

(c) For each of the $9$ pairs $(s_1,s_2)$ of pure strategies do the following:

1. Eliminate $s_1$ from the row-player's and $s_2$ from the column-player's strategy set. For the remaining $2\times 2$-game, find the pure NE.

2. If there is $1$ pure NE, move on.

3. If there are $0$ or $2$ pure NE, there must also be a mixed one. Calculate it by solving the corresponding $2\times 2$ system of equations.

4. Calculate the payoffs of both players at the mixed NE.

5. Check, whether the missing pure strategy of a player gives him a higher payoff against the opponent's mixture than his NE-payoff.

6. If this is the case for one of the two players, move on.

7. If this is the case for neither of the two players, you have found a (partially mixed) NE of the full game! (Just add a zero probability for the missing pure strategy.) Move on.

In your example, when eliminating $(B,R)$ you will find the unique NE $E=((1/2,1/2,0),(1/3,2/3,0))$.

Alternatively, go to this bimatrix game solver and let it do the job for you.