The complexity of two-person zero-sum games in extensive form (1992)

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.

Download Information

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.

Bibtex citation

@article{Koller+Megiddo:GEB92,
  author =       "D. Koller and N. Megiddo",
  title =        "The complexity of two-person zero-sum games in
                 extensive form",
  journal =      "Games and Economic Bahavior",
  volume =       "4",
  number =       "4",
  pages =        "528--552",
  year =         "1992",
}