---
res:
  bibo_abstract:
  - "We consider finite-state concurrent stochastic games, played by k>=2 players
    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. We consider reachability objectives that given a target set
    of states require that some state in the target set is visited, and the dual safety
    objectives that given a target set require that only states in the target set
    are 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.\r\n\r\n Our main results are as follows: We show that in two-player
    zero-sum concurrent stochastic games (with reachability objective for one player
    and the complementary safety objective for the other player): (i) the optimal
    bound on the patience of optimal and epsilon-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. In general we study
    the class of non-zero-sum games admitting epsilon-Nash equilibria. We show that
    if there is at least one player with reachability objective, then doubly-exponential
    patience is needed in general for epsilon-Nash equilibrium strategies, whereas
    in contrast if all players have safety objectives, then the optimal bound on patience
    for epsilon-Nash equilibrium strategies is only exponential.@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: 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
  - foaf_Person:
      foaf_givenName: Kristoffer
      foaf_name: Hansen, Kristoffer
      foaf_surname: Hansen
  bibo_doi: 10.15479/AT:IST-2015-322-v1-1
  dct_date: 2015^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/2664-1690
  dct_language: eng
  dct_publisher: IST Austria@
  dct_title: The patience of concurrent stochastic games with safety and reachability
    objectives@
...