Incomplete Argumentation Frameworks: Properties and Complexity

Gianvincenzo Alfano, Sergio Greco, Francesco Parisi, Irina TrubitsynaAAAI 2022 · DOI

Introduction

Dung’s Argumentation Framework (AF) is the standard model for representing disputes in artificial intelligence, using directed graphs where nodes represent arguments and edges represent attacks. However, real-world information is frequently incomplete or uncertain. We may not know if an argument exists or if one point truly invalidates another. Incomplete Argumentation Frameworks (iAFs) were developed to model this "unquantified uncertainty" by allowing arguments and attacks to be marked as uncertain.

An example of an Incomplete Argumentation Framework (iAF) where node 'e' and its associated attacks are uncertain.

Decidability Properties in iAFs

While existing methods focus on "possible" or "necessary" acceptance, this research introduces three new properties—totality, determinism, and functionality—to measure how "decided" an argument is within an iAF:

  • Totality (TS): Is the argument's status always "decided" (not "undecided") regardless of the uncertainty?
  • Determinism (DS): Does the argument always result in the same outcome across all possible interpretations?
  • Functionality (FS): Is the information sufficient to make a firm, unambiguous decision (i.e., both total and deterministic)?

These properties are vital for decision-support systems, helping to determine if there is "enough" information to act despite underlying uncertainty.

Complexity Analysis and Structural Rewriting

The authors provide a comprehensive complexity map for these properties across five major semantics: grounded (gr), complete (co), stable (st), preferred (pr), and semi-stable (sst). The analysis shows that checking these properties generally falls into coNP-complete or $\Pi^p_2$-complete categories.

Table 1: Computational complexity of checking Totality (TS), Determinism (DS), and Functionality (FS) in general and odd-cycle free iAFs.

A significant finding is that iAFs can be simplified without losing expressivity. Any complex iAF with both uncertain arguments and attacks can be rewritten into an equivalent form where only arguments or only attacks are uncertain. Furthermore, for "odd-cycle free" graphs, the complexity often drops by one level, making the problems more computationally tractable.

Probabilistic Mapping and Future Work

The research bridges qualitative and quantitative uncertainty by showing that iAFs can be mapped to Probabilistic AFs (PrAFs), where uncertain elements are assigned a probability (e.g., 0.5). However, calculating exact acceptance probabilities in these models is proven to be #P-hard, even for simple acyclic graphs.

Future work will involve extending these properties to "ideal" and "eager" semantics, investigating how functionality changes dynamically as attacks are added or removed, and developing practical SAT-based algorithms for large-scale systems.

Summary updated

BibTeX
@inproceedings{alfano2022incomplete,
  author = {Gianvincenzo Alfano and Sergio Greco and Francesco Parisi and Irina Trubitsyna},
  title = {{Incomplete Argumentation Frameworks: Properties and Complexity}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20483},
}
Figure