Hard-to-solve bimatrix games

• 成果类型: Article
• 署名作者: Savani, R; von Stengel, B
• 署名单位: University of London; London School Economics & Political Science
• 刊物名称: ECONOMETRICA
• ISSN/ISSBN: 0012-9682
• DOI: 10.1111/j.1468-0262.2006.00667.x
• 发表日期: 2006
• 页码: 397-429
• 关键词: COMPUTATIONAL-COMPLEXITY; EQUILIBRIUM POINTS; Nash equilibria; AVERAGE NUMBER; steps

摘要

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.