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.ITCS.2017.37
URN: urn:nbn:de:0030-drops-81575
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8157/
Dinur, Irit ;
Harsha, Prahladh ;
Venkat, Rakesh ;
Yuen, Henry
Multiplayer Parallel Repetition for Expanding Games
Abstract
We investigate the value of parallel repetition of one-round games with any number of players k>=2. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games.
Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are *connected* in a certain sense.
We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.
BibTeX - Entry
@InProceedings{dinur_et_al:LIPIcs:2017:8157,
author = {Irit Dinur and Prahladh Harsha and Rakesh Venkat and Henry Yuen},
title = {{Multiplayer Parallel Repetition for Expanding Games}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {37:1--37:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8157},
URN = {urn:nbn:de:0030-drops-81575},
doi = {10.4230/LIPIcs.ITCS.2017.37},
annote = {Keywords: Parallel Repetition, Multi-player, Expander}
}
|
Keywords: |
|
Parallel Repetition, Multi-player, Expander |
|
Collection: |
|
8th Innovations in Theoretical Computer Science Conference (ITCS 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
28.11.2017 |
