A Modal Logic for Joint Abilities under Strategy Commitments
Zhaoshuai Liu, Liping Xiong, Yongmei Liu, Yves Lespérance, Ronghai Xu, Hongyi Shi
Abstract
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.
BibTeX
@inproceedings{ijcai2020p250,
title = {A Modal Logic for Joint Abilities under Strategy Commitments},
author = {Liu, Zhaoshuai and Xiong, Liping and Liu, Yongmei and Lespérance, Yves and Xu, Ronghai and Shi, Hongyi},
booktitle = {Proceedings of the Twenty-Ninth International Joint Conference on
Artificial Intelligence, {IJCAI-20}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Christian Bessiere},
pages = {1805--1812},
year = {2020},
month = {7},
note = {Main track},
doi = {10.24963/ijcai.2020/250},
url = {https://doi.org/10.24963/ijcai.2020/250},
}