---
res:
  bibo_abstract:
  - '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.@eng'
  bibo_authorlist:
  - 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
  bibo_doi: 10.1007/978-3-662-44584-6_37
  bibo_volume: 8704
  dct_date: 2014^xs_gYear
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: 'Qualitative concurrent parity games: Bounded rationality@'
...