Hard-to-Solve Bimatrix Games
构造了一类双矩阵博弈，使得Lemke-Howson算法即使在最佳情况下也需要指数步才能找到纳什均衡，且支持枚举法平均也需要指数时间。
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.