Introduction
Belief revision is a cornerstone of artificial intelligence, focusing on how agents update their knowledge when presented with new, potentially conflicting information. Traditionally, this process has been governed by the AGM framework or the Katsuno-Mendelzon (KM) postulates. These classical theories typically assume that an agent's epistemic state is represented by a total pre-order, where every possible world can be compared and ranked by plausibility. However, in real-world scenarios, information is often incomplete, leading to partial orders where some possibilities are simply incomparable.
The Problem with Total Pre-orders
The assumption of totality is often too restrictive. Agents frequently encounter situations where they lack sufficient data to rank two competing hypotheses. Previous attempts to adapt belief revision for partial orders were often criticized for being too rigid. Specifically, older definitions required that every model of an agent's current beliefs be strictly preferred to every counter-model. This "faithful assignment" requirement effectively forced partial orders to behave like total orders, stripping away the nuance of incomparability.
As shown in Figure 3, a partial order allows for worlds like $\omega_3$ to exist outside a linear hierarchy, representing genuine uncertainty or lack of information regarding its relative plausibility compared to other states.
A New Axiomatic Foundation
To address these limitations, the authors propose a revised set of postulates ($P_1$ through $P_7$). A key contribution is the weakening of the classical $R_2$ postulate. In standard revision, if new information is consistent with existing beliefs, the two are simply combined. The authors argue that for partial orders, this can ignore the complex structure of incomparable worlds. They instead propose a more cautious approach where only revision by a tautology (empty information) is guaranteed to leave the epistemic state entirely unchanged.
Semantic Representation and Theorem
The paper introduces the concept of a P-faithful assignment. Unlike traditional faithful assignments, a P-faithful assignment only requires that a counter-model be strictly less preferred than at least one model of the agent's current beliefs, rather than all of them. This subtle shift allows "incomparability" to be treated as a first-class citizen in the revision process.
The authors prove a Representation Theorem (Theorem 2), establishing a mathematical equivalence between their logical postulates and these semantic structures. This ensures that any revision operator adhering to the $P_1$-$P_7$ rules is performing a consistent, "minimal change" operation on the underlying partial order.
Iterated Revision and New Operators
A significant portion of the work is dedicated to iterated revision—how the preference structure itself evolves over a sequence of updates. The authors characterize how well-known iterated revision postulates, such as those by Darwiche and Pearl, translate to the partial order setting.
They define and validate three specific operators for partial orders:
- Revision with Memory: Preserves the history of observations.
- Possibilistic Revision: A qualitative approach based on possibility theory.
- Natural Revision: An extension of Boutilier’s "minimal change" approach, which aims to keep the revision as close to the original state as possible.
Figure 6 illustrates the outcome of a natural revision, showing how the preference structure is reconfigured while maintaining certain relationships from the original partial order.
Conclusion
By relaxing the requirement for total pre-orders, this research provides a more realistic framework for AI agents operating in uncertain environments. The introduction of P-faithful assignments and the accompanying representation theorem bridge the gap between abstract logic and practical belief management. Future work remains in extending these results to "order-to-order" revision, where the incoming information is itself a complex partial order, and exploring the dynamics of "updating" in evolving worlds.
Summary updated