[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/lemke-howson-algorithm-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki24\/lemke-howson-algorithm-wikipedia\/","headline":"Lemke\u2013Howson algorithm – Wikipedia","name":"Lemke\u2013Howson algorithm – Wikipedia","description":"before-content-x4 The Lemke\u2013Howson algorithm[1] is an algorithm that computes a Nash equilibrium of a bimatrix game, named after its inventors,","datePublished":"2016-10-27","dateModified":"2016-10-27","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":100,"height":100},"url":"https:\/\/wiki.edu.vn\/en\/wiki24\/lemke-howson-algorithm-wikipedia\/","wordCount":3137,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4The Lemke\u2013Howson algorithm[1] 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”,[2] although more recently the Porter-Nudelman-Shoham algorithm[3] has outperformed on a number of benchmarks.[4][5]Description[edit]       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4The input to the algorithm is a 2-player game G.G is represented by two m\u00a0\u00d7\u00a0n 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\u00a0\u2265\u00a00, for all i\u00a0\u2208\u00a0{1,…,m},and a further n inequalitiesB1,jx1+…+Bm,jxm\u00a0\u2264\u00a01,for all j\u00a0\u2208\u00a0{1,…,n}.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4P2 is in Rn; let {xm+1,…,xm+n} denote the coordinates.P2 is defined by n inequalities xm+i \u2265 0, for all i\u00a0\u2208\u00a0{1,…,n},and a further m inequalitiesAi,1xm+1+…+Ai,nxm+n\u00a0\u2264\u00a01,for all i\u00a0\u2208\u00a0{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\u00a0+\u00a0n} as follows.For i\u00a0\u2208\u00a0{1,\u00a0…,\u00a0m}, vertex v gets the label i if xi\u00a0=\u00a00 at vertex v.For j\u00a0\u2208\u00a0{1,\u00a0…,\u00a0n}, vertex v gets the label m\u00a0+\u00a0j if B1,jx1\u00a0+\u00a0…\u00a0+\u00a0Bm,jxm\u00a0=\u00a01.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,\u00a0…,\u00a0m}.Each vertex w of P2 is associated with a set of labels from the set{1,\u00a0…,\u00a0m\u00a0+\u00a0n} as follows.For j\u00a0\u2208\u00a0{1,\u00a0…,\u00a0n}, vertex w gets the label m\u00a0+\u00a0j if xm+j\u00a0=\u00a00 at vertex\u00a0w.For i\u00a0\u2208\u00a0{1,\u00a0…,\u00a0m}, vertex w gets the label i ifAi,1xm+1\u00a0+\u00a0…\u00a0+\u00a0Ai,nxm+n\u00a0=\u00a01.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\u00a0+\u00a01,\u00a0…,\u00a0m\u00a0+\u00a0n}.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Consider pairs of vertices (v,w), v\u00a0\u2208\u00a0P1, w\u00a0\u2208\u00a0P2.We say that (v,w) is completely labeled if the sets associated with v and wcontain all labels {1,\u00a0…,\u00a0m\u00a0+\u00a0n}. 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,\u00a0…,\u00a0m\u00a0+\u00a0n} other than g.Note that in this case, there will be a duplicate label that is associated with bothv and w.A pivot operation consists of taking some pair (v,w) and replacing v with somevertex adjacent to v in P1, or alternatively replacing w with somevertex adjacent to w in P2. This has the effect (in the case thatv 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 possibleto drop that label by moving to a vertex adjacent to v that does not contain thehyperplane associated with that label.The algorithm starts at the completely labeled pair (v,w) consisting of the pair oforigins. An arbitrary label g is dropped via a pivot operation, taking us toan almost completely labeled pair (v\u2032,w\u2032). Any almost completely labeled pairadmits two pivot operations corresponding to dropping one or other copy of itsduplicated label, and each of these operations may result in another almost completelylabeled pair, or a completely labeled pair. Eventually the algorithm finds acompletely labeled pair (v*,w*), which is not the origin.(v*,w*) corresponds to a pair of unnormalised probability distributionsin which every strategy i of player 1 either pays that player 1, or pays less than 1 and is playedwith probability 0 by that player (and a similar observation holds forplayer 2). Normalizing these values to probability distributions, we have a Nashequilibrium (whose payoffs to the players are the inverses of the normalizationfactors).Properties[edit]The algorithm can find at most n\u00a0+\u00a0m different Nash equilibria. Any choice ofinitially-dropped label determines the equilibrium that is eventually found bythe algorithm.The Lemke\u2013Howson algorithm is equivalent to the following homotopy-based approach.Modify G by selecting an arbitrary pure strategy g, and giving the player who ownsthat strategy, a large payment B to play it. In the modified game, that strategy gis played with probability 1, and the other player will play his best responseto g with probability 1. Consider the continuum of games in which B iscontinuously reduced to 0. There exists a path of Nash equilibria connectingthe unique equilibrium of the modified game, to an equilibrium of G.The pure strategy g chosen to receive the bonus B corresponds to theinitially dropped label.[6]While the algorithm is efficient in practice, in the worst case the numberof pivot operations may need to be exponential in the number of pure strategiesin the game.[7]Subsequently, it has been shown that it is PSPACE-complete to find any of the solutionsthat can be obtained with the Lemke\u2013Howson algorithm.[8]References[edit]^ C. E. Lemke and J. T. Howson (1964). “Equilibrium points of bimatrix games”. SIAM Journal on Applied Mathematics. 12 (2): 413\u2013423. doi:10.1137\/0112033.^ Papadimitriou, Christos H. (2007). “The Complexity of Finding Nash Equilibria”. Algorithmic Game Theory. pp.\u00a029\u201352. doi:10.1017\/CBO9780511800481.004. ISBN\u00a0978-0-521-87282-9.^ Porter, Ryan; Nudelman, Eugene; Shoham, Yoav (1 July 2008). “Simple search methods for finding a Nash equilibrium”. Games and Economic Behavior. 63 (2): 642\u2013662. doi:10.1016\/j.geb.2006.03.015.^ 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 – Volume 2. pp.\u00a0495\u2013501. ISBN\u00a0978-1-57735-236-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.\u00a02. pp.\u00a0541\u2013548. doi:10.1109\/WI-IAT.2009.209. ISBN\u00a0978-0-7695-3801-3. S2CID\u00a0656183.^ P. J-J. Herings and R. Peeters (2010). “Homotopy methods to compute equilibria in game theory”. Economic Theory. 42 (1): 119\u2013156. doi:10.1007\/s00199-009-0441-5.^ R. Savani and B. von Stengel (2006). “Hard-to-Solve Bimatrix Games”. Econometrica. 74 (2): 397\u2013429. CiteSeerX\u00a010.1.1.63.1548. doi:10.1111\/j.1468-0262.2006.00667.x.^ P.W. Goldberg, C.H. Papadimitriou and R. Savani (2011). The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke\u2013Howson Solutions. Proc. 52nd FOCS. pp.\u00a067\u201376. arXiv:1006.5352. doi:10.1109\/FOCS.2011.26.     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/lemke-howson-algorithm-wikipedia\/#breadcrumbitem","name":"Lemke\u2013Howson algorithm – Wikipedia"}}]}]