2014/10/16 by André Chailloux, Chailloux, André, Scarpa, Giannicola
Computer Science · Decision Sciences · #Artificial Intelligence in Games #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Evolutionary Algorithms and Applications #FOS: Physical sciences #Game Theory and Applications #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1410.4397
openalex publication_date 2014/10/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a two-player game, two cooperating but non communicating players, Alice and Bob, receive inputs taken from a probability distribution. Each of them produces an output and they win the game if they satisfy some predicate on their inputs/outputs. The entangled value ω^*(G) of a game G is the maximum probability that Alice and Bob can win the game if they are allowed to share an entangled state prior to receiving their inputs. The n-fold parallel repetition Gn of G consists of n instances of G where Alice and Bob receive all the inputs at the same time and must produce all the outputs at the same time. They win Gn if they win each instance of G. Recently, there has been a series of works showing parallel repetition with exponential decay for projection games [DSV13], games on the uniform distribution [CS14] and for free games, i.e. games on a product distribution [JPY13]. This article is meant to be a follow up of [CS14], where we improve and simplify several parts of our previous paper. Our main result is that for any free game G with value ω^*(G)=1-ε, we have ω^*(Gn) ≤ (1 - ε2)Ω((n)/(log(l))) where l is the size of the output set of the game. This result improves on both the results in [JPY13] and [CS14]. The framework we use can also be extended to free projection games. We show that for a free projection game G with value ω^*(G)=1-ε, we have ω^*(Gn) ≤ (1 - ε)Ω(n).