Rakesh Venkat

Phani Raj Lolakapuri

Friday, 24 Feb 2017, 16:00 to 17:30

A-201 (STCS Seminar Room)

Abstract

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

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

© Copyright 2023, School of Technology and Computer Science | TIFR - All Rights Reserved | Login