Repeated Games with Finite Automata

摘要

This paper examines the set of equilibrium payoffs in a repeated game when there are bounds on the complexity of the strategies that players may select. The interest in putting such bounds comes from the limited computational ability of humans and devices used by humans. For example most of the strategies in a repeated game cannot be implemented by any computer. It is important to distinguish between the complexity of a strategy and the complexity of the process of selecting a strategy. The author does deal with the selection process directly. She assumes that the limitation of a player is such that he can consider all the strategies below a certain level of complexity. A possible interpretation is that the players' abilities are unbounded but they use bounded devices to implement their strategies (secretaries, or computers). We use the notion of a finite automation to define a complexity measure on the strategies. A finite automation is a machine that contains a finite number of states. One of these states is the initial state. The machine has an action function and a transition function. The action function determines the one-shot game strategy that is played at each state. The transition function specifies the next state as a function of the current state and the current action of the other players. (kr)