Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 42 / 4

The intended deletion theorem starts from the full action set $A=M\cup N$. Under that interpretation, each player's surviving action set remains nonempty: with only one action, no mixed strategy can weakly improve it and improve it strictly somewhere. Let the final reduced bimatrix game have a Nash equilibrium, which exists by Nash's theorem.

Restore the deleted actions in reverse order. Consider a row action $i$ when it is restored. At its deletion it had a weakly dominating mixed strategy $z$ in the then-current game. If $z_i>0$, remove that self-weight and renormalize: the strict-improvement clause guarantees $z_i<1$, and dividing the payoff comparison by $1-z_i$ gives a weakly dominating strategy supported on the other then-current row actions. Those other actions have already been restored in the reverse process. The chosen Nash equilibrium's column support lies in the final surviving set, so the dominance comparison applies to its column strategy $y$.

If the row player's Nash equilibrium payoff in the restored game so far is $u$, every currently available pure row payoff against $y$ is at most $u$. The dominating mixture therefore has payoff at most $u$, and the restored action has payoff no greater than that mixture. It cannot improve the payoff. Column deviations are unchanged by adding a row action, since the actual Nash equilibrium strategy remains fixed. The analogous argument works when restoring a column action. Induction restores the full game while preserving the final reduced Nash equilibrium and its support.

Thus iterated deletion of weakly dominated actions preserves at least one Nash equilibrium supported entirely on surviving actions. It need not preserve every Nash equilibrium or give an order-independent reduced game.

The literal printed use of an arbitrary initial $A$ needs qualification. For example, take row payoffs $\left(\begin{array}{cc}0& 3\\ 1& 0\end{array}\right)$ and column payoffs $\left(\begin{array}{cc}0& 1\\ 0& 1\end{array}\right)$. On the restricted set containing both rows but only column $1$, row $1$ is strictly dominated by row $2$. Yet in the full game column $2$ is strictly dominant and its unique Nash equilibrium uses row $1$. Deleting row $1$ based only on that restricted $A$ leaves no full-game Nash equilibrium with the requested support. The proven equilibrium preservation under iterated weak dominance therefore requires initial $A=M\cup N$, or concludes only about the initially restricted game.

Use the PDF's entry $P_{12}=4$, rather than the TeX aid's $2$. To check nondegeneracy of a bimatrix game, every opponent strategy of support size $k$ must have at most $k$ pure best responses. Against each pure column, the unique best rows are respectively $3,1,2$. Against each pure row, the unique best columns are respectively $1,2,2$.

The only mixture making all three rows indifferent solves $-y_1+2y_3=0$ and $-2y_1+2y_2-3y_3=0$, giving $y=(4,7,2)/13$, which has support size three. Thus no two-column-support mixture has three best rows. For the other player, column $1$ strictly dominates column $3$, because their payoff difference is $(1,1,2)$, so three best columns are impossible. These observations cover all support sizes, proving the game is nondegenerate.

For the Lemke-Howson algorithm, use unnormalized strategy vectors $u,v$ in the polytopesA row label $i\in \{1,2,3\}$ occurs at $u_i=0$ in $\mathcal{X}$ or at $(Pv{)}_i=1$ in $\mathcal{Y}$. A column label $3+j$ occurs at $(Q^{T}u{)}_j=1$ in $\mathcal{X}$ or at $v_j=0$ in $\mathcal{Y}$. The origin pair has all six labels.

Drop row label $3$ by increasing $u_3$. Column $2$ is the first binding payoff constraint, at $u_3=1/4$, so label $5$ becomes duplicated. Drop $5$ in $\mathcal{Y}$ by increasing $v_2$; row $1$ binds first, at $v_2=1/4$, duplicating label $1$. Drop $1$ in $\mathcal{X}$ by increasing $u_1$ while keeping $u_2=0$ and the column-$2$ constraint binding. Since that constraint does not involve $u_1$, $u_3$ stays $1/4$. Column $1$ binds at $u_1=1/4$, duplicating label $4$.

Now drop $4$ in $\mathcal{Y}$ by increasing $v_1$. Keep $v_3=0$ and row $1$ binding, so $v_2=1/4$. Row $3$ reaches payoff $1$ at $v_1=1/6$, earlier than row $2$, which would bind at $v_1=1/4$. The missing label $3$ returns, terminating the path. The successive vertex-label pairs areThe final pair is completely labelled and nonzero. Normalize each vector by its own sum to obtainThe row payoffs against $y$ are $(12/5,2,12/5)$ and the column payoffs against $x$ are $(2,2,1/2)$. Both supported actions are best responses, so this is a Nash equilibrium, with payoffs $\boxed{(12/5,2)}$.