The following is a way to represent two-player zero-sum games in extensive form. Consider a directed acyclic graph $G$ where each non-terminal vertex is one of 3 types: player 1 vertex, player 2 vertex or chance vertex. There is a designated initial vertex $v_0$. The vertices of each player are divided into information sets. The edges outcoming from player nodes are labeled by actions, s.t. vertices in the same information set have the same set of actions and vertices in different information sets have disjoint sets of actions. The edges outcoming from chance nodes are labeled by transition probabilities. The terminal vertices are labeled by payoffs.
We say that such a game has "perfect recall" when knowing the sequence of actions that player $i \in \{1,2\}$ took before reaching a given information set $U$ of player $i$ tells us nothing about which particular vertex $v \in U$ we reached, i.e. all vertices in $U$ have the same possible histories from the perspective of the given player.
Koller and Megiddo have established that zero-sum two-player games in extensive form with perfect recall can be solved in polynomial time (i.e. we can find a Nash equilibrium in behavioral strategies). This assumes the game is given as an explicit tree. Now, unpacking the DAG into a tree can obviously increase its size exponentially. The question is thus:
What is the complexity of computing the value of a two-player zero-sum DAG game with perfect recall?
Note that, as opposed to the tree case, I don't even know whether there is a Nash equilibrium in behavioral strategies.
As another variant, instead of labeling the terminal nodes by payoffs we can label every edge by a payoff so that the total payoff is a sum over traversed edges (this is similar to the games defined by McMahan and Gordon). For trees this doesn't matter but for DAGs separating vertices in order to remember accumulated payoff can again cause an exponential expansion (although if we're willing to settle on approximating with $\frac{1}{poly(n)}$, this expansion can probably be contained).
If the problems above are likely to require superpolynomial time, I am also interested in the special cases in which one of the players has perfect information (the case where both players have perfect information is solvable by backward induction).
