---
_id: '2211'
abstract:
- lang: eng
  text: 'In two-player finite-state stochastic games of partial observation on graphs,
    in every state of the graph, the players simultaneously choose an action, and
    their joint actions determine a probability distribution over the successor states.
    The game is played for infinitely many rounds and thus the players construct an
    infinite path in the graph. We consider 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 to 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, (a)
    the players may not be allowed to use randomization (pure strategies), or (b)
    they may choose a probability distribution over actions but the actual random
    choice is external and not visible to the player (actions invisible), or (c) they
    may use full randomization. Our main results for pure strategies are as follows:
    (1) For one-sided games with player 2 having perfect 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 almost-sure 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 and present symbolic algorithms that avoid the
    explicit exponential construction. (2) For one-sided games with player 1 having
    perfect observation we show that nonelementarymemory 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 nonelementary 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 exhibit serious
    flaws in previous results of the literature: we show a nonelementary memory lower
    bound for almost-sure winning whereas an exponential upper bound was previously
    claimed.'
article_number: '16'
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Laurent
  full_name: Doyen, Laurent
  last_name: Doyen
citation:
  ama: 'Chatterjee K, Doyen L. Partial-observation stochastic games: How to win when
    belief fails. <i>ACM Transactions on Computational Logic</i>. 2014;15(2). doi:<a
    href="https://doi.org/10.1145/2579821">10.1145/2579821</a>'
  apa: 'Chatterjee, K., &#38; Doyen, L. (2014). Partial-observation stochastic games:
    How to win when belief fails. <i>ACM Transactions on Computational Logic</i>.
    ACM. <a href="https://doi.org/10.1145/2579821">https://doi.org/10.1145/2579821</a>'
  chicago: 'Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic
    Games: How to Win When Belief Fails.” <i>ACM Transactions on Computational Logic</i>.
    ACM, 2014. <a href="https://doi.org/10.1145/2579821">https://doi.org/10.1145/2579821</a>.'
  ieee: 'K. Chatterjee and L. Doyen, “Partial-observation stochastic games: How to
    win when belief fails,” <i>ACM Transactions on Computational Logic</i>, vol. 15,
    no. 2. ACM, 2014.'
  ista: 'Chatterjee K, Doyen L. 2014. Partial-observation stochastic games: How to
    win when belief fails. ACM Transactions on Computational Logic. 15(2), 16.'
  mla: 'Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic
    Games: How to Win When Belief Fails.” <i>ACM Transactions on Computational Logic</i>,
    vol. 15, no. 2, 16, ACM, 2014, doi:<a href="https://doi.org/10.1145/2579821">10.1145/2579821</a>.'
  short: K. Chatterjee, L. Doyen, ACM Transactions on Computational Logic 15 (2014).
das_tickbox: '1'
date_created: 2018-12-11T11:56:21Z
date_published: 2014-04-01T00:00:00Z
date_updated: 2026-07-07T14:01:26Z
day: '01'
department:
- _id: KrCh
doi: 10.1145/2579821
external_id:
  arxiv:
  - '1107.2141'
  isi:
  - '000336005000006'
intvolume: '        15'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1107.2141
month: '04'
oa: 1
oa_version: Preprint
publication: ACM Transactions on Computational Logic
publication_status: published
publisher: ACM
publist_id: '4759'
quality_controlled: '1'
related_material:
  record:
  - id: '5381'
    relation: earlier_version
    status: public
  - id: '1903'
    relation: earlier_version
    status: public
  - id: '2955'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: 'Partial-observation stochastic games: How to win when belief fails'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2014'
...