Has anyone analyzed multi-round nonlocal games?

Question

The traditional definition of a nonlocal game is restricted to having two players and one round (e.g., here), but it is natural to consider a more general class of games that may have more than two players and more than one round of questions. While there has been a lot of work dealing with games with more than two players, I have found very little on multi-round games. For instance, there is a recent preprent of Crépeau and Yang that gives a definition of a multi-party, multi-round non-signaling distribution and seems to describe a multi-round game (although the paper is written in the language of commitment schemes rather than games, so I'm not entirely sure my interpretation is correct).

Has there been any other work dealing with multi-round games? And is there a reason so much of the literature has focused on single-round games? Are multi-round games inherently "no more interesting" than single-round games from the perspective of understanding nonlocality?

Answer 1

It seems that using more rounds will not be such helpful for us to get something more powerful from complexity perspectives. There are a few comments about the number of rounds and the number of players for $\mathsf{MIP}^*$ in Thomas Vidick's lecture note regarding quantum mutli-prover interactive proofs. Note that the non-local games are $\mathsf{MIP^*}$ protocols.

• If we allow an extra prover and quantum messages (i.e. a $\mathsf{QMIP^*}$ protocol), then non-local games with polynomially many rounds can be parallelized to one round, which it proved by Kempe-Kobayashi-Matsumoto-Vidick. But as @John Watrous mentioned, we don't know how to do that for non-local games with classical messages, i.e. $\mathsf{MIP^*}$ protocol.

More details see section 6.3.2 in Watrous-Vidick's survey about quantum proofs, or the KKMV paper mentioned above.

• But we did not know something similar for the number of provers, even the following could be true $\mathsf{MIP^*}(2,\mathrm{poly}) \subsetneq \mathsf{MIP^*}(3,\mathrm{poly}) \subsetneq \cdots$, where $\mathsf{MIP^*}(r,k)$ denote $r$-round $k$-prover non-local games. Namely, we may get something more powerful by adding new provers.