21/2-player generalized reactivity (1) games

Abstract

We introduce a new class of 21/2-player games, the 21/2-player GR(1) games, that allows for solving problems of stochastic nature by adding a probabilistic component to simple 2-player GR(1) games. Further, we present an efficient approach for solving qualitative 21/2-player GR(1) games with polynomial-time complexity. Our approach is based on a reduction from 21/2-player GR(1) games to 2-player GR(1) games that allows for solving the game and constructing, from a sure winning strategy for player □ (resp. L) in a 2-player GR(1) game, an almost-sure (resp. positively) winning strategy for its corresponding 21/2-player GR(1) game. Key to the effectiveness of the proposed approach is the fact that the reduction generates a 2-player game that is linearly larger than the original 21/2-player game, more precisely, it is linear with respect to the number of probabilistic states in the 21/2-player GR(1) game.