---
_id: '12101'
abstract:
- lang: eng
  text: 'Spatial games form a widely-studied class of games from biology and physics
    modeling the evolution of social behavior. Formally, such a game is defined by
    a square (d by d) payoff matrix M and an undirected graph G. Each vertex of G
    represents an individual, that initially follows some strategy i ∈ {1,2,…,d}.
    In each round of the game, every individual plays the matrix game with each of
    its neighbors: An individual following strategy i meeting a neighbor following
    strategy j receives a payoff equal to the entry (i,j) of M. Then, each individual
    updates its strategy to its neighbors'' strategy with the highest sum of payoffs,
    and the next round starts. The basic computational problems consist of reachability
    between configurations and the average frequency of a strategy. For general spatial
    games and graphs, these problems are in PSPACE. In this paper, we examine restricted
    setting: the game is a prisoner’s dilemma; and G is a subgraph of grid. We prove
    that basic computational problems for spatial games with prisoner’s dilemma on
    a subgraph of a grid are PSPACE-hard.'
acknowledgement: "Krishnendu Chatterjee: The research was partially supported by the
  ERC CoG 863818\r\n(ForM-SMArt).\r\nIsmaël Jecker: The research was partially supported
  by the ERC grant 950398 (INFSYS).\r\nJakub Svoboda: The research was partially supported
  by the ERC CoG 863818 (ForM-SMArt)"
article_number: 11:1-11:14
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: Rasmus
  full_name: Ibsen-Jensen, Rasmus
  id: 3B699956-F248-11E8-B48F-1D18A9856A87
  last_name: Ibsen-Jensen
  orcid: 0000-0003-4783-0389
- first_name: Ismael R
  full_name: Jecker, Ismael R
  id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425
  last_name: Jecker
- first_name: Jakub
  full_name: Svoboda, Jakub
  id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
  last_name: Svoboda
  orcid: 0000-0002-1419-3267
citation:
  ama: 'Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. Complexity of spatial
    games. In: <i>42nd IARCS Annual Conference on Foundations of Software Technology
    and Theoretical Computer Science</i>. Vol 250. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik; 2022. doi:<a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2022.11">10.4230/LIPIcs.FSTTCS.2022.11</a>'
  apa: 'Chatterjee, K., Ibsen-Jensen, R., Jecker, I. R., &#38; Svoboda, J. (2022).
    Complexity of spatial games. In <i>42nd IARCS Annual Conference on Foundations
    of Software Technology and Theoretical Computer Science</i> (Vol. 250). Madras,
    India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2022.11">https://doi.org/10.4230/LIPIcs.FSTTCS.2022.11</a>'
  chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Ismael R Jecker, and Jakub
    Svoboda. “Complexity of Spatial Games.” In <i>42nd IARCS Annual Conference on
    Foundations of Software Technology and Theoretical Computer Science</i>, Vol.
    250. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2022.11">https://doi.org/10.4230/LIPIcs.FSTTCS.2022.11</a>.
  ieee: K. Chatterjee, R. Ibsen-Jensen, I. R. Jecker, and J. Svoboda, “Complexity
    of spatial games,” in <i>42nd IARCS Annual Conference on Foundations of Software
    Technology and Theoretical Computer Science</i>, Madras, India, 2022, vol. 250.
  ista: 'Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. 2022. Complexity of spatial
    games. 42nd IARCS Annual Conference on Foundations of Software Technology and
    Theoretical Computer Science. FSTTC: Foundations of Software Technology and Theoretical
    Computer Science vol. 250, 11:1-11:14.'
  mla: Chatterjee, Krishnendu, et al. “Complexity of Spatial Games.” <i>42nd IARCS
    Annual Conference on Foundations of Software Technology and Theoretical Computer
    Science</i>, vol. 250, 11:1-11:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2022, doi:<a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2022.11">10.4230/LIPIcs.FSTTCS.2022.11</a>.
  short: K. Chatterjee, R. Ibsen-Jensen, I.R. Jecker, J. Svoboda, in:, 42nd IARCS
    Annual Conference on Foundations of Software Technology and Theoretical Computer
    Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
conference:
  end_date: 2022-12-20
  location: Madras, India
  name: 'FSTTC: Foundations of Software Technology and Theoretical Computer Science'
  start_date: 2022-12-18
date_created: 2023-01-01T23:00:50Z
date_published: 2022-12-14T00:00:00Z
date_updated: 2025-07-14T09:09:55Z
day: '14'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.FSTTCS.2022.11
ec_funded: 1
file:
- access_level: open_access
  checksum: a21e3ba2421e2c4a06aa2cb6d530ede1
  content_type: application/pdf
  creator: dernst
  date_created: 2023-01-20T10:19:19Z
  date_updated: 2023-01-20T10:19:19Z
  file_id: '12323'
  file_name: 2022_LIPICs_Chatterjee.pdf
  file_size: 657396
  relation: main_file
  success: 1
file_date_updated: 2023-01-20T10:19:19Z
has_accepted_license: '1'
intvolume: '       250'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 42nd IARCS Annual Conference on Foundations of Software Technology and
  Theoretical Computer Science
publication_identifier:
  isbn:
  - '9783959772617'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Complexity of spatial games
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 250
year: '2022'
...
---
_id: '12102'
abstract:
- lang: eng
  text: 'Given a Markov chain M = (V, v_0, δ), with state space V and a starting state
    v_0, and a probability threshold ε, an ε-core is a subset C of states that is
    left with probability at most ε. More formally, C ⊆ V is an ε-core, iff ℙ[reach
    (V\C)] ≤ ε. Cores have been applied in a wide variety of verification problems
    over Markov chains, Markov decision processes, and probabilistic programs, as
    a means of discarding uninteresting and low-probability parts of a probabilistic
    system and instead being able to focus on the states that are likely to be encountered
    in a real-world run. In this work, we focus on the problem of computing a minimal
    ε-core in a Markov chain. Our contributions include both negative and positive
    results: (i) We show that the decision problem on the existence of an ε-core of
    a given size is NP-complete. This solves an open problem posed in [Jan Kretínský
    and Tobias Meggendorfer, 2020]. We additionally show that the problem remains
    NP-complete even when limited to acyclic Markov chains with bounded maximal vertex
    degree; (ii) We provide a polynomial time algorithm for computing a minimal ε-core
    on Markov chains over control-flow graphs of structured programs. A straightforward
    combination of our algorithm with standard branch prediction techniques allows
    one to apply the idea of cores to find a subset of program lines that are left
    with low probability and then focus any desired static analysis on this core subset.'
acknowledgement: "The research was partially supported by the Hong Kong Research Grants
  Council ECS\r\nProject No. 26208122, ERC CoG 863818 (FoRM-SMArt), the European Union’s
  Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie
  Grant Agreement No. 665385, HKUST– Kaisa Joint Research Institute Project Grant
  HKJRI3A-055 and HKUST Startup Grant R9272. Ali Ahmadi and Roodabeh Safavi were interns
  at HKUST."
article_number: '29'
article_processing_charge: No
author:
- first_name: Ali
  full_name: Ahmadi, Ali
  last_name: Ahmadi
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Amir Kafshdar
  full_name: Goharshady, Amir Kafshdar
  id: 391365CE-F248-11E8-B48F-1D18A9856A87
  last_name: Goharshady
  orcid: 0000-0003-1702-6584
- first_name: Tobias
  full_name: Meggendorfer, Tobias
  id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
  last_name: Meggendorfer
  orcid: 0000-0002-1712-2165
- first_name: Roodabeh
  full_name: Safavi Hemami, Roodabeh
  id: 72ed2640-8972-11ed-ae7b-f9c81ec75154
  last_name: Safavi Hemami
- first_name: Dorde
  full_name: Zikelic, Dorde
  id: 294AA7A6-F248-11E8-B48F-1D18A9856A87
  last_name: Zikelic
  orcid: 0000-0002-4681-1699
citation:
  ama: 'Ahmadi A, Chatterjee K, Goharshady AK, Meggendorfer T, Safavi Hemami R, Zikelic
    D. Algorithms and hardness results for computing cores of Markov chains. In: <i>42nd
    IARCS Annual Conference on Foundations of Software Technology and Theoretical
    Computer Science</i>. Vol 250. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2022. doi:<a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29">10.4230/LIPIcs.FSTTCS.2022.29</a>'
  apa: 'Ahmadi, A., Chatterjee, K., Goharshady, A. K., Meggendorfer, T., Safavi Hemami,
    R., &#38; Zikelic, D. (2022). Algorithms and hardness results for computing cores
    of Markov chains. In <i>42nd IARCS Annual Conference on Foundations of Software
    Technology and Theoretical Computer Science</i> (Vol. 250). Madras, India: Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29">https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29</a>'
  chicago: Ahmadi, Ali, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer,
    Roodabeh Safavi Hemami, and Dorde Zikelic. “Algorithms and Hardness Results for
    Computing Cores of Markov Chains.” In <i>42nd IARCS Annual Conference on Foundations
    of Software Technology and Theoretical Computer Science</i>, Vol. 250. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29">https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29</a>.
  ieee: A. Ahmadi, K. Chatterjee, A. K. Goharshady, T. Meggendorfer, R. Safavi Hemami,
    and D. Zikelic, “Algorithms and hardness results for computing cores of Markov
    chains,” in <i>42nd IARCS Annual Conference on Foundations of Software Technology
    and Theoretical Computer Science</i>, Madras, India, 2022, vol. 250.
  ista: 'Ahmadi A, Chatterjee K, Goharshady AK, Meggendorfer T, Safavi Hemami R, Zikelic
    D. 2022. Algorithms and hardness results for computing cores of Markov chains.
    42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical
    Computer Science. FSTTC: Foundations of Software Technology and Theoretical Computer
    Science vol. 250, 29.'
  mla: Ahmadi, Ali, et al. “Algorithms and Hardness Results for Computing Cores of
    Markov Chains.” <i>42nd IARCS Annual Conference on Foundations of Software Technology
    and Theoretical Computer Science</i>, vol. 250, 29, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2022, doi:<a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29">10.4230/LIPIcs.FSTTCS.2022.29</a>.
  short: A. Ahmadi, K. Chatterjee, A.K. Goharshady, T. Meggendorfer, R. Safavi Hemami,
    D. Zikelic, in:, 42nd IARCS Annual Conference on Foundations of Software Technology
    and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2022.
conference:
  end_date: 2022-12-20
  location: Madras, India
  name: 'FSTTC: Foundations of Software Technology and Theoretical Computer Science'
  start_date: 2022-12-18
date_created: 2023-01-01T23:00:50Z
date_published: 2022-12-14T00:00:00Z
date_updated: 2025-07-14T09:09:55Z
day: '14'
ddc:
- '000'
department:
- _id: KrCh
- _id: GradSch
doi: 10.4230/LIPIcs.FSTTCS.2022.29
ec_funded: 1
file:
- access_level: open_access
  checksum: 6660c802489013f034c9e8bd57f4d46e
  content_type: application/pdf
  creator: dernst
  date_created: 2023-01-20T10:39:44Z
  date_updated: 2023-01-20T10:39:44Z
  file_id: '12324'
  file_name: 2022_LIPICs_Ahmadi.pdf
  file_size: 872534
  relation: main_file
  success: 1
file_date_updated: 2023-01-20T10:39:44Z
has_accepted_license: '1'
intvolume: '       250'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '665385'
  name: International IST Doctoral Program
publication: 42nd IARCS Annual Conference on Foundations of Software Technology and
  Theoretical Computer Science
publication_identifier:
  isbn:
  - '9783959772617'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Algorithms and hardness results for computing cores of Markov chains
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 250
year: '2022'
...