Semantic Foundations of Neuro-Symbolic Multi-Agent Systems

Neuro-symbolic AI aims to integrate learning-based and symbolic reasoning components within a unified framework. While most existing work focuses on single-agent settings and engineering architectures, formal foundations for neuro-symbolic multi-agent systems remain limited. In this paper, we introduce a game-theoretic formal model capturing the interaction between probabilistic neural evaluation and symbolic strategic reasoning in multi-agent environments. The framework extends logical models of strategic reasoning while embedding probabilistic propositional inference into a distributed setting. We establish basic properties of the model and provide a comprehensive complexity-theoretic analysis of optimally stable strategic behaviour. In particular, for one-shot games, we show that utility evaluation corresponds to weighted model counting and characterise the complexity of the main associated Nash equilibrium problems, ranging from FP and #P to PP and Sigma^PP_2. We further study an iterated variant of the core model, showing PSPACE-completeness for the main decision problem in such a class of multi-player games. These results provide formal foundations for reasoning about neuro-symbolic multi-agent systems and clarify the computational limits of combining learning, uncertainty, and strategic interaction within the same formal reasoning framework.