CS Paper Radar

The Complexity of Verifying Strategic Abilities in Succinct Multiagent Systems

Yifan He, Munyque Mittelmann, Aniello Murano, Michael Thielscher

cs.LO ·submitted 2026-10-13 12:15 UTC · v1

Abstract

This paper studies the complexity of model checking strategic abilities in multiagent systems under imperfect information, in particular systems represented succinctly. Such a representation can describe systems that are exponentially larger than their input and is particularly relevant to practical implementations of model checkers such as MCMAS. The logics we consider include epistemic strategy logic supporting partial binding $SLK_{P}$, and its syntactic fragments: epistemic strategy logic $SLK$ and variants of Alternating Time Temporal logics. We show that succinct model checking for $SLK_P$ and $SLK$ is $AEXP(poly)$-complete, while objective ATL and ATL$^{*}$ are $P^{NEXP}$-complete. The latter corrects a previous NEXP-completeness result for model checking succinct imperfect-information systems. Under subjective semantics, $P^{NEXP}$-completeness already holds for one-step Coalition Logic, and therefore also for ATL and ATL$^{*}$.

Closest papers

Nearest neighbours by meaning across the whole index.

The Lattice of Coalition Logics between MCL and CL: Coatoms and Compact Meets

cs.LO math.LO ·2026-10-17 ·Shanxia Wang, Yuqiang Dou
similarity 0.61
Abstract · 19 pages, one table; supplementary finite-checking Python program in ancillary files

For a fixed finite set $N$ of at least two agents, we investigate the lattice $L_N$ of coalition logics between minimal coalition logic (MCL) and classical coalition logic (CL), with extensions required to be structural. This lattice is order-dual to an interval in the subvariety lattice of Boolean coalition algebras. The eight basic extensions obtained by imposing seriality, independence of agents, and determinism form a Boolean cube under inclusion, but not a sublattice of $L_N$. Our main results concern coatoms and compact meets. First, finite critical coalition algebras, realized as complex algebras of finite general concurrent games, yield three infinite families of pairwise distinct coatoms containing seriality, distinguished by failures of independence, determinism, or both. An explicit splitting characterizes the unique coatom omitting seriality. Second, the meet of two basic extensions is compact if and only if the extensions are comparable. For incomparable pairs, no axiomatization of the meet can use formulas of uniformly bounded modal depth, even with infinitely many axioms. Consequently, $L_N$ and three natural principal intervals are non-coherent algebraic lattices. These results reveal lattice-theoretic phenomena beyond the inclusion order of the eight basic extensions.

0.28

Limit-sure Winning in Team Games without Shared Randomness

cs.GT cs.FLcs.MA ·2026-10-09 ·Léonard Brice, Thomas A. Henzinger, Alipasha Montaseri, Ali Shafiee, K. S. Thejaswini
similarity 0.60
Abstract · 31 pages, 6 figures. Full version with appendix

We study concurrent stochastic games in which a team of agents plays against an adversarial environment. If the agents could access a shared source of randomness, then these games reduce to two-player games. Despite being common in the literature on coalition games, this assumption does not accurately model real-world systems. In this paper, we consider the setting where the agents only have access to individual sources of randomness, and must satisfy a given reachability or safety objective. The limit-sure problem asks whether the team can ensure that the objective is satisfied with probability at least $1-λ$ for every $λ>0$. For reachability objectives, we show that this problem is $\mathsf{NP}$-complete. For safety objectives, we show that limit-sure winning coincides with almost-sure winning, which is known to lie in $\mathsf{P}$. As a corollary of these results, we conclude that model checking of the qualitative fragment of the logic Individually Randomised ATL -- introduced in the recent work of Brice et al. -- is $\mathsf{P}^{\mathsf{NP}}$-complete.

0.20

Collective Counterfactual Planning: Coordination, Consent, and Verification under Representational Constraints

cs.MA cs.AI ·2026-08-18 ·Chainarong Amornbunchornvej
code/datahot direction similarity 0.57
Abstract · The code is available at https://github.com/DarkEyes/Coll-Counterfactual-Plan

Groups routinely complete projects that no single member can plan, execute, or verify alone. We propose a formal model of this phenomenon, Collective Counterfactual Planning (CCP), in which the binding limitation on each agent is neither capability, knowledge, nor observability, but representational geometry: each agent perceives the state, conceives moves, consents to actions, and certifies goal requirements only through a projection onto an agent-specific subspace of a common task space. Four gates jointly determine whether a team can reach a conjunctive goal and legitimately recognize that it has done so: the exogenous implementation coalitions required to perform each action, together with three representational gates -- conception, consent, and task-relative verification qualification. We define the Collective Counterfactual Solvability (CCS) problem, separating geometric feasibility, executable attainment, and validated completion. The results expose a positive-negative duality. Iterated cross-agent relay can unlock a solution that no one-shot pooling of individual plans contains, but any goal requirement depending essentially on the subspace dark to the entire team is unverifiable and therefore not validly completable, even when the trajectory accidentally attains it. Memoryless and audited consent further constrain different objects -- action directions versus cumulative trajectory states -- and neither dominates the other. A four-step exhaustive horizon-bounded solvability scheme is sound and complete under exact representation of the relay closure; restricted implementations remain sound on returned plans but need not be complete. The model gives one geometry for sequential mutual enabling, competent execution of steps whose purpose is invisible to the executor, forced sub-teaming at expertise boundaries, and completion that cannot be validly declared.

0.50

Substantive Agency and Computational Non-Anticipability: An Axiomatic Route to a Conditional Separation of P and N P

cs.LO ·2026-09-23 ·Jérome Clech
theory similarity 0.57
Abstract

This paper characterises substantive agency and identifies the additional bridges under which it has a standard complexity-theoretic consequence: conditionally, P __ = N P . The constitutive core separates coherent plurality, causal openness, anticipatory non-pointing, act-level singularisation, and endogenous sourcehood. Its temporal claim yields a two-sided modal result: exact passive pre-act selection is incompatible with jointly retaining singularising priority and invariance under causally inert informational extension. If every standard polynomial procedure is deployable in that passive form, the actualisation map $α$ has no polynomial-time selector. On an effective presentation, $α$ is therefore either computable outside FP or noncomputable. A separate certifiedactualisation protocol supplies polynomially bounded, polynomially verifiable traces with extensional unique projection. This is the constructive interface that turns historical actualisation into a total standard search relation; combined with the modal result, it places that relation in TFNP search \ FP search , from which a self-contained search argument yields P __ = N P . The result is a domain-relative conditional transfer theorem: it neither assumes polynomial non-anticipability in the definition of agency nor proves that human decision-making satisfies the bridge and certification premises.

0.20

Complexity of Grounded Semantics and Preferred Semantics in Finitary Argumentation Frameworks

cs.AI cs.LO ·2026-10-08 ·Jinfan Xu, Jieting Luo
similarity 0.57
Abstract · 15 pages

Abstract argumentation frameworks (AFs) introduced by Dung provide a formal foundation for non-monotonic reasoning in artificial intelligence. While decision problems for general infinite AFs typically reside at high levels of the analytical hierarchy ($Σ_1^1$ or $Π_1^1$), restricting the framework to be computably finitary reduces some of the complexity to the arithmetical hierarchy. In this paper, we present a complexity mapping of grounded and preferred semantics in computably finitary AFs across standard decision problems: credulous acceptance ($\Cred$), skeptical acceptance ($\Skep$), extension existence ($\Ex$), uniqueness ($\Uni$), and non-empty existence ($\NE$). For grounded semantics, credulous and skeptical acceptance are already known to be $Σ_1^0$-complete. We show that non-empty existence is also $Σ_1^0$-complete, whereas existence and uniqueness are trivial. These classifications are understood within the domain of valid computably finitary representations. For preferred semantics, using a computably finitely branching computation tree, $\Cred_{\pref}$ is shown to be in $Π_1^0$-c and $\NE_{\pref}$ is $Σ_2^0$-c. However, it is insufficient to reduce universal quantification and global uniqueness, leaving $\Skep_{\pref}$ in $Π_1^1$ and $\UniPref$ in $Σ_2^1$-c. Our results show the precise boundary where finitarity succeeds to bring reasoning down to the arithmetical hierarchy and where second-order quantification forces problems back into the analytical hierarchy.

0.27

Organising Trajectory Evidence for Language-Model Agent Assurance: Fragments, Methods, and the Residual

cs.MA cs.AI ·2026-10-03 ·Xiaowei Huang
benchmark similarity 0.57
Abstract

Methods for assessing language-model agents include rule checkers over logs, analyses of skill coverage and composition, support checkers, prefix monitors, execution gates, and rare-event estimators. Each observes a different part of a run and makes a claim of a different strength, and no common account says how these claims combine or what they leave unchecked. We give one, built from a logic, information fragments, and an assurance ledger. Requirements are formulas of a two-tier logic: an outer finite-trace temporal logic over recorded events, and an inner logic of standing over the argument structure that the agent's recorded context supports at a decision. A rule violation and an action taken on withdrawn support are thus formulas of one language. The information available to an assessor, to the agent, and to an execution gate defines fragments of that language; each checking method decides one fragment and returns a typed claim: exact, on a named test suite, a risk bound, or descriptive. The ledger merges the evidence and classifies every obligation as established, addressed but not established, or unaddressed. On 456 released $τ^2$-bench telecom trajectories, the benchmark oracle flags 231 runs; adding a rule checker, a support stand-in, and a prefix-monitor baseline raises the union to 391, 401, and 407, each contributing flags the others miss, and a gate makes one prohibition exact on a gated deployment. The 49 unflagged runs and the unmet or unaddressed obligations form the residual. Discovery makes unknown requirements explicit, and new or stronger checkers then reduce it.

0.17

The Infinite, in Finite Time

cs.LO ·2026-08-24 ·Rayhana Amjad, Rob van Glabbeek, Liam O'Connor
publishedtheory similarity 0.57
Abstract · This paper contains the material of arXiv:2411.14581

Linear-time temporal properties, such as those described by Linear-time Temporal Logic, are typically modelled as sets of infinite traces. Yet, in a run-time verification context, such as when testing or monitoring a system, only a finite prefix of the system's behaviour can be observed. For some properties, these finite prefixes may be definitive---a yes or no answer can be given without further observation. By enriching the semantics of LTL with these definitive prefixes, we give a proper inductive accounting of the semantics of LTL$_3$, a multi-valued variant of Linear-time Temporal Logic for run-time verification applications. The semantic descriptions of LTL$_3$ in previous work are given only in terms of their relationship to conventional LTL. We show that the semantics of LTL and of LTL$_3$ are isomorphic. In addition, we formalise the formula progression evaluation technique, popularly used in runtime verification contexts, and show its soundness and completeness up to finite traces with respect to our semantics. Then, we turn to linear-time properties more generally: using our theory of definitive prefixes, we re-prove the well-known safety-liveness decomposition theorem, and reconstruct the topology of infinite traces. We define monitorability for properties, providing neat topological characterisations for various monitorability classes, and arrange them into a hierarchy. All of our definitions and proofs are mechanised in Isabelle/HOL.

0.16

Cost-Efficient Theorem Proving via Agent Orchestration in Program Verification

cs.AI cs.LOcs.PLcs.SE ·2026-10-07 ·Shuangjie Yao, Nikolaus Holzer, Mark Paul Santolucito, Baishakhi Ray, Suman Jana +1 more
benchmarktheory similarity 0.57
Abstract

Program verification establishes software correctness through machine-checkable proofs constructed in theorem provers. It's a guarantee especially valuable for code generated by large language models (LLMs), which is fluent but carries no assurance of correctness. Almost all existing provers, however, pursue pass rates alone at whatever sampling or search budget it takes, and overlook the success-vs-cost frontier; yet real software often carries hundreds of interdependent proof obligations, so what matters at scale is not whether one theorem can be proved, but how many can be proved economically. We introduce CoCo-Prover, which formalizes cost-efficient program proving as metalevel decision-making under cost, grounded on two-level proof graphs: an AND/OR proof hypergraph within each declaration is joined to a lemma-dependency graph across declarations; and at each step, it answers two questions: which open goals to select, and which actions to purchase on these goals. Selection stays symbolic as a topological pass over the proof graphs. Action choice is agent orchestration via metalevel decision-making: an agentic router treats every bounded specialist invocation as a separately priced, best-effort computation, matching heterogeneous specialist agents together with configurations, under evolved routing rules as evidence accumulates. On five program verification benchmarks in Lean 4 including function-level CLEVER, VERINA, and AlgoVeri, and repository-level NTP4VC and Vero, we show that CoCo-Prover achieves a better success-vs-cost frontier than baselines including frontier coding agents and state-of-the-art LLM-based provers: it achieves the best solve rate on every benchmark and up to 100% on two benchmarks. It also reduces cost by up to 30.9% compared to the strongest baseline with the strongest LLM in our evaluation.

0.12