Efficient Computation of Behavior Strategies

We propose thesequence formas 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...

Full description

Saved in:
Bibliographic Details
Published in:Games and economic behavior 1996-06, Vol.14 (2), p.220-246
Main Author: von Stengel, Bernhard
Format: Article
Language:English
Subjects:
Economic analysis
Economic behaviour
Economic efficiency
Game theory
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose thesequence formas 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 Kolleret al., 1996 (Games Econ. Behav.14, 247–259).Journal of Economic LiteratureClassification Number: C72.
ISSN:0899-8256
1090-2473
DOI:10.1006/game.1996.0050