11/07 lecture -- the Feige NA counterexample
There was a little confusion in class over Feige's "NA" game which shows that omega(NA^k) = omega(NA)^k doesn't strictly hold for parallel repetition of 2P1R games. I just thought I'd repost the example here in case people wanted to stare at it.
The (1 round) Noninteractive Agreement (NA) game:
Note 2: omega(NA) = 1/2. The fact that Anna and Venkat can succeed with probability at least 1/2 is obvious (say, Anna always claims about her own coin, and Venkat always claims "Anna got sent the coin 0"; then they win whenever Anna gets sent the coin 0 -- probability 1/2).
The argument that this is the best they can do is the following: Suppose each player always make a claim about the other's coin. Then of course their claims never agree with each other and they never succeed. So we can assume (without loss of generality) that, say, Anna, sometimes makes a claim about her own coin; (WOLOG, again) suppose Anna's strategy includes claiming "Anna got sent the coin 0" whenever she gets sent the coin 0. In this case, I claim that if Venkat gets sent the coin 0 then no matter what his strategy is, there is failure with probability 1/2; and, I also claim the same is true if Venkat gets sent the coin 1. If I can show both of these, then of course overall the players can succeed with probability at most 1/2.
So suppose Venkat gets sent the coin 0. If his strategy is to claim "Anna got sent the coin 0", then whenever it also holds that Anna gets sent 1 (probability 1/2), the players lose; this is because Venkat's claim will not agree with reality. On the other hand, if Venkat's strategy in this case is to claim anything else, then the players lose whenever it also holds that Anna gets sent 0 (probability 1/2) -- because we assume she claims "Anna got sent the coin 0" in this case, so the players' claims will disagree.
The exact same argument holds for the case that Venkat gets sent the coin 1; literally, just change the first sentence in the above paragraph.
----------------------------------------------------------
So we've shown that omega(NA) = 1/2. Let's now show that omega(NA^2) = 1/2.
The proof that omega(NA^2) is at most 1/2 is trivial: In fact, for any game G and for any k, omega(G^k) is at most omega(G). The reason is, if the players are going to win on the k-repeated version of the game, they certainly have to win in, say, the first coordinate. But the probability that they even win in the first coordinate is just omega(G).
To show that omega(NA^2) is at least 1/2, we have to give a strategy for Anna and Venkat.
Now the NA^2 game is a little confusing; let's recap what it is. In this game, Ryan flips two coins for Anna and two coins for Venkat. Let's call Anna's two coins her "round 1 coin" and her "round 2 coin", and similarly for Venkat. Now this terminology is kind of misleading, since all questions get asked in one shot; i.e., Anna gets asked sent her round 1 coin and her round 2 coin simultaneously, and the same for Venkat. Better terminology might be "coordinate 1 coin" and "coordinate 2 coin" or even "red coin" and "blue coin". But let me stick with "round 1 coin" and "round 2 coin".
Both players have to send back an answer of the following two-part format: "So-and-so's round 1 coin was such-and-such; AND whose-it's round 2 coin was thus-and-such." I.e., both players must make a claim about somebody's round 1 coin and also a claim about somebody's round 2 coin. The players win if their claims totally agree with each other and the claims totally agree with reality.
That's the game NA^2; here is the strategy: Both players always claim about Anna's round 1 coin and they both always claim about Venkat's round 2 coin. So at least their claims are guaranteed to be in agreement in terms of the So-and-sos/whose-its. Naturally, to be consistent with reality, the round 1 part of Anna's claim will correctly be about her round 1 coin, and the round 2 half of Venkat's claim will correctly be about his round 2 coin. So each player has half of a claim left to make. The idea is that the players will operate under the assumption that Anna's round 1 coin equals Venkat's round 2 coin. This lets us finish saying the strategies -- the round 2 half of Anna's claim will be "Venkat's round 2 coin equals [whatever her round 1 coin is]" (which she knows), and the round 1 part of Venkat's claim will be "Anna's round 1 coin equals [whatever his round 2 coin is]" (which he knows).
This properly defines Anna and Venkat's strategy, and indeed they succeed completely (i.e. their claims agree with each other and with reality 100%) whenever Anna's round 1 coin equals Venkat's round 2 coin. This happens with probability 1/2.
The (1 round) Noninteractive Agreement (NA) game:
- There are two players, Anna and Venkat.
- The verifier, Ryan, flips a random coin and sends it to Anna, and flips another random coin and sends it to Venkat.
- Venkat and Anna both have to answer with a claim of the form "So-and-so got sent the coin such-and-such" (where So-and-so in {Anna, Venkat}, such-and-such in {0,1}; so, answer set is of size 4.)
- The players win if a) they make the same claim, and b) the claim agrees with reality.
Note 2: omega(NA) = 1/2. The fact that Anna and Venkat can succeed with probability at least 1/2 is obvious (say, Anna always claims about her own coin, and Venkat always claims "Anna got sent the coin 0"; then they win whenever Anna gets sent the coin 0 -- probability 1/2).
The argument that this is the best they can do is the following: Suppose each player always make a claim about the other's coin. Then of course their claims never agree with each other and they never succeed. So we can assume (without loss of generality) that, say, Anna, sometimes makes a claim about her own coin; (WOLOG, again) suppose Anna's strategy includes claiming "Anna got sent the coin 0" whenever she gets sent the coin 0. In this case, I claim that if Venkat gets sent the coin 0 then no matter what his strategy is, there is failure with probability 1/2; and, I also claim the same is true if Venkat gets sent the coin 1. If I can show both of these, then of course overall the players can succeed with probability at most 1/2.
So suppose Venkat gets sent the coin 0. If his strategy is to claim "Anna got sent the coin 0", then whenever it also holds that Anna gets sent 1 (probability 1/2), the players lose; this is because Venkat's claim will not agree with reality. On the other hand, if Venkat's strategy in this case is to claim anything else, then the players lose whenever it also holds that Anna gets sent 0 (probability 1/2) -- because we assume she claims "Anna got sent the coin 0" in this case, so the players' claims will disagree.
The exact same argument holds for the case that Venkat gets sent the coin 1; literally, just change the first sentence in the above paragraph.
----------------------------------------------------------
So we've shown that omega(NA) = 1/2. Let's now show that omega(NA^2) = 1/2.
The proof that omega(NA^2) is at most 1/2 is trivial: In fact, for any game G and for any k, omega(G^k) is at most omega(G). The reason is, if the players are going to win on the k-repeated version of the game, they certainly have to win in, say, the first coordinate. But the probability that they even win in the first coordinate is just omega(G).
To show that omega(NA^2) is at least 1/2, we have to give a strategy for Anna and Venkat.
Now the NA^2 game is a little confusing; let's recap what it is. In this game, Ryan flips two coins for Anna and two coins for Venkat. Let's call Anna's two coins her "round 1 coin" and her "round 2 coin", and similarly for Venkat. Now this terminology is kind of misleading, since all questions get asked in one shot; i.e., Anna gets asked sent her round 1 coin and her round 2 coin simultaneously, and the same for Venkat. Better terminology might be "coordinate 1 coin" and "coordinate 2 coin" or even "red coin" and "blue coin". But let me stick with "round 1 coin" and "round 2 coin".
Both players have to send back an answer of the following two-part format: "So-and-so's round 1 coin was such-and-such; AND whose-it's round 2 coin was thus-and-such." I.e., both players must make a claim about somebody's round 1 coin and also a claim about somebody's round 2 coin. The players win if their claims totally agree with each other and the claims totally agree with reality.
That's the game NA^2; here is the strategy: Both players always claim about Anna's round 1 coin and they both always claim about Venkat's round 2 coin. So at least their claims are guaranteed to be in agreement in terms of the So-and-sos/whose-its. Naturally, to be consistent with reality, the round 1 part of Anna's claim will correctly be about her round 1 coin, and the round 2 half of Venkat's claim will correctly be about his round 2 coin. So each player has half of a claim left to make. The idea is that the players will operate under the assumption that Anna's round 1 coin equals Venkat's round 2 coin. This lets us finish saying the strategies -- the round 2 half of Anna's claim will be "Venkat's round 2 coin equals [whatever her round 1 coin is]" (which she knows), and the round 1 part of Venkat's claim will be "Anna's round 1 coin equals [whatever his round 2 coin is]" (which he knows).
This properly defines Anna and Venkat's strategy, and indeed they succeed completely (i.e. their claims agree with each other and with reality 100%) whenever Anna's round 1 coin equals Venkat's round 2 coin. This happens with probability 1/2.
posted by Ryan O'Donnell at 12:03 PM
0 Comments:
Post a Comment
<< Home