We propose the sequence form as a new strategic description for an extensive game with perfect recall. It is similar to the normal form but has linear instead of exponential complexity, and allows a direct representation and efficient computation of behavior strategies. Pure strategies and their mixed strategy probabilities are replaced by sequences of consecutive choices and their realization probabilities. A zero-sum game is solved by a corresponding linear program that has linear size in the size of the game tree. General two-person games are studied in the paper by Koller, Megiddo, and von Stengel, 1996 (Games and Economic Behavior 14, 247-259)
Behavior strategy, equilibrium, extensive game, linear programming, normal form, reduced normal form.
Games and Economic Behavior 14 (1996), 220-246
PDF-file (265 kB, 27 pages)
gz-compressed POSTSCRIPT-file (123 kB, 27 pages)