Arena-independent finite-memory determinacy in stochastic games (Q6830509)

The paper studies two-player, perfect-information, stochastic zero-sum games and investigates the complexity of optimal strategies. In particular, it provides conditions under which a class of strategies called ``arena-independent finite-memory'' (AIFM) strategies are sufficient, in the sense that that class includes an optimal strategy. The paper extends research on deterministic games to the case of stochastic games.\N\NIn this context, a game is partially specified by an ``arena'', meaning a directed graph whose vertices are partitioned into those controlled by Player 1 and those controlled by Player 2, and a mapping from the action chosen at each vertex to an arbitrary set of ``colors''. Players' preferences are defined over colors. A ``memory skeleton'' is a set of states together with a mapping that takes the color and the current memory state and outputs the updated memory state. Thus, a given memory skeleton can be applied to any arena, given the set of colors. A finite-memory strategy, then, is a mapping from memory states arena vertices to actions.\N\NAIFM strategies are sufficient if there exists a memory skeleton such that some strategy based on that memory skeleton is optimal for any arena. Whether or not AIFM strategies are sufficient depends on the players' preferences. There are three main results: ``First, we show that objectives for which pure AIFM strategies suffice to play optimally also admit pure AIFM subgame perfect strategies. Second, we show that we can reduce the study of objectives for which pure AIFM strategies suffice in two-player stochastic games to the easier study of one-player stochastic games (i.e., Markov decision processes). Third, we characterize the sufficiency of AIFM strategies through two intuitive properties of objectives.''