2½-player generalized reactivity (1) games

DIPPOLITO R. NICOLAS; BRABERMAN VICTOR; RODRIGUEZ, NATALIA; UCHITEL SEBASTIAN

Congreso; 55th IEEE Conference on Decision and Control, CDC 2016,; 2016

We introduce a new class of 2½-player games, the 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 2½-player GR(1) games with polynomial-time complexity. Our approach is based on a reduction from 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. □) in a 2-player GR(1) game, an almost-sure (resp. positively) winning strategy for its corresponding 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 2½-player game, more precisely, it is linear with respect to the number of probabilistic states in the 2½-player GR(1) game.