Jump to content

Lemke–Howson algorithm

From Wikipedia, the free encyclopedia

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.[1] It is said to be "the best known among the combinatorial algorithms for finding a Nash equilibrium",[2] although more recently the Porter-Nudelman-Shoham algorithm[3] has outperformed on a number of benchmarks.[4][5]

Description

[edit]

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. 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.)

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 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 for all i ∈ {1,...,m}.

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. 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 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}.

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 if Assuming that P2 is nondegenerate, each vertex is incident to n facets 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. The pairs of vertices (v,w) is said to be completely labeled if the sets associated with v and w contain all labels {1, ..., m + n}. Note that if v and w are the origins of Rm and Rn respectively, then (v,w) is completely labeled. The pairs of vertices (v,w) is said to be almost completely labeled (with respect to some missing label g) if the sets associated with v and w contain all labels in {1, ..., m + n} other than g. Note that in this case, there will be a duplicate label that is associated with both v and w.

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

The algorithm starts at the completely labeled pair (v,w) consisting of the pair of origins. An arbitrary label g is dropped via a pivot operation, taking us to an almost completely labeled pair (v,w). 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 (v*,w*), which is not the origin. (v*,w*) corresponds to a pair of unnormalised probability distributions in which every strategy i 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

[edit]

The algorithm can find at most n + m 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 G by selecting an arbitrary pure strategy g, and giving the player who owns that strategy, a large payment B to play it. In the modified game, the strategy g is played with probability 1, and the other player will play his best response to g with probability 1. Consider the continuum of games in which B is continuously reduced to 0. 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.[8]

References

[edit]
  1. ^ Lemke, C. E.; Howson, J. T. (1964). "Equilibrium points of bimatrix games". SIAM Journal on Applied Mathematics. 12 (2): 413–423. doi:10.1137/0112033.
  2. ^ Papadimitriou, Christos H. (2007). "The Complexity of Finding Nash Equilibria". Algorithmic Game Theory. pp. 29–52. doi:10.1017/CBO9780511800481.004. ISBN 978-0-521-87282-9.
  3. ^ Porter, Ryan; Nudelman, Eugene; Shoham, Yoav (1 July 2008). "Simple search methods for finding a Nash equilibrium". Games and Economic Behavior. 63 (2): 642–662. doi:10.1016/j.geb.2006.03.015.
  4. ^ Sandholm, Thomas; Gilpin, Andrew; Conitzer, Vincent (9 July 2005). "Mixed-integer programming methods for finding Nash equilibria" (PDF). Proceedings of the 20th National Conference on Artificial Intelligence. Vol. 2. pp. 495–501. ISBN 978-1-57735-236-5.
  5. ^ Ceppi, Sofia; Gatti, Nicola; Basilico, Nicola (September 2009). "Computing Bayes-Nash Equilibria through Support Enumeration Methods in Bayesian Two-Player Strategic-Form Games". 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology. Vol. 2. pp. 541–548. doi:10.1109/WI-IAT.2009.209. ISBN 978-0-7695-3801-3. S2CID 656183.
  6. ^ Herings, P. J-J.; Peeters, R. (2010). "Homotopy methods to compute equilibria in game theory". Economic Theory. 42 (1): 119–156. doi:10.1007/s00199-009-0441-5.
  7. ^ Savani, R.; von Stengel, B. (2006). "Hard-to-Solve Bimatrix Games". Econometrica. 74 (2): 397–429. CiteSeerX 10.1.1.63.1548. doi:10.1111/j.1468-0262.2006.00667.x.
  8. ^ Goldberg, P. W.; Papadimitriou, C. H.; Savani, R. (2011). The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke–Howson Solutions. Proc. 52nd FOCS. pp. 67–76. arXiv:1006.5352. doi:10.1109/FOCS.2011.26.