Paper Info
Title
The structure of winning strategies in parallel repetition games
Abstract
Given a function f: X → Σ, its l-wise direct product is the function F = fl: Xl → Σl defined by F(x1,..., xl) = (f(x1),...,f(xl)). A two prover game G is a game that involves 3 participants: V,A, and B. V picks a random pair (x, y) and sends x to A, and y to B. A responds with f(x), B with g(y). A, B win if V(x, y, f(x), g(y)) = 1. The repeated game Gl is the game where A, B get l questions in a single round and each of them responds with an l symbol string (this is also called the parallel repetition of the game). A, B win if they win each of the questions. In this work we analyze the structure of the provers that win the repeated game with non negligible probability. We would like to deduce that in such a case A, B must have a global structure, and in particular they are close to some direct product encoding. A similar question was studied by the authors and by Impagliazzo et. al. in the context of testing Direct Product. Their result can be be interpreted as follows: For a specific game G, if A, B win Gl with non negligible probability, then A, B must be close to be a direct product encoding. We would like to generalize these results for any 2-prover game. In this work we prove two main results: In the first part of the work we show that for a certain type of games, there exist A, B that win the repeated game with non negligible probability yet are still very far from any Direct Product encoding. In contrast, in the second part of the work we show that for a certain type of games, called "miss match" games, we have the following behavior. Whenever A, B win non negligibly then they are both close to a Direct Product strategy.
Year
DOI
Venue
2010
10.1007/978-3-642-15369-3_39
APPROX-RANDOM
Keywords
Field
DocType
non negligible probability,whenever a,parallel repetition game,2-prover game,prover game g,direct product,certain type,b. a,specific game,direct product encoding,repeated game
Discrete mathematics,Global structure,Direct product,Symbol,Algorithm,Repeated game,Gas meter prover,Mathematics,Encoding (memory)
Conference
Volume
ISSN
ISBN
6302
0302-9743
3-642-15368-2
Citations 
PageRank 
References 
2
0.36
12
Authors
2
Name
Order
Citations
PageRank
Irit Dinur1118785.67
Elazar Goldenberg2171.45