My home page
My group
Professional activities

Daphne Koller Publications

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.

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. pdf

Bibtex citation

  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",

full list
Click to go to robotics Click to go to theory Click to go to CS Stanford Click to go to Stanford's Webpage
home | biography | research | papers | my group
courses | professional activities | FAQ | personal