---
res:
bibo_abstract:
- 'We consider two-player stochastic games played on finite graphs with reachability
objectives where the first player tries to ensure a target state to be visited
almost-surely (i.e., with probability 1), or positively (i.e., with positive probability),
no matter the strategy of the second player. We classify such games according
to the information and the power of randomization available to the players. On
the basis of information, the game can be one-sided with either (a) player 1,
or (b) player 2 having partial observation (and the other player has perfect observation),
or two-sided with (c) both players having partial observation. On the basis of
randomization, the players (a) may not be allowed to use randomization (pure strategies),
or (b) may choose a probability distribution over actions but the actual random
choice is external and not visible to the player (actions invisible), or (c) may
use full randomization. Our main results for pure strategies are as follows. (1)
For one-sided games with player 1 having partial observation we show that (in
contrast to full randomized strategies) belief-based (subset-construction based)
strategies are not sufficient, and we present an exponential upper bound on memory
both for almostsure and positive winning strategies; we show that the problem
of deciding the existence of almost-sure and positive winning strategies for player
1 is EXPTIME-complete. (2) For one-sided games with player 2 having partial observation
we show that non-elementary memory is both necessary and sufficient for both almost-sure
and positive winning strategies. (3) We show that for the general (two-sided)
case finite-memory strategies are sufficient for both positive and almost-sure
winning, and at least non-elementary memory is required. We establish the equivalence
of the almost-sure winning problems for pure strategies and for randomized strategies
with actions invisible. Our equivalence result exhibits serious flaws in previous
results of the literature: we show a non-elementary memory lower bound for almost-sure
winning whereas an exponential upper bound was previously claimed.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Laurent
foaf_name: Doyen, Laurent
foaf_surname: Doyen
bibo_doi: 10.1109/LICS.2012.28
dct_date: 2012^xs_gYear
dct_language: eng
dct_publisher: IEEE@
dct_title: 'Partial-observation stochastic games: How to win when belief fails@'
...