Playing repeated games with sublinear randomness

Abstract

We study the amount of entropy players asymptotically need to play a repeated normal-form game in a Nash equilibrium. Hubáček, Naor, and Ullman (SAGT'15, TCSys'16) gave sufficient conditions on a game for the minimal amount of randomness required to be $O(1)$ or $\Omega (n)$ for all players, where $n$ is the number of repetitions. We provide a complete characterization of games in which there exists Nash equilibria of the repeated game using $O(1)$ randomness, closing an open question posed by Budinich and Fortnow (EC'11) and Hubáček, Naor, and Ullman. Moreover, we show a 0--1 law for randomness in repeated games, showing that any repeated game either has $O(1)$-randomness Nash equilibria, or all of its Nash equilibria require $\Omega (n)$ randomness. Our techniques are general and naturally characterize the payoff space of sublinear-entropy equilibria, and could be of independent interest to the study of players with other bounded capabilities in repeated games.

31 pages