A Computable Game-Theoretic Framework for Multi-Agent Theory of Mind¶

🕒 Published (v1): 2025-11-27 15:13 UTC · Source: Arxiv · Venue: AAAI 2026 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

This paper proposes a computable game-theoretic framework for multi-agent Theory of Mind (ToM), formalizing goals, intentions, and beliefs within a stochastic game model augmented by a Poisson cognitive hierarchy and Bayesian (Gamma-Poisson conjugate) belief updates. It achieves bounded rationality and recursive belief modeling while retaining computational tractability by approximating POMDP inference with the QMDP method.

Problem¶

Existing logical formalisms for multi-agent ToM (nested modal operators, epistemic planners) are expressive but lack scalable, computable solutions for recursive belief reasoning. Statistical/RL approaches (e.g., GR2) embed static cognitive hierarchies without online belief updates, and machine ToM work (Rabinowitz et al.) covers only single-agent belief modeling. No prior framework jointly handles recursive multi-agent beliefs, computable best responses, and online belief revision.

Method¶

Agents interact in a stochastic game ⟨N, S, A, T, R⟩. Beliefs about opponents are structured via a Poisson(λ) cognitive hierarchy (level-0: random; level-k: best response to level-(k-1)). The parameter λ is given a Gamma(a,b) prior, enabling closed-form Bayesian updates via Gamma-Poisson conjugacy after observing opponent play. Two implementations for level construction are provided: 1. Singleton: level-(k+1) agent best-responds to a single level-k strategy profile, solving one induced MDP per level (O(K) MDPs, one-time). 2. Mixed: level-(k+1) agent best-responds to a Poisson-weighted mixture over all levels ≤k via QMDP approximation (O(K) MDPs per belief update).

Each agent's best response reduces to solving an induced MDP M(π_{-j}) formed by marginalizing over opponents' mixed strategies. QMDP avoids full POMDP intractability by summing Q-functions from constituent MDPs.

Key Contributions¶

Formal embedding of ToM concepts (goals→reward, intentions→policy, beliefs→cognitive hierarchy) into a stochastic game framework.
Gamma-Poisson conjugate belief update for online, closed-form Bayesian inference of opponents' reasoning level.
Two tractable level-k hierarchy constructions, both preserving stationary-policy closure under best response.
QMDP approximation to sidestep POMDP undecidability in mixed-strategy best responses.
Positioned as a computable instantiation of I-POMDP that avoids its decidability failures.

Results¶

No empirical experiments are reported; the paper is purely theoretical. The authors note experimental results on human-robot cohabitation systems are forthcoming.

Limitations¶

No experiments; computational claims are unverified on real tasks.
Belief update is non-monotonic and may not converge to a consistent distribution.
QMDP approximation sacrifices optimality for tractability; performance gap is uncharacterized.
Scalability to large state/action spaces or many agents is not analyzed.
Framework assumes opponents can be modeled by a single global Poisson distribution, which may not hold in heterogeneous populations.

Relevance to Agentic AI / LLM Agents¶

This framework provides a principled formal substrate for recursive mental modeling—an open problem in multi-agent systems where LLM agents currently lack structured belief representations about other agents. The Bayesian online update mechanism is directly applicable to agent architectures that must adapt strategy based on observed opponent behavior. As LLM-based agents are increasingly benchmarked on ToM tasks (MMToM-QA, AutoToM), this work offers a computationally grounded alternative to purely neural approaches, potentially serving as a planning backbone or evaluation reference for structured theory-of-mind in agentic pipelines.