Approximating values of generalized-reachability stochastic games
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.
Download
Conference Paper
| Published
| English
Scopus indexed
Author
Ashok, Pranav;
Chatterjee, KrishnenduISTA 
;
Kretinsky, Jan;
Weininger, Maximilian;
Winkler, Tobias
;
Kretinsky, Jan;
Weininger, Maximilian;
Winkler, TobiasDepartment
Grant
Abstract
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.
Publishing Year
Date Published
2020-07-08
Proceedings Title
Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science
Publisher
Association for Computing Machinery
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
“Statistical Unbounded Verification”. Krishnendu Chatterjee was supported by the ERC CoG 863818 (ForM-SMArt) and Vienna Science and Technology Fund (WWTF) Project ICT15-
003. Tobias Winkler was supported by the RTG 2236 UnRAVe.
Page
102-115
Conference
LICS: Symposium on Logic in Computer Science
Conference Location
Saarbrücken, Germany
Conference Date
2020-07-08 – 2020-07-11
ISBN
IST-REx-ID
Cite this
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
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
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.
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.
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.
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.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
2020_LICS_Ashok.pdf
1.00 MB
Access Level
Open Access
Date Uploaded
2020-11-25
MD5 Checksum
d0d0288fe991dd16cf5f02598b794240
Export
Marked PublicationsOpen Data ISTA Research Explorer
Web of Science
View record in Web of Science®Sources
arXiv 1908.05106
Google Scholar
ISBN Search