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 {\em 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 (\ie, 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.
In:
Proceedings of the 26th ACM Symposium on Theory of Computing
(1994), 750-759.
Back
to Bernhard von Stengel's list of publications