Consider $l,m,n,N \in \mathbb{N}$ and circuits $C: \{0,1\}^{l+m} \rightarrow \{0,1\}^l$, $D: \{0,1\}^{l+n} \rightarrow \{0,1\}^l$. Consider the following zero-sum two-layer extensive-form game with perfect information:

  • The positions of the game are $\{0,1\}^l$ and the initial position is $0^l$.
  • The 1st player's moves are $\{0,1\}^m$ and their effect on the position is defined by $C$.
  • The 2nd player's moves are $\{0,1\}^n$ and their effect on the position is defined by $D$.
  • After $N$ moves the game is over. The first bit of the resulting position determines whether the winner is the 1st player or the 2nd player (the game is zero-sum with pure payoffs $\pm 1$).

It is well-known that the value of such a game can be computed in space polynomial in $l, m, n, N$ and the size of $C$ and $D$ (or even just the depth of $C$ and $D$, assuming appropriate representation).

Now consider the same setting as above with additional parameters $k,j \in \mathbb{N}$ s.t. $k + j \leq l$. Consider the extensive-form game with imperfect information which is the same as above but positions are grouped into 1st player information sets by the first $k$ bits and into 2nd player information sets by the last $j$ bits. That is, the 1st player's pure strategies are functions $\{0,1\}^k \rightarrow \{0,1\}^m$ and the 2nd player's pure strategies are functions $\{0,1\}^j \rightarrow \{0,1\}^n$, which are evaluated on the first $k$ bits or the last $j$ bits of the position correspondingly.

Is it true that for every $\epsilon > 0$ we can decide whether the value $v$ of the game is positive, in polynomial space, given the promise that $\lvert v \rvert > \epsilon$?

Also, consider the same question for the extensive-form game with perfect recall that results when we allow each player to remember history, i.e. each player's moves can depend both on the current observable part of the position and the history of observable positions and moves for the same player. Note that in this case the game is known to be solvable in time polynomial in $2^{(m+n)N}$ due to the result of Koller and Megiddo.

  • $\begingroup$ Is N in unary or binary? ​ ​ $\endgroup$
    – user6973
    Commented Oct 23, 2016 at 23:38
  • $\begingroup$ @RickyDemer I meant literally polynomial in these parameters, not polynomial in the length of encoding these parameters i.e. you can regard it as unary. $\endgroup$
    – Vanessa
    Commented Oct 24, 2016 at 7:45
  • $\begingroup$ I slightly reformulated the question as a weaker (and more precisely defined) hypothesis. $\endgroup$
    – Vanessa
    Commented Oct 24, 2016 at 8:13


Your Answer

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