Winning Concurrent Reachability Games Requires Doubly-Exponential Patience

TY - GEN

T1 - Winning Concurrent Reachability Games Requires Doubly-Exponential Patience

AU - Hansen, Kristoffer Arnsfelt

AU - Koucký, Michal

AU - Miltersen, Peter Bro

N1 - Conference code: 24

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

U2 - 10.1109/LICS.2009.44

DO - 10.1109/LICS.2009.44

M3 - Conference article

SN - 1043-6871

SP - 332

EP - 341

JO - Symposium on Logic in Computer Science

JF - Symposium on Logic in Computer Science

T2 - Annual IEEE Symposium on Logic in Computer Science. LICS'09

Y2 - 11 August 2009 through 14 August 2009

ER -