4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.