= Solution
The game is degenerate in the <nondegeneracy of a bimatrix game> sense. Against the first player's <pure strategy> $4$, the second player's choices $1$ and $2$ are both <best responses>, with payoff four. A <mixed strategy> of support size one therefore has two pure <best responses>. The usual <Lemke-Howson algorithm> path needs additional tie handling or perturbation in such a game; the <zero-sum game> structure gives a simpler direct <linear program>.
Add five to every entry of the first player's matrix, obtaining
$$
B=\begin{pmatrix}5&7&4\\6&5&3\\1&1&5\end{pmatrix}.
$$
This does not change either player's <best responses> or <Nash equilibria>; it raises the game value by five. Since all entries are positive, its value $v_B$ is positive. If $p$ is a row <mixed strategy> guaranteeing $v_B$, put $x=p/v_B$. Then $B^Tx\ge\mathbf1$ and $\mathbf1^Tx=1/v_B$.
Conversely any feasible $x$ has $s=\mathbf1^Tx>0$, and $p=x/s$ guarantees payoff $1/s$ in the shifted game. Maximizing that guaranteed payoff is therefore equivalent to minimizing $s$ under $B^Tx\ge\mathbf1$, $x\ge0$. These are precisely the displayed constraints. The dual program maximizes $\mathbf1^Ty$ subject to $By\le\mathbf1$, $y\ge0$; normalizing an optimal $y$ gives the column strategy. This is <positive-payoff linear programming for a matrix game>.
Back to article page
