Parallel repetition for all 3-player games over binary alphabet

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We prove that for every 3-player (3-prover) 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 (multiprover) 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: For each player i, we define the graph Gi, whose vertices are the possible questions for that player and two questions x,x′ are connected by an edge if there exists a vector y of questions for all other players, such that both (x,y) and (x′,y) are asked by the referee with non-zero probability. We say that the game is playerwise connected if for every i, the graph Gi is connected. Our class of playerwise connected games is strictly larger than the class of connected games that was defined by Dinur, Harsha, Venkat and Yuen (ITCS 2017) and for which they proved exponential decay bounds on the value of parallel repetition. For playerwise connected games that are not connected, only inverse Ackermann decay bounds were previously known (Verbitsky 1996). 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. That is, there exists a constant c>0, such that the value of the n-fold parallel repetition of the game is at most 2-c n. Only inverse Ackermann decay bounds were previously known (Verbitsky 1996). The 3-player anti-correlation game was studied and motivated in several previous works. In particular, Holmgren and Yang (STOC 2019) 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.

Original languageEnglish (US)
Title of host publicationSTOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
EditorsStefano Leonardi, Anupam Gupta
PublisherAssociation for Computing Machinery
Pages998-1009
Number of pages12
ISBN (Electronic)9781450392648
DOIs
StatePublished - Sep 6 2022
Event54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 - Rome, Italy
Duration: Jun 20 2022Jun 24 2022

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022
Country/TerritoryItaly
CityRome
Period6/20/226/24/22

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Multiplayer Games
  • Parallel Repetition

Fingerprint

Dive into the research topics of 'Parallel repetition for all 3-player games over binary alphabet'. Together they form a unique fingerprint.

Cite this