OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Relaxing Exclusive Control in Boolean Games

Belardinelli, Francesco and Grandi, Umberto and Herzig, Andreas and Longin, Dominique and Lorini, Emiliano and Novaro, Arianna and Perrussel, Laurent Relaxing Exclusive Control in Boolean Games. (2017) In: 16th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2017), 24 July 2017 - 26 July 2017 (Liverpool, United Kingdom).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://doi.org/10.4204/EPTCS.251.4


In the typical framework for boolean games (BG) each player can change the truth value of some propositional atoms, while attempting to make her goal true. In standard BG goals are propositional formulas, whereas in iterated BG goals are formulas of Linear Temporal Logic. Both notions of BG are characterised by the fact that agents have exclusive control over their set of atoms, meaning that no two agents can control the same atom. In the present contribution we drop the exclusivity assumption and explore structures where an atom can be controlled by multiple agents. We introduce Concurrent Game Structures with Shared Propositional Control (CGS-SPC) and show that they account for several classes of repeated games, including iterated boolean games, influence games, and aggregation games. Our main result shows that, as far as verification is concerned, CGS-SPC can be reduced to concurrent game structures with exclusive control. This result provides a polynomial reduction for the model checking problem of specifications in Alternating-time Temporal Logic on CGS-SPC.

Item Type:Conference or Workshop Item (Paper)
Additional Information:https://arxiv.org/abs/1707.08736v1
HAL Id:hal-01919061
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Université d'Évry-Val-d'Essonne - UEVE (FRANCE)
Laboratory name:
French ANR JCJC Project SVeDaS (ANR-16-CE40-0021)
Deposited On:16 Oct 2018 14:22

Repository Staff Only: item control page