Lecture: Strategies for Extensive Form Games

Richard Edwin Stearns

Abstract:

We want to describe sets of mixed strategies using linear equations such that
1. The number of variables is small compared to the game size.
2. Every mixed strategy has an equivalent strategy in the set.
3. Implementing the strategies is easy.
It is known how to do this for players with perfect recall using equations for behavior strategies or equations for path probabilities. We generalize the perfect recall techniques to cover players without perfect recall. Although the number of variables needed is not always small, it will be small if the recall is close enough to perfect.