Solving parity games (from a "start" node) relies on the existence of a history-free winning strategy for player 0 (V) or 1 (R). Whether there is more than one such strategy is probably never discovered, is it? Are there algorithms to keep searching even after discovering one appropriate strategy, i.e. searching for more than one (say all possible) strategies?
1
-
$\begingroup$ What's the problem with iterating over all possible strategies in the minmax tree of the game? $\endgroup$– R BCommented Apr 23, 2014 at 23:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Parity games can be reduced to discounted payoff games. See, e.g.,
Marcin Jurdziński (1998). Deciding the winner in parity games is in UP ∩ co-UP. Information Processing Letters 68:3 119-124.
As explained in that paper (and first observed by Zwick and Paterson, I believe), there are min/max optimality equations for discounted payoff games with a unique solution that assigns a "value" to each state. From these values, it is easy to read off all optimal strategies of the players.
Discounted payoff games can in turn can be solved as a P-matrix Linear Complementarity Problem (LCP), where the reduction uses the optimality equations and from a solution to the LCP one could again read off all optimal strategies. See,
Marcin Jurdziński and Rahul Savani (2008). A simple P-matrix linear complementarity problem for discounted games. Computability in Europe (CiE), 283-293.
Now in the following paper a discrete strategy improvement algorithm for parity games is given that essentially defines and uses optimality equations.
Jens Vöge and Marcin Jurdziński (2000). A Discrete Strategy Improvement Algorithm for Solving Parity Games. Computer-aided Verification (CAV).
It's very possible you could read off all strategies from a "solution" to those optimality equations, e.g., obtained via their algorithms - but, I am not sure.
