Sub-game optimal strategies in concurrent games with prefix-independent objectives

01/25/2023
by   Benjamin Bordais, et al.
0

We investigate concurrent two-player win/lose stochastic games on finite graphs with prefix-independent objectives. We characterize subgame optimal strategies and use this characterization to show various memory transfer results: 1) For a given (prefix-independent) objective, if every game that has a subgame almost-surely winning strategy also has a positional one, then every game that has a subgame optimal strategy also has a positional one; 2) Assume that the (prefix-independent) objective has a neutral color. If every turn-based game that has a subgame almost-surely winning strategy also has a positional one, then every game that has a finite-choice (notion to be defined) subgame optimal strategy also has a positional one. We collect or design examples to show that our results are tight in several ways. We also apply our results to Büchi, co-Büchi, parity, mean-payoff objectives, thus yielding simpler statements.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset