Krishnendu Chatterjee and Luca de Alfaro and Thomas A. Henzinger

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-05-1406

2005

We present a simple proof of the fact that in concurrent games with reachability objectives, for all epsilon > 0, memoryless epsilon-optimal strategies exist. A memoryless strategy is independent of the history of plays; and an epsilon-optimal strategy achieves the objective with probability within epsilon of the value of the game. In contrast to previous proofs of this fact, which rely on the limit behavior of discounted games using advanced Puisieux series analysis, our proof is elementary and combinatorial.

---

BibTeX citation:

@techreport{Chatterjee:CSD-05-1406,
    Author= {Chatterjee, Krishnendu and de Alfaro, Luca and Henzinger, Thomas A.},
    Title= {Memoryless Strategies in Concurrent Games with Reachability Objectives},
    Year= {2005},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5248.html},
    Number= {UCB/CSD-05-1406},
    Abstract= {We present a simple proof of the fact that in concurrent games with reachability objectives, for all epsilon > 0, memoryless epsilon-optimal strategies exist. A memoryless strategy is independent of the history of plays; and an epsilon-optimal strategy achieves the objective with probability within epsilon of the value of the game. In contrast to previous proofs of this fact, which rely on the limit behavior of discounted games using advanced Puisieux series analysis, our proof is elementary and combinatorial.},
}

EndNote citation:

%0 Report
%A Chatterjee, Krishnendu 
%A de Alfaro, Luca 
%A Henzinger, Thomas A. 
%T Memoryless Strategies in Concurrent Games with Reachability Objectives
%I EECS Department, University of California, Berkeley
%D 2005
%@ UCB/CSD-05-1406
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5248.html
%F Chatterjee:CSD-05-1406