---
res:
bibo_abstract:
- 'We consider two player, zero-sum, finite-state concurrent reachability games,
played for an infinite number of rounds, where in every round, each player simultaneously
and independently of the other players chooses an action, whereafter the successor
state is determined by a probability distribution given by the current state and
the chosen actions. Player 1 wins iff a designated goal state is eventually visited.
We are interested in the complexity of stationary strategies measured by their
patience, which is defined as the inverse of the smallest non-zero probability
employed. Our main results are as follows: We show that: (i) the optimal bound
on the patience of optimal and -optimal strategies, for both players is doubly
exponential; and (ii) even in games with a single non-absorbing state exponential
(in the number of actions) patience is necessary. @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
- foaf_Person:
foaf_givenName: Kristofer
foaf_name: Hansen, Kristofer
foaf_surname: Hansen
- foaf_Person:
foaf_givenName: Rasmus
foaf_name: Ibsen-Jensen, Rasmus
foaf_surname: Ibsen-Jensen
foaf_workInfoHomepage: http://www.librecat.org/personId=3B699956-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0003-4783-0389
bibo_doi: 10.4230/LIPIcs.MFCS.2017.55
bibo_volume: 83
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/978-395977046-0
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Strategy complexity of concurrent safety games@
...