Calculating Nash equilibrium in mixed strategy in a game where a Nash equilibrium in pure strategy exists

Question

Let's say I want to calculate Nash equilibrium with mixed strategies for a two-players game, in which there is no Nash equilibrium with pure strategies (no dominant strategy for any of the two players), for example, take the Matching Pennies game with the following payoffs:

\begin{bmatrix} & H & T\\ H & 1,-1 & -1,1\\ T & -1,1 & 1,-1 \end{bmatrix}

Now to calculate the Nash equilibrium, let player 2 (columns player) play $H$ with probability $p$, and $T$ with probability $1-p$. If player 1 (rows player) best responds with mixed strategy, then player 2 must make him indifferent between choosing $H$ or $T$.
This gives us the constraint:

$u_1(H)=u_1(T)$
$\Rightarrow 1\cdot p-1(1-p)=-1\cdot p+1(1-p)$
$\Rightarrow p=0.5$

No surprise here.

What interests me is when trying to apply the same logic in a game where we do have a Nash equilibrium (and dominant strategy to the players), specifically, the Prisoner Dillema game:

\begin{bmatrix} & C & D\\ C & -1,-1 & -4,0\\ D & 0,-4 & -3,-3 \end{bmatrix}

Since intuitively you can't make player 1 (rows player) indifferent between choosing $C$ or $D$ (he is always better-off choosing $D$), we should expect $p=1$ - meaning we should expect that player 2 need to play $D$ with probability $1$, and play $C$ with probability $0$, but that's not the case:

$u_1(C)=u_1(D)$
$\Rightarrow -1\cdot p-4(1-p)=0\cdot p-3(1-p)$
$\Rightarrow -3=-4$

No such $p$.
Why is that?

Answer 1

Since intuitively you can't make player 1 (rows player) indifferent between choosing $C$ or $D$ (he is always better-off choosing $D$), we should expect p=1

Actually, since player I can't be made indifferent between $C$ and $D$ (he always prefers $D$), there is no solution to the equation $u_1(C)=u_1(D)$. This is exactly what you have discovered.

In general, if player I's payoff matrix is $A$, then against a mixed strategy $y$ of player II, represented as a column vector, player I expects payoff $(Ay)_i$ for row $i$. For a given subset of rows, $R$, we may or may not be able to find $y$ such that $(Ay)_i = u$ for all $i \in R$. In fact, even if we can make player I indifferent between the rows in $R$ such that he expects payoff $u$, it could still be the case that there is a row $j \notin R$ with $(Ay)_j > u$, i.e., against $y$ the rows in $R$ are not best responses.

Here's a $3 \times 2$ example:

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

For $y = (1/3, 2/3)^\top$ we have $Ay = \left ( \begin{array}{c}{4/3\\4/3\\1}\end{array} \right )$, so rows 1 and 2 are best responses against $y$. Likewise, for $y = (1/2, 1/2)^\top$, rows 2 and 3 are best responses with expected payoff 1.5 versus payoff 1 for row 1. However, for $y = (2/5, 3/5)^\top$, player I is indifferent between rows 1 and 3, which have payoff $6/5$, but the unique best response is row 2 with payoff $7/5$.

In general, potential Nash equilibria correspond to vertices of polyhedra defined by an upper envelope of payoff hyperplanes for pure strategies against the mixed strategy of the opponent. Some sets of hyperplanes do not meet in a vertex, and some that do meet in a vertex are below the upper envelope, i.e., they are not best responses against the mixed strategy that equalizes the payoffs of the corresponding pure strategies.

For more details on finding equilibria using upper envelopes, see the answer to this question:

Mixed strategy nash equilibria in from $2\times N$ bimatrix form