---
_id: '7955'
abstract:
- lang: eng
  text: Simple stochastic games are turn-based 2½-player games with a reachability
    objective. The basic question asks whether one player can ensure reaching a given
    target with at least a given probability. A natural extension is games with a
    conjunction of such conditions as objective. Despite a plethora of recent results
    on the analysis of systems with multiple objectives, the decidability of this
    basic problem remains open. In this paper, we present an algorithm approximating
    the Pareto frontier of the achievable values to a given precision. Moreover, it
    is an anytime algorithm, meaning it can be stopped at any time returning the current
    approximation and its error bound.
acknowledgement: "Pranav Ashok, Jan Křetínský and Maximilian Weininger were funded
  in part by TUM IGSSE Grant 10.06 (PARSEC) and the German Research Foundation (DFG)
  project KR 4890/2-1\r\n“Statistical Unbounded Verification”. Krishnendu Chatterjee
  was supported by the ERC CoG 863818 (ForM-SMArt) and Vienna Science and Technology
  Fund (WWTF) Project ICT15-\r\n003. Tobias Winkler was supported by the RTG 2236
  UnRAVe."
article_processing_charge: No
arxiv: 1
author:
- first_name: Pranav
  full_name: Ashok, Pranav
  last_name: Ashok
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Jan
  full_name: Kretinsky, Jan
  last_name: Kretinsky
- first_name: Maximilian
  full_name: Weininger, Maximilian
  last_name: Weininger
- first_name: Tobias
  full_name: Winkler, Tobias
  last_name: Winkler
citation:
  ama: 'Ashok P, Chatterjee K, Kretinsky J, Weininger M, Winkler T. Approximating
    values of generalized-reachability stochastic games. In: <i>Proceedings of the
    35th Annual ACM/IEEE Symposium on Logic in Computer Science </i>. Association
    for Computing Machinery; 2020:102-115. doi:<a href="https://doi.org/10.1145/3373718.3394761">10.1145/3373718.3394761</a>'
  apa: 'Ashok, P., Chatterjee, K., Kretinsky, J., Weininger, M., &#38; Winkler, T.
    (2020). Approximating values of generalized-reachability stochastic games. In
    <i>Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science
    </i> (pp. 102–115). Saarbrücken, Germany: Association for Computing Machinery.
    <a href="https://doi.org/10.1145/3373718.3394761">https://doi.org/10.1145/3373718.3394761</a>'
  chicago: Ashok, Pranav, Krishnendu Chatterjee, Jan Kretinsky, Maximilian Weininger,
    and Tobias Winkler. “Approximating Values of Generalized-Reachability Stochastic
    Games.” In <i>Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer
    Science </i>, 102–15. Association for Computing Machinery, 2020. <a href="https://doi.org/10.1145/3373718.3394761">https://doi.org/10.1145/3373718.3394761</a>.
  ieee: P. Ashok, K. Chatterjee, J. Kretinsky, M. Weininger, and T. Winkler, “Approximating
    values of generalized-reachability stochastic games,” in <i>Proceedings of the
    35th Annual ACM/IEEE Symposium on Logic in Computer Science </i>, Saarbrücken,
    Germany, 2020, pp. 102–115.
  ista: 'Ashok P, Chatterjee K, Kretinsky J, Weininger M, Winkler T. 2020. Approximating
    values of generalized-reachability stochastic games. Proceedings of the 35th Annual
    ACM/IEEE Symposium on Logic in Computer Science . LICS: Symposium on Logic in
    Computer Science, 102–115.'
  mla: Ashok, Pranav, et al. “Approximating Values of Generalized-Reachability Stochastic
    Games.” <i>Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer
    Science </i>, Association for Computing Machinery, 2020, pp. 102–15, doi:<a href="https://doi.org/10.1145/3373718.3394761">10.1145/3373718.3394761</a>.
  short: P. Ashok, K. Chatterjee, J. Kretinsky, M. Weininger, T. Winkler, in:, Proceedings
    of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science , Association
    for Computing Machinery, 2020, pp. 102–115.
conference:
  end_date: 2020-07-11
  location: Saarbrücken, Germany
  name: 'LICS: Symposium on Logic in Computer Science'
  start_date: 2020-07-08
date_created: 2020-06-14T22:00:48Z
date_published: 2020-07-08T00:00:00Z
date_updated: 2025-06-02T08:53:42Z
day: '08'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1145/3373718.3394761
ec_funded: 1
external_id:
  arxiv:
  - '1908.05106'
  isi:
  - '000665014900010'
file:
- access_level: open_access
  checksum: d0d0288fe991dd16cf5f02598b794240
  content_type: application/pdf
  creator: dernst
  date_created: 2020-11-25T09:38:14Z
  date_updated: 2020-11-25T09:38:14Z
  file_id: '8804'
  file_name: 2020_LICS_Ashok.pdf
  file_size: 1001395
  relation: main_file
  success: 1
file_date_updated: 2020-11-25T09:38:14Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 102-115
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
  grant_number: ICT15-003
  name: Efficient Algorithms for Computer Aided Verification
publication: 'Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer
  Science '
publication_identifier:
  isbn:
  - '9781450371049'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Approximating values of generalized-reachability stochastic games
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2020'
...