caa a22 4500 477048366 CHVBK 20180405111336.0 cr unu---uuuuu 170330e19960301xx s 000 0 eng 10.1007/BF01254386 doi (NATIONALLICENCE)springer-10.1007/BF01254386 Finding mixed strategies with small supports in extensive form games [Elektronische Daten] [Daphne Koller, Nimrod Megiddo] The complexity of algorithms that compute strategies or operate on them typically depends on the representation length of the strategies involved. One measure for thesize of a mixed strategy is the number of strategies in itssupport — 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 ofrealization 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. Physica-Verlag, 1996 Koller Daphne Computer Science Division, University of California, 387 Soda Hall, 94720, Berkeley, CA, USA aut Megiddo Nimrod IBM Almaden Research Center, 650 Harry Road, 95120-6099, San Jose, CA aut International Journal of Game Theory Physica-Verlag 25/1(1996-03-01), 73-92 0020-7276 25:1<73 1996 25 182 https://doi.org/10.1007/BF01254386 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01254386 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Koller Daphne Computer Science Division, University of California, 387 Soda Hall, 94720, Berkeley, CA, USA aut NATIONALLICENCE 700 1- Megiddo Nimrod IBM Almaden Research Center, 650 Harry Road, 95120-6099, San Jose, CA aut NATIONALLICENCE 773 0- International Journal of Game Theory Physica-Verlag 25/1(1996-03-01), 73-92 0020-7276 25:1<73 1996 25 182 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer