Repeated games, finite automata, and complexity

We study the structure of Nash equilibria in 2-player repeated games played with finite automata, when complexity considerations matter. We argue that the traditional number-of-states measure of complexity of an automaton neglects some essential features such as informational requirements at a state. We propose a criterion of complexity to remedy this; our criterion takes into account both the size (number of states) and transitional structure of a machine. We prove that the resulting Nash equilibria of the machine game are now trivial: the machines recommend actions every period that are invariably stage-game Nash equilibria