Agent Modeling Methods Using Limited Rationality

José M. Vidal, Edmund H. DurfeeAAAI 1994

Introduction

In multiagent systems, the ability of an agent to predict the actions of others is fundamental to rational decision-making. However, this predictive process often leads to a recursive "infinite mirror" effect: Agent A models Agent B, who is simultaneously modeling Agent A. This hierarchy of nested beliefs, while theoretically sound, presents significant computational challenges. This paper explores the application of limited rationality to the Recursive Modeling Method (RMM) to manage these complexities efficiently.

The Challenge of Recursive Modeling

The Recursive Modeling Method (RMM) provides a structured framework for representing multiagent interactions using payoff matrices. In RMM, an agent’s decision is based on its beliefs about other agents' strategies, which in turn are based on those agents' beliefs about others, and so on. This creates a belief tree that faces two primary obstacles:

  1. Computational Complexity: The branching factor and depth of the belief tree can grow exponentially, making exhaustive search impossible for real-time applications.
  2. Infinite Recursion: When agents share "common knowledge"—where both agents know that they both know a specific fact—the recursion has no natural stopping point.

Meta-Reasoning and Limited Rationality

To address these hurdles, the authors propose a meta-reasoning approach grounded in the concept of limited rationality. The core insight is that computation itself is an action with an associated cost. An agent should only expand its belief tree if the expected improvement in the quality of its decision outweighs the cost of the time spent calculating it.

The authors define a "situation" ($S$) as a 4-tuple: $S = \langle M, f, l, P \rangle$

Where:

  • $M$ is the payoff matrix.
  • $f$ is a probability distribution over the other agent's possible strategies.
  • $l$ is the depth of the belief.
  • $P$ is the set of possible situations the other agent might perceive.

The Decision to Expand

Using principles from Russell and Wefald’s work on bounded rationality, the framework employs three key metrics to determine the depth of reasoning:

  • Utility ($U(s)$): The expected payoff resulting from a chosen strategy.
  • Time Cost ($TC(s)$): The computational cost incurred by processing a deeper level of the hierarchy.
  • Expected Gain ($G(s)$): A meta-reasoning function that evaluates whether the potential increase in $U(s)$ from further recursion justifies the $TC(s)$.

By applying $G(s)$, the agent can selectively prune the belief tree, focusing only on branches that are likely to change the final action. This prevents the agent from wasting resources on "stable" beliefs that do not impact the immediate decision.

Hybridizing RMM with Game Theory

A significant contribution of this work is the treatment of common knowledge. When the system detects a loop of mutual beliefs, it recognizes that standard RMM recursion will fail to terminate. In these instances, the algorithm switches to classical game theory methods, such as identifying a Nash Equilibrium. This hybrid approach allows the agent to leverage the flexibility of RMM for asymmetric information while using the efficiency of game theory for symmetric, common-knowledge scenarios.

Conclusion and Future Directions

The proposed meta-reasoning framework offers a path toward making recursive agent modeling practical for real-world interactions. By treating "thinking" as a resource-constrained activity, agents can navigate complex social environments without becoming paralyzed by infinite loops.

While the current model is limited to two-agent interactions and requires further empirical validation, it lays the groundwork for more sophisticated learning strategies. Future work aims to improve how agents estimate the probability distributions of others' strategies ($f$) and refine the meta-reasoning accuracy to better predict the value of deeper computation.

Summary updated

BibTeX
@inproceedings{vidal1994agent,
  author = {José M. Vidal and Edmund H. Durfee},
  title = {{Agent Modeling Methods Using Limited Rationality}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure