文章基本信息

标题：On the Parallel Repetition of Multi-Player Games: The No-Signaling Case
本地全文：下载
作者：Harry Buhrman ; Serge Fehr ; Christian Schaffner 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：27
页码：24-35
DOI：10.4230/LIPIcs.TQC.2014.24
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider the natural extension of two-player nonlocal games to an arbitrary number of players. An important question for such nonlocal games is their behavior under parallel repetition. For two-player nonlocal games, it is known that both the classical and the non-signaling value of any game converges to zero exponentially fast under parallel repetition, given that the game is non-trivial to start with (i.e., has classical/non-signaling value 0). Our parallel repetition theorem for multi-player games is weaker than the known parallel repetition results for two-player games in that the rate at which the non-signaling value of the game decreases not only depends on the non-signaling value of the original game (and the number of possible responses), but on the complete description of the game. Nevertheless, we feel that our result is a first step towards a better understanding of the parallel repetition of nonlocal games with more than two players.
关键词：Parallel repetition; non-signaling value; multi-player non-local games