EFFICIENT COMPUTATION OF BEHAVIOR STRATEGIES

We propose the sequence form as a new strategic description for an ext ensive game with perfect recall. It is similar to the normal form but has linear instead of exponential complexity and allows a direct repre sentation and efficient computation of behavior strategies. Pure strat egies and their mixed strategy probabilities are replaced by sequences of consecutive choices and their realization probabilities. A zero-su m game is salved by a corresponding linear program that has linear siz e in the size of the game tree. General two-person games are studied i n the paper by Koller el al., 1996 (Games Econ. Behav. 14, 247-259). ( C) 1996 Academic Press, Inc.