# Memoryless Strategies in Concurrent Games with Reachability Objectives

### 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://www.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://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/2005/5248.html %F Chatterjee:CSD-05-1406