Name
Abstract | ||
|---|---|---|
The Lemke-Howson algorithm is the classical algorithm for the problem NASH of finding one Nash equilibrium of a bimatrix game. It provides a constructive and elementary proof of existence of an equilibrium, by a typical "directed parity argument", which puts NASH into the complexity class PPAD. This paper presents a class of bimatrix games for which the Lemke-Howson algorithm takes, even in the best case, exponential time in the dimension d of the game, requiring \Omega ((\theta ^{{3 \mathord{\left/ {\vphantom {3 4}} \right. \kern-\nulldelimiterspace} 4}} )^d ) many steps, where 驴 is the Golden Ratio. The "parity argument" for NASH is thus explicitly shown to be inefficient. The games are constructed using pairs of dual cyclic polytopes with 2d suitably labeled facets in d-space. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1109/FOCS.2004.28 | FOCS |
Keywords | Field | DocType |
computational complexity,game theory,matrix algebra,Lemke-Howson algorithm,Nash equilibrium,bimatrix game,complexity class PPAD,directed parity argument,dual cyclic polytopes,exponential time | Correlated equilibrium,Discrete mathematics,Combinatorics,Epsilon-equilibrium,Best response,Repeated game,Nash equilibrium,Folk theorem,Lemke–Howson algorithm,Mathematics,PPAD | Conference |
ISSN | ISBN | Citations |
0272-5428 | 0-7695-2228-9 | 51 |
PageRank | References | Authors |
4.82 | 12 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rahul Savani | 1 | 243 | 30.09 |
| Bernhard von Stengel | 2 | 275 | 38.51 |