The parallel repetition of non-signaling games: counterexamples and dichotomy
The parallel repetition of non-signaling games: counterexamples and dichotomy
复制标题
非信号博弈的并行重复：反例和二分法
DOI：
10.1145/3313276.3316367
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Lisa Yang
中科院分区：
文献类型：
--
作者：
Justin Holmgren;Lisa Yang
非信号游戏是在计算理论中的重要对象，因为它们在量子信息和（经典）加密中的作用。对于古典游戏和两人非信号游戏的情况，都有K-玩家的非信号游戏（对于K≥3），其价值不倾向于以足够的平行重复。有时，我们表明，在平行重复下的每个游戏的不信号值都不会降低其价值。 Game的子信号值（Lancien and Winter，CJTCS '16）小于1。
Non-signaling games are an important object of study in the theory of computation, for their role both in quantum information and in (classical) cryptography. In this work, we study the behavior of these games under parallel repetition. We show that, unlike the situation both for classical games and for two-player non-signaling games, there are k-player non-signaling games (for k ≥ 3) whose values do not tend to 0 with sufficient parallel repetition. In fact, parallel repetition sometimes does not decrease their value whatsoever. We show that in general, every game’s non-signaling value under parallel repetition is either lower bounded by a positive constant or decreases exponentially with the number of repetitions. Furthermore, exponential decrease occurs if and only if the game’s sub-non-signaling value (Lancien and Winter, CJTCS ’16) is less than 1.