A Caltech Library Service

Repeated games, finite automata, and complexity

Banks, Jeffrey S. and Sundaram, Rangarajan K. (1990) Repeated games, finite automata, and complexity. Games and Economic Behavior, 2 (2). pp. 97-117. ISSN 0899-8256. doi:10.1016/0899-8256(90)90024-O.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 1990 Academic Press. Received June 3, 1989. We are very grateful to Professor Ariel Rubinstein for his numerous comments and suggestions. We also thank Professor Ehud Kalai and seminar participants at the Hoover Institution, and at the Universities of Arizona and Rochester, especially John H. Boyd III and Mahmoud El-Gamal, and an anonymous referee for suggesting changes that have significantly improved the exposition. The first author also thanks the NSF for support under Grant SES 87-00468, and the University of Arizona for its hospitality during Spring 1989, when the first draft of this paper was completed. Bonnie Huck provided much appreciated technical support during the many rewrites of this paper.
Funding AgencyGrant Number
NSFSES 87-00468
Issue or Number:2
Classification Code:Classification Numbers: 020, 022, 026
Record Number:CaltechAUTHORS:20160524-072532526
Persistent URL:
Official Citation:Jeffrey S Banks, Rangarajan K Sundaram, Repeated games, finite automata, and complexity, Games and Economic Behavior, Volume 2, Issue 2, 1990, Pages 97-117, ISSN 0899-8256, (
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:67279
Deposited By: Ruth Sustaita
Deposited On:24 May 2016 18:48
Last Modified:11 Nov 2021 00:30

Repository Staff Only: item control page