License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2014.24
URN: urn:nbn:de:0030-drops-48034
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4803/
Buhrman, Harry ;
Fehr, Serge ;
Schaffner, Christian
On the Parallel Repetition of Multi-Player Games: The No-Signaling Case
Abstract
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 < 1). Very recent results show similar behavior of the quantum value of a two-player game under parallel repetition. For nonlocal games with three or more players, very little is known up to present on their behavior under parallel repetition; this is true for the classical, the quantum and the non-signaling value.
In this work, we show a parallel repetition theorem for the non-signaling value of a large class of multi-player games, for an arbitrary number of players. Our result applies to all multi-player games for which all possible combinations of questions have positive probability; this class in particular includes all free games, in which the questions to the players are chosen independently. Specifically, we prove that if the original game G has a non-signaling value v_{ns}(G) < 1, then the non-signaling value of the n-fold parallel repetition is exponentially small in n. Stronger than that, we prove that the probability of winning more than (v_{ns}(G) + delta) * n parallel repetitions is exponentially small in n (for any delta > 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.
BibTeX - Entry
@InProceedings{buhrman_et_al:LIPIcs:2014:4803,
author = {Harry Buhrman and Serge Fehr and Christian Schaffner},
title = {{On the Parallel Repetition of Multi-Player Games: The No-Signaling Case}},
booktitle = {9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
pages = {24--35},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-73-6},
ISSN = {1868-8969},
year = {2014},
volume = {27},
editor = {Steven T. Flammia and Aram W. Harrow},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4803},
URN = {urn:nbn:de:0030-drops-48034},
doi = {10.4230/LIPIcs.TQC.2014.24},
annote = {Keywords: Parallel repetition, non-signaling value, multi-player non-local games}
}
|
Keywords: |
|
Parallel repetition, non-signaling value, multi-player non-local games |
|
Collection: |
|
9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) |
|
Issue Date: |
|
2014 |
|
Date of publication: |
|
11.12.2014 |
