Given a deterministic partial-information zero-sum game with only finitely many states,
whose possible outcomes are [lose,draw,win] with values [-1,0,+1] respectively,
what is the complexity of approximating the value of such a game additively within $\epsilon$?

In particular, I can't come up any algorithm whatsoever for doing that.
The rest of this post is devoted entirely to giving a more thorough description
of the problem, so if you can already figure out what the question at the top
of this post means, then there's no reason for you to read the rest of this post.

Given a referee machine with states $\{1,2,3,...,S\}$, with a designated initial state $s_0$, a state $s_a$ whose score pair is $[-1,+1]$, a state $s_b$ whose score pair is $[+1,-1]$, and states of the form

$[\mbox{p1_info,p2_info,num_of_choices,player_to_move,next_state_table}]$ where:

  • $\mbox{player_to_move} \in \{1,2\}$
  • $\mbox{next_state_table}$ is a function from $\{1,2,3,...,\mbox{num_of_choices}\} \to \{1,2,3,...,S\}$
  • $\mbox{p1_info},\mbox{p2_info}, \mbox{num_of_choices} \geq 1$

When the machine is in a state of that form:

  • sends $\mbox{p1_info}$ to Player_1 and sends $\mbox{p2_info}$ to Player_2,
  • sends $\mbox{num_of_choices}$ to the indicated player, waits for an element of $\{1,2,3,...,\mbox{num_of_choices}\}$ as input from that player,
  • then goes to the state indicated by $\mbox{next_state_table}$

When the machine enters one of the other two states $s_a$ or $s_b$,

  • halts with that state's score pair as its output

There is a natural two-player game: the referee machine is started in state $s_0 = 1$,
the players provide the inputs that the referee machine waits for, if the referee machine
halts then Player 1 scores the first value of the machine's output pair and Player 2
scores the second value of the machine's output pair, otherwise both players score 0.

What is the complexity of the following problem?
Given such a referee machine and a positive integer N, output a rational number
that is (additively) within 1/N of the value of the natural game for Player 1.

As mentioned earlier in this question, I can't come
up with any algorithm whatsoever for doing that.

  • $\begingroup$ Do the players know the internal structure? What is the advantage of having additional information, it gives more possible moves? $\endgroup$
    – domotorp
    Jun 9, 2013 at 12:44
  • $\begingroup$ Yes. $\:$ It gives them a better idea of what the current state is. $\;\;\;$ $\endgroup$
    – user6973
    Jun 9, 2013 at 22:03
  • $\begingroup$ Sorry but I still don't get it. Then they know the internal structure but they don't know where they are at the moment? Please make the description clear, I am sure I am not the only one who cannot understand the problem. $\endgroup$
    – domotorp
    Jun 10, 2013 at 5:44
  • 3
    $\begingroup$ Is your model the same as a "zero-sum turn-based stochastic game with partial information" ? $\endgroup$ Jun 10, 2013 at 13:23
  • 1
    $\begingroup$ @Kristoffer : $\:$ It's not obvious (at least to me) that my model allows for coding $\hspace{.8 in}$ irrational probabilities, although my model is otherwise equivalent to that one. $\;\;\;\;$ $\endgroup$
    – user6973
    Jun 10, 2013 at 22:02

2 Answers 2


NOTE: my purported algorithm was incorrect; I deleted it.

One thing to realize is that it doesn't matter whether the game is deterministic or not. To randomize, the referee can ask each of the players to contribute a random number mod $p$, and then add them. It's easy to show that if the players use their optimal strategy, the sum is a random number mod $p$, which the referee can then use to randomize his strategy. This doesn't greatly increase the number of states in the game.

For a lower bound on the complexity, the question of approximating the value of a simple stochastic game is not known to be in P. Using the randomization trick I gave above, it is easy to write a simple stochastic game as a refereed game with a polynomial-size lookup table.

  • $\begingroup$ That randomization idea (at least, as you described it) can only give rational probabilities. $\:$ Also, the definitions used in the first two papers you linked too imply that their games have a finite game tree, whereas I'm only requiring a finite state space (where "state" does not include the game's history). $\endgroup$
    – user6973
    Jun 10, 2013 at 21:36
  • $\begingroup$ You're right ... the first part of my answer is incorrect. Let me delete it. I am fairly sure that approximating the value of simple stochastic games is not known to be in P even when all the coin flips have probability 1/2. $\endgroup$ Jun 11, 2013 at 0:30

By Theorem 3.1 and the proof's IPS being one-way,
for all real numbers $\epsilon$, if ​ $0<\epsilon$ ​ then the promise problem

Input: ​ a game as described in my question
must output YES if : ​ ​ ​ the game's value for Player 1 is greater than 1-$\hspace{.025 in}\epsilon$
must output ​ NO ​ if : ​ ​ ​ the game's value for Player 1 is less than $\epsilon$

remains RE-hard even when

player_to_move is always 1 ​ (i.e., only 1 player is needed)
s0 ≠ sa ​ and ​ sa is not in Range(next_state_table)
(i.e., it's literally impossible for the player to lose)
p1_info and p2_info and number_of_choices are independent of the state
(i.e., the player's only feedback is whether or not it just won)



Your Answer

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