I was (and still am) really interested in the answer to this question, because this is an interesting variation on the complexity of games which hasn't been resolved, so I offered a bounty. I thought the original question was very likely too hard, so I posted three related questions which would also be worthy of the bounty. Nobody posted any answers before the bounty expired. I was later able to answer two of the related questions (questions 3 and 4, discussed below my original post), showing that approximating the value of refereed games with correlated semi-private coins (defined below) was EXPTIME-complete. The original question is still unanswered. I'd also be interested in any results putting related games between PSPACE and EXPTIME in interesting complexity classes.
This question was inspired by the discussion on Itai's hex question. A refereed game is a game where two computationally unbounded players play by communicating through a polynomial-time verifier who can flip private coins (thus the number of turns and the amount of communication is also polynomial-time bounded). At the end of the game, the referee runs an algorithm in P to determine who wins. Determining who wins such a game (even approximately) is EXPTIME complete. If you have public coins, and public communication, such games are in PSPACE. (See Feige and Killian, "Making Games Short.") My question concerns the boundary between these two results.
Question: Suppose you have two computationally unbounded players who play a polynomial-length game. The referee's role is limited to, before each move, giving each player some number of private coin flips (uncorrelated with the other player's). All of the player's moves are public, and so seen by his opponent -- the only private information is the coin flips. At the end of the game, all the private coin flips are revealed, and the poly-time referee uses these coin flips and the player's moves to decide who wins.
By the refereed games result, approximating the probability that the first player wins is in EXPTIME, and it is also clearly PSPACE-hard. Which (if either) is it? Is anything known about this problem?
Note that the players may have to use mixed strategies, since you can play zero-sum matrix games (a la von Neumann) this way.
Let's call this complexity class RGUSP (all languages $L$ which can be reduced to a Refereed Game with Uncorrelated Semiprivate Coins as described above, such that if $x \in L$, player 1 wins with probability $\geq 2/3$, and if $x \notin L$, player 1 wins with probability $\leq 1/3$). My three related questions are:
Question 2: RGUSP seems fairly robust. For example, if we change the game so the referee does not send messages, but only observes player 1 and 2's public messages, and receives private messages from them, then approximating the value of this game is still equivalent to RGUSP. I'd like to demonstrate that RGUSP is robust, so I'm willing to give the bounty to anyone who finds a natural complexity class C so that PSPACE $\subseteq$ C $\subseteq$ RGUSP, where neither of the containments appear to be exact.
Question 3: I also strongly suspect that the class RGCSP (Refereed Games with Correlated Semiprivate Coins) is EXPTIME complete, and I'm also willing to give the bounty to somebody who proves this fact. In RGCSP, at the first step, the referee gives the two players correlated random variables (for example, he might give the first player a point in a large projective plane, and the second player a line containing this point). After this, for a polynomial number of rounds the two players alternate sending each other poly-size public messages. After the game has been played, the poly-time referee decides who won. What is the complexity of approximating the winning probability for player 1?
Question 4: Finally, I have a question which may really be about cryptography and probability distributions: Does giving the ability to perform oblivious transfer to two players in a refereed game with uncorrelated semi-private coins let them play an arbitrary refereed game with correlated coins (or alternatively, does it let them play a game determining the winner of which is EXPTIME-complete)?