Extending the Harper Identity to Iterated Belief Change

Richard Booth, Jake ChandlerIJCAI 2016

Abstract

In the field of formal logic and artificial intelligence, belief change theory explores how agents update their internal models when faced with new information. While single-step belief revision and contraction are well-linked by the classical Harper Identity, extending this relationship to iterated sequences of changes has historically led to mathematical triviality. This paper introduces the "TeamQueue" family of combinators—a semantic framework based on total preorders—to bridge the gap between iterated revision and iterated contraction. By providing a consistent method for deriving contraction operators from established revision rules, the authors offer a robust foundation for sequential belief dynamics.

Introduction

Belief change, often formalized through the AGM (Alchourrón, Gärdenfors, and Makinson) framework, distinguishes between two primary operations: Revision, where an agent accepts a new fact $A$, and Contraction, where an agent relinquishes a belief $A$. For a single instance of change, these operations are duals, connected by the Harper Identity. This identity provides a functional recipe for contraction if the revision mechanism is known.

However, modern AI systems must handle sequences of updates over time, a process known as iterated belief change. While iterated revision has seen significant development since the 1990s, iterated contraction has remained underdeveloped. The primary obstacle is the "triviality result": naive extensions of the Harper Identity to iterated steps are so mathematically restrictive that they cannot represent common-sense belief structures. This paper addresses this gap by proposing a more sophisticated link between revision and contraction that preserves logical consistency across multiple steps.

Methodology: The TeamQueue Framework

The authors move beyond purely syntactic approaches, utilizing a semantic model based on Total Preorders (tpos). In this model, an agent’s belief state is represented as an ordering of "possible worlds" from most plausible to least plausible.

The core innovation is the TeamQueue combinator, a mathematical function that merges two plausibility orderings—the initial state and the state resulting from a revision—to produce a new ordering for contraction. The authors illustrate this through a "supermarket checkout" analogy: imagine a couple splitting up to join two different checkout lines (the "team queue" strategy) to see who finishes first. By adjusting the relative "speed" of these lines (how the operator weights the input orderings), different types of belief change behavior emerge.

One specific variant, the Synchronous TeamQueue (STQ), treats both input orderings with equal weight, representing a "fair" integration of information. This framework allows the authors to define a family of operators that avoid the triviality traps of simpler models.

Key Theoretical Insights

The Triviality Trap and Trifurcation

The paper demonstrates that the Extended Harper Identity (EHI) is fundamentally inconsistent with basic principles of belief dynamics. To solve this, the authors identify the Trifurcation Property. They prove that for any TeamQueue combinator, the set of most plausible worlds in the resulting state must be either the most plausible worlds of the first input, the second input, or the union of both. This property ensures that the agent's new beliefs remain grounded in the original information.

Postulate Translation

A significant contribution of this work is the ability to use TeamQueue combinators as a "bridge" for logical postulates. If a revision operator satisfies the standard Darwiche-Pearl (DP) postulates—the gold standard for iterated revision—the TeamQueue framework automatically derives a corresponding, consistent set of rules for contraction. This provides a formal justification for the Principled Factored Intersection (PFI), a contraction principle that previously lacked a rigorous theoretical foundation.

Results and Implications

The research yields several key results for the formal logic community:

  1. Proposition 7: The authors prove that contraction operators derived via TeamQueue from DP-compliant revision operators will satisfy the counterpart contraction postulates proposed by researchers like Chopra et al.
  2. Characterization of STQ: The Synchronous TeamQueue is uniquely characterized by a property called "Parity," which is linked to the concept of "Strong Belief."
  3. Unification: The framework successfully recovers existing operators. For instance, applying STQ to "natural" or "restrained" revision yields the standard "natural contraction" operator, demonstrating the framework's broad applicability.

Conclusion and Future Directions

While the mathematical properties of the TeamQueue family are robust, the authors note that further work is needed to establish the "normative appeal" of certain properties—essentially explaining why a rational agent should prefer one specific combinator over another in human-centric terms.

Additionally, while this paper focuses on the path from Revision to Contraction, the authors suggest that future research should explore the "Levi Identity" to investigate the reverse path (Contraction to Revision) in an iterated context. Expanding these findings from specific plausibility variants to a completely domain-general setting remains a primary goal for the field.

Summary updated

BibTeX
@inproceedings{booth2016extending,
  author = {Richard Booth and Jake Chandler},
  title = {{Extending the Harper Identity to Iterated Belief Change}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure