Author(s):

Chatterjee, Krishnendu; Hansen, Kristofer A; IbsenJensen, Rasmus

Title: 
Strategy complexity of concurrent safety games

Title Series: 
LIPIcs

Affiliation 
IST Austria 
Abstract: 
We consider two player, zerosum, finitestate 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 nonzero 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 nonabsorbing state exponential (in the number of actions) patience is necessary.

Keywords: 
concurrent games; patience of strategies; reachability and safety

Conference Title:

MFCS: Mathematical Foundations of Computer Science (SG)

Volume: 
83

Conference Dates:

August 21  25, 2017

Conference Location:

Aalborg, Denmark

Publisher:

Schloss Dagstuhl  LeibnizZentrum für Informatik

Date Published:

20171101

Start Page: 
Article number: 55

Copyright Statement: 
CC BY

URL: 

DOI: 
10.4230/LIPIcs.MFCS.2017.55

Open access: 
yes (OA journal) 