Finitely repeated games with finite automata

The paper studies the implications of bounding the complexity of the strate gies players may select, on the set of equilibrium payoffs in repeated game s. The complexity of a strategy is measured by the size of the minimal auto mation that can implement it. A finite automation 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 a transition function changing the state of the automaton as a function of it s current state and the present actions of the other players. The size of a n automaton is its number of slates. The main results imply in particular that in two person repeated games, the set of equilibrium payoffs of a sequence of such games, G(n), n = 1, 2, .. . , converges as n goes to infinity to the individual rational and feasible payoffs of the one shot game, whenever the bound on one of the two automat a sizes is polynomial or subexponential in ii and both, the length of the g ame and the bounds of the automata sizes are at least n. A special case of such result justifies cooperation in the finitely repeate d prisoner's dilemma, without departure from strict utility maximization or complete information, but under the assumption that there are bounds (poss ibly very large) to the complexity of the strategies that the players may u se.