Extension Removal in Abstract Argumentation - An Axiomatic Approach

Ringo Baumann, Gerhard BrewkaAAAI 2019 · DOI

Abstract

In the field of Artificial Intelligence, Abstract Argumentation Frameworks (AFs) provide a structured way to model conflicting information. While significant research has focused on how to enforce specific sets of arguments (extensions) as acceptable, the inverse problem—removing undesired extensions—has remained under-explored. This paper introduces a formal, axiomatic framework for extension removal, adapting the well-known AGM postulates for belief contraction. The authors prove that for many common semantics, such as stable semantics, extension removal is always possible and results in a semantically unique outcome.

Introduction: The Problem of Extension Removal

Abstract Argumentation Frameworks (AFs) represent arguments as nodes in a directed graph, where edges signify attacks between them. A chosen "semantics" determines which sets of arguments, known as extensions, are collectively acceptable.

The running example argumentation framework $F$ used to illustrate the concepts of nodes (arguments) and directed edges (attacks).

While "extension enforcement" (modifying a graph to make a set of arguments acceptable) is a well-studied area, "extension removal" addresses the opposite need. For instance, an autonomous agent might discover that one of its possible world views (an extension) is flawed and must be eliminated. The challenge lies in modifying the internal argumentation graph to remove that specific view while maintaining as much of the original structure and meaning as possible.

The Axiomatic Approach

The authors adopt an axiomatic methodology inspired by the AGM theory (Alchourrón, Gärdenfors, and Makinson), the standard for belief change in classical logic. They propose six "removal postulates" ($R1^\sigma$ - $R6^\sigma$) that any valid removal operator should satisfy:

  • Inclusion: The new set of extensions must be a subset of the original ones.
  • Vacuity: If the extension to be removed is not present, the AF remains unchanged.
  • Success: The targeted extensions are successfully removed from the resulting AF.

To achieve this, the paper introduces "$\sigma$-candidates"—AFs that produce exactly the set of extensions remaining after the undesired ones are subtracted. For stable semantics, the authors provide a "Standard Construction" method to build these new AFs.

Key Insights: Semantic Uniqueness and Structural Changes

A major finding of this research is semantical uniqueness: for any given AF and set of extensions to remove, the resulting set of extensions is unique. While multiple different graphs might represent this result, they are all semantically equivalent.

Another counter-intuitive insight involves the relationship between subgraphs and supergraphs. The authors demonstrate that it is not always possible to remove an extension simply by deleting attacks or arguments (creating a subgraph).

A comparison between an argumentation framework $G$ and its subgraph $G'$, illustrating that simple deletion of components may not suffice for extension removal.

Instead, removal can always be guaranteed by adding new arguments and attacks (creating a supergraph) to "drown out" the undesired extensions. This is particularly effective under stable semantics, which allow for "collapse" (an AF having no extensions), making it mathematically easier to guarantee a removal operator exists.

Key Results and Theoretical Bounds

  • Existence and Uniqueness: The paper proves that if a "candidate" AF exists for a given semantics, a removal operator exists and is semantically unique (Theorems 1 & 3).
  • Stable Semantics Success: For stable semantics, the existence of a removal operator is unconditionally guaranteed (Theorem 6).
  • Universal Impossibility: For semantics that must always have at least one extension (e.g., grounded or preferred), it is logically impossible to remove all extensions (Theorem 7). At least one must remain.
  • Syntactic Bounds: For stable semantics, a result can always be found by adding exactly one new argument for every extension targeted for removal (Theorem 10).

Conclusion and Future Directions

While this work establishes a robust semantic foundation for extension removal, it notes that syntactic minimal change—modifying the fewest possible edges or nodes—remains a difficult challenge that often conflicts with semantic postulates. Future research will look to extend these axioms to more complex frameworks like Abstract Dialectical Frameworks (ADFs) and develop efficient algorithms for real-time application in large-scale systems.

Summary updated

BibTeX
@inproceedings{baumann2019extension,
  author = {Ringo Baumann and Gerhard Brewka},
  title = {{Extension Removal in Abstract Argumentation - An Axiomatic Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012670},
}
Figure