---
res:
  bibo_abstract:
  - "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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Ali
      foaf_name: Asadi, Ali
      foaf_surname: Asadi
      foaf_workInfoHomepage: http://www.librecat.org/personId=02d96aae-000e-11ec-b801-cadd0a5eefbb
  - foaf_Person:
      foaf_givenName: Krishnendu
      foaf_name: Chatterjee, Krishnendu
      foaf_surname: Chatterjee
      foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-4561-241X
  - foaf_Person:
      foaf_givenName: Raimundo J
      foaf_name: Saona Urmeneta, Raimundo J
      foaf_surname: Saona Urmeneta
      foaf_workInfoHomepage: http://www.librecat.org/personId=BD1DF4C4-D767-11E9-B658-BC13E6697425
    orcid: 0000-0001-5103-038X
  - foaf_Person:
      foaf_givenName: Jakub
      foaf_name: Svoboda, Jakub
      foaf_surname: Svoboda
      foaf_workInfoHomepage: http://www.librecat.org/personId=130759D2-D7DD-11E9-87D2-DE0DE6697425
    orcid: 0000-0002-1419-3267
  bibo_doi: 10.4230/LIPIcs.FSTTCS.2024.5
  bibo_volume: 323
  dct_date: 2024^xs_gYear
  dct_identifier:
  - UT:001537516500005
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/9783959773553
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: 'Concurrent stochastic games with stateful-discounted and parity objectives:
    Complexity and algorithms@'
...