The complexity of two-person zero-sum games in extensive form (1992)by D. Koller and N. Megiddo
This paper investigates the complexity of finding max-min strategies for finite two-person zero-sum games in the extensive form. The problem of determining whether a player with imperfect recall can guarantee himself a certain payoff is shown to be NP-hard. When both players have imperfect recall, this is even harder. Moreover, the max-min behavior strategy of such a player may use irrational numbers. Thus, for games with imperfect recall, computing the max-min strategy or the value of the game is a hard problem. For a game with perfect recall, we present an algorithm for computing a max-min behavior strategy, which runs in time polynomial in the size of the game tree.
D. Koller and N. Megiddo (1992). "The complexity of two-person zero-sum games in extensive form." Games and Economic Bahavior, 4(4), 528-552.
author = "D. Koller and N. Megiddo",
title = "The complexity of two-person zero-sum games in
journal = "Games and Economic Bahavior",
volume = "4",
number = "4",
pages = "528--552",
year = "1992",