Higher-Order Belief in Incomplete Information MAIDs
Jack Foxabbott, Rohan Subramani, Francis Rhys Ward · 2025
Read Higher-Order Belief in Incomplete Information MAIDs by Jack Foxabbott, Rohan Subramani, Francis Rhys Ward (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-06323.txt.
Introduction
Jack Foxabbott, Rohan Subramani, and Francis Rhys Ward work in 2025 on diagrams that model how agents reason about each other's beliefs. Multi-agent influence diagrams capture strategic play compactly, but in their standard form they cannot handle settings where agents hold different beliefs about the game, and different beliefs about each other's beliefs.
The authors define an extended form of the diagram that covers such incomplete information, in both endless and fixed-depth versions. They prove it matches extensive form games with incomplete information and no shared prior. The extension also keeps the classic solution ideas from game theory, opening richer reasoning problems to the diagram approach.
Catalog record
| CREATOR | Jack Foxabbott, Rohan Subramani, Francis Rhys Ward |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-06323
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Higher-Order Belief in Incomplete Information MAIDs Jack Foxabbott, Rohan Subramani, Francis Rhys Ward Abstract . Multi-agent influence diagrams (MAIDs) are probabilistic graphical models which represent strategic interactions between agents. MAIDs are equivalent to extensive form games (EFGs) but have a more compact and informative structure. However, MAIDs cannot, in general, represent settings of incomplete information — wherein agents have different beliefs about the game being played, and different beliefs about each-other’s beliefs. In this paper, we introduce incomplete information MAIDs (II-MAIDs). We define both infinite and finite-depth II-MAIDs and prove an equivalence relation to EFGs with incomplete information and no common prior over types. We prove that II-MAIDs inherit classical equilibria concepts via this equivalence, but note that these solution concepts are often unrealistic in the setting with no common prior because they violate common knowledge of rationality. We define a more realistic solution concept based on recursive best-response. Throughout, we describe an example with a hypothetical AI agent undergoing evaluation to illustrate the applicability of II-MAIDs. A. El Fallah Seghrouchni, Y. Vorobeychik, S. Das, A. Nowe (eds.) Conference: Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025); May 19 – 23, 2025; Detroit, Michigan, USA 1. Introduction In real-life strategic interactions, agents may hold different subjective beliefs about the world, including different higher-order beliefs — beliefs about the beliefs of others. While game-theoretic models aim to represent these interactions, traditional models lack a natural way to account for situations in which agents do not share the same beliefs about the structure of the world or have different higher-order beliefs. In these situations, agents have incomplete information . MAIDs offer a powerful representation of agents’ beliefs in games ( Koller and Milch, 2003 ; Hammond et al., 2023 ) . However, MAIDs assume that all agents in the game share correct prior beliefs about the world, each-other’s beliefs, each-other’s beliefs about other’s beliefs, and so on. With this common-knowledge assumption in place, MAIDs do not explicitly model the agents’ subjective or higher-order beliefs. Consider a situation in which a human is evaluating whether an AI agent is truthful or not, but the AI agent believes it is undergoing an evaluation for dangerous capabilities. These agents have different beliefs about the structure of the strategic interaction, and different higher-order beliefs. Specifically, the AI agent has incorrect beliefs about the game being played and about the human’s beliefs. To formally capture situations like this, we generalise MAIDs to incomplete information MAIDs (II-MAIDs) . In the incomplete information setting, agents may have different and inconsistent beliefs about the world, and each agent may have different higher-order beliefs. Figure 1 shows an II-MAID representing the AI evaluation scenario as a tree structure. At the root of the tree is the ground truth MAID graph (described in the figure caption). Each node in the tree represents the subjective beliefs of an agent in the node above. The tree thereby captures the agents’ recursive higher-order beliefs. We formalise this example in II-MAIDs in Section 4 . We show that II-MAIDs are equivalent to a formulation of incomplete information extensive form games (II-EFGs). II-MAIDs therefore inherit existing solution concepts from the literature, including Nash equilibria. However, we argue that existing equilibria concepts do not respect a “common knowledge of rationality” assumption and therefore prescribe counter-intuitive behaviour in settings where agents have inconsistent beliefs. D^{A} D^{H} C U^{A} U^{H} D^{A} D^{H} C U^{A} U^{H} D^{A} D^{H} C U^{A} U^{H} D^{A} D^{H} C U^{A} U^{H} D^{A} D^{H} C U^{A} U^{H} ... ... ... ... ... ... Ground truth H^{\prime}s beliefs A^{\prime}s beliefs H^{\prime}s beliefs about H ’s beliefs H^{\prime}s beliefs about A^{\prime}s beliefs II-MAID legend chance node decision node utility node causal link information link higher-order belief Figure 1 . Recursive tree structure of agents’ beliefs in the II-MAID representation of example 3.2 . Each node in the tree is a subjective MAID graph consisting of environment variables (circular), agent decisions (square), and utilities (diamond). Decisions and utilities are coloured according to association with particular agents. Solid edges represent causal dependence and dotted edges are information links. The root node is the ground truth model of reality: the variable C is the AI agent A ’s capability level, which is observed by both agents (represented by the information links from C into their decisions). The AI agent chooses its decision D^{A} to truthfully report its capabilities or hide them. Then, the human decides ( D^{H} ) whether to deploy the AI agent. The agent A gets utility for being deployed ( U^{A} ) and the human gets utility for deploying a truthful AI ( U^{H} ). At a node in the II-MAID tree corresponding to a subjective MAID S , for each agent in S , there is a branch to the agent’s beliefs in S . The human H has correct beliefs (corresponding to the root), including correct beliefs about the AI agent’s beliefs. In contrast, the AI agent A has incorrect beliefs. The tree continues infinitely to model each agent’s beliefs about the other agent’s beliefs about… To represent the behaviour and beliefs of real-life agents, we introduce a finite-depth variant of II-MAIDs, wherein, agents represent each other’s beliefs recursively but not infinitely. This enables us to define a more intuitive solution concept by repeatedly assigning best responses at the bottom of the belief hierarchy until all policies in the original game are assigned. Contributions and Outline. First, we review related literature on probabilistic graphical models and incomplete information games ( Section 2 ). In Section 3 , we provide formal background on MAIDs and EFGs. We formally define our framework of incomplete information MAIDs (II-MAIDs) in Section 4 . In Section 5 , we present a variant of an existing formalism for incomplete information games using EFGs rather than normal-form games, and in Section 6 we prove that it is equivalent to MAIDs with incomplete information. We then use this equivalence result to prove the existence of Nash equilibria in II-MAIDs ( Section 7 ). After arguing that existing solution concepts are not appropriate in our setting, we introduce a variant of II-MAIDs with finite-depth belief hierarchies in Section 8 and present a more natural solution concept. All proofs are contained in the supplementary material. 2. Related Work Probabilistic graphical models of decision-making. MAIDs are a form of probabilistic graphical model adapted to represent game-theoretic dynamics — they build on Bayesian networks, which consist of a set of variables and their conditional dependencies represented by a directed acyclic graph (DAG). Influence diagrams (IDs) generalise Bayesian networks to the decision-theoretic setting by adding decision and utility variables ( Howard and Matheson, 2005 ; Miller III et al., 1976 ) , and MAIDs generalise IDs by introducing multiple agents ( Koller and Milch, 2003 ) . A MAID can therefore be viewed as a Bayesian network with extra structure to capture game theory. Following Pearl’s causality ( Pearl, 2009 ) , causal games ( Hammond et al., 2023 ) refine MAIDs by attributing a causal meaning to each edge in the DAG, and have been extensively applied to problems in safe AI [ 10 ; 5 ; 9 ; 38 ; 41 ;