The complexity of twoperson zerosum games in extensive form (1992)by D. Koller and N. Megiddo
Abstract:
This paper investigates the complexity of finding maxmin strategies for finite twoperson zerosum 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 NPhard. When both players have imperfect recall, this is even harder. Moreover, the maxmin behavior strategy of such a player may use irrational numbers. Thus, for games with imperfect recall, computing the maxmin strategy or the value of the game is a hard problem. For a game with perfect recall, we present an algorithm for computing a maxmin 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 twoperson zerosum games in extensive form." Games and Economic Bahavior, 4(4), 528552.


Bibtex citation
@article{Koller+Megiddo:GEB92,
author = "D. Koller and N. Megiddo",
title = "The complexity of twoperson zerosum games in
extensive form",
journal = "Games and Economic Bahavior",
volume = "4",
number = "4",
pages = "528552",
year = "1992",
}
full list
