A Formal Theory of Multiple Agent Nonmonotonic Reasoning

Leora MorgensternAAAI 1990

Introduction

In the late 1980s, non-monotonic reasoning (NMR) was a cornerstone of artificial intelligence research, providing a framework for agents to draw common-sense conclusions despite incomplete information. However, early formalisms—such as Moore’s Autoepistemic Logic (AEL) and Reiter’s Default Logic—were primarily "lonely" frameworks. They focused on a single agent reasoning about their own world or their own lack of knowledge.

In the paper A Formal Theory of Multiple Agent Nonmonotonic Reasoning, Leora Morgenstern identifies a critical gap: real-world reasoning is inherently social. To function in a multi-agent environment, an agent must reason not just about the world, but about the non-monotonic conclusions that other agents are likely to reach. This paper introduces Multiple-Agent Non-Monotonic Logic (MANML) to bridge this gap.

The Problem: The Social Frame Problem

The fundamental limitation of single-agent logic is its inability to handle the "Frame Problem" in a multi-agent context. In a single-agent scenario, an agent might assume that if they don't know of a reason why a bird cannot fly, it does fly. But in a social scenario, if you tell a friend you bought a bird, you must be able to predict that they will conclude it flies.

Existing frameworks were too weak for these scenarios. Without a way to model the internal default reasoning of others, agents remained paralyzed by the possibility that another agent might possess private information that invalidates a default assumption. Morgenstern argues that for effective communication and planning, agents must have a mechanism to reason about the ignorance of their peers.

The MANML Framework and the Principles of Arrogance

The author proposes MANML (Multiple-Agent Non-Monotonic Logic), which extends standard AEL through two primary technical shifts:

  1. Indexed Belief Operators: The standard belief operator $L$ is extended to $L_a$, representing "agent $a$ believes."
  2. Stable Set Expansion: The logic defines how a theory $T$ remains stable when multiple agents perform simultaneous introspection.

The Principles of Arrogance

The paper’s most significant conceptual contribution is the "Principles of Arrogance." Because an agent rarely has a complete map of another agent's mind, they must make default assumptions about what the other agent does not know. To bridge the epistemic gap, an agent must be "arrogant"—assuming that if there were a reason for another agent to change their mind, they (the first agent) would already be aware of it.

  • Principle of Moderate Arrogance (PMA): If Agent A believes Agent B uses a specific default rule, and Agent A has no reason to believe Agent B has seen an exception to that rule, Agent A concludes that Agent B has applied that default rule.
  • Principle of Cautious Arrogance (PCA): This is a stricter variant where Agent A only assumes Agent B is ignorant of an exception if Agent A is also ignorant of that exception.

Key Insights and Applications

The Necessity of Asymmetry

In single-agent AEL, an agent has a complete description of their own "mind." In a multi-agent world, this symmetry is broken; you only ever have a partial description of others. MANML provides the formal machinery to allow agents to "jump to conclusions" about the beliefs of others, preventing the epistemic paralysis that occurs in strictly monotonic or indexed-only versions of AEL.

The Chain Request Frame Problem

Morgenstern introduces the "Chain Request Frame Problem" to demonstrate the logic’s utility. Imagine Alice wants a safe combination. She asks Susan to ask Jim for it. To believe this plan will work, Alice must reason that Jim—who is not part of the current conversation—will still believe the combination is the same by the time Susan reaches him. MANML allows Alice to formally assume that Jim has not observed a combination change in the interim.

Formal Results

  • Backward Compatibility: The author proves (Theorem 1) that for a single agent, MANML collapses back into standard Autoepistemic Logic, ensuring it maintains the strengths of previous NMR theories.
  • Temporal Projection: The paper demonstrates that a restricted version of the Principle of Arrogance (EMAT-PMA) is functionally equivalent to Epistemic Motivated Action Theory (EMAT). This allows MANML to solve classic AI puzzles like the "Yale Shooting Problem" within a multi-agent context.
  • Speech Acts: The logic can model Gricean communication conventions, where agents assume a "mutual absence of doubt" to interpret each other's statements.

Limitations and Future Directions

While MANML provides a robust foundation, the author notes that raw "arrogance" can be over-permissive. Without domain-specific restrictions, a moderately arrogant agent might make absurd leaps—such as assuming a stranger has no siblings simply because the agent doesn't know of any.

Furthermore, the current version of MANML lacks quantification into epistemic contexts (e.g., "Alice knows that someone knows the code"). Future work is required to integrate MANML with theories of planning and action to solve complex commonsense problems that remain out of reach for purely monotonic logics.

Summary updated

BibTeX
@inproceedings{morgenstern1990formal,
  author = {Leora Morgenstern},
  title = {{A Formal Theory of Multiple Agent Nonmonotonic Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1990},
}
Figure