UC BERKELEY
EECS technical reports
TECHNICAL REPORTS


CSD-05-1406.pdf
CSD-05-1406.ps
Conditions of Use

Archive Home Page

Memoryless Strategies in Concurrent Games with Reachability Objectives

Authors:
Chatterjee, Krishnendu
de Alfaro, Luca
Henzinger, Thomas A.
Technical Report Identifier: CSD-05-1406
August 2005
CSD-05-1406.pdf
CSD-05-1406.ps

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.