Published Articles >> Table of Contents >> Abstract

The Quantitative Evaluation of Systems, First International Conference on (QEST'04)   pp. 206-217
Trading Memory for Randomness
Krishnendu Chatterjee, University of California, Berkeley
Luca de Alfaro, University of California, Santa Cruz
Thomas A. Henzinger, University of California, Berkeley; EPFL, Switzerland

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/QEST.2004.10051
Send link to a friend

Abstract
Strategies in repeated games can be classified as to whether or not they use memory and/or randomization. We consider Markov decision processes and 2-player graph games, both of the deterministic and probabilistic varieties. We characterize when memory and/or randomization are required for winning with respect to various classes of w-regular objectives, noting particularly when the use of memory can be traded for the use of randomization. In particular, we show that Markov decision processes allow randomized memoryless optimal strategies for all Müller objectives. Furthermore, we show that 2-player probabilistic graph games allow randomized memoryless strategies for winning with probability 1 those Müller objectives which are upward-closed. Upward-closure means that if a set α of infinitely repeating vertices is winning, then all supersets of α are also winning.
Back to Top Additional Information
Citation:  Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger, "Trading Memory for Randomness," qest, pp. 206-217,  The Quantitative Evaluation of Systems, First International Conference on (QEST'04),  2004