Lemke–Howson algorithm

The Lemke–Howson algorithmis an algorithm that computes aNash 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 Lemke–Howson algorithmis an algorithm that computes aNash 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, containingthe 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, anygame 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 inequalitiesB1,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 inequalitiesAi,1xm+1+...+Ai,nxm+n ≤ 1,for all i ∈ {1,...,m}. P1 represents the set of unnormalized probability distributions over player 1’sm pure strategies, such that player 2’s expectedpayoff is at most 1. The first m constraints require the probabilities to benon-negative, and the other n constraints require each of the n pure strategies ofplayer 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 mfacets of P1 and has m labels.Note that the origin, which is a vertex of P1, has the labels {1, ..., m}. Each vertex w of P2 is associated with a set of labels from the set{1, ..., m + n} as follows.For j ∈ {1, ..., n}, vertex w gets the label m + j if xm+j = 0 at vertex w.For i ∈ {1, ..., m}, vertex w gets the label i ifAi,1xm+1 + ... + Ai,nxm+n = 1.Assuming that P2 is nondegenerate, each vertex is incident to nfacets of P2 and has n labels.Note that the origin, which is a vertex of P2, has the labels {m + 1, ..., m + n}. Consider pairs of vertices (v,w), v ∈ P1, w ∈ P2.We say that (v,w) is completely labeled if the sets associated with v and wcontain all labels {1, ..., m + n}. Note that if v and w are the origins of Rm and Rnrespectively, then (v,w) is completely labeled.We say that (v,w) is almost completely labeled (with respect to some missing label g)if the sets associated with v and wcontain all labels in {1, ..., m + n} other than g.Note that in this case, there will be a duplicate label that is associated with bothv and w.