The Lemke Howson Algorithm

The Lemke Howson algorithm implemented in Nashpy is based on the one described in [Nisan2007] originally introduced in [Lemke1964].

The algorithm is as follows:

For a nondegenerate 2 player game \((A, B)\in{\mathbb{R}^{m\times n}}^2\) the following algorithm returns a single Nash equilibria:

  1. Obtain the best response Polytopes \(P\) and \(Q\).

  2. Choose a starting label to drop, this will correspond to a vertex of \(P\) or \(Q\).

  3. In that polytope, remove the label from the corresponding vertex and move to the vertex that shared that label. A new label will be picked up and duplicated in the other polytope.

  4. In the other polytope drop the duplicate label and move to the vertex that shared that label.

Repeat steps 3 and 4 until there are no duplicate labels.

Discussion

This algorithm is implemented using integer pivoting.

  1. Step 1, the best response polytopes \(P\) and \(Q\) are represented by a tableau. For example for:

    \[\begin{split}A = \begin{pmatrix} 3 & 1\\ 1 & 3 \end{pmatrix}\end{split}\]
    \[\begin{split}B = \begin{pmatrix} 1 & 3\\ 2 & 1 \end{pmatrix}\end{split}\]

    This is represented as a pair of tableau:

    \[\begin{split}T_c = \begin{pmatrix} 3 & 1 & 1 & 0 & 1\\ 1 & 3 & 0 & 1 & 1 \end{pmatrix}\end{split}\]

    For reasons that will become clear, we infact shift this tableau so that the labelling is coherent across both polytopes:

    \[\begin{split}T_c = \begin{pmatrix} 1 & 0 & 3 & 1 & 1\\ 0 & 1 & 1 & 3 & 1 \end{pmatrix}\end{split}\]

    Here it is as a numpy array:

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

    Here is the tableau that corresponds to \(B\):

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

    Here it is as a numpy array:

    >>> row_tableau = np.array([[1, 2, 1, 0, 1],
    ...                         [3, 1, 0, 1, 1]])
    
  2. Step 2, choosing a starting label is choosing an integer from \(0 \leq k < m + n\) (we start our indices at 0). As an example, let us choose the label \(1\).

    First we need to identify which vertex has that label. The labels of a tableau correspond to the non basic variables: these are the columns with more than a single non zero variable:

    • The labels of \(T_c\) are thus \(\{2, 3\}\):

      >>> import nashpy as nash
      >>> nash.integer_pivoting.non_basic_variables(col_tableau)
      {2, 3}
      
    • The labels of \(T_r\) are thus \(\{0, 1\}\):

      >>> nash.integer_pivoting.non_basic_variables(row_tableau)
      {0, 1}
      

    So we are going to drop label \(1\) from \(T_r\).

  3. Step 3, removing a label and moving from one vertex to another corresponds to integer pivoting [Dantzig2016]. This is a manipulation of \(T\), dropping label \(1\) corresponds to pivoting the second column.

    To do this we need to identify which row will not change (the “pivot row”), this is done by finding the smallest ratio of value in that column over the value in the last column: \((T_{r})_{i4}/(T_{r})_{ik}\).

    In our case the first row has corresponding ratio: \(1/2\) and the second ratio \(1/1\). So our pivot row is the first row:

    >>> nash.integer_pivoting.find_pivot_row(row_tableau, column_index=1)
    0
    

    What we now do is row operations so as to make the second column correspond to a basic variable. We will do this by multiplying the second row by 2 and then subtracting the first row by it:

    \[\begin{split}T_r = \begin{pmatrix} 1 & 2 & 1 & 0 & 1\\ 5 & 0 & -1 & 2 & 1 \end{pmatrix}\end{split}\]

    Our resulting tableau has labels: \(\{0, 2\}\) so it has “picked up” label \(2\):

    >>> nash.integer_pivoting.pivot_tableau(row_tableau, column_index=1)
    {2}
    >>> row_tableau
    array([[ 1,  2,  1,  0,  1],
           [ 5,  0, -1,  2,  1]])
    
  4. Step 4, we will now repeat the previous manipulation on \(T_c\) where we now need to drop the duplicate label \(2\). We do this by pivoting the third column.

    The ratios are: \(1/3\) for the first row and \(1/1\) for the second, thus the pivot row is the first row:

    >>> nash.integer_pivoting.find_pivot_row(col_tableau, column_index=2)
    0
    

    Using similar row operations we obtain:

    \[\begin{split}T_c = \begin{pmatrix} 1 & 0 & 3 & 1 & 1\\ -1 & 3 & 0 & 8 & 2 \end{pmatrix}\end{split}\]

    Our resulting tableau has labels: \(\{0, 3\}\), so it has picked up label \(0\):

    >>> nash.integer_pivoting.pivot_tableau(col_tableau, column_index=2)
    {0}
    >>> col_tableau
    array([[ 1,  0,  3,  1,  1],
           [-1,  3,  0,  8,  2]])
    

    We now need to drop \(0\) from \(T_r\), we do this by pivoting the first column. The ratio test: \(1/1 > 1/5\) implies that the second row is the pivot row. Using similar algebraic manipulations we obtain:

    \[\begin{split}T_r = \begin{pmatrix} 0 & 10 & 6 & -2 & 4\\ 5 & 0 & -1 & 2 & 1 \end{pmatrix}\end{split}\]

    Our resulting tableau has labels: \(\{2, 3\}\), so it has picked up label \(3\):

    >>> nash.integer_pivoting.pivot_tableau(row_tableau, column_index=0)
    {3}
    >>> row_tableau
    array([[ 0, 10,  6, -2,  4],
           [ 5,  0, -1,  2,  1]])
    

    We now need to drop \(3\) from \(T_c\), we do this by pivoting the fourth column. The ratio test: \(1/1>2/8\) indicates that we pivot on the second row which gives:

    \[\begin{split}T_c = \begin{pmatrix} 9 & -1& 24 & 0 & 6\\ -1 & 3& 0 & 8 & 2 \end{pmatrix}\end{split}\]

    Our resulting tableau has labels: \(\{0, 1\}\):

    >>> nash.integer_pivoting.pivot_tableau(col_tableau, column_index=3)
    {1}
    >>> col_tableau
    array([[ 9, -3, 24,  0,  6],
           [-1,  3,  0,  8,  2]])
    

    The union of the labels of \(T_r\) and \(T_c\) is: \(\{0, 1, 2, 3\}\) which implies that we have a fully labeled vertx pair.

    The vertex corresponding to \(T_r\) are obtained by setting the non basic variables to 0 and looking at the corresponding values of the first two columns:

    \[v_r = (1/5, 4/10) = (1/5, 2/5)\]

    The vertex corresponding to \(T_c\) are obtained from the last 2 columns:

    \[v_c = (6/24, 2/8) = (1/4, 1/4)\]

The final step of the algorithm is to return the normalised probabilities that correspond to these vertices:

\[((1/3, 2/3), (1/2, 1/2))\]