Efficient computation of behavior strategies

Bernhard von Stengel

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)

Related work:

BvSBack to Bernhard von Stengel's list of publications