Krishnendu Chatterjee, Luca de Alfaro and Thomas A. Henzinger

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-05-1406
August 2005

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/CSD-05-1406.pdf

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},
    Institution = {EECS Department, University of California, Berkeley},
    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