Fausto Bernardini, Holly Rushmeier
Proceedings of SPIE - The International Society for Optical Engineering
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.
Fausto Bernardini, Holly Rushmeier
Proceedings of SPIE - The International Society for Optical Engineering
Peter Wendt
Electronic Imaging: Advanced Devices and Systems 1990
John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
Moutaz Fakhry, Yuri Granik, et al.
SPIE Photomask Technology + EUV Lithography 2011