21/2-player generalized reactivity (1) games
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 polynom...
Guardado en:
| Autor principal: | |
|---|---|
| Publicado: |
2016
|
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_97815090_v_n_p6996_Rodriguez http://hdl.handle.net/20.500.12110/paper_97815090_v_n_p6996_Rodriguez |
| Aporte de: |
| Sumario: | 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. © 2016 IEEE. |
|---|