An Anti-Folk Theorem for Large Repeated Games with Imperfect Monitoring

Mallesh M Pai, Aaron Roth, Jonathan Ullman

[arXiv]

We study infinitely repeated games in settings of imperfect monitoring. We first prove a family of theorems that show that when the signals observed by the players satisfy a condition known as (epsilon,gamma)-differential privacy, that the folk theorem has little bite: for values of epsilon and gamma sufficiently small, for a fixed discount factor, any equilibrium of the repeated game involve players playing approximate equilibria of the stage game in every period. Next, we argue that in large games (n player games in which unilateral deviations by single players have only a small impact on the utility of other players), many monitoring settings naturally lead to signals that satisfy (epsilon,gamma)-differential privacy, for epsilon and gamma tending to zero as the number of players n grows large. We conclude that in such settings, the set of equilibria of the repeated game collapse to the set of equilibria of the stage game.