




Publications  Strategy Iteration using NonDeterministic Strategies for Solving Parity Games





Reference:
Michael Luttenberger. Strategy iteration using nondeterministic strategies for solving parity games. Technical report, Technische Universität München, Institut für Informatik, April 2008.
Abstract:
This article extends the idea of solving parity games by strategy iteration to nondeterministic strategies: In a nondeterministic strategy a player restricts himself to some nonempty subset of possible actions at a given node, instead of limiting himself to exactly one action. We show that a strategyimprovement algorithm by by Björklund, Sandberg, and Vorobyov can easily be adapted to the more general setting of nondeterministic strategies. Further, we show that applying the heuristic of ``all profitable switches'' leads to choosing a ``locally optimal'' successor strategy in the setting of nondeterministic strategies, thereby obtaining an easy proof of an algorithm by Schewe. In contrast to the aglorithm by Björklund et al., we present our algorithm directly for parity games which allows us to compare it to the algorithm by Jurdzinski and Vöge: We show that the valuations used in both algorithm coincide on parity game arenas in which one player can ``surrender''. Thus, our algorithm can also be seen as a generalization of the one by Jurdzinski and Vöge to nondeterministic strategies. Finally, using nondeterministic strategies allows us to show that the number of improvement steps is bound from above by . For strategyimprovement algorithms, this bound was previously only known to be attainable by using randomization.
Suggested BibTeX entry:
@techreport{Lut08a:tp,
author = {Michael Luttenberger},
institution = {Technische Universit\"{a}t M\"{u}nchen, Institut f\"{u}r Informatik},
month = {April},
title = {Strategy Iteration using NonDeterministic Strategies for Solving Parity Games},
year = {2008}
}




