---
OA_place: publisher
OA_type: gold
_id: '17099'
abstract:
- lang: eng
  text: "We study two-player zero-sum concurrent stochastic games with finite state
    and action space played for an infinite number of steps. In every step, the two
    players simultaneously and independently choose an action. Given the current state
    and the chosen actions, the next state is obtained according to a stochastic transition
    function. An objective is a measurable function on plays (or infinite trajectories)
    of the game, and the value for an objective is the maximal expectation that the
    player can guarantee against the adversarial player. We consider: (a) stateful-discounted
    objectives, which are similar to the classical discounted-sum objectives, but
    states are associated with different discount factors rather than a single discount
    factor; and (b) parity objectives, which are a canonical representation for ω-regular
    objectives. For stateful-discounted objectives, given an ordering of the discount
    factors, the limit value is the limit of the value of the stateful-discounted
    objectives, as the discount factors approach zero according to the given order.\r\nThe
    computational problem we consider is the approximation of the value within an
    arbitrary\r\nadditive error. The above problem is known to be in EXPSPACE for
    the limit value of statefuldiscounted objectives and in PSPACE for parity objectives.
    The best-known algorithms for both the above problems are at least exponential
    time, with an exponential dependence on the number of states and actions. Our
    main results for the value approximation problem for the limit value of stateful-discounted
    objectives and parity objectives are as follows: (a) we establish TFNP[NP] complexity;
    and (b) we present algorithms that improve the dependency on the number of actions
    in the exponent from linear to logarithmic. In particular, if the number of states
    is constant, our algorithms run in polynomial time."
acknowledgement: "This research was partially supported by ERC CoG 863818 (ForM-SMArt),
  Austrian\r\nScience Fund (FWF) 10.55776/COE12, and French Agence Nationale de la
  Recherche (ANR)\r\nANR-21-CE40-0020 (CONVERGENCE project)"
alternative_title:
- LIPIcs
article_number: '5'
article_processing_charge: No
arxiv: 1
author:
- first_name: Ali
  full_name: Asadi, Ali
  id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
  last_name: Asadi
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Raimundo J
  full_name: Saona Urmeneta, Raimundo J
  id: BD1DF4C4-D767-11E9-B658-BC13E6697425
  last_name: Saona Urmeneta
  orcid: 0000-0001-5103-038X
- first_name: Jakub
  full_name: Svoboda, Jakub
  id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
  last_name: Svoboda
  orcid: 0000-0002-1419-3267
citation:
  ama: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Concurrent stochastic
    games with stateful-discounted and parity objectives: Complexity and algorithms.
    In: <i>44th IARCS Annual Conference on Foundations of Software Technology and
    Theoretical Computer Science</i>. Vol 323. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik; 2024. doi:<a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5">10.4230/LIPIcs.FSTTCS.2024.5</a>'
  apa: 'Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., &#38; Svoboda, J. (2024).
    Concurrent stochastic games with stateful-discounted and parity objectives: Complexity
    and algorithms. In <i>44th IARCS Annual Conference on Foundations of Software
    Technology and Theoretical Computer Science</i> (Vol. 323). Gujarat, India: Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5">https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5</a>'
  chicago: 'Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Jakub
    Svoboda. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives:
    Complexity and Algorithms.” In <i>44th IARCS Annual Conference on Foundations
    of Software Technology and Theoretical Computer Science</i>, Vol. 323. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5">https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5</a>.'
  ieee: 'A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and J. Svoboda, “Concurrent
    stochastic games with stateful-discounted and parity objectives: Complexity and
    algorithms,” in <i>44th IARCS Annual Conference on Foundations of Software Technology
    and Theoretical Computer Science</i>, Gujarat, India, 2024, vol. 323.'
  ista: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. 2024. Concurrent stochastic
    games with stateful-discounted and parity objectives: Complexity and algorithms.
    44th IARCS Annual Conference on Foundations of Software Technology and Theoretical
    Computer Science. FSTTCS: Foundations of Software Technology and Theoretical Computer
    Science, LIPIcs, vol. 323, 5.'
  mla: 'Asadi, Ali, et al. “Concurrent Stochastic Games with Stateful-Discounted and
    Parity Objectives: Complexity and Algorithms.” <i>44th IARCS Annual Conference
    on Foundations of Software Technology and Theoretical Computer Science</i>, vol.
    323, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5">10.4230/LIPIcs.FSTTCS.2024.5</a>.'
  short: A. Asadi, K. Chatterjee, R.J. Saona Urmeneta, J. Svoboda, in:, 44th IARCS
    Annual Conference on Foundations of Software Technology and Theoretical Computer
    Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
  end_date: 2024-12-18
  location: Gujarat, India
  name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science'
  start_date: 2024-12-16
corr_author: '1'
date_created: 2024-06-03T07:44:27Z
date_published: 2024-12-05T00:00:00Z
date_updated: 2025-12-02T13:40:52Z
day: '05'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.FSTTCS.2024.5
ec_funded: 1
external_id:
  arxiv:
  - '2405.02486'
  isi:
  - '001537516500005'
file:
- access_level: open_access
  checksum: 5b544ab4692b93300b404435c036ddd4
  content_type: application/pdf
  creator: dernst
  date_created: 2025-01-08T09:49:31Z
  date_updated: 2025-01-08T09:49:31Z
  file_id: '18777'
  file_name: 2024_LIPIcs_Asadi.pdf
  file_size: 847960
  relation: main_file
  success: 1
file_date_updated: 2025-01-08T09:49:31Z
has_accepted_license: '1'
intvolume: '       323'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
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: 44th IARCS Annual Conference on Foundations of Software Technology and
  Theoretical Computer Science
publication_identifier:
  isbn:
  - '9783959773553'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Concurrent stochastic games with stateful-discounted and parity objectives:
  Complexity and algorithms'
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: 323
year: '2024'
...