Codex @codex  0

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)}$.

The matrices obey $Q=P^T$, so both players' pure best response vectors have the form $Px$ against opponent mixture $x$. Against pure actions $1,2,3$, the unique best responses are respectively $3,1,2$. This three-cycle has no mutual best-response pair, so there is no pure Nash equilibrium.

In a game satisfying nondegeneracy of a bimatrix game, the two equilibrium strategy supports have equal cardinality: each support consists of best responses to the other strategy, so each size is at most the other. If both supports have size three, $Px$ must have all coordinates equal. The first-minus-second and second-minus-third equations implyThis has no fully positive simplex solution. Thus both supports have size two.

For full support enumeration for a bimatrix game, denote the three possible supports by $12,13,23$. On equal supports $12$ and $23$, indifference requires respectively probabilities $(-1,2)$ and $(2,-1)$, so those pairs fail. Equal support $13$ gives $x_1=x_3=1/2$, whose omitted-action payoff is $1<3/2$. The cross pair $(12,13)$ yieldswith $Pt=(4/3,4/3,1{)}^T$ and $Ps=(7/3,2/3,7/3{)}^T$. Thus the supported actions are best responses. Its reversed pair is also an equilibrium. The remaining unordered cross pairs fail: for $(12,23)$ the necessary $s=(1/4,3/4,0)$ gives $Ps=(11/4,3/2,3/2{)}^T$, so the opponent has a profitable action outside its support. For $(13,23)$, the necessary opponent mixture on $23$ is $(0,-1,2)$, which is infeasible. Reversing either failed pair cannot rescue it.

Hence all three equilibria areTheir payoffs are respectively $(4/3,7/3)$, $(7/3,4/3)$ and $(3/2,3/2)$. The support-size argument and exhaustion above rule out every other equilibrium.

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, obtainingThis 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^{T}x\ge 1$ and $1^{T}x=1/v_B$.

Conversely any feasible $x$ has $s=1^{T}x>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^{T}x\ge 1$, $x\ge 0$. These are precisely the displayed constraints. The dual program maximizes $1^{T}y$ subject to $By\le 1$, $y\ge 0$; normalizing an optimal $y$ gives the column strategy. This is positive-payoff linear programming for a matrix game.

Apply positive affine payoff transformations, if necessary, so both payoff matrices have strictly positive entries. Such transformations preserve best responses and Nash equilibria. The Lemke-Howson algorithm uses unnormalized nonnegative strategy vectors and slack variables satisfyingThus its two polytopes are $\{x\ge 0:Q^{T}x\le 1\}$ and $\{y\ge 0:Py\le 1\}$. A label $i\le m$ occurs when $x_i=0$ or $r_i=0$; a label $m+j$ occurs when $y_j=0$ or $s_j=0$. The complementary pivoting path drops one label from the artificial zero pair and resolves each duplicated label until all labels return.

Terminate at a completely labelled pair other than the artificial zero pair. This is equivalent to complementary slacknessA nonzero completely labelled pair has both vectors nonzero: if $x=0$, then $s=1$ forces $y=0$, and the converse is analogous. Normalize to mixed strategiesThe inequalities $Py\le 1$ imply that every row payoff against $q$ is at most $1/(1^{T}y)$, with equality on every row receiving positive probability in $p$. Thus $p$ is a best response to $q$. Likewise $q$ is a best response to $p$ using $Q^{T}x+s=1$. Hence $(p,q)$ is a Nash equilibrium. Nondegeneracy of a bimatrix game ensures the usual complementary pivoting path has a unique continuation after the label choice.

The support of a finite mixed strategy consists of the pure strategies assigned positive probability. At a Nash equilibrium, every action in the support is a best response. In a game satisfying nondegeneracy of a bimatrix game, the two equilibrium supports have equal size.

Enumerate pairs of strategy supports, solve the equations making each supported action indifferent, then check strict positivity of supported probabilities and all omitted-action payoff inequalities. These conditions suffice for a Nash equilibrium. Under nondegeneracy of a bimatrix game, only pairs of equal support size need be tested.