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.
Complementary pivoting follows adjacent bases while maintaining all but one label of a complementarity system. The Lemke-Howson algorithm for a bimatrix game follows the duplicated label between two tableaux until it restores the dropped label at a nonzero completely labelled pair. Normalization then gives a Nash equilibrium.
Articles by others on the same topic
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.