---
_id: '3891'
abstract:
- lang: eng
text: '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).'
alternative_title:
- 'LNCS '
author:
- first_name: Krishnendu
full_name: Krishnendu Chatterjee
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: 'Chatterjee K. Concurrent games with tail objectives. In: Vol 4207. Springer;
2006:256-270. doi:10.1007/11874683_17'
apa: 'Chatterjee, K. (2006). Concurrent games with tail objectives (Vol. 4207, pp.
256–270). Presented at the CSL: Computer Science Logic, Springer. https://doi.org/10.1007/11874683_17'
chicago: Chatterjee, Krishnendu. “Concurrent Games with Tail Objectives,” 4207:256–70.
Springer, 2006. https://doi.org/10.1007/11874683_17.
ieee: 'K. Chatterjee, “Concurrent games with tail objectives,” presented at the
CSL: Computer Science Logic, 2006, vol. 4207, pp. 256–270.'
ista: 'Chatterjee K. 2006. Concurrent games with tail objectives. CSL: Computer
Science Logic, LNCS , vol. 4207, 256–270.'
mla: Chatterjee, Krishnendu. Concurrent Games with Tail Objectives. Vol.
4207, Springer, 2006, pp. 256–70, doi:10.1007/11874683_17.
short: K. Chatterjee, in:, Springer, 2006, pp. 256–270.
conference:
name: 'CSL: Computer Science Logic'
date_created: 2018-12-11T12:05:44Z
date_published: 2006-09-28T00:00:00Z
date_updated: 2021-01-12T07:53:00Z
day: '28'
doi: 10.1007/11874683_17
extern: 1
intvolume: ' 4207'
month: '09'
page: 256 - 270
publication_status: published
publisher: Springer
publist_id: '2272'
quality_controlled: 0
status: public
title: Concurrent games with tail objectives
type: conference
volume: 4207
year: '2006'
...