21/2-player generalized reactivity (1) games

File Description SizeFormat 
paper.pdfAccepted version340.36 kBAdobe PDFDownload
Title: 21/2-player generalized reactivity (1) games
Author(s): Rodriguez, N
Braberman, V
D'Ippolito, N
Uchitel, S
Item 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.
Publication Date: 29-Dec-2016
Date of Acceptance: 12-Dec-2016
URI: http://hdl.handle.net/10044/1/44793
DOI: https://dx.doi.org/10.1109/CDC.2016.7799347
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.
Conference Name: 2016 IEEE 55th Conference on Decision and Control, CDC 2016
Publication Status: Published
Start Date: 2016-12-12
Finish Date: 2016-12-14
Appears in Collections:Faculty of Engineering
Computing



Items in Spiral are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commons