Loading...
Please wait, while we are loading the content...
Similar Documents
Hard-to-solve Bimatrix Games by Rahul Savani
| Content Provider | Semantic Scholar |
|---|---|
| Author | Stengel, Bernhard Von |
| Copyright Year | 2006 |
| Abstract | The Lemke–Howson algorithm is the classical method for finding one Nash equilibrium of a bimatrix game. This paper presents a class of square bimatrix games for which this algorithm takes, even in the best case, an exponential number of steps in the dimension d of the game. Using polytope theory, the games are constructed using pairs of dual cyclic polytopes with 2d suitably labeled facets in d-space. The construction is extended to nonsquare games where, in addition to exponentially long Lemke–Howson computations, finding an equilibrium by support enumeration takes on average exponential time. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.maths.lse.ac.uk/Personal/stengel/TEXTE/ecta2006.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
