A Modal Logic for Joint Abilities under Strategy Commitments

A Modal Logic for Joint Abilities under Strategy Commitments

Zhaoshuai Liu, Liping Xiong, Yongmei Liu, Yves Lespérance, Ronghai Xu, Hongyi Shi

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 1805-1812. https://doi.org/10.24963/ijcai.2020/250

Representation and reasoning about strategic abilities has been an active research area in AI and multi-agent systems. Many variations and extensions of alternating-time temporal logic ATL have been proposed. However, most of the logical frameworks ignore the issue of coordination within a coalition, and are unable to specify the internal structure of strategies. In this paper, we propose JAADL, a modal logic for joint abilities under strategy commitments, which is an extension of ATL. Firstly, we introduce an operator of elimination of (strictly) dominated strategies, with which we can represent joint abilities of coalitions. Secondly, our logic is based on linear dynamic logic (LDL), an extension of linear temporal logic (LTL), so that we can use regular expressions to represent commitments to structured strategies. We analyze valid formulas in JAADL, give sufficient/necessary conditions for joint abilities, and show that model checking memoryless JAADL is in EXPTIME.
Keywords:
Knowledge Representation and Reasoning: Logics for Knowledge Representation