We prove that for every 3-player (3-prover) game, with binary questions and answers and value less than $1$, the value of the $n$-fold parallel repetition of the game decays polynomially fast to $0$. That is, for every such game, there exists a constant $c>0$, such that the value of the $n$-fold parallel repetition of the game is at most $n^{-c}$.
Along the way to proving this theorem, we prove two additional parallel repetition theorems for multiplayer (multiprover) games, that may be of independent interest:
$\textbf{Playerwise Connected Games (with any number of players and any Alphabet size):}$ We identify a large class of multiplayer games and prove that for every game with value less than $1$ in that class, the value of the $n$-fold parallel repetition of the game decays polynomially fast to $0$.
More precisely, our result applies for $\textit{playerwise connected games}$, with any number of players and any alphabet size:
For each player $i$, we define the graph $G_i$, whose vertices are the possible questions for that player and two questions $x,x'$ are connected by an edge if there exists a vector $y$ of questions for all other players, such that both $(x,y)$ and $(x',y)$ are asked by the referee with non-zero probability. We say that the game is $\textit{playerwise connected}$ if for every $i$, the graph $G_i$ is connected.
Our class of playerwise connected games is strictly larger than the class of connected games that was defined in [DHVY17] and for which exponentially fast decay bounds are known [DHVY17]. For playerwise connected games that are not connected, only inverse Ackermann decay bounds were previously known [Ver96].
$\textbf{Exponential Bounds for the Anti-Correlation Game:}$ In the 3-player $\textit{anti-correlation game}$, two out of three players are given $1$ as input, and the remaining player is given $0$. The two players who were given $1$ must produce different outputs in $\{0,1\}$. We prove that the value of the $n$-fold parallel repetition of that game decays exponentially fast to $0$. That is, there exists a constant $c>0$, such that the value of the $n$-fold parallel repetition of the game is at most $2^{-cn}$. Only inverse Ackermann decay bounds were previously known [Ver96].
The 3-player anti-correlation game was studied and motivated in several previous works. In particular, Holmgren and Yang gave it as an example for a 3-player game whose non-signaling value (is smaller than $1$ and yet) does not decrease at all under parallel repetition [HY19].
