On the Inference of Strategies (revised)

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 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

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

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

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