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

<p>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.</p>

<p>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.</p>

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

<hr>

<p>An example:</p>

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

<hr>

<p>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.</p>

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

CC BY-SA 4.0
2020-02-11T05:06:33.823Z
2020-02-11T05:06:33.823Z
Giskard
<p>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:</p>

<p>(a) Check for pure NE. (None in your case.)</p>

<p>(b) Check for a completely mixed NE. This means solve the corresponding <span class="math-container">$3\times 3$</span> system of equations. (None in your case.)</p>

<p>(c) For each of the <span class="math-container">$9$</span> pairs  <span class="math-container">$(s_1,s_2)$</span> of pure strategies do the following:</p>

<ol>
<li><p>Eliminate <span class="math-container">$s_1$</span> from the row-player's and <span class="math-container">$s_2$</span> from the
column-player's strategy set. For the remaining <span class="math-container">$2\times 2$</span>-game,
find the pure NE.</p></li>
<li><p>If there is <span class="math-container">$1$</span> pure NE, move on.</p></li>
<li><p>If there are <span class="math-container">$0$</span> or <span class="math-container">$2$</span> pure NE, there must also be a mixed one.
    Calculate it by solving the corresponding <span class="math-container">$2\times 2$</span> system of
    equations.</p></li>
<li><p>Calculate the payoffs of both players at the mixed NE.</p></li>
<li><p>Check, whether the missing pure strategy of a player gives him a
            higher payoff against the opponent's mixture than his NE-payoff.</p></li>
<li><p>If this is the case for one of the two players, move on.</p></li>
<li><p>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.</p></li>
</ol>

<p>In your example, when eliminating <span class="math-container">$(B,R)$</span> you will find the unique NE <span class="math-container">$E=((1/2,1/2,0),(1/3,2/3,0))$</span>.</p>

<p>Alternatively, go to <a href="https://cgi.csc.liv.ac.uk/~rahul/bimatrix_solver/" rel="nofollow noreferrer">this bimatrix game solver</a> and let it do the job for you.</p>

CC BY-SA 4.0
2020-02-28T13:56:57.067Z
2020-02-28T13:56:57.067Z
VARulle
<p>I am tasked with finding all of the Nash Equilibria (pure or mixed) in the of the following game:</p>

<p><span class="math-container">$$\begin{array}
\\&amp;L&amp;C&amp;R\\
T&amp;2,2&amp;2,3&amp;1,2\\
M&amp;0,3&amp;3,2&amp;1,1\\
B&amp;3,1&amp;0,2&amp;0,3\end{array}$$</span></p>

<p>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. </p>

<p>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 <span class="math-container">$1$</span>, <span class="math-container">$T$</span>, <span class="math-container">$M$</span>, and <span class="math-container">$B$</span> got probabilities of <span class="math-container">$x$</span>, <span class="math-container">$y$</span>, and <span class="math-container">$1-x-y$</span>, respectively; I did a similar thing for Player <span class="math-container">$2$</span>, with <span class="math-container">$p$</span>, <span class="math-container">$q$</span>, and <span class="math-container">$1-p-q$</span>. Then, I calculated each players' utility given that his opponent picked a pure strategy; for Player <span class="math-container">$1$</span>:</p>

<p><span class="math-container">$$U_1((x,y,1-x-y),L)=3-x-3y$$</span>
<span class="math-container">$$U_1((x,y,1-x-y), C)=2x+3y$$</span>
<span class="math-container">$$U_1((x,y,1-x-y), R)=x+y$$</span></p>

<p>and for Player <span class="math-container">$2$</span>:</p>

<p><span class="math-container">$$U_2(T, (p,q,1-p-q))=q+2$$</span>
<span class="math-container">$$U_2(M, (p,q,1-p-q))=2p+q+1$$</span>
<span class="math-container">$$U_2(B, (p,q,1-p-q))=3-2p-q$$</span></p>

<p>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. <span class="math-container">$M$</span> is strictly dominated by some combination of <span class="math-container">$t$</span> and <span class="math-container">$B$</span>). 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. </p>

<game-theory>
Finding Mixed Nash Equilibria in a $3\times 3$ Game
scoopfaze
# Finding Mixed Nash Equilibria in a $3\times 3$ Game

(Asked by: username_0 on 2020-02-11)

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.

**Tags:** game-theory


---

## 2 answers

### Answer by username_1 on 2020-02-11. Score: 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 by username_2 on 2020-02-28. Score: 0

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](https://cgi.csc.liv.ac.uk/~rahul/bimatrix_solver/) and let it do the job for you.


---

