p.397

Finite Rationality and Interpersonal Complexity in Repeated Games

Ehud Kalai
William Stanford

Abstract

A measure of complexity for repeated games strategies is studied. This measure facilitates the investigation of some issues regarding finite rationality and the structure of subgame perfect equilibria of repeated games with discounting. Specifically, the complexity of a strategy in a given repeated game is defined to be the cardinality of the induced strategy set, i.e., the number of distinct strategies induced by the original strategy in all possible subgames. We observe that this cardinality is equal to the size (cardinality of the state set) of the smallest automaton which can implement the strategy. Thus, in a sense, complexity is measured on the basis of the amount of computing power inherent in the strategy. A measure of strategic memory is also studied. The following results are obtained: (1) combining tow notions of "bounded rationality" (epsilon equilibrium and finite complexity), we find that every subgame perfect equilibrium of the repeated game can be approximated (with regard to payoffs) by a subgame perfect epsilon equilibrium of finite complexity. (2) For a generic class of normal form stage games, at every discount robust subgame perfect (DRSP) equilibrium, there are necessary relationships among the complexities and memories of the players' strategies. In the two player case, strategies must be equally complex and must have equal memories. (3) For a second class of two player stage games, we show that the payoff vectors for all DRSP equilibria are obtainable via equilibria in which the players' strategies are equally complex and have equal memories.