Refereed games with uncorrelated semi-private coins

Question

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.

ORIGINAL POST:

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.

ADDED MATERIAL:

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)?

Answer 1

I can't answer my original question, but I can answer the question 3 (and 4), which I added when I offered a bounty because I thought the original question was likely too hard. In fact, I have two proofs of question 3.

Here's the setting for question 3: We have a polynomial-time referee who, at the beginning of the game, gives players 1 and 2 correlated random variables. Players 1 and 2 then play the game, without any interference from the referee. At the end of the game, the referee looks over the transcript and decides who wins. I can show that deciding who wins such a game is EXPTIME complete, even if you are given the promise that the winner wins with probability at least $2/3$.

========Proof 1============

The first proof uses the fact that oblivious transfer is universal for secure two-party computation. Thus, if players 1 and 2 can perform oblivious transfer, they can simulate an arbitrary polynomial-time referee, so the previous results that refereed games are EXPTIME complete can be applied.

Now, to achieve 1-2 oblivious transfer, at the beginning of the game, the referee gives the two players a large number of "oblivious transfer boxes." We describe one of these oblivious transfer boxes. P1 gets two random numbers, $r_1$ and $r_2$. P2 gets one of these random numbers, $r_i$ and the variable $i$ ($=1$ or $2$) saying which of P1's random numbers he got. To perform oblivious transfer, P1 takes the two pieces of data he wants to transfer, and XOR's them with $r_1$ and $r_2$. P2 can then decode one of these, but P1 cannot tell which one P2 can decode. This is 1-2 oblivious transfer. (Obviously, the referee also has to give the players oblivious transfer boxes directed the other way, from P2 to P1.)

When I first asked question 4, I was worried that the secure two-party computation results didn't apply to this kind of interactive computation with a referee, but in fact it's quite easy to show that they do.

===========Proof 2===========

Now for the second proof for question 3. Here, we need to go back and modify the Feige-Kilian proof. In this proof, they consider a Turing machine T which is running an exponential time computation. Feige and Kilian encode the $2^n$ bits on the tape at time $t$ in a multilinear polynomial $Q_t($x_1$, \ldots, $x_n$)$ over a large finite field GF($p$). Now, the referee gives a point to P1 and a line containing this point to P2, and the two players give the evaluation of the point and the line on $Q_t$ back to the referee. The referee uses binary search to find a time $t$ where P1 and P2's evaluations of $Q_t$ agree, but their evaluations of $Q_{t+1}$ disagree, after which he asks P1 a clever question which will reveal whether she is the one who is lying.

The first thing we will use is that, even with uncorrelated random coins, the referee can make players 1 and 2 perform bit committment, by having them XOR the data they want to commit with the random coins. Thus, we can talk about P1 and P2 putting things in sealed envelopes.

One thing you might try to simulate the Feige-Kilian proof is: the referee gives P1 a lot of different points $p_i$, and P2 a lot of lines $\ell_i$, so that $p_i$ is on $\ell_i$. Now, at each step of the binary search, the players put the values $Q_{t}(p_i)$ and $Q_t(\ell_i)$ into sealed envelopes, and then the referee chooses one randomly for the players to open. The two players decide whether the values are consistent, and proceed with the binary search accordingly. Now, we've ruined the $(p_i, \ell_i)$ pair, because both players know the value of the point and line, but we still have a lot of other (point, line) pairs that we can use.

(How can the referee choose one $(p_i, \ell_i)$ randomly if he gives the players instructions only at the beginning of the game? He can encode his instructions in the XOR of values he gives to the two players at the beginning, and the two players can't read the instruction until they both reveal the values at the relevant time.)

This strategy doesn't quite work, because P1 and P2 don't have to be consistent about the time at which they start lying with two points (or lines) That is, P1 could let give the right value for $Q_t(p_i)$ and the wrong value for $Q_t(p_j)$. This would completely mess up the binary search, and make the protocol inconclusive. However, there's a neat trick we can use to force P1 to be consistent. Add a bunch of dummy points ${p}'_k$ to P1's set of points, and add dummy lines ${\ell}'_k$ to P2's set of lines. Let each dummy line have two points on it. If P1 happens to give the right value for one dummy point on a line and the wrong value for the other dummy point, then he has revealed himself as a liar, since there is no way for P2 to give the value for a line that is correct for one of P1's two points on it and not the other. We can do a similar trick to make P2 answer consistently. Then the only thing left is showing that the last step of the Feige-Kilian proof still works. This turns out to be straightforward, although going through the details would make this answer much longer.