Uncommon Belief in Rationality

Qi Shi, Pavel NaumovAAAI 2025 · DOI

TL;DR

This paper introduces "RBR graphs," a novel graphical language to model complex, "uncommon" belief structures about rationality among agents, going beyond the standard assumption of common knowledge of rationality. They propose "doxastic rationalisability" as a solution concept for these systems and an algorithm to simplify RBR graphs, making them computationally tractable.

What Problem Does This Paper Address?

In game theory and multi-agent systems, a cornerstone assumption is that agents are rational and that this rationality is common knowledge (RCBR). However, this assumption is often too strong in real-world scenarios where agents might have differing levels of rationality or incomplete information about others' rationality. For instance, an adult interacting with a child might not assume the child is rational, or a sophisticated agent might believe another agent is rational even if they are not. The paper addresses the challenge of formally modeling these "uncommon" belief structures about rationality and developing a framework to predict agent behavior within them. Existing approaches, like Bayesian belief modeling or influence diagrams, struggle to capture these higher-order beliefs about rationality in a flexible way.

Methods

The core contribution is the introduction of RBR graphs, a directed graph representation where nodes represent agents (real or "doxastic" – existing only in beliefs) and edges capture belief relationships about rationality. A path in the graph corresponds to a sequence of beliefs, like "agent A believes agent B believes agent C is rational."

To analyze these RBR graphs, the authors define iterative rationalisation, a process where agents repeatedly eliminate strategies that are strongly dominated by others, given their beliefs about others' rationality. This process continues until a stable state is reached.

Based on this, they propose doxastic rationalisability as a solution concept. This concept extends traditional rationalisability to systems with uncommon RBR by considering the beliefs of both real and doxastic agents.

Finally, they introduce an algorithm for minimizing RBR graphs. This algorithm identifies and merges nodes that represent agents with equivalent belief hierarchies, producing a canonical and minimal representation of the RBR system. This is crucial for computational efficiency, as the complexity of rationalisation is proportional to the number of nodes.

Datasets

Not discussed in the paper. The paper focuses on theoretical modeling and does not present empirical evaluations on specific datasets.

Key Insights and Ideas

  • Beyond Common Knowledge: The paper highlights that assuming common knowledge of rationality is often unrealistic and limits the analysis of complex agent interactions.
  • RBR Graphs as a Unified Language: RBR graphs provide a flexible and expressive way to represent diverse belief structures about rationality, including cases where agents are irrational or have mistaken beliefs about others' rationality.
  • Doxastic Agents: The concept of "doxastic agents" is key – agents that exist in the beliefs of other agents but not necessarily in reality. This allows for modeling situations where an agent believes in the rationality of someone who is actually irrational.
  • Iterative Rationalisation as a Reasoning Process: The paper formalizes the idea that agents iteratively refine their beliefs and eliminate strategies based on their beliefs about others' rationality, mirroring human reasoning processes.
  • Equivalence of Belief Hierarchies: A significant theoretical result is that two nodes in RBR graphs are "doxastically equivalent" (meaning agents represented by them behave identically) if and only if they represent agents with identical belief hierarchies. This provides a strong theoretical foundation for graph minimization.
  • Minimization for Efficiency: The ability to minimize RBR graphs is crucial for practical applications, as it reduces computational complexity while preserving the essential strategic behavior of the agents.

Key Results

  • Formalization of Uncommon RBR: The paper provides a formal language (RBR graphs) and a solution concept (doxastic rationalisability) for analyzing games with uncommon belief structures about rationality.
  • Iterative Rationalisation Convergence: They prove that the iterative rationalisation process, starting from the assumption that all agents choose from their full strategy space, always converges to a stable state (a rational solution) in a finite number of steps.
  • Doxastic Equivalence Theorem: A key theorem establishes that two nodes in RBR graphs are doxastically equivalent if and only if they represent agents with identical belief hierarchies.
  • RBR Graph Minimization Algorithm: An efficient algorithm is presented to compute an equivalent canonical RBR graph, which is the most condensed representation of an RBR system. The algorithm's time complexity is O(|A|·|N|².log|N|), where |A| is the number of agents and |N| is the number of nodes.

Limitations and Future Work

  • Computational Complexity: While the minimization algorithm improves efficiency, the complexity of rationalisation can still be high for very large RBR graphs.
  • Simplification of Rationality: The paper simplifies the definition of rationalisation to the elimination of strongly dominated pure strategies. Extending this to mixed strategies or other notions of rationality could be a future direction.
  • Eliciting RBR Systems: The paper assumes RBR systems are given. Future work could focus on methods for eliciting these complex belief structures from real agents, which is a challenging task in behavioral economics and AI.
  • Applications: The authors suggest that their framework can be applied to model bounded rationality and other complex strategic interactions in multi-agent systems. Further exploration of specific applications would be valuable.

Summary updated

BibTeX
@inproceedings{shi2025uncommon,
  author = {Qi Shi and Pavel Naumov},
  title = {{Uncommon Belief in Rationality}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i13.33546},
}
Figure