Finding all equilibria reachable by Lemke-Howson

by Virag Varga for The Gambit Project

For a two-player in strategic form (also called bimatrix games), what are the Nash equilibria that can be found using the Lemke-Howson method? Each pure strategy as an “initially dropped label” leads to an equilibrium along a computational path obtained by “pivoting” in a linear system. If two equilibria found in that way are different, using the second label on the first equilibrium (and vice versa) will find yet another equilibrium. The set of all equilibria reachable in that way should be recorded and is a (normally) fast way to find many equilibria when the game is large.