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.
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.
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