Research map / Multi-agent systems and games / Games and equilibria
Probabilistic Strategy Logic with Degrees of Observability
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 Strategy Logic with observability and degree-of-observability operators for information transparency in partially observable stochastic MAS, and shows memoryless-strategy model checking is decidable (3EXPSPACE).
Problem
Existing logics such as PSL cannot express information transparency, i.e., the extent to which agents' behaviours and actions are observable by other agents, in stochastic multi-agent systems.
Approach
Introduces oPSL, adding an observability operator (opacity-style: a property is observable to agent i if no observationally equivalent path violates it) and a degree-of-observability term defined as the conditional probability of observable satisfying paths, interpreted under strategy bindings; model checking reduces to real arithmetic with memoryless strategies.
Key results
- Model checking oPSL with memoryless strategies is decidable, with complexity triple exponential in the sentence size and double exponential in the system size.
- Worked message-interception example yields a degree of observability of 0.5 for F stolen under the given strategies.
- Full observability operator reduced to a real-arithmetic formula via Büchi/Streett/Rabin automata and Safra-style determinization.
Limitations
- Decidability only holds for memoryless strategies; general PSL model checking is undecidable.
- Complexity is triple exponential in the sentence and double exponential in the system, so practical use is doubtful.
- No implementation or experimental evaluation is reported.
Experimental setup
Baselines: PSL PATL* incomplete-information PATL*
Builds on: Probabilistic Strategy Logic Strategy Logic opacity framework PCTL* model checking
Closest papers by meaning
- Strengthening Agents Strategic Ability with Communication (AAAI 2016 · similarity 0.89)
- Natural Strategic Ability in Stochastic Multi-Agent Systems (AAAI 2024 · similarity 0.87)
- Responsibility-aware Strategic Reasoning in Probabilistic Multi-Agent Systems (AAAI 2025 · similarity 0.85)
- Narrowing the Collaboration Gap, Probably (NeurIPS 2026 · similarity 0.83)
- On Alternating-Time Temporal Logic, Hyperproperties, and Strategy Sharing (AAAI 2024 · similarity 0.83)
- Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives (AAAI 2025 · similarity 0.83)
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.