 Solution

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.