# AF- Revisiting Lemke-Howson¶

## Corresponding chapters¶

Duration: 50 minutes

## Objectives¶

• Re visit Lemke Howson Algorithm

## Notes¶

Consider the $$(A,B)\in{\mathbb{R}^{2\times 2}}^2$$ game:

$\begin{split}A = \begin{pmatrix} 1 & 4 \\ -3 & 2 \end{pmatrix} \qquad B = \begin{pmatrix} 5 & 2 \\ -1 & 9 \end{pmatrix}\end{split}$

Ask students in pairs to construct the column player best response polytope

First we add $$4$$ to all elements to ensure they are positive:

$\begin{split}A = \begin{pmatrix} 5 & 8 \\ 1 & 6 \end{pmatrix} \qquad B = \begin{pmatrix} 9 & 6 \\ 3 & 13 \end{pmatrix}\end{split}$

By definition (https://vknight.org/gt/chapters/06/#Definition-of-best-response-polytopes), the column player best response polytope $$\mathcal{Q}$$ is given by:

$\mathcal{Q} = \{y\in\mathbb{R}^{n}\;|\;Ay\leq 1\;y\geq0\}$

So the inequalities are:

\begin{split}\begin{align*} 5y_1+8y_2&\leq 1&&\text{ label: }0\\ y_1 + 6y_2&\leq 1&&\text{ label: }1\\ y_1&\geq 0&&\text{ label: }2\\ y_2&\geq 0&&\text{ label: }3 \end{align*}\end{split}

The first two inequalities come from $$Ay\leq 1$$, however, $$Ay$$ corresponds to the row players utility against vertex $$y$$.

Note that everything is scaled so that the best response of the row player is $$1$$ (the scaling takes place in the strategies/vertices).

Thus if a vertex has label $$0$$ or $$1$$ that implies that the first/second row player strategy is a best response to $$y$$.

We will return to this idea but first let us plot our $$Q$$. We start by rearranging our inequalities:

\begin{split}\begin{align*} y_2 &\leq 1/8 - 5/8y_1&&\text{ label: }0\\ y_2 &\leq 1/6 - y_1/6&&\text{ label: }1\\ y_1&\geq 0&&\text{ label: }2\\ y_2&\geq 0&&\text{ label: }3 \end{align*}\end{split}

Now let us sketch these:

import matplotlib.pyplot as plt
%matplotlib inline
y1s = [0, 1]
first_line = [1 / 8 - 5 / 8 * y for y in y1s]
second_line = [1 / 6 - y / 6 for y in y1s]
plt.figure()
plt.plot(first_line, label="$1/8-5/8y_1$ (label: 0)")
plt.plot(second_line, label="$1/6-y_1/6$ (label: 1)")
plt.legend();


This gives:

We can see that our polytope is a straightforward triangle and that no vertex will ever have label $$1$$.

Discuss if this is OK?

Returning to the game:

$\begin{split}A = \begin{pmatrix} \underline{5} & \underline{8} \\ 1 & 6 \end{pmatrix}\end{split}$

We see that the first strategy dominates the second: so the second strategy is never a best response.

Our vertices with labels are:

\begin{split}\begin{align*} (0, 0)&\text{ labels }\{2, 3\}\\ (0, 1/8)&\text{ labels }\{0, 2\}\\ (1/5, 0)&\text{ labels }\{0, 3\}\\ \end{align*}\end{split}

Exercise:

Obtain the best response polytope for the row player:

By definition (https://vknight.org/gt/chapters/06/#Definition-of-best-response-polytopes), the row player best response polytope $$\mathcal{P}$$ is given by:

$\mathcal{Q} = \{x\in\mathbb{R}^{m}\;|\;x\geq0\;xB\leq 1\}$

So the inequalities are:

\begin{split}\begin{align*} x_1&\geq 0&&\text{ label: }0\\ x_2&\geq 0&&\text{ label: }1\\ 9x_1+3x_2&\leq 1&&\text{ label: }2\\ 2x_1 + 9x_2&\leq 1&&\text{ label: }3 \end{align*}\end{split}

Rearranging:

\begin{split}\begin{align*} x_1&\geq 0&&\text{ label: }0\\ x_2&\geq 0&&\text{ label: }1\\ x_2&\leq 1/3 - 3 x_1&&\text{ label: }2\\ x_2&\leq 1/9 - 2/9x_1&&\text{ label: }3 \end{align*}\end{split}

Now let us sketch these:

x1s = [0, 1]
first_line = [1 / 3 - 3 * x for x in x1s]
second_line = [1 / 9 - 2 / 9 * x for x in x1s]
plt.figure()
plt.plot(first_line, label="$1/3-3x_1$ (label: 2)")
plt.plot(second_line, label="$1/9-2/9x_1/6$ (label: 3)")
plt.legend();


This gives:

We see that there our polytope has 4 vertices:

\begin{split}\begin{align*} (0, 0)&\text{ labels }\{0, 1\}\\ (0, 1/9)&\text{ labels }\{0, 3\}\\ (1/9, 0)&\text{ labels }\{1, 2\}\\ (2/25, 7/75)&\text{ labels }\{2, 3\}\\ \end{align*}\end{split}

Here is some sympy code to verify the intersection of both boundaries:

>>> import sympy as sym
>>> x = sym.Symbol("x")
>>> sym.solveset(sym.S(1) / 3-3 * x - sym.S(1) / 9 + sym.S(2) / 9 * x, x)
{2/25}


We now carry out the Lemke-Howson algorithm.

• Start at $$((0, 0), (0, 0))$$, have labels $$\{0, 1, 2, 3\}$$. Drop 3 in $$\mathcal{Q}$$: move to $$((0, 0), (0, 1/8))$$ and pick up 0.
• At $$((0, 0), (0, 1/8))$$, have labels $$\{0, 1, 2\}$$. Drop 0 in $$\mathcal{P}$$: move to $$((1 / 9, 0), (0, 1/8))$$ and pick up 2.
• At $$((1/9, 0), (0, 1/8))$$, have labels $$\{0, 1, 2\}$$. Drop 2 in $$\mathcal{Q}$$: move to $$((1 / 9, 0), (1/5, 0))$$ and pick up 3.
• At $$((1/9, 0), (1/5, 0))$$, have labels $$\{0, 1, 2, 3\}$$: stop.

Normalise to get:

$((1, 0), (1, 0))$

Now, ask students to carry this out using tableaux:

Apply definitions to get:

$\begin{split}T_r = \begin{pmatrix} 9 & 3 & 1 & 0 & 1 \\ 6 & 13 & 0 & 1 & 1 \\ \end{pmatrix}\end{split}$

and:

$\begin{split}T_c = \begin{pmatrix} 1 & 0 & 5 & 8 & 1 \\ 0 & 1 & 1 & 6 & 1 \\ \end{pmatrix}\end{split}$
• $$T_r$$ has labels $$\{0, 1\}$$.
• $$T_c$$ has labels $$\{2, 3\}$$.

Now let us drop 3 from $$T_c$$. The minimum ratio test: $$1/8<1/6$$ so pivot on 1st row.

$\begin{split}T_c = \begin{pmatrix} 1 & 0 & 5 & 8 & 1 \\ -6 & 8 & -22 & 0 & 2 \\ \end{pmatrix}\end{split}$

which has labels $$\{0, 2\}$$ thus we need to drop 0 in $$\mathcal{P}$$. The minimum ratio test: $$1/9<1/6$$ so pivot on 1st row:

$\begin{split}T_r = \begin{pmatrix} 9 & 3 & 1 & 0 & 1 \\ 0 & 99 & -6 & 9 & 3 \\ \end{pmatrix}\end{split}$

which has labels $$\{1, 2\}$$ thus we need to drop 2 in $$\mathcal{Q}$$. The minimum ratio test: there is only 1 positive ratio so we pivot on 1st row.

$\begin{split}T_c = \begin{pmatrix} 1 & 0 & 5 & 8 & 1 \\ -8 & 40 & 0 & 176 & 32 \\ \end{pmatrix}\end{split}$

which has labels $$\{0, 3\}$$ thus we have a Nash equilibria.

Recall that the variable for $$T_r$$ in order are:

$x_1, x_2, s_1, s_2$

Recall that the variable for $$T_r$$ in order are:

$s_1, s_2, y_1, y_2$

Thus, $$5y_1=1$$ and $$9x_1=1$$ which gives:

$x = (1/9, 0)\qquad y=(1/5, 0)$

after normalising we get the required result:

$\sigma_r = (1, 0)\qquad \sigma_c=(1, 0)$