论文标题
通过二进制字母的所有三个玩家游戏的平行重复
Parallel Repetition For All 3-Player Games Over Binary Alphabet
论文作者
论文摘要
我们证明，对于每三个玩家游戏，带有二进制问题，答案和价值$ <1 $，$ n $ flold的平行重复的价值在多项单位上衰落至0。也就是说，对于每一个这样的游戏，都存在$ c> 0 $的常数$ c> 0 $，因此，$ n $ n $ - fold-fold-fold-fold paratele the游戏的价值是$ n $ $ n^$ $ n^$ c。在证明该定理的过程中，我们证明了多人游戏的另外两个并行重复定理，这可能具有独立的兴趣： PlayerWise连接的游戏（带有任何数量的玩家和任何字母尺寸）：我们确定了一大批多人游戏游戏，并证明，该游戏中的每个游戏中的每个游戏中，该类别的价值<1 $，$ n $ fold-fold-fold平行游戏的价值在多面地是多面地衰减的，从而快速地衰减到0。 PlayerWise连接的游戏类别严格比[DHVY17]中定义的连接游戏类别更大，并且已知快速衰减的界限[DHVY17]。对于未连接的PlayerWise连接的游戏，以前仅知道逆Ackermann衰减界限[Ver96]。 反相关游戏的指数界限：在三人反相关游戏中，三分之二的玩家被赋予$ 1 $作为输入，剩下的玩家将获得$ 0 $。获得$ 1 $的两个玩家必须以$ \ {0,1 \} $产生不同的输出。我们证明，该游戏的$ n $折叠并行重复的价值呈指数速度衰减至0。只有倒数的Ackermann衰减范围以前是已知的[Ver96]。该游戏在以前的几部作品中被研究和动机。特别是，霍姆格伦（Holmgren）和杨（Yang）以3播放器游戏为例，其非信号值（小于1且尚未达到1）并不能在平行重复下完全减少[HY19]。
We prove that for every 3-player game with binary questions and answers and value $<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 games, that may be of independent interest: 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 $<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 playerwise connected games, with any number of players and any alphabet size. The 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]. Exponential Bounds for the Anti-Correlation Game: In the 3-player 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. Only inverse Ackermann decay bounds were previously known [Ver96]. This 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].
