= 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> satisfying
$$
\boxed{x\geq0,\quad Q^Tx+s=\mathbf1,\quad s\geq0;\qquad y\geq0,\quad Py+r=\mathbf1,\quad r\geq0.}
$$
Thus its two polytopes are $\{x\geq0:Q^Tx\leq\mathbf1\}$ and $\{y\geq0:Py\leq\mathbf1\}$. A label $i\leq 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.
\b[Terminate at a completely labelled pair other than the artificial zero pair.] This is equivalent to <complementary slackness>
$$
x_ir_i=0\quad(1\leq i\leq m),\qquad y_js_j=0\quad(1\leq j\leq n).
$$
A nonzero completely labelled pair has both vectors nonzero: if $x=0$, then $s=\mathbf1$ forces $y=0$, and the converse is analogous. Normalize to <mixed strategies>
$$
p=\frac{x}{\mathbf1^Tx},\qquad q=\frac{y}{\mathbf1^Ty}.
$$
The inequalities $Py\leq\mathbf1$ imply that every row payoff against $q$ is at most $1/(\mathbf1^Ty)$, 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^Tx+s=\mathbf1$. 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.
Back to article page
