3

Prelude: we get this question about specific finite games. Let us answer it generally. (examples 1, 2)


Suppose there is a two-player finite game (a "matrix game") where both players maximize their expected payoff - e.g., if player $1$ attributes probability $q_i$ to any strategy $s_{2i}$ of player $2$, then given her payoff function $f_1$ and a strategy $s_{1k}$ her payoff is $$ \sum_i q_i \cdot f_1(s_k,s_{2i}). $$

The game is dominance solvable; that is, after the iterated elimination of strictly dominated strategies only one pure strategy profile remains.

Is it possible for this game to have a mixed strategy Nash-equilibrium?

Giskard
  • 29,387
  • 11
  • 45
  • 76
  • A game is dominance solvable means the process of iterated deletion of strictly dominated strategies leads to a unique outcome, which in matrix games amounts to a profile of sure strategies. We also know that the process does not eliminate any NEs. Therefore dominance solvable games must have unique pure strategy NE. – Herr K. Jul 15 '22 at 20:54
  • @HerrK. "We also know that the process does not eliminate any NEs." Do the people who asked the questions in examples 1 and 2 know? – Giskard Jul 15 '22 at 20:57
  • They should know the result, if not the proof. I don't think the result itself is difficult to comprehend. – Herr K. Jul 15 '22 at 21:05

1 Answers1

4

No, that is not possible.

Assume that player $2$ has a strategy $s_{2j'}$ that is strictly dominated by $s_{2j}$. This means that for all pure strategies $s_1$ of player $1$, we have $$ f_2(s_1,s_{2j}) > f_2(s_1,s_{2j'}). $$

Lemma 1. This above inequality is also true for any mixed strategies $s_1$ of player $1$.

Proof. Assume player $1$ mixes with a probability vector $p$. Thus the expected payoffs of player $2$ when playing strategies $s_{2j}$ and $s_{2j'}$ are respectively $$ \sum_i p_i \cdot f_2(s_{1i},s_{2j}), \hskip 10pt \text{and} \hskip 10pt \sum_i p_i \cdot f_2(s_{1i},s_{2j'}). $$ For positive probabilities $p_i$ any member $p_i \cdot f_2(s_{1i},s_{2j})$ of the left hand sum will be larger than the corresponding $p_i \cdot f_2(s_{1i},s_{2j'})$ member of the right hand sum. When $p_i = 0$ the members too will be equal. $\sum_i p_i = 1$, so at least one $p_i$ is positive, thus the left hand sum is itself larger than the right hand sum; hence $s_{2j}$ dominated $s_{2j'}$ even against mixed strategies. $QED$


Lemma 2. If a mixed strategy $s_2'$ of player $2$ places positive weight $q_{j'}$ on her pure strategy $s_{2j'}$, then player $2$ has a mixed strategy $s_2$ that dominates $s_2'$.

Proof. Player $2$ can increase her payoff by removing the probability from $s_{2j'}$, because regardless of the strategy $s_1$ player $1$ plays we have $$ \begin{align*} f_2(s_{1},s_{2j'}) & < f_2(s_{1},s_{2j}) \\ q_{j'} \cdot f_2(s_{1},s_{2j'}) & < q_{j'} \cdot f_2(s_{1},s_{2j}) \\ q_{j'} \cdot f_2(s_{1},s_{2j'}) + \sum_{i\neq j'} q_i \cdot f_2(s_{1},s_{2i}) & < q_{j'} \cdot f_2(s_{1},s_{2j}) + \sum_{i\neq j'} q_i \cdot f_2(s_{1},s_{2i}). \end{align*} $$ The left hand side of the final inequality is the expected playoff of player $2$ while playing $s_2'$, while the larger right hand side is her expected payoff while playing another strategy. This other strategy - which we will denote by $s_2$ - yields a larger payoff than $s_2'$ irrespective of $s_1$, thus $s_2$ strictly dominated $s_2'$. $QED$


One can now perform the iteration of strictly dominated pure strategies again. In the end a player should never put positive weight on a strictly dominated pure strategy, even when facing mixed strategies. In equilibrium players act optimally, they will place 0 positive weight on all eliminated strategies. Thus in a dominance solvable game in equilibrium players will play pure strategies.

Giskard
  • 29,387
  • 11
  • 45
  • 76
  • But why shouldn't it be enough to say: (a) In a mixed NE at least one player uses at least two pure strategies. (b) Players don't use interatively strictly dominated pure strategies. From (a) and (b), a dominance solvable game cannot have a mixed NE. – VARulle Oct 21 '22 at 11:48
  • I think the question is essentially about how to prove your (b) lemma. – Giskard Oct 21 '22 at 13:20