Finding mixed strategies with small supports in extensive form games

Abstract

The complexity of algorithms that compute strategies or operate on them typically depends on the representation length of the strategies involved. One measure for the size of a mixed strategy is the number of strategies in its support - the set of pure strategies to which it gives positive probability. This paper investigates the existence of "small" mixed strategies in extensive form games, and how such strategies can be used to create more efficient algorithms. The basic idea is that, in an extensive form game, a mixed strategy induces a small set of realization weights that completely describe its observable behavior. This fact can be used to show that for any mixed strategy μ, there exists a realization-equivalent mixed strategy μ′ whose size is at most the size of the game tree. For a player with imperfect recall, the problem of finding such a strategy μ′ (given the realization weights) is NP-hard. On the other hand, if μ is a behavior strategy, μ′ can be constructed from μ in time polynomial in the size of the game tree. In either case, we can use the fact that mixed strategies need never be too large for constructing efficient algorithms that search for equilibria. In particular, we construct the first exponential-time algorithm for finding all equilibria of an arbitrary two-person game in extensive form.