Author(s):

Chatterjee, Krishnendu

Article Title: 
Concurrent games with tail objectives

Affiliation 

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 (proceed for an infinite number of rounds). The analysis of concurrent stochastic games can be classified into: quantitative analysis, analyzing the optimum value of the game and epsilonoptimal strategies that ensure values within epsilon of the optimum value; and qualitative analysis, analyzing the set of states with optimum value 1 and epsilonoptimal strategies for the states with optimum value 1. We consider concurrent games with tail objectives, i.e., objectives that are independent of the finiteprefix of traces, and show that the class of tail objectives is strictly richer than that of the omegaregular objectives. We develop new proof techniques to extend several properties of concurrent games with omegaregular objectives to concurrent games with tail objectives. We prove the positive limitone property for tail objectives. The positive limitone property states that 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 the player for the objective Phi. We also show that the optimum values of zerosum (strictly conflicting objectives) games with tail objectives can be related to equilibrium values of nonzerosum (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 subclass of oneplayer stochastic games (Markov decision processes).

Keywords: 
concurrent games; omegaregular objectives; Muller objectives; tail objectives

Journal Title:

Theoretical Computer Science

Volume: 
388

Issue 
13

ISSN:

03043975

Publisher:

Elsevier

Date Published:

20071205

Start Page: 
181

End Page:

198

Copyright Statement: 
Copyright 2007 Elsevier B.V. All rights reserved

DOI: 
10.1016/j.tcs.2007.07.047

Notes: 
A preliminary version of the paper appeared in Computer Science Logic (CSL) 2006.

Open access: 
no 