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

AI summary

arXiv: 2511.22536v1 [cs.AI], 27 Nov 2025 Authors: Fengming Zhu, Yuxin Pan, Xiaomeng Zhu, Fangzhen Lin (The Hong Kong University of Science and Technology, Hong Kong SAR, China)

Overview

• Research area: Multi-agent Theory of Mind (ToM) — the intersection of game theory, decision theory, stochastic games, and autonomous agents.
• Technical level: Advanced. The paper is a formal, mathematical framework paper; it assumes familiarity with stochastic games, MDPs, POMDPs, Bayesian conjugate priors, and game-theoretic best response.
• Scope: The paper proposes a game-theoretic computational framework in which agents make boundedly rational decisions while recursively modeling the beliefs, goals, and intentions of other agents, using Bayesian belief updating to preserve computability.

What This Paper Is About

Theory of Mind — the ability to reason about others' goals, intentions, and beliefs — has been studied in psychology, logic, economics, and robotics, but psychological work generally does not formalize these concepts in a way that can be automated, and logical formalisms can be hard to scale. This paper offers an alternative: a decision-theoretic and game-theoretic framework in which agents are utilitarian (maximizing reward), hold a recursive hierarchy of beliefs about one another, and update those beliefs statistically. The authors explicitly state that, due to page limits, they focus on elaborating the theoretical framework and leave experiments to future work.

Key Contributions

1. A game-theoretic formalization of ToM concepts. Goals, intentions, and beliefs are recast in a stochastic game setting: the planning "goal" is subsumed by the reward structure, an agent's "intention" is defined as a policy (a strategy) for maximizing accumulated reward, and a "belief" is structured private information used to infer others' intentions.

2. A recursive Poisson cognitive hierarchy with Bayesian updating of the population's reasoning level. Beliefs are formalized using a Poisson(λ) cognitive hierarchy in the tradition of Camerer, Ho, and Chong (2004), with λ treated as a random variable drawn from a Gamma(a, b) prior so that the hierarchy can be updated by Bayesian inference as interactions are observed.

3. Two concrete bottom-up constructions of the hierarchy, with complexity analysis. The paper gives two ways to build level-(k+1) strategies — best responding to a singleton level-k profile, or to a normalized mixed distribution over levels up to k — and analyzes their differing computational costs.

4. A computability-preserving approximation. Because best responding to a mixed strategy in principle requires solving a POMDP (with potential undecidability), the authors adopt the QMDP approximation and note that the framework can be seen as an instantiation of I-POMDP that circumvents the latter's computability issues.

Main Findings

• Stochastic game backbone: The interaction system is modeled as a 5-tuple ⟨N, S, A, T, R⟩ with a finite set of n agents, a finite set of environmental states, a set of joint actions A = A₁ × ⋯ × Aₙ, stochastic transitions T, and per-agent immediate rewards Rᵢ.

• Goal, intention, and belief redefined: The paper states that the "goal" concept from automated planning is subsumed by the reward structure and must be compatible with it; an "intention" is a stationary policy πᵢ : S ↦ Δ(Aᵢ) (also called a strategy); and a "belief" is well-structured private information used to infer the up-to-date intentions of others.

• Poisson cognitive hierarchy: The probability that an agent belongs to level k is f(k; λ) = e^(−λ) λ^k / k!, so the level K follows a Poisson(λ) distribution with 𝔼[K] = λ, capturing the population's average reasoning level. Level-0 agents play random or simple rules; level-k agents best respond to those below level-k; a level-∞ agent is perfectly rational.

• Gamma prior and closed-form Bayesian update: Λ is assumed to follow Gamma(a, b), with 𝔼(Λ) = a/b. After observing m additional rounds in which the opponent played at level k₁, …, k_m, the posterior becomes Gamma(a + Σᵣ kᵣ, b + m), and the next estimate is λ′ ← (a + Σᵣ kᵣ) / (b + m). The derivation is given in Appendix B.

• Two implementation variants with different costs: In the first, a level-(k+1) agent assumes all others are at level k and best responds to that singleton profile by optimally solving the induced MDP M(π₋ⱼ|k). In the second, the agent assumes the others are distributed over levels no more than k according to the normalized Poisson distribution with weights g_ι = f_λ(ι) / Σ{ι′=0}^{k} f_λ(ι′), and best responds to that mixed strategy.

• Complexity difference between the implementations: If agent j believes it is at level K_j, the first implementation requires solving Θ(K_j) MDPs only for the initial step (after which only the belief distribution is updated, since the hierarchy's support strategies stay the same), whereas the second requires solving Θ(K_j) MDPs every time the belief is updated, because changes in the g_ι weights change the best response.

• QMDP approximation for tractability: Computing BR(π^mixed₋ⱼ|k) would require solving an underlying POMDP, which incurs potential undecidability. The authors instead use a QMDP approximation, selecting actions by arg max over a_j of Σ{ι=0}^{k} g_ι · Q*_{M(π₋ⱼ|_ι)}(S, a_j).

• Stationarity is preserved: The paper argues that if the level-0 strategy is stationary, then under both implementations the level-(k+1) strategy is also stationary, up to any k.

• Relation to I-POMDP and caveat on belief updates: The framework can be viewed as an instantiation of I-POMDP but avoids the latter's computability issues. The authors also note that belief updating may be non-monotonic and non-converging in the sense of approaching a specific distribution with decreasing entropy, since a belief may be "restored" when it does not accurately reflect the truth.

• Distinction from GR2: The authors contrast their approach with GR2, which embeds a static Poisson hierarchy within RL training, performs no belief update during execution, and considers only action-wise best responses in a given state; their framework updates the belief structure periodically and considers strategy-wise best responses.

• No experiments reported: The paper states that experiments are left to future work, and that results on certain human-robot cohabiting systems "will be reported soon." No benchmark numbers, dataset sizes, or empirical evaluations appear in the content.

Methodology in Plain English

The authors take a mathematical modeling approach rather than an empirical one:

1. Model the world as a game. All agents interact inside a stochastic game with states, joint actions, probabilistic transitions, and per-agent rewards. Each agent tries to maximize its discounted accumulated reward (with a user-specified discount factor γ). What classical planning calls a "goal" becomes the reward structure; what the paper calls an "intention" becomes the policy the agent follows.

2. Model ignorance of others as beliefs. Because agent i does not know agent j's reward structure, j's exact intention is hidden. Agent i therefore maintains a belief about how sophisticated the others are.

3. Use a "levels of reasoning" hierarchy. Borrowing from cognitive hierarchy theory, agents are assigned a level: level-0 agents act randomly or by simple rules, and each higher level best responds to the levels below it. The probability of being at level k follows a Poisson distribution with parameter λ, and λ itself is uncertain, drawn from a Gamma prior.

4. Update the belief with Bayesian conjugacy. When an agent observes how opponents actually played, it treats those observations as evidence about λ. Because the Gamma and Poisson distributions are conjugate, the update has a simple closed form — the Gamma parameters are revised by adding the observed levels to a and the number of observations to b — so no expensive numerical inference is needed.

5. Compute a best response. Given a belief about the others, the agent computes what to do. If it assumes everyone else is one level below, this reduces to solving a standard MDP. If it assumes a whole distribution of levels, the problem is harder (a POMDP); to keep it solvable, the authors use the QMDP approximation, which averages Q-values computed from each level's induced MDP.

6. Iterate. Appendix D gives the loop: start with a Gamma(a, b) prior; estimate λ; compute the support strategies of the belief structure (in the first implementation, only once); compute the agent's own best response; observe opponents; and update (a, b) accordingly.

Why This Matters

Impact on research. The paper bridges two traditions that usually stay separate: logical formalisms for multi-agent belief and intention (including work on belief change, ConGolog-style concurrent planning, and general game playing) and decision/game-theoretic models. It argues the two exhibit a "tight reciprocal relation." It also positions itself against existing statistical approaches — Boutilier's early Dirichlet-Categorical opponent modeling, which it notes was applied only to tiny-scale matrix games, and Rabinowitz et al.'s POMDP-based "machine theory of mind," which it says covered beliefs only in single-agent domains without incorporating belief change into multi-agent planning. By framing the method as an I-POMDP instantiation that sidesteps computability problems, it offers a practical alternative for recursive multi-agent modeling.

Real-world applications (as suggested by the framework and the authors' stated plans):

• Human-robot cohabiting systems — the paper explicitly says experimental results on certain human-robot cohabiting systems will be reported soon.
• Modeling and prescribing the behavior of populations of agents, robots, or humans, as the concluding remarks state.
• Multi-agent settings where an artificial agent must infer the sophistication of human or machine counterparts and revise those estimates from observed play.
• Domains where opponents' reward structures are hidden but their actions are observable, making recursive belief modeling necessary.

Industry relevance. The framework targets a recurring difficulty in deployed multi-agent systems: agents rarely know each other's objectives. Because the belief update uses Gamma-Poisson conjugacy, it is cheap to maintain, and because the harder variant is reduced to MDP and QMDP computations, the approach is compatible with standard planning and reinforcement learning tooling. The paper also notes that modern statistical and machine learning techniques can be integrated to scale to larger domains.

Future Directions

• Empirical evaluation. The authors state that experiments are left to future work and that results on human-robot cohabiting systems will be reported soon; evaluating the framework on real multi-agent domains is the most immediate open step.
• Scaling beyond the computed hierarchy. The differing complexity of the two implementations — Θ(K_j) MDPs once versus on every belief update — raises the question of how to keep the second variant tractable as the reasoning level grows.
• Handling non-convergent belief updates. The paper notes that belief updating may be non-monotonic and non-converging; understanding when beliefs fail to converge, and how agents recover, remains open.
• Formalized terms for multi-agent ToM with LLMs. The authors observe that recent LLM ToM benchmarks (single-agent multimodal, multi-agent multimodal, and open-ended tasks) still do not present well-formalized terms for multi-agent ToM, suggesting that grounding those evaluations in a framework like this one is a natural next step.

Target Audience

This paper is best suited to researchers and graduate students working on multi-agent systems, game theory, decision-theoretic planning, reinforcement learning, and computational cognitive modeling. It is also relevant to researchers in logic-based AI who want to compare logical formalizations of belief and intention against a game-theoretic alternative, and to roboticists or practitioners who need agents that reason about the hidden objectives of human or artificial counterparts. Because the paper is theoretical and reports no experiments, readers looking for empirical benchmarks or implementation-ready results will not find them here; the value lies in the formal framework, the recursive hierarchy construction, and the tractable Bayesian update.

Authors’ abstract

Originating in psychology, $\textit{Theory of Mind}$ (ToM) has attracted significant attention across multiple research communities, especially logic, economics, and robotics. Most psychological work does not aim at formalizing those central concepts, namely $\textit{goals}$, $\textit{intentions}$, and $\textit{beliefs}$, to automate a ToM-based computational process, which, by contrast, has been extensively studied by logicians. In this paper, we offer a different perspective by proposing a computational framework viewed through the lens of game theory. On the one hand, the framework prescribes how to make boudedly rational decisions while maintaining a theory of mind about others (and recursively, each of the others holding a theory of mind about the rest); on the other hand, it employs statistical techniques and approximate solutions to retain computability of the inherent computational problem.