Abstract
Belief revision and update, two significant types of belief change, both focus on how an agent modifies her beliefs in the presence of new information. The most striking difference between them is that the former studies the change of beliefs in a static world while the latter concentrates on a dynamically-changing world. The famous AGM and KM postulates were proposed to capture rational belief revision and update, respectively. However, both of them are too permissive to exclude some unreasonable changes in the iteration. In response to this weakness, the DP postulates and its extensions for iterated belief revision were presented. This paper refines the logical framework for iterated belief update, identifying flaws in previous attempts to combine KM update postulates with DP iterated revision postulates. The authors propose a new semantic characterization based on "faithful collective assignments" and reveal surprising incompatibilities between standard iteration principles and the logic of a changing world.
What Problem Does This Paper Address?
In formal logic, belief change is traditionally split into two distinct categories:
- Belief Revision (AGM): How an agent incorporates new information about a static world (e.g., "I thought the keys were on the table, but I found them in my pocket").
- Belief Update (KM): How an agent tracks a dynamically changing world (e.g., "The robot moved the keys from the table to the pocket").
While the Katsuno-Mendelzon (KM) postulates handle a single update well, they struggle with iteration—a sequence of updates. Without additional constraints, an agent might make "rational" one-step updates that lead to "irrational" long-term beliefs. For example, if a robot is told to move a cup, it shouldn't suddenly forget where a book was just because the KM postulates didn't explicitly forbid it. This requires a formal way to represent possible states of the world and how they transition.
Previous work by Fermé and Gonçalves (2023) tried to bridge this gap by migrating the Darwiche-Pearl (DP) postulates—the gold standard for iterated revision—to the update context. However, the authors of this paper argue that the previous approach was redundant, used the wrong "starting point" for updates (initial vs. most recent belief sets), and failed to explain the rationale for these postulates in an update setting.
Methods: Rebuilding the Framework
The authors rebuild the framework from the ground up using several key technical moves:
- Belief States over Belief Sets: Instead of just tracking what an agent believes (a belief set), they use belief states. A state encodes not just current facts, but the agent's "preference" or "ranking" of possible worlds, which dictates how they will react to future information. This is often represented by truth tables for various propositions across possible worlds.
- Faithful Collective Assignments: In belief revision, an agent typically has one "total preorder" (a ranking of all possible worlds). In belief update, because the world is changing, the agent needs a collection of partial preorders—one for each possible world they think might be the current one. The authors define a "faithful collective assignment" to map belief states to these collections.
- Postulate Migration (CU1-CU4): They adapt the four DP postulates (C1-C4) into a new set of "Iterated Update" postulates (CU1-CU4). These regulate how the agent's internal ranking of worlds should shift after an update.
- Semantic Characterization: They provide "representation theorems," proving that an update operator satisfies their proposed logic if and only if it behaves according to specific constraints on the underlying preorders.
Key Insights and Results
The Incompatibility Shock
Perhaps the most significant finding is that CU1 and CU2 are inconsistent with the KM postulates. In belief revision, these postulates are standard and uncontroversial. However, the authors prove that in the KM update framework, you cannot satisfy both the basic update rules and these specific iteration rules simultaneously. This highlights a fundamental logical divergence between revision and update.
Safe Postulates and New Axiomatization
While CU1 and CU2 fail, the authors identify that CU3 and CU4 (which deal with preserving certain plausibility rankings) are compatible with KM update and help prevent the agent from "unjustifiably" discarding beliefs during a sequence of events.
Key results include:
- A New Axiomatization: A modified set of KM postulates ($U*1$ through $U*8$) that work correctly with belief states.
- Theorem 7: The "Representation Theorem" providing exact semantic conditions required to satisfy the new iterated update postulates.
- Theorem 9 (The "No-Go" Theorem): Formal proof that no update operator can satisfy standard KM postulates while also satisfying CU1 or CU2.
- Existence Proof: Definition of a concrete update operator ($\diamondsuit_1$) that satisfies KM postulates plus the compatible iteration postulates (CU3 and CU4).
Conclusion
This research refines the logic of iterated belief update by identifying the limitations of simply porting revision principles to a dynamic context. By establishing that certain iteration postulates are fundamentally incompatible with the KM framework, the authors pave the way for more robust models of how autonomous agents should track changes in their environment over time. Future work remains in exploring even stricter iteration principles and addressing the computational complexity of these refined operators in practical systems.
Summary updated