This project incorporates notions of bounded rationality and measures of complexity into economic analysis. The importance of bringing complexity considerations into economic models is shown by the organizational structures, social mechanisms, and data base systems designed for the purpose of simplifying the process of decision making as well as simplifying implementations of strategies. This need takes on an added importance now since economic agents are beginning to relegate decisions and strategies to computers. Thus, studying the effects of finite computational ability, computational costs, and computing power in general becomes an essential part of the strategic analysis. In their previous work the investigators demonstrated that the concept of an automaton is a natural way of characterizing the needs for simplicity and the notions of bounded rationality of players in the types of strategic games central to modern economic analysis and other social sciences. This project continues to expand existing results in several directions. It investigates automaton-complexity and alternative notions of complexity in repeated games with emphasis on algebraic (group theoretic) measures. It extends complexity results on repeated games to stochastic games. This extension is especially important because stochastic games are more useful to economists than repeated games. Complexity results are extended to general extensive games with imperfect information.
