--- _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 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: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science . Association for Computing Machinery; 2020:102-115. doi:10.1145/3373718.3394761' apa: 'Ashok, P., Chatterjee, K., Kretinsky, J., Weininger, M., & Winkler, T. (2020). Approximating values of generalized-reachability stochastic games. In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 102–115). Saarbrücken, Germany: Association for Computing Machinery. https://doi.org/10.1145/3373718.3394761' chicago: Ashok, Pranav, Krishnendu Chatterjee, Jan Kretinsky, Maximilian Weininger, and Tobias Winkler. “Approximating Values of Generalized-Reachability Stochastic Games.” In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science , 102–15. Association for Computing Machinery, 2020. https://doi.org/10.1145/3373718.3394761. ieee: P. Ashok, K. Chatterjee, J. Kretinsky, M. Weininger, and T. Winkler, “Approximating values of generalized-reachability stochastic games,” in Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science , 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.” Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science , Association for Computing Machinery, 2020, pp. 102–15, doi:10.1145/3373718.3394761. 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: 2023-08-21T08:24:36Z 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' ...