Algorithms for game metrics
Chatterjee K, De Alfaro L, Majumdar R, Raman V. 2010. Algorithms for game metrics. Logical Methods in Computer Science. 6(3), 1–27.
Download
Journal Article
| Published
| English
Scopus indexed
Author
Chatterjee, KrishnenduISTA ;
De Alfaro, Luca;
Majumdar, Ritankar;
Raman, Vishwanath
Department
Abstract
Simulation and bisimulation metrics for stochastic systems provide a quantitative generalization of the classical simulation and bisimulation relations. These metrics capture the similarity of states with respect to quantitative specifications written in the quantitative mu-calculus and related probabilistic logics. We first show that the metrics provide a bound for the difference in long-run average and discounted average behavior across states, indicating that the metrics can be used both in system verification, and in performance evaluation. For turn-based games and MDPs, we provide a polynomial-time algorithm for the computation of the one-step metric distance between states. The algorithm is based on linear programming; it improves on the previous known exponential-time algorithm based on a reduction to the theory of reals. We then present PSPACE algorithms for both the decision problem and the problem of approximating the metric distance between two states, matching the best known algorithms for Markov chains. For the bisimulation kernel of the metric our algorithm works in time O(n(4)) for both turn-based games and MDPs; improving the previously best known O(n(9).log(n)) time algorithm for MDPs. For a concurrent game G, we show that computing the exact distance be tween states is at least as hard as computing the value of concurrent reachability games and the square-root-sum problem in computational geometry. We show that checking whether the metric distance is bounded by a rational r, can be done via a reduction to the theory of real closed fields, involving a formula with three quantifier alternations, yielding O(vertical bar G vertical bar(O(vertical bar G vertical bar 5))) time complexity, improving the previously known reduction, which yielded O(vertical bar G vertical bar(O(vertical bar G vertical bar 7))) time complexity. These algorithms can be iterated to approximate the metrics using binary search
Publishing Year
Date Published
2010-09-01
Journal Title
Logical Methods in Computer Science
Publisher
International Federation of Computational Logic
Volume
6
Issue
3
Page
1 - 27
IST-REx-ID
Cite this
Chatterjee K, De Alfaro L, Majumdar R, Raman V. Algorithms for game metrics. Logical Methods in Computer Science. 2010;6(3):1-27. doi:10.2168/LMCS-6(3:13)2010
Chatterjee, K., De Alfaro, L., Majumdar, R., & Raman, V. (2010). Algorithms for game metrics. Logical Methods in Computer Science. International Federation of Computational Logic. https://doi.org/10.2168/LMCS-6(3:13)2010
Chatterjee, Krishnendu, Luca De Alfaro, Ritankar Majumdar, and Vishwanath Raman. “Algorithms for Game Metrics.” Logical Methods in Computer Science. International Federation of Computational Logic, 2010. https://doi.org/10.2168/LMCS-6(3:13)2010.
K. Chatterjee, L. De Alfaro, R. Majumdar, and V. Raman, “Algorithms for game metrics,” Logical Methods in Computer Science, vol. 6, no. 3. International Federation of Computational Logic, pp. 1–27, 2010.
Chatterjee K, De Alfaro L, Majumdar R, Raman V. 2010. Algorithms for game metrics. Logical Methods in Computer Science. 6(3), 1–27.
Chatterjee, Krishnendu, et al. “Algorithms for Game Metrics.” Logical Methods in Computer Science, vol. 6, no. 3, International Federation of Computational Logic, 2010, pp. 1–27, doi:10.2168/LMCS-6(3:13)2010.
All files available under the following license(s):
Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0):
Main File(s)
File Name
IST-2015-370-v1+1_0809.4326.pdf
346.53 KB
Access Level
Open Access
Date Uploaded
2018-12-12
MD5 Checksum
a18988135fef3016c93808ecb15b55f5