Krishnendu Chatterjee
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-05-1385
April 2005
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/CSD-05-1385.pdf
We study infinite stochastic games played by two-players over a finite state space, with objectives specified by sets of infinite traces. The games are concurrent (players make moves simultaneously and independently), stochastic (the next state is determined by a probability distribution that depends on the current state and chosen moves of the players) and infinite (proceeds for infinite number of rounds). The analysis of concurrent stochastic games can be classified into: quantitative analysis, analyzing the optimum value of the game and epsilon-optimal strategies that ensure values within epsilon of the optimum value; and qualitative analysis, analyzing the set of states with optimum value 1 and epsilon-optimal strategies for the states with optimum value 1. We consider concurrent games with tail objectives, i.e., objectives that are independent of the finite-prefix of traces, and show that the class of tail objectives are strictly richer than the omega-regular objectives. We develop new proof techniques to extend several properties of concurrent games with omega-regular objectives to concurrent games with tail objectives. We prove the positive limit-one property for tail objectives, that states for all concurrent games if the optimum value for a player is positive for a tail objective Phi at some state, then there is a state where the optimum value is 1 for objective Phi for the player. We show that the strategies for quantitative winning can be constructed from witnesses of strategies for qualitative winning. The results establish relationship between the quantitative and qualitative analysis of concurrent games with tail objectives. We also show that the optimum values of zero-sum (strictly conflicting objectives) games with tail objectives can be related to equilibrium values of nonzero-sum (not strictly conflicting objectives) games with simpler reachability objectives. A consequence of our analysis presents a polytime reduction of the quantitative analysis of tail objectives to the qualitative analysis for the sub-class of one-player stochastic games (Markov decision processes).
BibTeX citation:
@techreport{Chatterjee:CSD-05-1385,
Author = {Chatterjee, Krishnendu},
Title = {Concurrent Games with Tail Objectives},
Institution = {EECS Department, University of California, Berkeley},
Year = {2005},
Month = {Apr},
URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5656.html},
Number = {UCB/CSD-05-1385},
Abstract = {We study infinite stochastic games played by two-players over a finite state space, with objectives specified by sets of infinite traces. The games are concurrent (players make moves simultaneously and independently), stochastic (the next state is determined by a probability distribution that depends on the current state and chosen moves of the players) and infinite (proceeds for infinite number of rounds). The analysis of concurrent stochastic games can be classified into: quantitative analysis, analyzing the optimum value of the game and epsilon-optimal strategies that ensure values within epsilon of the optimum value; and qualitative analysis, analyzing the set of states with optimum value 1 and epsilon-optimal strategies for the states with optimum value 1. We consider concurrent games with tail objectives, i.e., objectives that are independent of the finite-prefix of traces, and show that the class of tail objectives are strictly richer than the omega-regular objectives. We develop new proof techniques to extend several properties of concurrent games with omega-regular objectives to concurrent games with tail objectives. We prove the positive limit-one property for tail objectives, that states for all concurrent games if the optimum value for a player is positive for a tail objective Phi at some state, then there is a state where the optimum value is 1 for objective Phi for the player. We show that the strategies for quantitative winning can be constructed from witnesses of strategies for qualitative winning. The results establish relationship between the quantitative and qualitative analysis of concurrent games with tail objectives. We also show that the optimum values of zero-sum (strictly conflicting objectives) games with tail objectives can be related to equilibrium values of nonzero-sum (not strictly conflicting objectives) games with simpler reachability objectives. A consequence of our analysis presents a polytime reduction of the quantitative analysis of tail objectives to the qualitative analysis for the sub-class of one-player stochastic games (Markov decision processes).}
}
EndNote citation:
%0 Report %A Chatterjee, Krishnendu %T Concurrent Games with Tail Objectives %I EECS Department, University of California, Berkeley %D 2005 %@ UCB/CSD-05-1385 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5656.html %F Chatterjee:CSD-05-1385