<jupyter_start><jupyter_text>The Lemke Howson algorithmThe vertex and support enumeration algorithms are all algorithms that use an exhaustive search. For large games, this can take a long time and/or have a high computational cost. The following algorithm gives an approach to create a path through vertices in both best response polytopes to find a pair that is fully labelled.--- The Lemke Howson algorithm[Video](https://youtu.be/HekHAuWR_30?list=PLnC5h3PY-znxMsG0TRYGOyrnEO-QhVwLb)For a nondegenerate 2 player game $(A, B)\in{\mathbb{R}^{m\times n}_{>0}}^2$ the following algorithm returns a nash equilibrium:1. Start at the artificial equilibrium: $(0, 0)$2. Choose a label to drop.3. Remove this label from the corresponding vertex by traversing an edge of the corresponding polytope to another vertex. 4. The new vertex will now have a duplicate label in the other polytope. Remove this label from the vertex of the other polytope and traverse an edge of that polytope to another vertex.5. Repeat step 4 until the pair of vertices is fully labelled.---As an example let us consider the matching pennies game:$$A = \begin{pmatrix}    1 & -1\\    -1&  1\end{pmatrix}\qquadB = \begin{pmatrix}    -1 & 1\\    1&  -1\end{pmatrix}$$First let us add 2 to all utilities:$$A = \begin{pmatrix}    3 & 1\\    1 &  3\end{pmatrix}\qquadB = \begin{pmatrix}    1 & 3\\    3 &  1\end{pmatrix}$$The vertices for $\mathcal{P}$ are:1. $a=(0, 0)$ has labels $\{0, 1\}$ 2. $b=(1/3, 0)$ has labels $\{1, 3\}$3. $c=(1/4, 1/4)$ has labels $\{2, 3\}$4. $d=(0, 1/3)$ has labels $\{0, 2\}$The vertics and labels for $\mathcal{Q}$ are:1. $w=(0, 0)$ has labels $\{2, 3\}$2. $x=(1/3, 0)$ has labels $\{0, 3\}$3. $y=(1/4, 1/4)$ has labels $\{0, 1\}$4. $z=(0, 1/3)$ has labels $\{1, 2\}$Let us apply the algorithm:- $(a, w)$ have labels: $\{0, 1\}, \{2, 3\}$. Drop 0 (arbitrary decision) in $\mathcal{P}$.- $\to (b, w)$ have labels: $\{1, 3\}, \{2, 3\}$. In $\mathcal{Q}$ drop 3.- $\to (b, z)$ have labels: $\{1, 3\}, \{1, 2\}$. In $\mathcal{P}$ drop 1.- $\to (c, z)$ have labels: $\{2, 3\}, \{1, 2\}$. In $\mathcal{Q}$ drop 2.- $\to (c, y)$ have labels: $\{2, 3\}, \{0, 1\}$. Fully labeled vertex pair.We now return the strategy pair by normalising these vertices:$$((1/2, 1/2), (1/2, 1/2))$$This is also implemented in `Nashpy`:<jupyter_code>import numpy as np
import nashpy as nash
A = np.array([[1, -1], [-1, 1]])
matching_pennies = nash.Game(A)
matching_pennies.lemke_howson(initial_dropped_label=0)<jupyter_output><empty_output><jupyter_text>You can also iterate over all possible starting labels:<jupyter_code>for eq in matching_pennies.lemke_howson_enumeration():
    print(eq)<jupyter_output>(array([0.5, 0.5]), array([0.5, 0.5]))
(array([0.5, 0.5]), array([0.5, 0.5]))
(array([0.5, 0.5]), array([0.5, 0.5]))
(array([0.5, 0.5]), array([0.5, 0.5]))