3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Herr K.
    Commented Jul 15, 2022 at 20:54
  • $\begingroup$ @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? $\endgroup$
    – Giskard
    Commented Jul 15, 2022 at 20:57
  • $\begingroup$ They should know the result, if not the proof. I don't think the result itself is difficult to comprehend. $\endgroup$
    – Herr K.
    Commented Jul 15, 2022 at 21:05

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – VARulle
    Commented Oct 21, 2022 at 11:48
  • $\begingroup$ I think the question is essentially about how to prove your (b) lemma. $\endgroup$
    – Giskard
    Commented Oct 21, 2022 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.