On games of incomplete information (Q1199525): Difference between revisions

We study two-person games of cooperation and multi-prover interactive proof systems. We consider a two-person game \(G\), which we call a free game, defined as follows. A Boolean function \(\phi_ G\) is given. Player I and II each pick a random number \(i\) and \(j\) in private, where \(1\leq i\), \(j\leq s\), and then each chooses a private number \(f(i)\) and \(g(j)\), \(1\leq f(i)\), \(g(j)\leq s\). If \(\phi_ G(i,j,f(i),g(j))=1\), then both players win, otherwise they lose. The objective of both players is to win collectively. We ask whether, if such a game is played \(n\) times in parallel, the probability of winning all the games decays exponentially in \(n\). Intuitively, we might first expect that \(w(G^ n)\) is \(w(G)^ n\); since all \(n\) instances of game \(G\) are drawn independently, and if the players play all instances independently, the winning probability of the \(n\)-product game is \(w(G)^ n\). However, before this work, it was unknown even if \(w(G^ n)\to 0\) as \(n\to\infty\). The first result of this paper is that the winning probability of the product game \(G^ n\) converges to 0 exponentially fast as \(n\to\infty\). Theorem. If \(G\) is a non-trivial free game, then there exists a \(q<1- e^{-3s}/2\) such that the winning probability of \(G^ n\) is at most \(2eq^ n\). We also discuss applications to multiprover interactive proof systems. Since this work first appeared, there have been many new results on multi-prover interactive proof systems and two-person games of cooperation. In particular, the authors solved the motivating problem of the current paper, namely any unbounded round single prover interactive proof system can be simulated by a bounded round two prover interactive proof system.