---
_id: '2054'
abstract:
- lang: eng
  text: 'We study two-player concurrent games on finite-state graphs played for an
    infinite number of rounds, where in each round, the two players (player 1 and
    player 2) choose their moves independently and simultaneously; the current state
    and the two moves determine the successor state. The objectives are ω-regular
    winning conditions specified as parity objectives. We consider the qualitative
    analysis problems: the computation of the almost-sure and limit-sure winning set
    of states, where player 1 can ensure to win with probability 1 and with probability
    arbitrarily close to 1, respectively. In general the almost-sure and limit-sure
    winning strategies require both infinite-memory as well as infinite-precision
    (to describe probabilities). While the qualitative analysis problem for concurrent
    parity games with infinite-memory, infinite-precision randomized strategies was
    studied before, we study the bounded-rationality problem for qualitative analysis
    of concurrent parity games, where the strategy set for player 1 is restricted
    to bounded-resource strategies. In terms of precision, strategies can be deterministic,
    uniform, finite-precision, or infinite-precision; and in terms of memory, strategies
    can be memoryless, finite-memory, or infinite-memory. We present a precise and
    complete characterization of the qualitative winning sets for all combinations
    of classes of strategies. In particular, we show that uniform memoryless strategies
    are as powerful as finite-precision infinite-memory strategies, and infinite-precision
    memoryless strategies are as powerful as infinite-precision finite-memory strategies.
    We show that the winning sets can be computed in (n2d+3) time, where n is the
    size of the game structure and 2d is the number of priorities (or colors), and
    our algorithms are symbolic. The membership problem of whether a state belongs
    to a winning set can be decided in NP ∩ coNP. Our symbolic algorithms are based
    on a characterization of the winning sets as μ-calculus formulas, however, our
    μ-calculus formulas are crucially different from the ones for concurrent parity
    games (without bounded rationality); and our memoryless witness strategy constructions
    are significantly different from the infinite-memory witness strategy constructions
    for concurrent parity games.'
alternative_title:
- LNCS
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
citation:
  ama: 'Chatterjee K. Qualitative concurrent parity games: Bounded rationality. In:
    Baldan P, Gorla D, eds. <i>Lecture Notes in Computer Science (Including Subseries
    Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i>.
    Vol 8704. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2014:544-559. doi:<a
    href="https://doi.org/10.1007/978-3-662-44584-6_37">10.1007/978-3-662-44584-6_37</a>'
  apa: 'Chatterjee, K. (2014). Qualitative concurrent parity games: Bounded rationality.
    In P. Baldan &#38; D. Gorla (Eds.), <i>Lecture Notes in Computer Science (including
    subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i>
    (Vol. 8704, pp. 544–559). Rome, Italy: Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik. <a href="https://doi.org/10.1007/978-3-662-44584-6_37">https://doi.org/10.1007/978-3-662-44584-6_37</a>'
  chicago: 'Chatterjee, Krishnendu. “Qualitative Concurrent Parity Games: Bounded
    Rationality.” In <i>Lecture Notes in Computer Science (Including Subseries Lecture
    Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i>, edited
    by Paolo Baldan and Daniele Gorla, 8704:544–59. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2014. <a href="https://doi.org/10.1007/978-3-662-44584-6_37">https://doi.org/10.1007/978-3-662-44584-6_37</a>.'
  ieee: 'K. Chatterjee, “Qualitative concurrent parity games: Bounded rationality,”
    in <i>Lecture Notes in Computer Science (including subseries Lecture Notes in
    Artificial Intelligence and Lecture Notes in Bioinformatics)</i>, Rome, Italy,
    2014, vol. 8704, pp. 544–559.'
  ista: 'Chatterjee K. 2014. Qualitative concurrent parity games: Bounded rationality.
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial
    Intelligence and Lecture Notes in Bioinformatics). CONCUR: Concurrency Theory,
    LNCS, vol. 8704, 544–559.'
  mla: 'Chatterjee, Krishnendu. “Qualitative Concurrent Parity Games: Bounded Rationality.”
    <i>Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial
    Intelligence and Lecture Notes in Bioinformatics)</i>, edited by Paolo Baldan
    and Daniele Gorla, vol. 8704, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2014, pp. 544–59, doi:<a href="https://doi.org/10.1007/978-3-662-44584-6_37">10.1007/978-3-662-44584-6_37</a>.'
  short: K. Chatterjee, in:, P. Baldan, D. Gorla (Eds.), Lecture Notes in Computer
    Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture
    Notes in Bioinformatics), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014,
    pp. 544–559.
conference:
  end_date: 2014-09-05
  location: Rome, Italy
  name: 'CONCUR: Concurrency Theory'
  start_date: 2014-09-02
corr_author: '1'
date_created: 2018-12-11T11:55:27Z
date_published: 2014-09-01T00:00:00Z
date_updated: 2026-07-07T14:02:37Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-662-44584-6_37
ec_funded: 1
editor:
- first_name: Paolo
  full_name: Baldan, Paolo
  last_name: Baldan
- first_name: Daniele
  full_name: Gorla, Daniele
  last_name: Gorla
intvolume: '      8704'
language:
- iso: eng
month: '09'
oa_version: None
page: 544 - 559
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
  name: Microsoft Research Faculty Fellowship
publication: Lecture Notes in Computer Science (including subseries Lecture Notes
  in Artificial Intelligence and Lecture Notes in Bioinformatics)
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '4992'
quality_controlled: '1'
related_material:
  record:
  - id: '3354'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: 'Qualitative concurrent parity games: Bounded rationality'
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8704
year: '2014'
...