<p>Parity games can be reduced to discounted payoff games. See, e.g.,</p>

<p>Marcin Jurdziński (1998). Deciding the winner in parity games is in UP ∩ co-UP. Information Processing Letters 68:3 119-124.</p>

<p>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.</p>

<p>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,</p>

<p>Marcin Jurdziński and Rahul Savani (2008). A simple P-matrix linear complementarity problem for discounted games. Computability in Europe (CiE), 283-293.</p>

<p>Now in the following paper a discrete strategy improvement algorithm for parity games is given that essentially defines and uses optimality equations.</p>

<p>Jens Vöge and Marcin Jurdziński (2000). A Discrete Strategy Improvement Algorithm for Solving Parity Games. Computer-aided Verification (CAV).</p>

<p>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.</p>

CC BY-SA 3.0
2014-04-26T06:36:54.020Z
2014-04-26T08:55:34.550Z
2014-04-26T08:55:34.550Z
Rahul Savani
<p>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? </p>

CC BY-SA 3.0
2014-04-23T23:37:15.497Z
What's the problem with iterating over all possible strategies in the minmax tree of the game?
R B
<lo.logic>
Do algorithms for solving parity games ignore other possible strategies for player V after finding one?
Dimiter
# Do algorithms for solving parity games ignore other possible strategies for player V after finding one?

(Asked by: username_0 on 2014-04-23)

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?

**Tags:** lo.logic
> **Comments:**
> **username_1**: What's the problem with iterating over all possible strategies in the minmax tree of the game?  

---

## 1 answers

### Answer by username_2 on 2014-04-26. Score: 3

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.


---

