Introduction: Softening Logic for Real-World Argumentation
Abstract Argumentation Frameworks (AAFs) are a cornerstone of AI reasoning, modeling arguments as nodes in a graph and "attacks" as directed edges. Traditionally, researchers seek "stable extensions"—sets of arguments that are internally consistent (conflict-free) and collectively defeat all external arguments.
However, stable extensions are often non-existent in complex, real-world graphs. This paper addresses the need for graded or "soft" semantics. Instead of an all-or-nothing approach, the authors introduce measures of how close a set of arguments is to being stable, allowing for the ranking of arguments even when perfect consistency is impossible.
Quantitative Relaxations and Heuristics
The authors propose two primary optimization problems to handle these scenarios:
- MAXSTABLE: Seeks a conflict-free set that attacks the maximum number of external arguments (referred to as $k$-stable).
- MAXSTABLE: Seeks a set that covers all arguments (full-range) while minimizing internal conflicts (referred to as $k$-stable).
To solve these, four greedy heuristic algorithms were developed: GCF (Growing Conflict-Free) and SCF (Shrinking Conflict-Free) for MAXSTABLE, and GFR and SFR for MAXSTABLE*. These heuristics aim to provide fast, near-optimal solutions where exact solvers might struggle.
Theoretical Hardness vs. Empirical Success
Theoretically, these optimization problems are highly complex ($FP^{NP[\log]}$-complete) and difficult to approximate (Poly-APX-complete). This suggests that in the worst case, finding a good approximation is as hard as solving the classic Independent Set problem.
Despite these grim theoretical bounds, empirical testing on benchmarks from the International Competition on Computational Models of Argumentation (ICCMA) tells a different story.
Key Results
The greedy heuristics demonstrated remarkable accuracy and efficiency across thousands of instances from the ICCMA17 and ICCMA19 competitions:
- Accuracy: The heuristics achieved surprisingly high approximation ratios (AR). For MAXSTABLE, the GCF algorithm achieved an average AR of 0.964 on the ICCMA17-B dataset. For MAXSTABLE, the SFR algorithm reached an AR of 0.984*.
- Efficiency: Heuristics were significantly faster than optimal MaxSAT-based solvers. As shown in the results table, optimal solvers (OPT/OPT*) suffered from over 700 timeouts (#TO) on ICCMA17-B, whereas the greedy approaches had minimal to zero timeouts.
Conclusion
This work bridges the gap between qualitative logic and quantitative optimization. While the theoretical complexity is high, the practical performance of simple greedy algorithms suggests that real-world argumentation structures are more amenable to approximation than mathematical worst cases suggest. Future research will look to extend these "soft" semantics to other frameworks like admissible and preferred semantics.
Summary updated