Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Optimal Strategy Synthesis in Stochastic Muller Games

Krishnendu Chatterjee

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-122
October 4, 2006

http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-122.pdf

The theory of graph games with \omega-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We consider \omega-regular winning conditions formalized as Muller winning conditions. We present optimal memory bounds for pure (deterministic) almost-sure winning and optimal winning strategies in stochastic graph games with Muller winning conditions. We also present improved memory bounds for randomized almost-sure winning and optimal strategies. Our results are relevant in synthesis of stochastic reactive processes.


BibTeX citation:

@techreport{Chatterjee:EECS-2006-122,
    Author = {Chatterjee, Krishnendu},
    Title = {Optimal Strategy Synthesis in Stochastic Muller Games},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2006},
    Month = {Oct},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-122.html},
    Number = {UCB/EECS-2006-122},
    Abstract = {The theory of graph games with \omega-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We consider \omega-regular winning conditions formalized as Muller winning conditions. We present optimal memory bounds for pure (deterministic) almost-sure winning and optimal winning strategies in stochastic graph games with Muller winning conditions. We also present improved memory bounds for randomized almost-sure winning and optimal strategies. Our results are relevant in synthesis of stochastic reactive processes.}
}

EndNote citation:

%0 Report
%A Chatterjee, Krishnendu
%T Optimal Strategy Synthesis in Stochastic Muller Games
%I EECS Department, University of California, Berkeley
%D 2006
%8 October 4
%@ UCB/EECS-2006-122
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-122.html
%F Chatterjee:EECS-2006-122