On the Responsibility for Undecisiveness in Preferred and Stable Labellings in Abstract Argumentation (Extended Abstract)

Claudia Schulz, Francesca ToniIJCAI 2019 · DOI

Abstract

In the field of Abstract Argumentation (AF), automated reasoning systems often encounter "undecisiveness," where arguments cannot be definitively accepted or rejected. While stable semantics offer decisiveness by labelling every argument as in or out, they are not guaranteed to exist. Preferred semantics are guaranteed to exist but frequently result in undec (undecided) labels. This paper introduces formal characterizations to pinpoint the specific arguments and structural components responsible for this lack of decisiveness. By defining labelling-based concepts like enforcement sets and structural concepts like Strongly Connected undec Parts (SCUPs), we provide a framework for "debugging" argumentation graphs and enabling targeted structural revisions to achieve stable outcomes.

Introduction

Abstract Argumentation Frameworks (AFs) represent knowledge as graphs where nodes are arguments and directed edges represent attacks. Determining which arguments to accept requires applying "semantics"—sets of rules for assigning labels. A primary goal in many applications is to reach a stable state where every argument is either accepted (in) or rejected (out). However, structural conflicts, such as odd-length cycles, can prevent the existence of stable labellings. In such cases, preferred semantics are used, which always exist but may leave some arguments in an undec state.

The Problem of Undecisiveness

When a reasoning system returns an undecided result, it is often unclear which part of the knowledge base is at fault. This paper addresses the practical problem of identifying "responsibility": which specific arguments or cycles are blocking a stable, decisive conclusion?

A preferred labelling where arguments A, B, C, and D remain undecided due to a cycle and a self-attack.

Characterizing Responsibility

The authors propose two complementary approaches to localizing the cause of indecision.

1. Labelling-Based Characterisations

  • Enforcement Sets: These are minimal sets of undecided arguments that, if externally forced to be in or out, would allow the entire framework to reach a stable state. They represent the minimal necessary changes for decisiveness.
  • Preventing Sets: These are minimal sets of arguments that inherently block stability. No valid assignment of in or out labels can be found for these arguments without violating the rules of the framework.

2. Structural Characterisations

  • Responsible Odd-Length Cycles: The authors identify cycles of undecided arguments (e.g., A attacks B, B attacks C, C attacks A) as primary drivers of instability.
  • Strongly Connected undec Parts (SCUPs): These are initial components of the graph consisting entirely of undecided arguments. The paper proves that every SCUP contains at least one responsible odd-length cycle, identifying them as the "root causes" of indecision.

Insights and Results

A key contribution of this work is the "Duality of Responsibility." Enforcement sets identify what needs to be fixed, while preventing sets identify what is blocking the solution. Furthermore, the research demonstrates that indecision is often local rather than systemic. By identifying SCUPs, users can focus their attention on specific "troublemaker" regions of the graph.

A stable labelling achieved by adding an external argument ("A is not effective") to break the cycle of indecision.

As shown in the figures, identifying the responsible arguments allows for "structural revision." In the clinical example, adding a new argument ("A is not effective") breaks the cycle between A, B, and C, allowing the framework to collapse into a stable state where B is accepted and A, C, and D are rejected.

Conclusion and Future Work

This research provides a formal foundation for explaining why an argumentation system fails to reach a firm conclusion. While it identifies where the problem lies, future work is needed to automate the "how" of structural revision—prescribing specific additions or removals of attacks to resolve conflicts efficiently. Additionally, the computational complexity of finding these sets in large-scale graphs remains an open area for investigation.

Summary updated

BibTeX
@inproceedings{schulz2019responsibility,
  author = {Claudia Schulz and Francesca Toni},
  title = {{On the Responsibility for Undecisiveness in Preferred and Stable Labellings in Abstract Argumentation (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/892},
}
Figure