---
OA_type: closed access
_id: '3890'
abstract:
- lang: eng
  text: We consider two-player infinite games played on graphs. The games are concurrent,
    in that at each state the players choose their moves simultaneously and independently,
    and stochastic, in that the moves determine a probability distribution for the
    successor state. The value of a game is the maximal probability with which a player
    can guarantee the satisfaction of her objective. We show that the values of concurrent
    games with w-regular objectives expressed as parity conditions can be decided
    in NP boolean AND coNP. This result substantially improves the best known previous
    bound of 3EXPTIME. It also shows that the full class of concurrent parity games
    is no harder than the special case of turn-based stochastic reachability games,
    for which NP boolean AND coNP is the best known bound. While the previous, more
    restricted NP boolean AND coNP results for graph games relied on the existence
    of particularly simple (pure memoryless) optimal strategies, in concurrent games
    with parity objectives optimal strategies may not exist, and epsilon-optimal strategies
    (which achieve the value of the game within a parameter epsilon > 0) require
    in general both randomization and infinite memory. Hence our proof must rely on
    a more detailed analysis of strategies and, in addition to the main result, yields
    two results that are interesting on their own. First, we show that there exist
    epsilon-optimal strategies that in the limit coincide with memoryless strategies;
    this parallels the celebrated result of Mertens-Neyman for concurrent games with
    limit-average objectives. Second, we complete the characterization of the memory
    requirements for epsilon-optimal strategies for concurrent games with parity conditions,
    by showing that memoryless strategies suffice for epsilon-optimality for coBachi
    conditions.
acknowledgement: This research was supported in part by the AFOSR MURI grant F49620-00-1-0327
  and the NSF ITR grant CCR-0225610.
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: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
citation:
  ama: 'Chatterjee K, De Alfaro L, Henzinger TA. The complexity of quantitative concurrent
    parity games. In: <i>Proceedings of the Seventeenth Annual ACM-SIAM Symposium
    on Discrete Algorithm</i>. SIAM; 2006:678-687. doi:<a href="https://doi.org/10.1145/1109557.1109631">10.1145/1109557.1109631</a>'
  apa: 'Chatterjee, K., De Alfaro, L., &#38; Henzinger, T. A. (2006). The complexity
    of quantitative concurrent parity games. In <i>Proceedings of the seventeenth
    annual ACM-SIAM symposium on Discrete algorithm</i> (pp. 678–687). Miami, FL,
    United States: SIAM. <a href="https://doi.org/10.1145/1109557.1109631">https://doi.org/10.1145/1109557.1109631</a>'
  chicago: Chatterjee, Krishnendu, Luca De Alfaro, and Thomas A Henzinger. “The Complexity
    of Quantitative Concurrent Parity Games.” In <i>Proceedings of the Seventeenth
    Annual ACM-SIAM Symposium on Discrete Algorithm</i>, 678–87. SIAM, 2006. <a href="https://doi.org/10.1145/1109557.1109631">https://doi.org/10.1145/1109557.1109631</a>.
  ieee: K. Chatterjee, L. De Alfaro, and T. A. Henzinger, “The complexity of quantitative
    concurrent parity games,” in <i>Proceedings of the seventeenth annual ACM-SIAM
    symposium on Discrete algorithm</i>, Miami, FL, United States, 2006, pp. 678–687.
  ista: 'Chatterjee K, De Alfaro L, Henzinger TA. 2006. The complexity of quantitative
    concurrent parity games. Proceedings of the seventeenth annual ACM-SIAM symposium
    on Discrete algorithm. SODA: Symposium on Discrete Algorithms, 678–687.'
  mla: Chatterjee, Krishnendu, et al. “The Complexity of Quantitative Concurrent Parity
    Games.” <i>Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete
    Algorithm</i>, SIAM, 2006, pp. 678–87, doi:<a href="https://doi.org/10.1145/1109557.1109631">10.1145/1109557.1109631</a>.
  short: K. Chatterjee, L. De Alfaro, T.A. Henzinger, in:, Proceedings of the Seventeenth
    Annual ACM-SIAM Symposium on Discrete Algorithm, SIAM, 2006, pp. 678–687.
conference:
  end_date: 2006-01-26
  location: Miami, FL, United States
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2006-01-22
date_created: 2018-12-11T12:05:43Z
date_published: 2006-01-01T00:00:00Z
date_updated: 2026-08-27T07:53:44Z
day: '01'
doi: 10.1145/1109557.1109631
extern: '1'
fulldoi: https://doi.org/10.1145/1109557.1109631
language:
- iso: eng
month: '01'
oa_version: None
page: 678 - 687
publication: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete
  algorithm
publication_identifier:
  isbn:
  - '9780898716054'
publication_status: published
publisher: SIAM
publist_id: '2273'
status: public
title: The complexity of quantitative concurrent parity games
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2006'
...