---
_id: '2854'
abstract:
- lang: eng
  text: We consider concurrent games played on graphs. At every round of a game, each
    player simultaneously and independently selects a move; the moves jointly determine
    the transition to a successor state. Two basic objectives are the safety objective
    to stay forever in a given set of states, and its dual, the reachability objective
    to reach a given set of states. First, we present a simple proof of the fact that
    in concurrent reachability games, for all ε>0, memoryless ε-optimal strategies
    exist. A memoryless strategy is independent of the history of plays, and an ε-optimal
    strategy achieves the objective with probability within ε of the value of the
    game. In contrast to previous proofs of this fact, our proof is more elementary
    and more combinatorial. Second, we present a strategy-improvement (a.k.a. policy-iteration)
    algorithm for concurrent games with reachability objectives. Finally, we present
    a strategy-improvement algorithm for turn-based stochastic games (where each player
    selects moves in turns) with safety objectives. Our algorithms yield sequences
    of player-1 strategies which ensure probabilities of winning that converge monotonically
    (from below) to the value of the game. © 2012 Elsevier Inc.
acknowledgement: This work was partially supported in part by the NSF grants CCR-0132780,
  CNS-0720884, CCR-0225610, by the Swiss National Science Foundation, ERC Start Grant
  Graph Games (Project No. 279307), FWF NFN Grant S11407-N23 (RiSE), and a Microsoft
  faculty fellows
article_processing_charge: No
article_type: original
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Luca
  full_name: De Alfaro, Luca
  last_name: De Alfaro
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
citation:
  ama: Chatterjee K, De Alfaro L, Henzinger TA. Strategy improvement for concurrent
    reachability and turn based stochastic safety games. <i>Journal of Computer and
    System Sciences</i>. 2013;79(5):640-657. doi:<a href="https://doi.org/10.1016/j.jcss.2012.12.001">10.1016/j.jcss.2012.12.001</a>
  apa: Chatterjee, K., De Alfaro, L., &#38; Henzinger, T. A. (2013). Strategy improvement
    for concurrent reachability and turn based stochastic safety games. <i>Journal
    of Computer and System Sciences</i>. Elsevier. <a href="https://doi.org/10.1016/j.jcss.2012.12.001">https://doi.org/10.1016/j.jcss.2012.12.001</a>
  chicago: Chatterjee, Krishnendu, Luca De Alfaro, and Thomas A Henzinger. “Strategy
    Improvement for Concurrent Reachability and Turn Based Stochastic Safety Games.”
    <i>Journal of Computer and System Sciences</i>. Elsevier, 2013. <a href="https://doi.org/10.1016/j.jcss.2012.12.001">https://doi.org/10.1016/j.jcss.2012.12.001</a>.
  ieee: K. Chatterjee, L. De Alfaro, and T. A. Henzinger, “Strategy improvement for
    concurrent reachability and turn based stochastic safety games,” <i>Journal of
    Computer and System Sciences</i>, vol. 79, no. 5. Elsevier, pp. 640–657, 2013.
  ista: Chatterjee K, De Alfaro L, Henzinger TA. 2013. Strategy improvement for concurrent
    reachability and turn based stochastic safety games. Journal of Computer and System
    Sciences. 79(5), 640–657.
  mla: Chatterjee, Krishnendu, et al. “Strategy Improvement for Concurrent Reachability
    and Turn Based Stochastic Safety Games.” <i>Journal of Computer and System Sciences</i>,
    vol. 79, no. 5, Elsevier, 2013, pp. 640–57, doi:<a href="https://doi.org/10.1016/j.jcss.2012.12.001">10.1016/j.jcss.2012.12.001</a>.
  short: K. Chatterjee, L. De Alfaro, T.A. Henzinger, Journal of Computer and System
    Sciences 79 (2013) 640–657.
corr_author: '1'
date_created: 2018-12-11T11:59:57Z
date_published: 2013-08-01T00:00:00Z
date_updated: 2025-09-29T13:40:38Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1016/j.jcss.2012.12.001
ec_funded: 1
external_id:
  isi:
  - '000316837300011'
file:
- access_level: open_access
  checksum: 6d3ee12cceb946a0abe69594b6a22409
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:18:48Z
  date_updated: 2020-07-14T12:45:51Z
  file_id: '5370'
  file_name: IST-2015-388-v1+1_1-s2.0-S0022000012001778-main.pdf
  file_size: 425488
  relation: main_file
file_date_updated: 2020-07-14T12:45:51Z
has_accepted_license: '1'
intvolume: '        79'
isi: 1
issue: '5'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 640 - 657
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 2587B514-B435-11E9-9278-68D0E5697425
  name: Microsoft Research Faculty Fellowship
publication: Journal of Computer and System Sciences
publication_status: published
publisher: Elsevier
publist_id: '3938'
pubrep_id: '388'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Strategy improvement for concurrent reachability and turn based stochastic
  safety games
tmp:
  image: /images/cc_by_nc_nd.png
  legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
  name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
    (CC BY-NC-ND 4.0)
  short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 79
year: '2013'
...