<p>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.</p>

<p>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$.</p>

<p>========Proof 1============</p>

<p>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. </p>

<p>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.)</p>

<p>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.</p>

<p>===========Proof 2===========</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>(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.)</p>

<p>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}&#39;_k$ to P1's set of points, and add dummy lines ${\ell}&#39;_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. </p>

CC BY-SA 2.5
2010-12-08T18:45:59.730Z
2010-12-10T21:25:38.640Z
2010-12-10T21:25:38.640Z
Peter Shor 
<p>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.</p>

<p>ORIGINAL POST:</p>

<p>This question was inspired by the discussion on <a href="https://cstheory.stackexchange.com/questions/2353/complexity-of-hex-with-random-turn-order/2372">Itai's hex question</a>. A <em>refereed game</em> 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. (<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.1990&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">See Feige and Killian, "Making Games Short."</a>) My question concerns the boundary between these two results.</p>

<ul>
<li><p>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. </p>

<p>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?</p></li>
</ul>

<p>Note that the players may have to use mixed strategies, since you can play zero-sum matrix games (a la von Neumann) this way.</p>

<p>ADDED MATERIAL:</p>

<p>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:</p>

<ul>
<li><p>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.</p></li>
<li><p>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?</p></li>
<li><p>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)?</p></li>
</ul>

CC BY-SA 2.5
2010-12-13T15:55:41.403Z
I think Magic: The Gathering (and probably other collectible card games) are perfect examples of this weaker type of refereed game. I don't play Magic, but each player has a deck, and the players start by shuffling their own deck, so all the randomness is uncorrelated.
Peter Shor 
CC BY-SA 2.5
2010-10-22T17:06:07.747Z
One observation is that the referee only needs to give the players random coins at the beginning of the game. You can generate random coins for player 1 just before his move by taking some of his private random coins $r$ from the beginning of the game and XOR'ing them with a string $s$ supplied by player 2. It's easy to show that player 2 cannot do any better than choosing $s$ at random (in which case $s$ XOR $r$ is also random).
Peter Shor 
CC BY-SA 2.5
2010-10-22T22:03:33.300Z
This sounds more like “half-private half-public” coins rather than “private coins.”  I understand that you call it private because the result of coin flips for prover 1 is not visible to prover 0 and vice versa.  However, it is not very private because the verifier cannot hide the result of coin flips for prover 1 from prover 1 (and the coin flips for prover 0 from prover 0), unlike the private coins in single-prover interactive proof systems.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-23T01:31:28.620Z
I hate the phrase "half-private half-public". How about semi-private?
Peter Shor 
CC BY-SA 2.5
2010-10-23T01:41:01.410Z
Also, if somebody has a better idea for a name for this type of game, feel free to suggest it. I'm not crazy about the name I came up with.
Peter Shor 
CC BY-SA 2.5
2010-10-23T07:19:45.410Z
call it 'facebook private' ;). you think it's private, but it's not
Suresh Venkat
CC BY-SA 2.5
2010-10-23T12:00:03.127Z
I was not claiming that the name “half-private half-public” was good; it was simply less confusing to me than calling it “private.”  “Semi-private” is a better name.  “Facebook private” is funny. :)
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-24T03:47:41.267Z
It appears to me that the Feige-Kilian proof cannot easily be adapted to answer this question.
Peter Shor 
CC BY-SA 2.5
2010-10-25T22:55:09.633Z
If the referee is allowed to make public announcements as a function of the public moves and the semi-private strings that seems sufficient to make the model as powerful as regular refereed games. This is because communication between the referee and the players can be encrypted using one-time pad. Ordinarily would use crypto to simulate the referee, but that doesn't work with computationally unbounded players.
Warren Schudy
CC BY-SA 2.5
2010-10-25T23:03:01.140Z
One example of this weaker type of refereed game is poker. (Approximately, since there is slight dependence between different player's hands.)
Warren Schudy
CC BY-SA 2.5
2010-10-25T23:14:22.457Z
"For example, if we change the game so the referee does not send messages, but only receives them from players 1 or 2 (and they are kept private from the other player), approximating the value of this game is still equivalent to RGUSP." Here's another equivalent variation. The referee gives the players semi-private coins at the beginning of the game, goes on a coffee break, and then returns when the game is done to judge the outcome from the public record of moves and the semi-private coins.
Warren Schudy
CC BY-SA 2.5
2010-10-25T23:27:39.450Z
If the players are provided a way to put a string in a sealed envelope at the beginning of the game then the referee needn't do anything until the end of the game. The semi-private strings can be simulated as the xor of what's in the envelope and an opposing player's move.
Warren Schudy
CC BY-SA 2.5
2010-10-26T01:17:33.680Z
What do you mean by “change the game so the referee does not send messages, but only receives them from players 1 or 2 (and they are kept private from the other player)”?  This sounds to me like succinct zero-sum games studied by [Fortnow, Impagliazzo, Kabanets and Umans 2008](http://www.springerlink.com/content/g58nm35xn8hp2673/), which is equivalent to (the promise version of) [S2P](http://qwiki.stanford.edu/index.php/Complexity_Zoo:S#s2p), which is inside the polynomial hierarchy (therefore cannot contain PSPACE unless something very surprising is proved).
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-26T01:35:50.693Z
@Tsuyoshi: I believe the difference is that in a succinct zero-sum games, the players don't also have $n$ rounds of public moves, which they play against each other with the referee watching. I'll edit my post to make it clearer.
Peter Shor 
CC BY-SA 2.5
2010-10-26T12:08:02.633Z
@Peter: Thanks for the clarification.  If part of the messages from the provers is public, I see that the situation is different from succinct zero-sum games.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-26T12:14:17.077Z
@Tsuyoshi: Of course, the techniques used in the succinct zero-sum game proof might still be useful for these.
Peter Shor 
<cc.complexity-theory><gt.game-theory><interactive-proofs>
Refereed games with uncorrelated semi-private coins
Peter Shor 
# Refereed games with uncorrelated semi-private coins

(Asked by: username_0 on 2010-10-22)

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](https://cstheory.stackexchange.com/questions/2353/complexity-of-hex-with-random-turn-order/2372). 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."](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.1990&rep=rep1&type=pdf)) 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)?

**Tags:** cc.complexity-theory, gt.game-theory, interactive-proofs
> **Comments:**
> **username_0**: One observation is that the referee only needs to give the players random coins at the beginning of the game. You can generate random coins for player 1 just before his move by taking some of his private random coins $r$ from the beginning of the game and XOR'ing them with a string $s$ supplied by player 2. It's easy to show that player 2 cannot do any better than choosing $s$ at random (in which case $s$ XOR $r$ is also random).  
> **username_1**: This sounds more like “half-private half-public” coins rather than “private coins.”  I understand that you call it private because the result of coin flips for prover 1 is not visible to prover 0 and vice versa.  However, it is not very private because the verifier cannot hide the result of coin flips for prover 1 from prover 1 (and the coin flips for prover 0 from prover 0), unlike the private coins in single-prover interactive proof systems.  
> **username_0**: I hate the phrase "half-private half-public". How about semi-private?  
> **username_0**: Also, if somebody has a better idea for a name for this type of game, feel free to suggest it. I'm not crazy about the name I came up with.  
> **username_2**: call it 'facebook private' ;). you think it's private, but it's not  
> **username_1**: I was not claiming that the name “half-private half-public” was good; it was simply less confusing to me than calling it “private.”  “Semi-private” is a better name.  “Facebook private” is funny. :)  
> **username_0**: It appears to me that the Feige-Kilian proof cannot easily be adapted to answer this question.  
> **username_3**: If the referee is allowed to make public announcements as a function of the public moves and the semi-private strings that seems sufficient to make the model as powerful as regular refereed games. This is because communication between the referee and the players can be encrypted using one-time pad. Ordinarily would use crypto to simulate the referee, but that doesn't work with computationally unbounded players.  
> **username_3**: One example of this weaker type of refereed game is poker. (Approximately, since there is slight dependence between different player's hands.)  
> **username_3**: "For example, if we change the game so the referee does not send messages, but only receives them from players 1 or 2 (and they are kept private from the other player), approximating the value of this game is still equivalent to RGUSP." Here's another equivalent variation. The referee gives the players semi-private coins at the beginning of the game, goes on a coffee break, and then returns when the game is done to judge the outcome from the public record of moves and the semi-private coins.  
> **username_3**: If the players are provided a way to put a string in a sealed envelope at the beginning of the game then the referee needn't do anything until the end of the game. The semi-private strings can be simulated as the xor of what's in the envelope and an opposing player's move.  
> **username_1**: What do you mean by “change the game so the referee does not send messages, but only receives them from players 1 or 2 (and they are kept private from the other player)”?  This sounds to me like succinct zero-sum games studied by [Fortnow, Impagliazzo, Kabanets and Umans 2008](http://www.springerlink.com/content/g58nm35xn8hp2673/), which is equivalent to (the promise version of) [S2P](http://qwiki.stanford.edu/index.php/Complexity_Zoo:S#s2p), which is inside the polynomial hierarchy (therefore cannot contain PSPACE unless something very surprising is proved).  
> **username_0**: @Tsuyoshi: I believe the difference is that in a succinct zero-sum games, the players don't also have $n$ rounds of public moves, which they play against each other with the referee watching. I'll edit my post to make it clearer.  
> **username_1**: @Peter: Thanks for the clarification.  If part of the messages from the provers is public, I see that the situation is different from succinct zero-sum games.  
> **username_0**: @Tsuyoshi: Of course, the techniques used in the succinct zero-sum game proof might still be useful for these.  
> **username_0**: I think Magic: The Gathering (and probably other collectible card games) are perfect examples of this weaker type of refereed game. I don't play Magic, but each player has a deck, and the players start by shuffling their own deck, so all the randomness is uncorrelated.  

---

## 1 answers

### Answer by username_0 on 2010-12-08. Score: 12

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.


---

