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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Braberman, Víctor Adrián
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:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_97815090_v_n_p6996_Rodriguez
record_format dspace
spelling paper:paper_97815090_v_n_p6996_Rodriguez2023-06-08T16:37:54Z 21/2-player generalized reactivity (1) games Braberman, Víctor Adrián 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. Fil:Braberman, V. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2016 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
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
description 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.
author Braberman, Víctor Adrián
spellingShingle Braberman, Víctor Adrián
21/2-player generalized reactivity (1) games
author_facet Braberman, Víctor Adrián
author_sort Braberman, Víctor Adrián
title 21/2-player generalized reactivity (1) games
title_short 21/2-player generalized reactivity (1) games
title_full 21/2-player generalized reactivity (1) games
title_fullStr 21/2-player generalized reactivity (1) games
title_full_unstemmed 21/2-player generalized reactivity (1) games
title_sort 21/2-player generalized reactivity (1) games
publishDate 2016
url 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
work_keys_str_mv AT brabermanvictoradrian 212playergeneralizedreactivity1games
_version_ 1768544754198380544

Ejemplares similares