Do finite-state 2-player zero-sum games of perfect information with only win-draw-loss outcomes always have deterministic-and-memoryless optimal strategies for both players?

In other words, consider 2-player games of the following form:

There is a non-empty finite set of states such that neither -1 nor +1 is a state.
One of the states is designated the initial state, and each state has [a label that's either A or B]
and [a finite list of probability distributions on the union of {-1,+1} with the set of states].
Starting with the initial state, the indicated player (A or B) chooses one of the probability distributions, an element is sampled from that distribution, if the element is -1 then the game
ends with the indicated player scoring -1 and the other player scoring +1, if the element is +1 then
the game ends with the indicated player scoring +1 and the other player scoring -1, and if the
element is a state then reveal that state to that player and repeat this process from that state.
If the game continues forever then both players score 0.

Is it always the case that both players have optimal strategies
that are deterministic and only depend on the curren state?

  • 1
    $\begingroup$ Note that "always make a move that maximizes your expected score, with ties broken arbitrarily" does not work. $\:$ One could have the deterministic game with states 0,1,2,3 all labeled A, 0 as the initial state and going to 2 as the only move from there, 1 and 3 as the moves from 2, 2 as the only move from 3, and winning as the only move from 1. $\;\;\;\;$ $\endgroup$ – user57159 Jan 20 '15 at 9:33
  • 1
    $\begingroup$ How is the example you gave a counterexample? $\endgroup$ – 5xum Jan 20 '15 at 9:35
  • 1
    $\begingroup$ From every state, the expected score for player A is +1, since A could win in at most three more moves. $\:$ Thus, if one broke ties by choosing the right-most of the tied states, then the play would go 0,2,3,2,3,2,3,..., which would make A only score zero. $\;\;\;\;$ $\endgroup$ – user57159 Jan 20 '15 at 9:41
  • 1
    $\begingroup$ Note: $\:$ I have cross-posted this to MO. $\;\;\;\;$ $\endgroup$ – user57159 Jan 24 '15 at 4:24
  • $\begingroup$ You may be interested in how the reduced form of partisan sudoku is analogous to impartial sudoku. In the reduced partisan form, elements have value, but the value is binary [-1 | +1] for [Player1 | Player2]. The game sum is always 1 or 0. Optimal strategies in the reduced partisan sudoku correspond to optimal strategies for impartial sudoku, demonstrated by Hamkins in Infinite Sudoku. $\endgroup$ – DukeZhou May 25 '18 at 18:16

Your Answer

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