Winning concurrent reachability games requires doubly-exponential patience

0336087 - MÚ 2010 RIV US eng C - Conference Paper (international conference)
Hansen, K.A. - Koucký, Michal - Miltersen, P.B.
Winning concurrent reachability games requires doubly-exponential patience.
Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LISC 2009. Los Angeles: IEEE Computer Society, 2009, s. 332-341. ISBN 978-0-7695-3746-7. ISSN 1043-6871.
[24th Annual IEEE Symposium on Logic in Computer Science. Los Angeles (US), 11.08.2009-14.08.2009]
R&D Projects: GA ČR GP201/07/P276; GA AV ČR IAA100190902; GA MŠMT(CZ) 1M0545
Institutional research plan: CEZ:AV0Z10190503
Keywords : concurrent reachability game * patience * winning strategies
Subject RIV: BA - General Mathematics

We exhibit a deterministic concurrent reachability game PURGATORY_n 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 /epsilon <1/2 must use non-zero behavior probabilities that are less than (/epsilon^2/1-/epsilon))^{2^{n-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.
Permanent Link: http://hdl.handle.net/11104/0180404