2023/12/20 by Arthaud, Farid
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2312.13453
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 Ω(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 Ω(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.