Optimal Status Enforcement in Abstract Argumentation

Andreas Niskanen, Johannes Peter Wallner, Matti JärvisaloIJCAI 2016

Abstract

Abstract Argumentation Frameworks (AFs) provide a robust structure for modeling conflict and reasoning. This paper investigates the problem of optimal status enforcement: the task of minimally modifying the attack relations within an AF so that a given set of arguments achieves a desired acceptance status (positive or negative) under a specific semantics. We provide a comprehensive complexity analysis, showing that while some variants are NP-complete, the inclusion of negative status requirements often elevates the problem to $\Sigma^P_2$-completeness. To address these challenges, we introduce PAKOTA, a solver that leverages MaxSAT encodings and Counterexample-Guided Abstraction Refinement (CEGAR). Experimental results demonstrate that PAKOTA can handle frameworks with up to 200 arguments, marking a significant step toward practical dynamic argumentation.

1. Introduction

In artificial intelligence, Abstract Argumentation Frameworks (AFs) represent arguments as nodes and attacks as directed edges. Traditional reasoning in AFs is static, focusing on identifying "winning" sets of arguments (extensions) for a fixed graph. However, real-world applications like legal reasoning or multi-agent negotiation are inherently dynamic. As new information emerges, the status of certain arguments may need to be enforced—either as accepted (positive status) or rejected (negative status).

Illustration of various enforcement scenarios where edges are added or removed to change argument status.

The challenge lies in "optimal" enforcement: modifying the attack structure with the minimum number of changes to preserve the original framework's integrity as much as possible. Unlike previous work on "extension enforcement," which focuses on forcing a specific set of arguments to be an extension, "status enforcement" allows for more flexible requirements on individual arguments.

2. Complexity and Semantics

The difficulty of status enforcement varies significantly depending on the chosen semantics (e.g., stable, admissible, grounded) and the nature of the enforcement:

  • Positive Enforcement: Forcing an argument to be accepted is typically NP-complete.
  • Negative Enforcement: Forcing an argument to be rejected often causes a complexity jump to the second level of the polynomial hierarchy ($\Sigma^P_2$). This is because verifying rejection requires checking all possible extensions, a coNP-hard task in itself.

The paper demonstrates that for unique-status semantics like grounded semantics, status enforcement aligns with extension enforcement. However, for multiple-status semantics like preferred or stable, the problems are distinct and computationally more demanding.

3. Algorithmic Implementation: PAKOTA

To solve these high-complexity problems, the authors developed the PAKOTA system, which employs two primary techniques:

  • MaxSAT Encodings: For NP-complete variants, the AF rules and the minimality constraint are translated into a Maximum Satisfiability problem.
  • CEGAR (Counterexample-Guided Abstraction Refinement): For $\Sigma^P_2$-complete problems, a CEGAR loop is used. The system solves an abstraction of the problem, checks for counterexamples (extensions where a rejected argument is still accepted), and refines the constraints iteratively.

4. Experimental Evaluation

PAKOTA was evaluated using randomly generated directed graphs with varying argument counts (20 to 200) and edge densities (0.05 to 0.35).

Performance of PAKOTA showing mean CPU time across different enforcement types and argument counts.

The results indicate that PAKOTA scales effectively for most cases up to 100 arguments. Credulous enforcement under admissible semantics generally proves easier than skeptical enforcement under stable semantics. While performance degrades as graph density and argument count increase, the CEGAR approach remains effective for handling $\Sigma^P_2$ variants.

5. Conclusion and Future Work

This work establishes the theoretical and practical foundations for optimal status enforcement. Future research will address even harder variants, such as skeptical preferred semantics ($\Sigma^P_3$), and incorporate structural constraints where certain attacks are immutable. Testing on real-world argumentation topologies from legal or medical domains will further refine the solver's capabilities.

Summary updated

BibTeX
@inproceedings{niskanen2016optimal,
  author = {Andreas Niskanen and Johannes Peter Wallner and Matti Järvisalo},
  title = {{Optimal Status Enforcement in Abstract Argumentation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure