Recursion in Abstract Argumentation is Hard - On the Complexity of Semantics Based on Weak Admissibility

Wolfgang Dvorák, Markus Ulbricht, Stefan WoltranAAAI 2021 · DOI

Introduction

Abstract Argumentation Frameworks (AFs) provide a formal way to model debates by representing arguments as nodes in a graph and attacks as directed edges. In the foundational work by Dung, a set of arguments is considered "admissible" if it is conflict-free and can defend itself against all attackers. However, classical semantics often struggle with self-defeating arguments—arguments that attack themselves or exist within odd-length attack loops. These "dummy" arguments can paradoxically block reasonable arguments from being accepted, even though the dummy arguments can never be part of a valid extension themselves.

To address this, researchers introduced weak admissibility. This approach uses a recursive "reduct" to ignore attackers that are not considered "serious rivals." While this provides more intuitive results for complex attack structures, the computational cost of this recursion remained largely unexplored. This paper provides a comprehensive complexity analysis, proving that the intuitive benefits of weak admissibility come with a significant computational price.

The Mechanism of Weak Admissibility

The core of weak admissibility is the reduct, denoted as $F^E$. When evaluating a set of arguments $E$, the reduct $F^E$ is formed by removing the "range" of $E$ (the set $E$ plus all arguments it attacks) and re-evaluating the remaining graph. An argument is weakly admissible if it can defend itself within this simplified, recursive context.

An Argumentation Framework $F$ and its reduct $F^{\{a\}}$, illustrating how weak admissibility re-evaluates the graph by removing the range of a set.

As shown in Figure 1, the reduct allows the system to essentially "filter out" arguments that are already defeated by the set under consideration, focusing only on the remaining active threats. This nested search structure is what allows weak admissibility to handle self-defeating arguments more gracefully than standard Dung-style semantics.

Computational Complexity: The Jump to PSPACE

The paper's primary contribution is the proof that this recursive re-evaluation pushes standard decision problems from their usual complexity classes (typically NP, coNP, or $\Sigma_2^P$) into PSPACE-complete territory.

To prove PSPACE-hardness, the authors provide a reduction from Quantified Boolean Formulas (QBF). They construct specific AF gadgets where the validity of a QBF corresponds to the existence of a weakly admissible set. The recursive nature of the weak admissibility reduct perfectly mirrors the nested quantifiers ($\forall, \exists$) found in QBF problems.

A complex Argumentation Framework gadget used in the reduction from Quantified Boolean Formulas (QBF) to prove PSPACE-hardness.

Figure 5 illustrates the type of complex gadgetry required for these proofs, showing how literals ($x_i, \bar{x}_i$) and clauses ($c_j$) are mapped onto an argumentation graph. The result is that all standard decision problems—including Credulous Acceptance, Verification, and the Existence of a non-empty extension—for weak admissible, weak complete, weak grounded, and weak preferred semantics are PSPACE-complete.

Tractable Fragments and Implementation

Despite the high general complexity, the authors identify specific graph structures where the problem remains manageable:

  • Symmetric, Acyclic, and Bipartite AFs: In these cases, the problems collapse back to P (polynomial time).
  • Odd-cycle free AFs: The complexity drops to NP/coNP, making it comparable to traditional Dung semantics.

Interestingly, the "culprit" for high complexity is the presence of odd cycles—the very structures weak admissibility was designed to improve. For practical implementation, the authors develop a polynomial-time reduction to non-recursive DATALOG with stratified negation. This provides a bridge for using existing high-performance logic programming solvers to compute these complex semantics, even if the general case remains theoretically difficult.

Conclusion

This research highlights a fundamental trade-off in formal argumentation: the more "intelligent" or intuitive a semantics is in handling edge cases like self-defeating arguments, the higher its computational cost is likely to be. While weak admissibility solves long-standing issues with Dung's original framework, its PSPACE-completeness suggests that future work must focus on fixed-parameter tractability and specialized solvers to make these semantics viable for large-scale, real-world applications.

Summary updated

BibTeX
@inproceedings{dvorak2021recursion,
  author = {Wolfgang Dvorák and Markus Ulbricht and Stefan Woltran},
  title = {{Recursion in Abstract Argumentation is Hard - On the Complexity of Semantics Based on Weak Admissibility}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i7.16781},
}
Figure