On Undisputed Sets in Abstract Argumentation

Matthias ThimmAAAI 2023 · DOI

TL;DR

This paper introduces "undisputed sets" and "strongly undisputed sets" as a way to relax the strict requirements of traditional argumentation semantics, particularly when dealing with irrelevant or self-defeating attacks. These new notions offer a conceptually simpler and computationally more tractable alternative to existing "weak admissibility" semantics, while still capturing desirable properties of argumentation.

What Problem Does This Paper Address?

Abstract argumentation frameworks (AFs) are a powerful tool for modeling reasoning and knowledge representation. They use a directed graph where nodes are arguments and edges represent attacks. Formal semantics define what constitutes a "valid" or "acceptable" set of arguments (an extension). However, traditional semantics like "admissibility" can be overly strict, requiring arguments to defend themselves against all attackers, even those that are self-attacking or part of a nonsensical cycle. This can lead to situations where intuitively acceptable arguments are rejected. Existing approaches to "weakening admissibility" to address this, like weak admissibility, are often computationally complex (PSPACE-complete) and can have opaque definitions. This paper aims to provide a conceptually simpler and more computationally efficient way to handle these issues.

Methods

The core of the paper introduces two new semantic notions:

  • Undisputed Sets: A set of arguments $S$ is undisputed if it's conflict-free (no argument in $S$ attacks another in $S$) and its "reduct" ($F_S$, the framework remaining after removing $S$ and all arguments attacked by $S$) contains no non-empty admissible sets. This essentially means that once you've removed the arguments in $S$ and those they defend, the remaining part of the argument graph is "empty" in terms of having any valid arguments.
  • Strongly Undisputed Sets: This is a stricter version where the reduct must not only be "adm-vacuous" (no non-empty admissible sets) but also "ud-vacuous" (no non-empty undisputed sets).

The authors analyze the properties of these new notions, showing how they relate to existing semantics like preferred and stable extensions. They also investigate their computational complexity.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of abstract argumentation frameworks, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Undisputed sets generalize preferred extensions: This is a key insight. It means that all preferred extensions are undisputed sets, but not vice-versa. This provides a broader notion of acceptability.
  • "Vacuous reduct" as a core concept: The idea that the remaining framework after considering a set of arguments should be "empty" or "nonsensical" is a powerful way to define acceptability, especially when dealing with problematic attackers.
  • Strongly undisputed sets address maximality issues: While undisputed sets can be in subset relations with each other, strongly undisputed sets are shown to be "maximally" undisputed, addressing a limitation of the weaker notion.
  • Conceptual simplicity and computational tractability: The authors highlight that their definitions are more straightforward than some existing weak admissibility semantics, and importantly, they achieve better computational complexity.

Key Results

  • Characterization of Preferred Extensions: The paper shows that preferred extensions are exactly the admissible sets that are also minimal undisputed sets.
  • Relationship to Classical Semantics: Undisputed sets generalize preferred extensions, and strongly undisputed sets generalize stable extensions. Figure 6 in the paper visually depicts these relationships.
  • Computational Complexity:
    • Reasoning tasks for undisputed sets lie on the second level of the polynomial hierarchy (e.g., $E^P$-complete for existential queries).
  • Reasoning tasks for strongly undisputed sets lie on the third level of the polynomial hierarchy (e.g., $\Sigma_2^P$-complete for existential queries).
  • While still complex, these are significantly more tractable than PSPACE-complete problems associated with weak admissibility.
  • Handling of Problematic Examples: The new notions successfully address the motivating examples (Fo and F1) where traditional semantics fail, correctly identifying {b} as an acceptable outcome.

Limitations and Future Work

  • Computational Complexity: While more tractable than weak admissibility, the complexity for undisputed and strongly undisputed sets is still relatively high (second and third levels of the polynomial hierarchy).
  • Undefined Semantics: The paper notes that strongly undisputed semantics can be undefined for certain frameworks (Example 8), similar to stable semantics.
  • Future Work: The authors suggest further investigation into "vacuous reduct semantics" as a general framework for defining new semantics. They also plan to explore the properties of undisputed sets in relation to argumentation principles and to investigate whether other semantics can be characterized similarly to how preferred extensions are characterized as admadm-extensions.

Summary updated

BibTeX
@inproceedings{thimm2023undisputed,
  author = {Matthias Thimm},
  title = {{On Undisputed Sets in Abstract Argumentation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25805},
}
Figure