Reference:

Michael Luttenberger. Strategy iteration using non-deterministic 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 non-deterministic strategies: In a non-deterministic strategy a player restricts himself to some non-empty subset of possible actions at a given node, instead of limiting himself to exactly one action. We show that a strategy-improvement algorithm by by Björklund, Sandberg, and Vorobyov can easily be adapted to the more general setting of non-deterministic strategies. Further, we show that applying the heuristic of ``all profitable switches'' leads to choosing a ``locally optimal'' successor strategy in the setting of non-deterministic 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 non-deterministic strategies. Finally, using non-deterministic strategies allows us to show that the number of improvement steps is bound from above by . For strategy-improvement 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 Non-Deterministic Strategies for Solving Parity Games},
    year = {2008}
}