---
_id: '3868'
abstract:
- lang: eng
  text: 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
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Luca
  full_name: De Alfaro, Luca
  last_name: De Alfaro
- first_name: Ritankar
  full_name: Majumdar, Ritankar
  last_name: Majumdar
- first_name: Vishwanath
  full_name: Raman, Vishwanath
  last_name: Raman
citation:
  ama: Chatterjee K, De Alfaro L, Majumdar R, Raman V. Algorithms for game metrics.
    <i>Logical Methods in Computer Science</i>. 2010;6(3):1-27. doi:<a href="https://doi.org/10.2168/LMCS-6(3:13)2010">10.2168/LMCS-6(3:13)2010</a>
  apa: Chatterjee, K., De Alfaro, L., Majumdar, R., &#38; Raman, V. (2010). Algorithms
    for game metrics. <i>Logical Methods in Computer Science</i>. International Federation
    of Computational Logic. <a href="https://doi.org/10.2168/LMCS-6(3:13)2010">https://doi.org/10.2168/LMCS-6(3:13)2010</a>
  chicago: Chatterjee, Krishnendu, Luca De Alfaro, Ritankar Majumdar, and Vishwanath
    Raman. “Algorithms for Game Metrics.” <i>Logical Methods in Computer Science</i>.
    International Federation of Computational Logic, 2010. <a href="https://doi.org/10.2168/LMCS-6(3:13)2010">https://doi.org/10.2168/LMCS-6(3:13)2010</a>.
  ieee: K. Chatterjee, L. De Alfaro, R. Majumdar, and V. Raman, “Algorithms for game
    metrics,” <i>Logical Methods in Computer Science</i>, vol. 6, no. 3. International
    Federation of Computational Logic, pp. 1–27, 2010.
  ista: Chatterjee K, De Alfaro L, Majumdar R, Raman V. 2010. Algorithms for game
    metrics. Logical Methods in Computer Science. 6(3), 1–27.
  mla: Chatterjee, Krishnendu, et al. “Algorithms for Game Metrics.” <i>Logical Methods
    in Computer Science</i>, vol. 6, no. 3, International Federation of Computational
    Logic, 2010, pp. 1–27, doi:<a href="https://doi.org/10.2168/LMCS-6(3:13)2010">10.2168/LMCS-6(3:13)2010</a>.
  short: K. Chatterjee, L. De Alfaro, R. Majumdar, V. Raman, Logical Methods in Computer
    Science 6 (2010) 1–27.
corr_author: '1'
date_created: 2018-12-11T12:05:36Z
date_published: 2010-09-01T00:00:00Z
date_updated: 2025-09-30T09:31:30Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.2168/LMCS-6(3:13)2010
external_id:
  isi:
  - '000282653500013'
file:
- access_level: open_access
  checksum: a18988135fef3016c93808ecb15b55f5
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:08:11Z
  date_updated: 2020-07-14T12:46:19Z
  file_id: '4671'
  file_name: IST-2015-370-v1+1_0809.4326.pdf
  file_size: 346527
  relation: main_file
file_date_updated: 2020-07-14T12:46:19Z
has_accepted_license: '1'
intvolume: '         6'
isi: 1
issue: '3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '09'
oa: 1
oa_version: Published Version
page: 1 - 27
publication: Logical Methods in Computer Science
publication_status: published
publisher: International Federation of Computational Logic
publist_id: '2312'
pubrep_id: '370'
quality_controlled: '1'
related_material:
  record:
  - id: '3504'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Algorithms for game metrics
tmp:
  image: /image/cc_by_nd.png
  legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
  name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
  short: CC BY-ND (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 6
year: '2010'
...