How to we remember the past in randomised strategies?
Abstract.
Infinite graph games are a natural model for open reactive processes: one
player represents the controller, trying to ensure a given specification, and
the other represents a hostile environment. The evolution of the system
depends on the decisions of both players, sometimes supplemented by a random
function.
In this work, we focus on the notion of randomised strategy. More specifically, we show that two very natural ways of defining these lead to very different results: in the most extreme cases, an almost-surely winning situation may become almost-surely losing if the player is only allowed to use the weaker notion of strategies. In more reasonable settings, translations exist, but they require infinite memory, even in very simple cases. Finally, some traditional problems becomes undecidable for strong strategies.