Research map / Multi-agent systems and games / Games and equilibria
Natural Strategic Ability in Stochastic Multi-Agent Systems
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.
Extends probabilistic ATL variants (PATL and PATL*) to natural strategies (condition-action lists with bounded memory) for stochastic multi-agent systems and gives model-checking complexity results for memoryless and recall settings.
Problem
Model checking strategic abilities of coalitions in stochastic multi-agent systems when strategies must be natural (bounded-memory condition-action lists) rather than combinatorial, since existing logics require infinite memory or have high complexity.
Approach
Introduces probabilistic temporal logics Nat-PATL and Nat-PATL* whose coalition operators quantify over behavioral natural strategies of bounded complexity, and derives complexity bounds for deterministic and probabilistic natural strategies with memoryless and recall settings, plus expressivity incomparability with PATL.
Key results
- Nat-PATL model checking with deterministic natural strategies for the coalition is Delta_2^P-complete in stochastic MAS (memoryless and recall).
- Nat-PATL* with deterministic natural strategies is in DNEXPTIME and DEXPTIME-hard.
- With behavioral (probabilistic) natural strategies, Nat-PATL is in EXPSPACE and Nat-PATL* is in TEXPSPACE; Nat-PATL and PATL have incomparable expressive power.
Surprising findings
- Nat-PATL and PATL have incomparable expressive power, so neither subsumes the other.
Limitations
- Probabilistic natural strategy upper bounds are exponential-space or triply-exponential, with no matching lower bounds
- Epistemic operators and quantitative thresholds are left out of scope
- Results are theoretical with no implementation or experiments
Experimental setup
Metrics: model checking complexity class expressive power distinguishing power
Baselines: PATL PATL*
Builds on: PATL PATL* ATL with natural strategies PSL Nat-SL
Closest papers by meaning
- A Modal Logic for Joint Abilities of Structured Strategies with Bounded Complexity (AAAI 2025 · similarity 0.91)
- On Alternating-Time Temporal Logic, Hyperproperties, and Strategy Sharing (AAAI 2024 · similarity 0.88)
- Probabilistic Strategy Logic with Degrees of Observability (AAAI 2025 · similarity 0.87)
- Responsibility-aware Strategic Reasoning in Probabilistic Multi-Agent Systems (AAAI 2025 · similarity 0.86)
- LTLf Synthesis on First-Order Agent Programs in Nondeterministic Environments (AAAI 2025 · similarity 0.86)
- 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.