Strong Explanations in Abstract Argumentation

Markus Ulbricht, Johannes Peter WallnerAAAI 2021 · DOI

Introduction

Abstract Argumentation Frameworks (AFs), introduced by Dung, provide a formal way to model debates as directed graphs. In these graphs, nodes represent arguments and edges represent attack relations. To determine the "winning" arguments, various semantics are employed to identify extensions—sets of arguments that are collectively acceptable.

A standard Abstract Argumentation Framework (AF) where nodes represent arguments and arrows represent attacks.

While extensions serve as a baseline for justifying why an argument is accepted, they suffer from two primary limitations: a lack of robustness and excessive verbosity. An extension is defined relative to the entire graph; removing a seemingly irrelevant argument can invalidate the entire set. Furthermore, extensions often contain many arguments not strictly necessary for defending a specific target, leading to overly complex explanations.

Defining Strong Explanations

To address these issues, this paper introduces the concept of Strong Explanations. A set of arguments $S$ is considered a strong explanation for a target set $X$ if $X$ remains acceptable in every possible sub-framework that contains $S$. This requirement ensures that the justification for $X$ is robust against changes in the surrounding context of the debate.

An illustration of a framework $F$ and its sub-framework $F \downarrow_S$, demonstrating how strong explanations hold across different sub-contexts.

A key property of strong explanations is monotonicity: if $S$ explains $X$, then any superset of $S$ also explains $X$. This aligns with the intuitive notion that providing more supporting information should not invalidate a valid justification.

Key Insights and Complexity

Strong explanations offer several advantages over traditional extensions:

  • Conciseness: A strong explanation can be significantly smaller than any valid extension. It focuses only on the "essential" arguments required to ensure the target's acceptance.
  • Conflict Tolerance: Unlike standard extensions, a minimal strong explanation does not need to be conflict-free. It may include conflicting arguments if their presence is necessary to neutralize counter-arguments across various sub-scenarios.
  • Independence: The explanation's validity does not depend on arguments outside of the set $S$.

However, this robustness comes with a "complexity tax." Verifying strong explanations is computationally more demanding than verifying standard extensions. For most semantics, the verification task jumps from Polynomial (P) or coNP-complete to $\Pi^p_2$-completeness.

Semantics Extension Verification Strong Expl. Verification
Grounded Polynomial (P) coNP-complete
Admissible / Stable Polynomial (P) $\Pi^p_2$-complete
Preferred coNP-complete $\Pi^p_2$-complete

Despite this high general complexity, the authors identify a tractable case: if an argument belongs to the grounded extension, a strong explanation can be computed in polynomial time.

Conclusion

Strong explanations provide a robust and concise framework for justifying reasoning in abstract argumentation. While the computational cost is high, the benefits in terms of explanation quality and context-independence make them a valuable tool for Explainable AI (XAI). Future work includes extending this logic to "strong rejections" and developing efficient heuristic solvers for high-complexity verification tasks.

Summary updated

BibTeX
@inproceedings{ulbricht2021strong,
  author = {Markus Ulbricht and Johannes Peter Wallner},
  title = {{Strong Explanations in Abstract Argumentation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i7.16805},
}
Figure