Alladi Ramakrishnan Hall

Multiplayer Parallel Repetition for Expanding Games

Rakesh Venkat

TIFR

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 sends them questions (x,y) resp., drawn from a known distribution D. 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 game in parallel n-times (where n question pairs are drawn independently and given to the players) 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>=3.  The only known upper bound  on the value of a  n-repeated, k-player game is due to Verbitsky; and it follows a weak Inverse-Ackermann(n) decay.  Some special classes of games (free and anchored) have been shown to have exponential decay in value w.r.t. n. The technical roadblock  in extending known proofs for k=2  to k>=3 is similar to one encountered in proving direct product results in communication complexity with >=3 players.

In this work, we show that under n-fold repetition, a large class of multiplayer 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.
 (Joint work with Irit Dinur, Prahladh Harsha and Henry Yuen).