Playing Repeated Games with Sublinear Randomness

The seminal result of Nash in game theory states that any normal-form game has a Nash equilibrium if each player can randomize their strategy. The assumption that players can randomize arbitrarily is non-trivial, as true randomness might be scarce or costly and humans are known to have difficulty generating truly random sequences. In a repeated game, the assumption that players are unconstrained in their capability to randomize their strategies is particularly strong if the amount of random bits required to play the repeated game scales linearly with the number of repetitions. We identify conditions on a normal-form game under which, if players have a limited capability to randomize, certain Nash equilibria of its finitely repeated version cannot be played. We provide a complete characterization of normal-form games for which there exists Nash equilibria of its finitely repeated version using O(1) randomness, closing an open question posed by Budinich and Fortnow [3] (EC ’11) and Hubáček, Naor and Ullman [8] (SAGT ’15, TCSys ’16). Moreover, we prove 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 \(\varOmega (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.