Lemke-Howson Algorithm (LHA) function computes a sample mixed strategy Nash equilibrium in a bimatrix game. This function implements the Lemke-Howson complementary pivoting algorithm for solving Bimatrix Games, a variant of the Lemke algorithm for linear complementarity problems (LCPs). The LHA not only provides an elementary proof for the existence of equilibrium points, but also an efficient computational method for finding at least one equilibrium point. The LHA follows a path (called LH path) of vertex pairs (x, y) of P × Q, for the polytopes P and Q,

P = {x ∈ R^{M}| x ≥ 0, B^{⊤}x ≤ 1},

Q = {y ∈ R^{N} |Ay ≤ 1, y ≥ 0}

that starts at (0, 0) and ends at a Nash equilibrium. An LH path alternately follows edges of P and Q, keeping the vertex in the other polytope fixed. Because the game is nondegenerate, a vertex of P is given by m labels, and a vertex of Q is given by n labels. An edge of P is defined by m−1 labels.

For example, in the above figure, the edge defined by labels 1 and 3 joins the vertices 0 and c. Dropping a label l of a vertex x of P, say, means traversing the unique edge that has all the labels of x except for l. For example, dropping label 2 of the vertex 0 of P in the figure gives the edge, defined by labels 1 and 3, that joins 0 to vertex c. The endpoint of the edge has a new label, which is said to be picked up, for example, label 5 is picked up at vertex c.

The LHA starts from (0, 0) in P × Q. This is called the artificial equilibrium, which is a completely labeled vertex pair because every pure strategy has probability zero. It does not represent a Nash equilibrium of the game because the zero vector cannot be rescaled to a mixed strategy vector. An initial free choice of the LHA is a pure strategy k of a player (any label in M ∪ N ), called the missing label. Starting with (x, y) = (0, 0), label k is dropped. At the endpoint of the corresponding edge (of P if k ∈ M, of Q if k ∈ N), the new label that is picked up is duplicate because it was present in the other polytope. That duplicate label is then dropped in the other polytope, picking up a new label. If the newly picked label is the missing label, the algorithm terminates and has found a Nash equilibrium. Otherwise, the algorithm repeats by dropping the duplicate label in the other polytope, and continues in this fashion.

Input: Nondegenerate bimatrix game.

Output: One Nash equilibrium of the game.

Method: Choose k ∈ M ∪ N , called the missing label. Let (x, y) = (0, 0) ∈ P × Q. Drop label k (from x in P if k ∈ M, from y in Q if k ∈ N).

Loop: Call the new vertex pair (x, y). Let l be the label that is picked up. If l = k, terminate with Nash equilibrium (x, y) (rescaled as mixed strategy pair). Otherwise, drop l in the other polytope and repeat.

The LHA terminates, and finds a Nash equilibrium, because P × Q has only finitely many vertex pairs. The next vertex pair on the path is always unique. Hence, a given vertex pair cannot be revisited because that would provide an additional possibility to proceed in the first place.

What we seem to have done is describe the LH path for missing label k by means of alternating edges between two polytopes. In fact, it is a path on the product polytope P × Q, given by the set of pairs (x, y) of P × Q that are k-almost completely labeled, meaning that every label in M ∪ N − {k} appears as a label of either x or y. In the above figure for k = 2, the vertex pairs on the path are (0, 0), (c, 0), (c, p), (d, p), (d, q).

For a fixed missing label k, the k-almost completely labeled vertices and edges of the product polytope P × Q form a graph of degree 1 or 2. Clearly, such a graph consists of disjoints paths and cycles. The endpoints of the paths are completely labeled. They are the Nash equilibria of the game and the artificial equilibrium (0, 0).

Though, there is a corollary to the this, in that, a nondegenerate bimatrix game has an odd number of Nash equilibria. The LHA can start at any Nash equilibrium, not just the artificial equilibrium. In the figure with missing label 2, starting the algorithm at the Nash equilibrium (d, q) would just generate the known LH path backward to (0, 0). When started at the Nash equilibrium (a, s), the LH path for the missing label 2 gives the vertex pair (b, s), where label 5 is duplicate, and then the equilibrium (b, r). This path cannot go back to (0, 0) because the path leading to (0, 0) starts at (d, q). This gives the three Nash equilibria of the game as endpoints of the two LH paths for missing label 2. These three equilibria can also be found by the LHA by varying the missing label.

However, some Nash equilibria can remain elusive to the LHA. An example is the following symmetric 3 × 3 game with

A = B^{⊤} =

Every Nash equilibrium (x, y) of this game is symmetric, i.e., x = y, where x^{⊤} is (0, 0, 1), (1/2, 1/4, 1/4), or (3/4, 1/4, 0). Only the first of these is found by the LHA, for any missing label; because the game is symmetric, it suffices to consider the missing labels 1, 2, 3. (A symmetric game remains unchanged when the players are exchanged; a symmetric game has always a symmetric equilibrium, but may also have nonsymmetric equilibria, which obviously come in pairs.)

[…] Lemke-Howson Algorithm follows the edges of a polyhedron, which is implemented algebraically by pivoting as used by the […]