Parallel Belief Revision via Order Aggregation

Jake Chandler, Richard BoothIJCAI 2025 · DOI

TL;DR

This paper tackles the challenge of extending single-step belief revision to handle sequences of "parallel" changes (revising by multiple beliefs simultaneously). The authors propose a novel constructive approach based on "TeamQueue" order aggregation, which successfully recovers plausible postulates for iterated parallel revision while discarding problematic ones from prior work.

What Problem Does This Paper Address?

Belief revision theory traditionally deals with how an agent updates their beliefs when presented with new information. Initially, this was modeled as "serial" change, where beliefs were incorporated one at a time. More recently, "parallel" change was introduced, allowing for multiple beliefs to be processed simultaneously. However, extending these parallel operations to handle sequences of changes (iterated parallel revision) has been a significant challenge. Prior work has proposed various rationality postulates for this iterated parallel case, but these often lack a unifying explanation and can include problematic principles. This paper aims to provide a principled, constructive method for iterated parallel revision that addresses these shortcomings.

Methods

The core of the paper's contribution lies in its constructive approach to iterated parallel revision, drawing inspiration from prior work on iterated parallel contraction using "TeamQueue" order aggregation.

Here's a breakdown of the key methods:

  • TeamQueue Aggregation: This is a family of functions that take multiple "total preorders" (representing an agent's beliefs about the relative likelihood of different possible worlds) as input and combine them into a single output preorder. The paper leverages this to combine the results of individual parallel revisions.
  • Iterated Parallel Revision Construction: The authors propose a two-step process for iterated parallel revision:
  • Aggregate individual revisions: For a sequence of parallel revisions by sets of sentences $S_1, S_2, \dots, S_n$, first, each individual parallel revision $S_i$ is performed. The resulting belief states (represented as TPOs) are then aggregated using a TeamQueue aggregator.
  • Serial revision for "Success": The aggregated TPO is then subjected to a final serial revision by the conjunction of the sentences in the last revision set. This step ensures that the "Success" postulate (which states that if an agent revises by a set of sentences $S$, they should believe all sentences in $S$) is satisfied.
  • Postulate Recovery and Rejection: This constructive approach is used to demonstrate which of the previously proposed postulates for iterated parallel revision are plausible and which are not. The authors show that their method validates desirable principles like (PC3), (PC4), and (S), while invalidating problematic ones like (SC2) and (P).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unifying Explanation for Postulates: The TeamQueue aggregation approach provides a principled way to derive and justify postulates for iterated parallel revision, offering a unifying explanation that was previously lacking.
  • Distinguishing Plausible from Problematic Postulates: The constructive method clearly separates the "good" postulates (those that are derivable from the aggregation approach) from the "bad" ones (those that are not). This is crucial for advancing the theory of belief revision.
  • Example 1 as a Crucial Test Case: The paper revisits Example 1 (concerning an adder and a multiplier circuit) to demonstrate how their approach correctly handles scenarios where serial revision postulates might lead to counterintuitive results, highlighting the importance of parallel revision.
  • The Limits of Simple Generalizations: The paper shows that straightforward generalizations of single-step identities (like the Harper and Levi identities) to the iterated parallel case are problematic, reinforcing the need for more sophisticated constructive methods.

Key Results

  • The proposed TeamQueue aggregation-based construction for iterated parallel revision is shown to be sound with respect to several key postulates, including:
  • (PC3) and (PC4) (which jointly entail (C1)-(C4) of the DP postulates).
  • (S) (a principle related to iterated contraction).
  • (Ind) (a generalization of the independence postulate).
  • The construction demonstrably fails to satisfy problematic postulates such as:
  • (SC2) (a strong generalization of a DP postulate that leads to issues with Example 1).
  • (P) (a postulate that the authors argue is not intuitively compelling).
  • The method correctly handles Example 1, yielding the intuitive outcome that an agent does not lose belief in the adder working after revising by {adder, multiplier} and then by {not multiplier}.

Limitations and Future Work

  • Soundness vs. Completeness: The paper primarily presents soundness results, meaning their construction satisfies certain postulates. Future work could aim to obtain completeness results, characterizing specific classes of revision operators based on the underlying serial revision operators.
  • Connection to Iterated Harper/Levi Identities: The paper notes that simple generalizations of Harper and Levi identities to the iterated parallel case are not promising. Exploring more sophisticated connections between iterated serial and parallel contraction/revision identities remains an open challenge.
  • Constructive Foundation: While the approach is constructive, the authors acknowledge that further work might be needed to fully explore the constructive foundations of their proposed operators, especially in relation to existing formalisms like ranking functions.

Summary updated

BibTeX
@inproceedings{chandler2025parallel,
  author = {Jake Chandler and Richard Booth},
  title = {{Parallel Belief Revision via Order Aggregation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/492},
}
Figure