Multiplayer Parallel Repetition for Expanding Games

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).