## Trading Memory for Randomness

*Krishnendu Chatterjee, Luca de Alfaro, and
Thomas A. Henzinger*

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 omega-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 Muller objectives. Furthermore, we show
that 2-player probabilistic graph games allow randomized memoryless
strategies for winning with probability 1 those Muller objectives
which are upward-closed. Upward-closure means that if a set *W*
of infinitely repeating vertices is winning, then all supersets of
*W* are also winning.

*Proceedings of the
First Annual Conference on Quantitative Evaluation of Systems*
(QEST), IEEE Computer Society Press, 2004, pp. 206-217.

Download inofficial, sometimes updated
PostScript /
PDF document.
© 2004 IEEE.