Lemke-Howson Algorithm

The Lemke-Howson algorithm computes a Nash equilibrium of a two-player game given in matrix form. It was created by Carlton E. Lemke and J. T. Howson in 1964 and works by tracing a path across two geometric structures called best-response polytopes, one for each player, in search of a pair of vertices that are completely labeled, which corresponds to an equilibrium of the game. It is described as the best known combinatorial algorithm for finding a single Nash equilibrium, though newer methods have since offered competitive practical alternatives. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/