TL;DR
This paper introduces "Control Argumentation Frameworks" (CAFs) to model uncertainty in argumentation, focusing on the "controllability" problem: can we use control arguments to ensure a desired outcome (e.g., a specific set of arguments being accepted) across all possible scenarios? The authors provide a comprehensive complexity map for this problem and develop efficient QBF and SAT-based algorithms, empirically evaluating their performance.
What Problem Does This Paper Address?
Argumentation systems, which model reasoning with conflicting information, often need to account for uncertainty. This uncertainty can arise from incomplete knowledge about the existence of arguments or the attacks between them. Control Argumentation Frameworks (CAFs) were proposed to address this by introducing "control" arguments that can be strategically manipulated to influence the outcome of the argumentation.
A key computational challenge in CAFs is "controllability": can we, by choosing a specific set of control arguments, guarantee that a target set of arguments is accepted (either credulously, meaning in at least one possible outcome, or skeptically, meaning in all possible outcomes) regardless of how the uncertain parts of the framework are resolved? While previous work touched on this, a complete understanding of the computational complexity and efficient algorithms for various argumentation semantics was lacking. This paper aims to fill that gap by providing a full complexity landscape and practical algorithmic solutions.
Methods
The authors tackle the controllability problem using two main approaches:
- Complexity Analysis: They establish tight computational complexity bounds for credulous and skeptical controllability under five standard argumentation semantics (admissible, complete, preferred, stable, grounded). This involves reductions from known hard problems in related areas like incomplete argumentation frameworks (IAFs).
- Algorithmic Approaches:
- Quantified Boolean Formulas (QBFs): They develop direct QBF encodings for controllability. These encodings are designed to be more compact than previous ones and capture the problem's structure by quantifying over control configurations, completions, and extensions.
- SAT-based Counterexample-Guided Abstraction Refinement (CEGAR): This iterative approach uses a SAT solver to find candidate control configurations and then checks for "counterexamples" (scenarios where the desired outcome is not achieved). If a counterexample is found, the abstraction is refined, and the process repeats. This is presented as an alternative to QBFs, potentially offering better performance on certain instances.
Datasets
The authors generated CAFs for their empirical evaluation using instances from the 2019 ICCMA (International Competition on Computational Models of Argumentation) competition. They describe a process of creating CAFs by taking existing argumentation frameworks and introducing uncertainty (uncertain arguments and attacks) and control arguments with specific probabilities. This resulted in a dataset of 6520 CAFs, including a subset of simplified CAFs (without uncertain parts).
Key Insights and Ideas
- Complexity Landscape: The paper provides a comprehensive map of the computational complexity for controllability across different semantics, revealing that most variants fall into the $\Sigma_2^P$ or $\Pi_2^P$ classes of the polynomial hierarchy. This highlights the inherent difficulty of reasoning about controllability.
- Connection to IAFs: A crucial insight is the tight connection established between controllability in simplified CAFs and acceptance problems in incomplete argumentation frameworks (IAFs). This allowed them to leverage existing results for IAFs to derive new complexity bounds for CAFs.
- Algorithmic Trade-offs: The empirical evaluation suggests that the choice between QBF-based and CEGAR-based approaches depends on the specific problem instance and semantics. While QBFs might have fewer timeouts, CEGAR can be faster on certain types of problems, indicating a practical trade-off between different solving strategies.
- Compact QBF Encodings: The proposed QBF encodings are noted for their compactness, which can be beneficial for QBF solver performance.
Key Results
- Complexity Results: The paper establishes tight complexity results for credulous and skeptical controllability for both general and simplified CAFs under various semantics. For instance, skeptical controllability for simplified CAFs is $\Sigma_2^P$-complete under stable semantics, and credulous controllability for general CAFs is $\Sigma_2^P$-complete under admissible, complete, preferred, and stable semantics.
- Algorithmic Implementations: The authors present and evaluate QBF and SAT-based algorithms for solving the controllability problem.
- Empirical Performance: The evaluation shows that both QBF and CEGAR approaches are viable, with performance varying based on the problem instance and semantics. For example, CEGAR generally showed lower mean runtimes for skeptical controllability under "com," while QBF was faster for credulous controllability under "stb."
Limitations and Future Work
- Skeptical Controllability under Preferred Semantics: The paper notes that the QBF encoding and CEGAR algorithm do not directly cover skeptical controllability under preferred semantics, suggesting this as a direction for future work.
- Further Semantics and Refinements: The authors suggest exploring additional argumentation semantics and developing more sophisticated CEGAR refinement strategies.
- QBF Solver Optimization: Evaluating different QBF solvers could further improve performance.
- Broader Empirical Evaluation: While the generated CAFs are based on ICCMA instances, a broader range of benchmarks and more extensive empirical analysis could provide deeper insights.
Summary updated