An Extension-Based Approach to Belief Revision in Abstract Argumentation

Martin Diller, Adrian Haret, Thomas Linsbichler, Stefan Rümmele, Stefan WoltranIJCAI 2015

Introduction

In the field of Artificial Intelligence, belief revision is a fundamental area of study concerned with how an agent should update its knowledge base when presented with new, potentially conflicting information. The cornerstone of this field is the AGM theory (Alchourrón, Gärdenfors, and Makinson), which establishes a set of rationality postulates for belief change in classical logic. However, extending these principles to Abstract Argumentation Frameworks (AFs)—where knowledge is represented as a directed graph of conflicting arguments—has historically been a significant challenge due to the unique structural constraints of argumentation.

A recent breakthrough by researchers at the Vienna University of Technology, titled "An Extension-Based Approach to Belief Revision in Abstract Argumentation," addresses these difficulties. The paper provides a formal framework that ensures the result of a revision is not just a set of possible outcomes, but a single, realizable argumentation graph.

The Realizability Problem in Argumentation

In Dung’s abstract argumentation, knowledge is modeled as a graph where nodes represent arguments and directed edges represent "attacks." To determine which arguments are acceptable, researchers use "semantics" to calculate extensions—sets of arguments that can be consistently accepted together.

The core problem in revising an AF is "realizability." When an agent learns new information—for instance, that a certain argument must be accepted or that two arguments are mutually exclusive—the resulting set of desired extensions might not correspond to any possible AF. Previous research often resulted in a set of multiple graphs or a set of extensions that could not be represented by a single graph. This lack of a unique, representable output makes "iterated revision" (performing multiple updates over time) impossible. This paper tackles this problem head-on, ensuring the output of a revision is always a single, valid AF.

Bridging AGM Theory and Abstract Argumentation

The authors bridge the gap between classical logic and argumentation by combining AGM rationality postulates with the study of realizability. Their approach focuses on "extension-based" revision, where the goal is to find a new AF whose extensions satisfy the new information while remaining as close as possible to the original AF's meaning.

Sigma-Compliance

A central contribution of the paper is the concept of sigma-compliance. Not every collection of argument sets can be the set of extensions for an AF under a given semantics. The authors define sigma-compliance as a constraint on the preference rankings over "possible worlds" (sets of arguments). By ensuring the revision process respects these constraints, they guarantee that the "most plausible" world selected is always one that can be realized as a valid AF.

Two Modes of Revision

The framework distinguishes between two primary scenarios:

  1. Revision by Formula: The agent updates its AF based on a logical constraint (e.g., "Arguments A and B cannot both be accepted").
  2. Revision by AF: The agent updates its own AF with the information contained in another agent's AF.

The Acyc Postulate and Preference Cycles

In the context of revision-by-AF, the authors identify a unique hurdle: the potential for non-transitive cycles in preference rankings. In classical logic, preferences are typically assumed to be transitive. However, the structural constraints of argumentation can lead to situations where an agent's preferences over sets of arguments form a cycle, making it impossible to select a single best outcome.

An illustration of a cycle in preference rankings over sets of arguments, which the Acyc postulate aims to address.

To solve this, the researchers introduce the Acyc postulate. This postulate ensures that the preference relation remains acyclic, allowing for a consistent selection of the revised extensions. Interestingly, they prove that if the Acyc postulate is satisfied, the requirement for sigma-compliance can be relaxed in certain revision-by-AF scenarios.

Key Results: Representation Theorems

The paper's most significant theoretical contributions are its "representation theorems" (Theorems 2 and 4). These theorems establish a formal one-to-one correspondence between revision operators that satisfy the proposed rationality postulates and specific types of rankings over argument sets.

Crucially, this framework is generic. It applies to any "proper I-maximal" semantics, a category that includes most standard evaluation methods such as stable, preferred, stage, and semi-stable semantics. This generality ensures that the approach is not limited to a single niche of argumentation theory but can be applied broadly across the field.

Limitations and Future Directions

While the paper marks a major step forward, the authors acknowledge several areas for future research:

  • Non-I-Maximal Semantics: The current framework does not yet cover semantics like "complete semantics," where one extension can be a subset of another.
  • Syntactic Minimal Change: The focus here is on "semantic" minimal change (minimizing the change in extensions). Future work could explore "syntactic" minimal change, which aims to minimize the number of edges or nodes modified in the graph itself.
  • Computational Complexity: Although checking sigma-compliance is polynomial for some semantics, the practical computational cost of performing these revisions at scale remains to be fully analyzed.

Conclusion

By solving the realizability problem, this research provides a robust foundation for belief change in abstract argumentation. It ensures that agents can update their argumentative knowledge bases in a way that is both logically sound and structurally consistent, paving the way for more sophisticated, iterative reasoning in multi-agent systems.

Summary updated

BibTeX
@inproceedings{diller2015extension,
  author = {Martin Diller and Adrian Haret and Thomas Linsbichler and Stefan Rümmele and Stefan Woltran},
  title = {{An Extension-Based Approach to Belief Revision in Abstract Argumentation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure