Lemke–Howson algorithm

Template:Short description 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.Template:R It is said to be "the best known among the combinatorial algorithms for finding a Nash equilibrium",Template:R although more recently the Porter-Nudelman-Shoham algorithmTemplate:R has outperformed on a number of benchmarks.Template:R

Description

Template:Unreferenced section The input to the algorithm is a 2-player game Template:Math. Here, Template:Math is represented by two Template:Math game matrices Template:Math and Template:Math, containing the payoffs for players 1 and 2 respectively, who have Template:Math and Template:Math pure strategies respectively. In the following, one assumes that all payoffs are positive. (By rescaling, any game can be transformed into a strategically equivalent game with positive payoffs.)

Template:Math has two corresponding polytopes (called the best-response polytopes) Template:Math and Template:Math, in Template:Math dimensions and Template:Math dimensions respectively, defined as follows:

• Template:Math is in Template:Math; let Template:Math denote the coordinates. Template:Math is defined by Template:Math inequalities Template:Math, for all Template:Math, and a further Template:Math inequalities $$B_{1,j}{x}_1+\dots +B_{m,j}{x}_m\le 1,$$ for all Template:Math.
• Template:Math is in Template:Math; let Template:Math denote the coordinates. Template:Math is defined by Template:Math inequalities Template:Math, for all Template:Math, and a further Template:Math inequalities $$A_{i,1}{x}_{m+1}+\dots +A_{i,n}{x}_{m+n}\le 1,$$ for all Template:Math.

Here, Template:Math represents the set of unnormalized probability distributions over player 1's Template:Math pure strategies, such that player 2's expected payoff is at most 1. The first Template:Math constraints require the probabilities to be non-negative, and the other Template:Math constraints require each of the Template:Math pure strategies of player 2 to have an expected payoff of at most 1. Template:Math has a similar meaning, reversing the roles of the players.

Each vertex Template:Math of Template:Math is associated with a set of labels from the set Template:Math as follows. For Template:Math vertex Template:Math gets the label Template:Math if Template:Math at vertex Template:Math. For Template:Math, vertex Template:Math gets the label Template:Math if $$B_{1,j}{x}_1+\dots +B_{m,j}{x}_m=1.$$ Assuming that Template:Math is nondegenerate, each vertex is incident to Template:Math facets of Template:Math and has Template:Math labels. Note that the origin, which is a vertex of Template:Math, has the labels Template:Math.

Each vertex Template:Math of Template:Math is associated with a set of labels from the set Template:Math as follows. For Template:Math, vertex Template:Math gets the label Template:Math if Template:Math at vertex Template:Math. For Template:Math, vertex Template:Math gets the label Template:Math if $$A_{i,1}{x}_{m+1}+\dots +A_{i,n}{x}_{m+n}=1.$$ Assuming that Template:Math is nondegenerate, each vertex is incident to Template:Math facets of Template:Math and has Template:Math labels. Note that the origin, which is a vertex of Template:Math, has the labels Template:Math.

Consider pairs of vertices Template:Math, Template:Math, Template:Math. The pairs of vertices Template:Math is said to be completely labeled if the sets associated with Template:Math and Template:Math contain all labels Template:Math. Note that if Template:Math and Template:Math are the origins of Template:Math and Template:Math respectively, then Template:Math is completely labeled. The pairs of vertices Template:Math is said to be almost completely labeled (with respect to some missing label Template:Math) if the sets associated with Template:Math and Template:Math contain all labels in Template:Math other than Template:Math. Note that in this case, there will be a duplicate label that is associated with both Template:Math and Template:Math.

A pivot operation consists of taking some pair Template:Math and replacing Template:Math with some vertex adjacent to Template:Math in Template:Math, or alternatively replacing Template:Math with some vertex adjacent to Template:Math in Template:Math. This has the effect (in the case that Template:Math is replaced) of replacing some label of Template:Math with some other label. The replaced label is said to be dropped. Given any label of Template:Math, it is possible to drop that label by moving to a vertex adjacent to Template:Math that does not contain the hyperplane associated with that label.

The algorithm starts at the completely labeled pair Template:Math consisting of the pair of origins. An arbitrary label Template:Math is dropped via a pivot operation, taking us to an almost completely labeled pair Template:Math. Any almost completely labeled pair admits two pivot operations corresponding to dropping one or other copy of its duplicated label, and each of these operations may result in another almost completely labeled pair, or a completely labeled pair. Eventually, the algorithm finds a completely labeled pair Template:Math, which is not the origin. Template:Math corresponds to a pair of unnormalised probability distributions in which every strategy Template:Math of player 1 either pays that player 1, or pays less than 1 and is played with probability 0 by that player (and a similar observation holds for player 2). Normalizing these values to probability distributions, one has a Nash equilibrium (whose payoffs to the players are the inverses of the normalization factors).

Properties

The algorithm can find at most Template:Math different Nash equilibria. Any choice of initially-dropped label determines the equilibrium that is eventually found by the algorithm.

The Lemke–Howson algorithm is equivalent to the following homotopy-based approach. Modify Template:Math by selecting an arbitrary pure strategy Template:Math, and giving the player who owns that strategy, a large payment Template:Math to play it. In the modified game, the strategy Template:Math is played with probability 1, and the other player will play his best response to Template:Math with probability 1. Consider the continuum of games in which Template:Math is continuously reduced to 0. There exists a path of Nash equilibria connecting the unique equilibrium of the modified game, to an equilibrium of Template:Math. The pure strategy Template:Math chosen to receive the bonus Template:Math corresponds to the initially dropped label.Template:R 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.Template:R 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.Template:R