Parallel Belief Contraction via Order Aggregation

Jake Chandler, Richard BoothIJCAI 2025 · DOI

TL;DR

This paper tackles the challenge of modeling how an agent's beliefs change when multiple pieces of information are removed simultaneously, especially over a sequence of such removals. They introduce a novel method based on "TeamQueue" aggregation, a generalization of binary order aggregators, to extend existing belief contraction models to handle these complex, iterated parallel changes. This work fills a significant gap in belief revision research, offering a principled way to manage sophisticated belief updates.

What Problem Does This Paper Address?

The field of belief revision studies how an agent's beliefs should rationally change when new information is added (revision) or existing information is removed (contraction). Traditionally, research focused on "serial" change, where a single piece of information is added or removed at a time. However, real-world scenarios often involve "parallel" change, where multiple pieces of information are removed simultaneously. While single-step parallel change has been explored, the more complex scenario of iterated parallel change – a sequence of parallel removals – has been largely neglected. Existing approaches to parallel change are often too weak or don't generalize well to iterated scenarios. This paper aims to bridge this gap by providing a robust framework for iterated parallel belief contraction, extending existing, strong AGM-compliant models.

Methods

The core of the paper's contribution lies in generalizing a binary order aggregation method called "TeamQueue" (TQ) aggregation to an n-ary case. This n-ary TQ aggregation is then used to construct operators for iterated parallel belief contraction. The authors leverage the concept of "TeamQueue" aggregators, which map multiple input "profiles" (ordered sets of propositional worlds representing beliefs) to a single output profile. They define TQ aggregators constructively and provide characterizations using properties like "factoring" and "Parity."

Specifically, they:

  • Generalize TeamQueue Aggregation: Extend binary TQ aggregation to handle an arbitrary number of input TPOs (total preorders), which are a formal way to represent belief states.
  • Propose an Iterated Parallel Contraction Operator: Define a method for iterated parallel contraction, denoted by $\ominus$, by aggregating the results of serial contractions on individual items within a set. This is achieved by applying the n-ary TQ aggregator to the TPOs resulting from serial contractions.
  • Connect to Rational Closure: Demonstrate that their proposed STQ parallel contraction operator relates to the concept of rational closure of conditional beliefs, providing a principled way to combine information.
  • Derive Plausible Generalizations: Show that their approach recovers existing principles for single-step parallel contraction and derives plausible generalizations of AGM postulates for iterated parallel contraction.

Datasets

Not discussed in the paper. The paper deals with formal logic and belief representation, not empirical datasets.

Key Insights and Ideas

  • The "Intersective" Approach is Key: The paper champions the "intersective" approach for parallel contraction, where the resulting belief set is the intersection of belief sets obtained from individual serial contractions. This is intuitively appealing: if you remove multiple things, you should retract anything that any of those individual removals would preclude.
  • TeamQueue Aggregation is a Powerful Tool: The generalization of TeamQueue aggregation from binary to n-ary cases provides a flexible and principled mechanism for combining multiple belief orderings, which is crucial for iterated parallel change.
  • Bridging Serial and Parallel Change: The work elegantly connects the well-established theory of serial belief contraction to the less-explored territory of parallel and iterated parallel contraction, showing how insights from one can inform the other.
  • Iterated Parallel Contraction is Non-Trivial: The paper highlights that simply applying serial contraction rules sequentially or combining them naively doesn't work for iterated parallel contraction. A more sophisticated aggregation mechanism is required.
  • Connection to Rational Closure is Significant: The link between the proposed aggregation method and rational closure provides a strong theoretical justification for the approach, suggesting it aligns with principles of conservative belief update.

Key Results

  • The paper proposes a general method for extending serial iterated belief change operators to handle parallel change, based on an n-ary generalization of Booth & Chandler's TeamQueue binary order aggregators.
  • They demonstrate that this method, when applied to AGM-compliant serial contraction operators, yields parallel contraction operators that satisfy plausible generalizations of both basic and supplementary AGM postulates.
  • Specifically, the STQ (Synchronous TQ) aggregator is shown to be particularly effective, leading to an STQ parallel contraction operator whose conditional belief set is the rational closure of the intersection of the input conditional belief sets.
  • The paper provides characterizations for TQ aggregators and parallel contraction operators, including properties like "factoring," "Parity," and Pareto-style properties.

Limitations and Future Work

  • Scope of Aggregators: While the paper focuses on TQ aggregators, it acknowledges that other aggregation methods might exist or be needed for different belief representation formalisms (e.g., ranking functions).
  • Application to Revision: The paper primarily focuses on contraction. The authors suggest that investigating whether the TQ approach could be applied to iterated parallel revision is a valuable future direction.
  • Generalizing TQ Aggregation: For applications beyond belief change, such as preference or judgment aggregation, the TQ aggregation method might need further generalization, as it is currently insensitive to duplicate TPOs in a profile.
  • Open Questions: The paper leaves open the question of characterizing the "MinRank" aggregator in terms of similar properties as STQ.

Summary updated

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