---
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@'
...