LcpSolve

This algorithm formulates and solves the game as a linear complementarity problem. For a normal form game, this algorithm searches for equilibria of the specified normal form game using the Lemke-Howson algorithm, as described in [LemHow64]. Eaves [Eav71] lexicographic rule for linear complementarity problems is used to avoid cycling.

In the Lemke-Howson algorithm equilibria are found by following paths of "almost" equilibria, where one relaxes at most one constaint. Equilibria are thus inter-connected by networks of paths that result when different of the constraints are relaxed. One can find the set of "accessible" equilibria in such methods by starting at the extraneous solution and then tracing out this entire network. See, e. g., Shapley [Sha74]. However, the set of accessible equilibria does not necessarily include all Nash equilibria.

For extensive form games, this algorithm implements Lemke's algorithm on the sequence form of the game, as defined by Koller, Megiddo and von Stengel, in [KolMegSte94].

Important

This algorithm is fast, but only works for two person games. Wilson [Wil71] and Rosenmuller [Ros71] have suggested ways in which the Lemke-Howson Algorithm can be extended to general $n$-player games, but these extensions require methods of tracing the solution to a set of non linear simultaneous equations, and have not been implemented in Gambit. Also, on some problems with data type of Double, the current implementation can exhibit numerical instability which in extreme cases can even lead to incorrect solutions. Solving the same problem with Rationals will resolve any such difficulties. However, the algorithm is much slower when operating on Rationals than on Doubles.