Citation
Krishnendu Chatterjee. "Concurrent Games with Tail Objectives". CSL 06, September, 2006.

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 qualitative analysis, analyzing the set of 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 Phi, for the player. 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 polynomial time reduction of the quantitative analysis of tail objectives to the qualitative analysis for the sub-class of one-player stochastic games (Markov decision processes).

Electronic downloads

• csl06_paper35.ps · application/postscript · 399 kbytes

• HTML

  Krishnendu Chatterjee. <a
  href="http://chess.eecs.berkeley.edu/pubs/235.html"
  >Concurrent Games with Tail Objectives</a>, CSL 06,
  September, 2006.

• Plain text

  Krishnendu Chatterjee. "Concurrent Games with Tail
  Objectives". CSL 06, September, 2006.

• BibTeX

  @inproceedings{Chatterjee06_ConcurrentGamesWithTailObjectives,
      author = {Krishnendu Chatterjee},
      title = {Concurrent Games with Tail Objectives},
      booktitle = {CSL 06},
      month = {September},
      year = {2006},
      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 qualitative
                analysis, analyzing the set of 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 Phi, for
                the player. 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 polynomial time reduction of
                the quantitative analysis of tail objectives to
                the qualitative analysis for the sub-class of
                one-player stochastic games (Markov decision
                processes). },
      URL = {http://chess.eecs.berkeley.edu/pubs/235.html}
  }
  

Posted by Krishnendu Chatterjee, PhD on 13 May 2007.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.