 Lemke–Howson algorithm

The Lemke-Howson algorithm follows an almost completely labeled path in the product of two best-response polytopes of a bimatrix game. Drop one label at the artificial zero pair, then alternately pivot away the duplicated label until the dropped label returns. A nonzero completely labeled endpoint, after normalization, gives a Nash equilibrium. The two players' vectors must be kept separate even in a symmetric game.

The Lemke–Howson algorithm is a mathematical method used for finding Nash equilibria in two-player games that can be expressed in a strategic form. It is particularly useful for games that have an odd number of pure strategy Nash equilibria, as this condition guarantees that at least one mixed strategy Nash equilibrium exists. Here are some key points about the Lemke–Howson algorithm: 1. **Background**: The algorithm was developed by Eugene Lemke and J. R.