On the Inference of Strategies

Report
Authors:Swart, Charles, Department of Computer ScienceUniversity of Virginia Richards, Dana, Department of Computer ScienceUniversity of Virginia
Abstract:

We investigate the use of automata theory to model strategies for nonzero - sum two - person games such as the Prisoner's Dilemma. We are particularly interested in infinite tournaments of such games. In the case of flnite-state strategies (such as ALL D or TIT FOR TAT) we use graph traversal techniques to show the existence of a (nomterminating) 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 - thus disproving a previous conjecture. We show that determining an optimal defense to an arbitrary Turing machine strategy is undecidable.
Note: Abstract extracted from PDF file via OCR

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Swart, Charles, and Dana Richards. "On the Inference of Strategies." University of Virginia Dept. of Computer Science Tech Report (1986).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1986