1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What's the problem with iterating over all possible strategies in the minmax tree of the game? $\endgroup$ – R B Apr 23 '14 at 23:37
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.