*** Welcome to piglix ***

Lemke–Howson algorithm


The Lemke–Howson algorithm is an algorithm that computes a Nash equilibrium of a bimatrix game, named after its inventors, Carlton E. Lemke and J. T. Howson. It is said to be “the best known among the combinatorial algorithms for finding a Nash equilibrium”.

The input to the algorithm is a 2-player game G. 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. In the following we assume that all payoffs are positive. (By rescaling, any game can be transformed to a strategically equivalent game with positive payoffs.)

G has two corresponding polytopes (called the best-response polytopes) P1 and P2, in m dimensions and n dimensions respectively, defined as follows.

P1 is in Rm; let {x1,...,xm} denote the coordinates. P1 is defined by m inequalities xi ≥ 0, for all i ∈ {1,...,m}, and a further n inequalities B1,jx1+...+Bm,jxm ≤ 1, for all j ∈ {1,...,n}.

P2 is in Rn; let {xm+1,...,xm+n} denote the coordinates. P2 is defined by n inequalities xm+i ≥ 0, for all i ∈ {1,...,n}, and a further m inequalities Ai,1xm+1+...+Ai,nxm+n ≤ 1, for all i ∈ {1,...,m}.

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. The first m constraints require the probabilities to be non-negative, and the other n constraints require each of the n pure strategies of player 2 to have an expected payoff of at most 1. P2 has a similar meaning, reversing the roles of the players.

Each vertex v of P1 is associated with a set of labels from the set {1,...,m + n} as follows. For i ∈ {1, ..., m}, vertex v gets the label i if xi = 0 at vertex v. For j ∈ {1, ..., n}, vertex v gets the label m + j if B1,jx1 + ... + Bm,jxm = 1. Assuming that P1 is nondegenerate, each vertex is incident to m facets of P1 and has m labels. Note that the origin, which is a vertex of P1, has the labels {1, ..., m}.


...
Wikipedia

...