Repeated games with Finite Automata
The paper examines the asymptotic behavior of the set of equilibrium payoffs in a repeated game when there are bounds on the complexity of the strategies players may select. The complexity of a strategy is measured by the size of the minimal automaton that can implement it. The main result is that in a zero—sum game, when the size of the automata of both players go together to infinity, the sequence of values converges to the value of the one—shot game. This is true even if the size of the automata of one player is a polynomial of the size of the automata of the other player. The result for the zero—sum games gives an estimation for the general case.