Research map / Multi-agent systems and games / Games and equilibria
A Modal Logic for Joint Abilities of Structured Strategies with Bounded Complexity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SJAADL, a variant of the joint-ability logic JAADL whose strategies are nondeterministic structured strategies (LDLf condition-action pairs) with bounded complexity, and gives model-checking and norm-synthesis algorithms.
Problem
JAADL defines joint abilities over combinatorial strategies, which are hard for humans to represent and are costly to model-check; the paper seeks a logic using human-friendly, bounded-complexity structured strategies.
Approach
Replace combinatorial strategies in JAADL with nondeterministic structured strategies given as sets of LDLf-condition/action-formula pairs, bounded by total condition length k, and use iterated elimination of dominated strategies over this bounded space; model checking reduces to LDL model checking on pruned or automaton-augmented Kripke structures.
Key results
- Model checking memoryless SJAADL runs in time exponential in k and formula size and polynomial in model size, versus exponential in model size for memoryless JAADL.
- Model checking memoryful SJAADL is shown decidable, double exponential in the strategy complexity bound k, exponential in formula size, and polynomial in model size.
- Theorem 3 shows JAADL is not weaker than SJAADL in distinguishing power (JAADL is not reducible to SJAADL), and SJAADL with deterministic strategies is expressible in JAADL.
Surprising findings
- Joint ability with nondeterministic structured strategies cannot be simulated by JAADL-style path formulas, so whether SJAADL is less expressive than JAADL remains open.
Limitations
- Expressivity comparison with JAADL for nondeterministic strategies remains open.
- Norm synthesis is only treated for the memoryless case; memoryful case left to future work.
- Algorithms are theoretical with no implementation or experiments reported.
Experimental setup
Baselines: JAADL NatATL
Builds on: JAADL ATL NatATL LDLf
Closest papers by meaning
- Natural Strategic Ability in Stochastic Multi-Agent Systems (AAAI 2024 · similarity 0.91)
- Satisfiability in Strategy Logic Can Be Easier than Model Checking (AAAI 2019 · similarity 0.89)
- On Alternating-Time Temporal Logic, Hyperproperties, and Strategy Sharing (AAAI 2024 · similarity 0.88)
- Responsibility-aware Strategic Reasoning in Probabilistic Multi-Agent Systems (AAAI 2025 · similarity 0.84)
- GTBench: Uncovering the Strategic Reasoning Capabilities of LLMs via Game-Theoretic Evaluations (NeurIPS 2024 · similarity 0.84)
- Benefits and Limitations of Communication in Multi-Agent Reasoning (ICLR 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.