Approximating values of generalized-reachability stochastic games

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, n.d., pp. 102–115.


Conference Paper | In Press | English

Scopus indexed
Author
Ashok, Pranav; Chatterjee, KrishnenduIST Austria ; Kretinsky, Jan; Weininger, Maximilian; Winkler, Tobias
Department
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
Page
102-115
Conference
LICS: Symposium on Logic in Computer Science
Conference Location
Saarbrücken, Germany
Conference Date
2020-07-08 – 2020-07-11
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; :102-115. doi:10.1145/3373718.3394761
Ashok, P., Chatterjee, K., Kretinsky, J., Weininger, M., & Winkler, T. (n.d.). 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, n.d. 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, pp. 102–115.
Ashok P, Chatterjee K, Kretinsky J, Weininger M, Winkler T. 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, 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. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1908.05106

Search this title in

Google Scholar
ISBN Search