On the Inference of Strategies (revised)Report
We investigate the use of automata theory to model strategies for nonzero-sum two - person games such as the Prisonefs Dilemma. We are particularly interested in infinite totmtaments of such games. In the case of flnite-state strategies (such as the well-known strategies ALL D or TIT FOR TAT) we use graph traversal techniques to show the existence of a (normerrninating) procedure for detecting our opponent's strategy and developing an "optimal" defense. We also investigate counter machine and Turing machine strategies. We show that the optimal defense to a counter machine strategy need not be flnite-state, thus disproving a previous conjectnre. We show that determining an optimal defense to an arbitrary Turing machine strategy is undecidable. .
Note: Abstract extracted from PDF file via OCR
All rights reserved (no additional license for public reuse)
Swart, Charles, and Dana Richards. "On the Inference of Strategies (revised)." University of Virginia Dept. of Computer Science Tech Report (1986).
University of Virginia, Department of Computer Science