AGM Meets Abstract Argumentation: Expansion and Revision for Dung Frameworks

Ringo Baumann, Gerhard BrewkaIJCAI 2015

Abstract

This research bridges the gap between classical belief revision (AGM theory) and abstract argumentation. By introducing a new family of "Dung logics," the authors define expansion and revision operators for argumentation frameworks that satisfy the gold-standard AGM postulates while respecting the crucial property of strong equivalence.

Introduction

In the field of Knowledge Representation, two major paradigms have traditionally stood apart: Belief Revision and Abstract Argumentation. Belief revision, governed by the famous AGM postulates, describes how a rational agent should update their knowledge base when faced with new, potentially conflicting information. Abstract Argumentation, specifically Dung’s Argumentation Frameworks (AFs), uses directed graphs to model arguments and their attack relations to determine which sets of arguments (extensions) are "acceptable."

The challenge is that AFs are non-monotonic; adding a new argument can completely change which previous arguments are considered valid. Previous attempts to combine these fields often ignored "strong equivalence"—the idea that two AFs are truly equivalent only if they behave the same way when any additional information is added. This paper tackles the fundamental question: How can we define AGM-style revision for AFs that respects the structural nuances of argumentation?

Methodology: Dung Logics and $k$-Models

The authors achieve this through several innovative steps, primarily the definition of a new family of monotonic logics where the "models" are actually other AFs (specifically $k$-models). This allows them to treat AFs like classical formulas. Crucially, they prove that "ordinary" equivalence in these new Dung logics perfectly matches "strong equivalence" in argumentation semantics, ensuring that the revision process preserves structural information.

Expansion and Revision Operators

Expansion—adding information without worrying about inconsistency—is defined as the intersection of sets of models. The authors provide a constructive method to show that this intersection can always be represented by a single, unique AF.

The result of the expansion operator $G *^k F$ for two frameworks.

Revision is more complex. The authors show that standard "distance-based" approaches fail for AFs because the resulting set of models might not be "realizable"—meaning no single AF could actually represent that set of models. To solve this for stable semantics, they construct the $k(stb)$-operator, which syntactically identifies the "maximal" non-conflicting information to satisfy all eight AGM postulates.

The result of the expansion operator $F *^k G$ showing structural differences based on operator order.

Key Insights

  • Models as Frameworks: By treating an AF not just as a graph but as a model of a specific logic ($k$-models), the authors can apply the machinery of classical logic to argumentation structures.
  • The Realizability Constraint: In classical logic, any set of models can be represented by a formula. In argumentation, a set of models must be "upward-closed" and have a "least element" to be representable as an AF. This is why standard revision techniques often break down.
  • Syntax vs. Semantics: Because semantic distance measures fail to guarantee a valid AF, the authors pivot to a syntactic construction for revision, proving its efficacy for stable semantics.

Results and Discussion

The paper provides a characterization theorem for when a set of models can be turned back into an AF. Key results include:

  • Expansion Success: Expansion is always possible and can be calculated by the union of the "kernels" (the essential, non-redundant parts) of the two AFs.
  • Postulate Satisfaction: For stable semantics ($k(stb)$), the authors successfully defined a revision operator that satisfies all 8 AGM postulates.
  • Broad Applicability: For other semantics (like admissible or complete), they showed that a "selection function" approach can satisfy at least the first 6 postulates, providing a roadmap for future research.

Conclusion and Future Work

The primary limitation is that the "perfect" 8-postulate revision is currently only fully defined for stable semantics. For other semantics, the plurality of potential "best" models requires a selection function whose properties are not yet fully explored. Future work will aim to extend these operators to more complex structures, such as Extended Argumentation Frameworks (EAFs) or Abstract Dialectical Frameworks (ADFs).

Summary updated

BibTeX
@inproceedings{baumann2015agm,
  author = {Ringo Baumann and Gerhard Brewka},
  title = {{AGM Meets Abstract Argumentation: Expansion and Revision for Dung Frameworks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure