05 Lemke Howson Algorithm

Corresponding chapters

• The Lemke Howson algorithm

Objectives

• Describe the Lemke Howson algorithm graphically
• Describe integer pivoting

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}\]

We first need to scale the tableaux so that all variables are positive:

\[\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 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.