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 twoplayer 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. 750759).


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 = "750759",
year = "1994",
}
full list
