Efficient computation of behavior strategies

Abstract:
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)

Keywords:
Behavior strategy, equilibrium, extensive game, linear programming, normal form, reduced normal form.

In:
Games and Economic Behavior 14 (1996), 220-246

PDF-file (265 kB, 27 pages)

gz-compressed POSTSCRIPT-file (123 kB, 27 pages)

Related work:

• D. Koller, N. Megiddo, and B. von Stengel (1996), Efficient computation of equilibria for extensive two-person games. Games and Economic Behavior 14, 247-259.

• 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, 750-759.

Back to Bernhard von Stengel's list of publications