Pseudorandom Processes: Entropy And Automata

This paper studies implementation of cooperative payoffs in finitely repeated games when players implement their strategies by finite automata of big sizes. Specifically, we analyze how much we have to depart from fully rational behavior to achieve the Folk Theorem payoffs, i.e., which are the maximum bounds on automata complexity which yield cooperative behavior in long but not infinite interactions. To this end we present a new approach to the implementation of the mixed strategy equilibrium paths leading to cooperation. The novelty is to offer a new construction of the set of the pure strategies which belong to the mixed strategy equilibrium. Thus, we consider the subset of strategies which is characterized by both the complexity of the finite automata and the entropy associated to the underlying coordination process. The equilibrium play consists of both a communication phase and the play of a cycle which depends on the chosen message. The communication set is designed by tools of Information Theory. Moreover, the characterization of this set is given by the complexity of the weaker player that implements the equilibrium play. We offer a domain of definition of the smallest automaton which includes previous domains in the literature.