Strategic Complexity in Repeated Extensive Games

This paper studies a two-player machine (finite automaton) game in which an extensive game with perfect information is infinitely repeated. We introduce a new measure of strategic complexity named "multiple complexity", which considers the responsiveness of a strategy to information as well as the number of states of machines. In contrast to Piccione and Rubinstein (1993), we prove that a machine game may include non-trivial Nash equilibria. In the sequential-move prisoners' dilemma, cooperation can be sustained in an equilibrium of the machine game.