For some background, a nonlocal game consists of questions $x,y\in X,Y$ and answers $a,b \in A,B$; the pair of questions $x,y$ is asked with probability $\mu(x,y)$, and a referee accepts the pair of answers $a,b$ for the pair of questions $x,y$ with probability $V(a,b,x,y)$. This function $V:A \times B \times X \times Y \to [0,1]$ is the predicate of the nonlocal game. The case I just defined is the most general one, of a probabilistic predicate. Usually, though, papers deal with only with the case of deterministic predicates, where $V(a,b,x,y)$ is always either $0$ or $1$, so the referee simply accepts of rejects a given answer pair for a given question pair.

What I want to know is who first studied nonlocal games with probabilistic predicate. Cleve et al., who pretty much started the are, only defines games with deterministic predicate. The earliest reference I know that talks about games with probabilistic predicate is Buhrman et al.. It doesn't seem to be the first one, though, they talk as if the concept is already known.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.