A two-player game is an important construct used in proving many hardness of approximation results. It consists of two non-communicating players, Alice and Bob, trying to win against a verifier $V$, who draws a question pair $(x,y) \in X \times Y$ from a known distribution $D$ and sends $x$ to Alice and $y$ to Bob. The goal of Alice and Bob is to come up with strategies to provide answers ($a(x), b(y)$ resp.) to these questions, in order to win (decided by a predicate V(x,y,a,b)) with maximum probability over $D$. This maximum probability is called the value of the game.
Raz first showed that repeating a two-player game in parallel $n$-times (where $n$ question pairs are drawn independently and given to the players simultaneously) drives down the probability of the players winning all the rounds exponentially with $n$. A series of subsequent works improved the parameters involved, and current known results are near-optimal.
In contrast to two-player games, very little is known about the parallel-repetition of games with $k$ players for $k\geq 3$. The only known universal upper bound on the value of a $n$-repeated, $k$-player game is due to Verbitsky; it shows a weak inverse-Ackermann decay with regards to $n$. Some special classes of multi-player games (free games and anchored games) have been shown to exhibit exponential decay in value. The technical roadblock in extending known proofs for $k=2$ to $k \geq 3$ is similar to one encountered in proving direct product results in communication complexity with 3 or more players.
In this work, we show that under $n$-fold repetition, a large class of $k$-player games do, in fact, exhibit an exponential decay in value. These games are expanding in a specific sense. Our result recovers exponential decay theorems for free and anchored games as a corollary. We also point out a simple game not handled by the above class, and conjecture that it is in fact, the hardest case (oint work with Irit Dinur, Prahladh Harsha and Henry Yuen).
