Non-Cooperative Rational Synthesis Problem on Stochastic Games for Positional Strategies

Synthesis problems on multiplayer non-zero-sum games (MG) with multiple environment players that behave rationally are the problems to find a good strategy of the system and have been extensively studied. This paper concerns the synthesis problems on stochastic MG (SMG), where a special controller other than players, called nature, which chooses a move in its turn randomly, may exist. Two types of synthesis problems on SMG exist: cooperative rational synthesis problem (CRSP) and non-cooperative rational synthesis problem (NCRSP). The rationality of environment players is modeled by Nash equilibria, and CRSP is the problem to decide whether there exists a Nash equilibrium that gives the system a payoff not less than a given threshold. Ummels et al. studied the complexity of CRSP for various classes of objectives and strategies of players. CRSP fits the situation where the system can make a suggestion of a strategy profile (a tuple of strategies of all players) to the environment players. However, in real applications, the system may rarely have an opportunity to make suggestions to the environment, and thus CRSP is optimistic. NCRSP is the problem to decide whether there exists a strategy σ0 of the system satisfying that for every strategy profile of the environment players that forms a 0-fixed Nash equilibrium (a Nash equilibrium where the system's strategy is fixed to σ0), the system obtains a payoff not less than a given threshold. In this paper, we investigate the complexity of NCRSP for positional (i.e. pure memoryless) strategies. We consider ω-regular objectives as the model of players' objectives, and show the complexity results of the problem for several subclasses of ω-regular objectives. In particular, the problem for terminal reachability (TR) objectives is shown to be Σp2-complete.