Paper Info
Title
Winning Concurrent Reachability Games Requires Doubly-Exponential Patience
Abstract
We exhibit a deterministic concurrent reachability game PURGATORYn with n non-terminal positions and a binary choice for both players in every position so that any positional strategy for Player 1 achieving the value of the game within given isin < 1/2 must use non-zero behavior probabilities that are less than (isin2/(1 - isin))2n-2 . Also, even to achieve the value within say 1 - 2-n/2, doubly exponentially small behavior probabilities in the number of positions must be used. This behavior is close to worst case: We show that for any such game and 0 < isin < 1/2, there is an isin-optimal strategy with all non-zero behavior probabilities being 20(n) at least isin2O(n). As a corollary to our results, we conclude that any (deterministic or nondeterministic) algorithm that given a concurrent reachability game explicitly manipulates isin-optimal strategies for Player 1 represented in several standard ways (e.g., with binary representation of probabilities or as the uniform distribution over a multiset) must use at least exponential space in the worst case.
Year
DOI
Venue
2009
10.1109/LICS.2009.44
Los Angeles, CA
Keywords
Field
DocType
computational complexity,game theory,reachability analysis,PURGATORYn,concurrent reachability games,doubly-exponential patience,isin-optimal strategy,nonzero behavior probabilities
Discrete mathematics,Combinatorics,Markov process,Exponential function,Polynomial,Upper and lower bounds,Computer science,Reachability,Game theory,Computational complexity theory,Binary number
Conference
ISSN
ISBN
Citations 
1043-6871
978-0-7695-3746-7
16
PageRank 
References 
Authors
1.14
9
3
Name
Order
Citations
PageRank
Kristoffer Arnsfelt Hansen117621.40
Michal Koucký239231.87
Peter Bro Miltersen3114694.49