# 06 Lemke Howson Algorithm¶

## Objectives¶

• Describe the Lemke Howson algorithm graphically
• Describe integer pivoting

Duration: 50 minutes

## Notes¶

### Describe the Lemke Howson algorithm¶

Using the polytopes for the matching pennies game:

$$\mathcal{P}$$:

$$\mathcal{Q}$$:

illustrate the Lemke Howson algorithm:

• $$((0, 0), (0, 0))$$ have labels $$\{0, 1\}, \{2, 3\}$$. Drop $$0$$ in $$\mathcal{P}$$.
• $$\to ((1/2, 0), (0, 0))$$ have labels $$\{1, 2\}, \{2, 3\}$$. Drop $$2$$ in $$\mathcal{Q}$$.
• $$\to ((1/2, 0), (1/3, 0))$$ have labels $$\{1, 2\}, \{0, 3\}$$. Have an equilibria.

Try varying other initial labels. Is it possible to arrive at the mixed nash equilibrium?

### Work through integer pivoting¶

Consider Rock Paper Scissors:

$\begin{split}A = \begin{pmatrix} 0 & -1 & 1\\ 1 & 0 & -1\\ -1 & 1 & 0\\ \end{pmatrix}\qquad B = \begin{pmatrix} 0 & 1 & -1\\ -1 & 0 & 1\\ 1 & -1 & 0\\ \end{pmatrix}\qquad\end{split}$

We see that drawing this would be a pain. Let us build the tableaux, but let us first scale our payoffs so that all variables are positive (let us add 2 to all the utilities):

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

This gives the following tableaux:

$\begin{split}T_r = \begin{pmatrix} 2 & 1 & 3 & 1 & 0 & 0 & 1\\ 3 & 2 & 1 & 0 & 1 & 0 & 1\\ 1 & 3 & 2 & 0 & 0 & 1 & 1\\ \end{pmatrix}\end{split}$

Following along in numpy:

>>> import numpy as np
>>> row_tableau = np.array([[2, 1, 3, 1, 0, 0, 1],
...                         [3, 2, 1, 0, 1, 0, 1],
...                         [1, 3, 2, 0, 0, 1, 1]])


and:

$\begin{split}T_c = \begin{pmatrix} 1 & 0 & 0 & 2 & 1 & 3 & 1\\ 0 & 1 & 0 & 3 & 2 & 1 & 1\\ 0 & 0 & 1 & 1 & 3 & 2 & 1\\ \end{pmatrix}\end{split}$

Following along in numpy:

>>> col_tableau = np.array([[1, 0, 0, 2, 1, 3, 1],
...                         [0, 1, 0, 3, 2, 1, 1],
...                         [0, 0, 1, 1, 3, 2, 1]])


The labels of $$T_r$$ are $$\{0, 1, 2\}$$ and the labels of $$T_c$$ are $$\{3, 4, 5\}$$.

Let us drop label $$0$$, so we pivot the first column of $$T_r$$. The minimum ratio test gives: $$1/3<1/2<1/1$$ so we pivot on the second row giving:

$\begin{split}T_r = \begin{pmatrix} 0 & -1 & 7 & 3 & -2 & 0 & 1\\ 3 & 2 & 1 & 0 & 1 & 0 & 1\\ 0 & 7 & 5 & 0 & -1 & 3 & 2\\ \end{pmatrix}\end{split}$

Code:

>>> import nashpy as nash
>>> dropped_label = nash.integer_pivoting.pivot_tableau(row_tableau,
...                                                     column_index=0)
>>> row_tableau
array([[ 0, -1,  7,  3, -2,  0,  1],
[ 3,  2,  1,  0,  1,  0,  1],
[ 0,  7,  5,  0, -1,  3,  2]])


This has labels $$\{1, 2, 4\}$$ so we need to drop label $$4$$ by pivoting the fifth column of $$T_c$$. The minimum ratio test implies that we pivot on the third row.

$\begin{split}T_c = \begin{pmatrix} 3 & 0 & -1 & 5 & 0 & 7 & 2\\ 0 & 3 & -2 & 7 & 0 & -1 & 1\\ 0 & 0 & 1 & 1 & 3 & 2 & 1\\ \end{pmatrix}\end{split}$

Code:

>>> dropped_label = nash.integer_pivoting.pivot_tableau(col_tableau,
...                                                     column_index=4)
>>> col_tableau
array([[ 3,  0, -1,  5,  0,  7,  2],
[ 0,  3, -2,  7,  0, -1,  1],
[ 0,  0,  1,  1,  3,  2,  1]])


This has labels $$\{2, 3, 5\}$$ so we need to drop $$2$$ by pivoting the third row of $$T_r$$. The minimum ratio test implies that we pivot on the first row:

$\begin{split}T_r = \begin{pmatrix} 0 & -1 & 7 & 3 & -2 & 0 & 1\\ 21 & 15 & 0 & -3 & 9 & 0 & 6\\ 0 & 54 & 0 & -15 & 3 & 21 & 9\\ \end{pmatrix}\end{split}$

Code:

>>> dropped_label = nash.integer_pivoting.pivot_tableau(row_tableau,
...                                                     column_index=2)
>>> row_tableau
array([[  0,  -1,   7,   3,  -2,   0,   1],
[ 21,  15,   0,  -3,   9,   0,   6],
[  0,  54,   0, -15,   3,  21,   9]])


This has labels $$\{1, 3, 4\}$$ so we need to drop $$3$$ by pivoting the fourth column of $$T_c$$. The minimum ratio test implies that we pivot on the second row:

$\begin{split}T_c = \begin{pmatrix} 21 & -15 & 3 & 0 & 0 & 54 & 9\\ 0 & 3 & -2 & 7 & 0 & -1 & 1\\ 0 & -3 & 9 & 0 & 21 & 15 & 6\\ \end{pmatrix}\end{split}$

Code:

>>> dropped_label = nash.integer_pivoting.pivot_tableau(col_tableau,
...                                                     column_index=3)
>>> col_tableau
array([[ 21, -15,   3,   0,   0,  54,   9],
[  0,   3,  -2,   7,   0,  -1,   1],
[  0,  -3,   9,   0,  21,  15,   6]])


This has labels $$\{1, 2, 5\}$$ so we need to drop $$1$$ by pivoting the second column of $$T_r$$. The minimum ratio test implies that we pivot on the third row:

$\begin{split}T_r = \begin{pmatrix} 0 & 0 & 378 & 147 & -105 & 21 & 63\\ 1134 & 0 & 0 & 63 & 441 & -315 & 189\\ 0 & 54 & 0 & -15 & 3 & 21 & 9\\ \end{pmatrix}\end{split}$

Code:

>>> dropped_label = nash.integer_pivoting.pivot_tableau(row_tableau,
...                                                     column_index=1)
>>> row_tableau
array([[   0,    0,  378,  147, -105,   21,   63],
[1134,    0,    0,   63,  441, -315,  189],
[   0,   54,    0,  -15,    3,   21,    9]])


This has labels $$\{3, 4, 5\}$$ so we need to drop $$5$$ by pivoting the sixth column of $$T_c$$. The minimum ratio test implies that we pivot on the first row:

$\begin{split}T_c = \begin{pmatrix} 21 & -15 & 3 & 0 & 0 & 54 & 9\\ 21 & 147 & -105 & 378 & 0 & 0 & 63\\ -315 & 63 & 441 & 0 & 1134 & 0 & 189\\ \end{pmatrix}\end{split}$

Code:

>>> dropped_label = nash.integer_pivoting.pivot_tableau(col_tableau,
...                                                     column_index=5)
>>> col_tableau
array([[  21,  -15,    3,    0,    0,   54,    9],
[  21,  147, -105,  378,    0,    0,   63],
[-315,   63,  441,    0, 1134,    0,  189]])


This has labels $$\{0, 1, 2\}$$ so we have a Nash equilibrium with vertices:

$\left((189/1134, 9/54, 63/378), (63/378, 189/1134, 9/54)\right) = \left((1/6, 1/6, 1/6), (1/6, 1/6, 1/6)\right)$

Which in turn corresponds to the expected equilibrium:

$\left((1/3, 1/3, 1/3, (1/3, 1/3, 1/3)\right)$
• Mention how different pivoting methods are fine, doing it this way ensures everything is an integer which is also more efficient for a computer.