Quantitative Reasoning over Incomplete Abstract Argumentation Frameworks

Bettina Fazzinga, Sergio Flesca, Filippo Furfaro, Giuseppina MonterossoIJCAI 2024

Introduction

Abstract Argumentation Frameworks (AAFs) provide a robust mathematical structure for modeling disputes, representing arguments as nodes and attacks as directed edges. However, real-world information is frequently "incomplete"—one might be uncertain whether a specific argument will be introduced or if a particular attack exists.

Traditional Incomplete AAFs (iAAFs) rely on qualitative reasoning, categorizing sets of arguments as either "possible" (true in at least one scenario) or "necessary" (true in all scenarios). This binary approach is often too coarse for practical decision-making. For instance, knowing an argument is "possible" provides little utility if it only holds in a negligible fraction of scenarios. While Probabilistic AAFs (prAAFs) offer a quantitative alternative, they require precise probability assignments for every element, which are often unavailable. This research bridges the gap by introducing quantitative reasoning based on the structural incompleteness of the framework itself.

Methodology: Quantifying Uncertainty

The authors propose shifting from binary labels to calculating the exact percentage of completions (scenarios) where an argument or set of arguments is accepted. They define two core computational problems:

  1. PERCVER: Determining the percentage of completions in which a set of arguments $S$ constitutes a valid extension.
  2. PERCACC: Determining the percentage of completions in which a specific argument $a$ is accepted.

Central to these is CNTCOM, the problem of counting the total number of valid completions given a set of logical dependencies. These dependencies allow for modeling complex relationships, such as "Argument A and Argument B are mutually exclusive."

An example of an iAAF featuring uncertain arguments ($e_1, e_2, e_3$) and a logical dependency constraint (NAND) that limits the valid completions of the framework.

Key Insights: The Nature of Incompleteness

A significant finding is that iAAFs are not merely simplified probabilistic models. The authors demonstrate that an iAAF cannot be trivially translated into an independent probabilistic framework where every uncertain element has a 50% chance of existence. Such a translation is computationally expensive and typically destroys the model's compactness.

Furthermore, the introduction of logical dependencies significantly increases complexity. Even without dependencies, it is mathematically impossible to assign simple marginal probabilities to individual arguments that result in a uniform distribution over all possible completions. The paper also identifies "islands of tractability": if the set of arguments being verified is small and its interactions are limited to certain (non-uncertain) parts of the framework, the problems become solvable in polynomial time.

Computational Complexity Results

The study establishes rigorous complexity bounds for these quantitative problems:

  • Counting Completions (CNTCOM): Proven to be #P-complete.
  • Percentage Problems (PERCVER and PERCACC): Proven to be $FP^{\#P}$-complete. These results indicate that these problems are significantly harder than standard NP-complete problems, as they involve counting solutions to hard problems.
  • Translation Hardness: Under the assumption that $P \neq NP$, there is no polynomial-time algorithm to convert a general iAAF into a standard probabilistic AAF while maintaining reasoning consistency.
  • Tractability (Theorem 9): PERCVER is shown to be in P (tractable) under admissible semantics when uncertainty is localized and the target set $S$ is small.

Conclusion and Future Directions

While the high computational complexity poses challenges for large-scale frameworks, this work provides a formal foundation for more nuanced reasoning in uncertain environments. Future research will focus on developing optimized counting algorithms, exploring approximate methods like Monte Carlo simulations for large frameworks, and integrating these measures into practical applications like legal reasoning tools or automated negotiation systems.

Summary updated

BibTeX
@inproceedings{fazzinga2024quantitative,
  author = {Bettina Fazzinga and Sergio Flesca and Filippo Furfaro and Giuseppina Monterosso},
  title = {{Quantitative Reasoning over Incomplete Abstract Argumentation Frameworks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}

Loading related content...

Figure