21/2-player generalized reactivity (1) games
File(s)paper.pdf (340.36 KB)
Accepted version
Author(s)
Rodriguez, N
Braberman, V
D'Ippolito, N
Uchitel, S
Type
Conference Paper
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.
Date Issued
2016-12-29
Date Acceptance
2016-12-12
Citation
2016 IEEE 55th Conference on Decision and Control, CDC 2016, 2016, pp.6996-7001
ISBN
9781509018376
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Start Page
6996
End Page
7001
Journal / Book Title
2016 IEEE 55th Conference on Decision and Control, CDC 2016
Copyright Statement
© 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Source
2016 IEEE 55th Conference on Decision and Control, CDC 2016
Publication Status
Published
Start Date
2016-12-12
Finish Date
2016-12-14