[4][5] The input to the algorithm is a 2-player game G. Here, G is represented by two m × n game matrices A and B, containing the payoffs for players 1 and 2 respectively, who have m and n pure strategies respectively.
G has two corresponding polytopes (called the best-response polytopes) P1 and P2, in m dimensions and n dimensions respectively, defined as follows: Here, P1 represents the set of unnormalized probability distributions over player 1's m pure strategies, such that player 2's expected payoff is at most 1.
P2 has a similar meaning, reversing the roles of the players.
Assuming that P1 is nondegenerate, each vertex is incident to m facets of P1 and has m labels.
Assuming that P2 is nondegenerate, each vertex is incident to n facets of P2 and has n labels.
Note that if v and w are the origins of Rm and Rn respectively, then (v,w) is completely labeled.
Eventually, the algorithm finds a completely labeled pair (v*,w*), which is not the origin.
Any choice of initially-dropped label determines the equilibrium that is eventually found by the algorithm.
There exists a path of Nash equilibria connecting the unique equilibrium of the modified game, to an equilibrium of G. The pure strategy g chosen to receive the bonus B corresponds to the initially dropped label.
[6] While the algorithm is efficient in practice, in the worst case the number of pivot operations may need to be exponential in the number of pure strategies in the game.
[7] Subsequently, it has been shown that it is PSPACE-complete to find any of the solutions that can be obtained with the Lemke–Howson algorithm.