Zielonka Algorithm

Question

When determining the winning strategy could there be only one correct strategy or is there a possibility of having multiple strategies. for example in the exam September 6, 2022 b part, the strategy that has been given is S8(S1S2)w. is there a possibility of player 1 winning with the strategy of (s8s0)w?

Answer 1

In general, the states are determined, i.e., for each state exactly one of the two players has a winning strategy. The winning strategy is not unique, there may be many choices a player can have if that player. has a winning strategy in a state.

In the game you mention, the play (s8s0)^w is a game play with highest rank 9 so player 1 will win. However, it would be foolish of player 0 to play that game: in state s9, player 0 has a winning strategy, and player 0 would therefore select the transition to s3, then to s4 where player 1 has no other choice to go back to s3. Then the game play is s8->s0->(s3->s4)^w with highest rank 8 and thus player 0 will win!

So, in state s8, player 1 has a winning strategy, but the only choice is to switch to s1 where player 1 also has a winning strategy. Switching to s0, i.e., to a state where the other player has a winning strategy is not wise.

Comments

Got it professor, thank you.