Two Player Games and Playing Them in Parallel

Consider a 2-player game defined as follows. A referee sends a pair of questions x and y to two players Alice and Bob and accepts if their answers a and b satisfy some predicate. The 2 players are not allowed to communicate once the game commences, however can share some prior randomness, quantum entanglement etc. We will begin by seeing examples of games in which the players have different optimal strategies depending on what they share: randomness, entanglement, no-signalling strategies, etc.

We will then consider the parallel repetition of games and ask if the players have an advantage over answering each of the repetitions independently. Surprisingly, we will show examples of games in which the players have an advantage by co-ordinating their answers across repetitions. Finally, we will show time permitting, we will see some applications of parallel repetition to theoretical computer science.

Image from: Andreas Winter, "Quantum mechanics: The usefulness of uselessness", Nature 466, 1053–1054, Aug 2010.