2
$\begingroup$

I asked essentially this on math.SE slightly more than
3 days ago, and it hasn't received any answer there.

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 P1 or P2]
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 (P1 or P2) 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 current state?

$\endgroup$
24
  • $\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 A,B,C,D all labeled P1, A as the initial state and going to C as the only move from there, B and D as the moves from B, C as the only move from D, and P1 winning as the only move from B. $\;\;\;\;$ $\endgroup$
    – user5810
    Jan 24, 2015 at 4:23
  • $\begingroup$ Perhaps I'm wrong, but isn't the notion of "optimal" fuzzy here? Perhaps it would help to define this. The most natural would be subgame perfect equilibrium, I think. But there you probably need to argue that it exists... $\endgroup$
    – usul
    Jan 24, 2015 at 17:46
  • $\begingroup$ Are you asking for something other than Zermelo's theorem? $\endgroup$ Jan 24, 2015 at 23:06
  • $\begingroup$ @DouglasZare : $\:$ Yes, since chance can "affect the decision making process". $\hspace{1.71 in}$ $\endgroup$
    – user5810
    Jan 25, 2015 at 3:18
  • $\begingroup$ I think that the only obstruction to otherwise maximizing strategy is the wrong choice of ties which may cause the game to repeat indefinitely. The right notion here for "optimal strategy" seems to me to be an ordinary Nash equilibrium and I believe it does exist when the strategy is defined in the right way. Can you come up with an example similar to your {A,B,C,D} game where NE does not exist when ties are well resolved? $\endgroup$ May 29, 2017 at 16:19

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.