Cooperation, Repetition, and Automata

This chapter studies the implications of bounding the complexity of players’ strategies in long term interactions. The complexity of a strategy is measured by the size of the minimal automaton that can implement it.A finite automaton has a finite number of states and an initial state. It prescribes the action to be taken as a function of the current state and its next state is a function of its current state and the actions of the other players. The size of an automaton is its number of states.The results study the equilibrium payoffs per stage of the repeated games when players’ strategies are restricted to those implement able by automata of bounded size.