Algorithms for Game Metrics

Krishnendu Chatterjee, Luca De Alfaro, Rupak Majumdar & Vishwanath Raman
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 present algorithms for computing the metrics on Markov decision processes (MDPs), turn-based stochastic games, and concurrent games. For turn-based games and MDPs, we provide a polynomial-time algorithm based on linear programming for the computation of...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.