Published June 1990
| public
Journal Article
Repeated games, finite automata, and complexity
- Creators
- Banks, Jeffrey S.
- Sundaram, Rangarajan K.
Abstract
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.
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.Additional details
- Eprint ID
- 67279
- DOI
- 10.1016/0899-8256(90)90024-O
- Resolver ID
- CaltechAUTHORS:20160524-072532526
- SES 87-00468
- NSF
- Created
-
2016-05-24Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field