A Modal Logic for Joint Abilities under Strategy Commitments

Zhaoshuai Liu, Liping Xiong, Yongmei Liu, Yves Lespérance, Ronghai Xu, Hongyi ShiIJCAI 2020 · DOI

TL;DR

This paper introduces JAADL, a new modal logic for reasoning about joint abilities in multi-agent systems, extending ATL* with operators for eliminating dominated strategies and using linear dynamic logic (LDL) to represent structured strategy commitments. This allows for more expressive modeling of coordination problems and strategic interactions, with the authors demonstrating its utility and showing that model checking memoryless JAADL is EXPTIME-complete.

What Problem Does This Paper Address?

Multi-agent systems research has long grappled with how to represent and reason about the strategic abilities of coalitions of agents. While existing logics like ATL* provide a framework for this, they often fall short in two key areas: coordination within a coalition and the internal structure of strategies. The coordination problem arises because even if a coalition has a group strategy to achieve a goal, individual agents might not know others' exact choices, potentially leading to failure. Furthermore, strategies are often treated as abstract objects, neglecting how their internal structure (e.g., following specific rules or programs) can impact outcomes. This paper aims to bridge this gap by introducing a logic that explicitly models strategy commitments and allows for reasoning about joint abilities after eliminating strategically inferior options.

Methods

The core contribution is the introduction of JAADL (Joint Abilities under Strategy Commitments), a modal logic that extends Alternating-time Temporal Logic (ATL*). The key innovations are:

  • Elimination of Dominated Strategies (EDS) Operators: JAADL introduces operators, denoted as (A)ψ and (A)kψ, which capture the notion of joint abilities after iterated elimination of strictly dominated strategies by a coalition A for a goal ψ. This allows reasoning about what a coalition can achieve if agents rationally discard strategies that are provably worse than others.
  • Linear Dynamic Logic (LDL) Foundation: The logic is built upon Linear Dynamic Logic (LDL), which allows for the representation of strategies using regular expressions. This is crucial for modeling "structured strategies" – commitments to specific sequences of actions or behaviors, like traffic rules or pre-defined plans.
  • Formal Semantics and Axiomatization: The paper provides a formal semantics for JAADL, interpreting formulas over concurrent game structures. It also analyzes valid formulas, deriving properties related to the EDS operators and their interaction with coalition abilities.

Datasets

Not discussed in the paper. The paper focuses on formal logic and theoretical properties, using abstract examples rather than empirical datasets.

Key Insights and Ideas

  • Rationality as a Driver of Joint Ability: The paper highlights that joint abilities are not just about having a strategy, but about what remains after agents rationally discard suboptimal strategies. This connects game-theoretic concepts like iterated elimination of dominated strategies directly to modal logic.
  • Structured Strategies Enable Coordination: By using LDL and regular expressions, JAADL can model commitments to specific strategy structures. This is shown to be crucial for overcoming coordination problems, as explicit commitments can guarantee desired outcomes where abstract strategies might fail.
  • The Power and Complexity of Elimination: The paper demonstrates that while eliminating dominated strategies can reveal joint abilities, it also leads to significant computational complexity. Model checking memoryless JAADL is shown to be EXPTIME-complete, reflecting the inherent difficulty of reasoning about strategic rationality.
  • Weak vs. Strong Joint Ability: The distinction between eliminating only "punishment strategies" (as in some prior work) and eliminating "strictly dominated strategies" is implicitly shown to lead to different notions of joint ability, with the latter being a stronger concept.

Key Results

  • JAADL Syntax and Semantics: A formal language and interpretation for joint abilities under strategy commitments are defined.
  • Properties of EDS Operators: Several valid formulas are proven, establishing properties like the K-axiom for EDS operators and relationships between different stages of elimination.
  • Sufficient and Necessary Conditions for Joint Abilities: The paper provides theorems that link the existence of winning/optimal strategies and the properties of strategy spaces to the presence of joint abilities at various stages of elimination.
  • Model-Checking Complexity: It is proven that model checking memoryless JAADL is EXPTIME-complete.

Limitations and Future Work

  • Computational Complexity: The EXPTIME-completeness for memoryless strategies suggests that full JAADL (with general strategies) is likely even more computationally demanding. The paper acknowledges this and suggests further investigation into the complexity of the general case.
  • Representing Optimal Strategies: The authors note that while they can define winning and punishment strategies, representing the concept of an "optimal strategy" (one that weakly dominates all others) directly in JAADL is not straightforward.
  • Implementation: The paper mentions the interest in implementing a symbolic model checker for memoryless JAADL, indicating that practical tools are a future direction.
  • General Strategies: The current complexity result is for memoryless strategies. Extending this to general strategies and analyzing their complexity remains an open area.

Summary updated

BibTeX
@inproceedings{liu2020modal,
  author = {Zhaoshuai Liu and Liping Xiong and Yongmei Liu and Yves Lespérance and Ronghai Xu and Hongyi Shi},
  title = {{A Modal Logic for Joint Abilities under Strategy Commitments}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/250},
}
Figure