My home page
Biography
Research
Publications
My group
Courses
Professional activities
FAQ
Personal
Papers

Daphne Koller Publications

Fast Algorithms for Finding Randomized Strategies in Game Trees (1994)

by D. Koller, N. Megiddo, and B. von Stengel


Abstract: Interactions among agents can be conveniently described by game trees. In order to analyze a game, it is important to derive optimal (or equilibrium) strategies for the different players. The standard approach to finding such strategies in games with imperfect information is, in general, computationally intractable. The approach is to generate the normal form of the game (the matrix containing the payoff for each strategy combination), and then solve a linear program (LP) or a linear complementarity problem (LCP). The size of the normal form, however, is typically exponential in the size of the game tree, thus making this method impractical in all but the simplest cases. This paper describes a new representation of strategies which results in a practical linear formulation of the problem of two-player games with perfect recall (i.e., games where players never forget anything, which is a standard assumption). Standard LP or LCP solvers can then be applied to find optimal randomized strategies. The resulting algorithms are, in general, exponentially better than the standard ones, both in terms of time and in terms of space.


Download Information

D. Koller, N. Megiddo, and B. von Stengel (1994). "Fast Algorithms for Finding Randomized Strategies in Game Trees." Proceedings of the 26th ACM Symposium on Theory of Computing (STOC '94) (pp. 750-759). pdf ps.gz

Bibtex citation

@inproceedings{Koller+al:STOC94,
  author =       "D. Koller and N. Megiddo and B. {von Stengel}",
  booktitle =    "Proceedings of the 26th ACM Symposium on Theory of
                 Computing (STOC '94)",
  title =        "Fast Algorithms for Finding Randomized Strategies in
                 Game Trees",
  pages =        "750--759",
  year =         "1994",
}

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