Choices and their Provenance: Explaining Stable Solutions of Abstract Argumentation Frameworks

The rule Defeated(x) leftarrow Attacks(y,x),, neg , Defeated(y), evaluated under the well-founded semantics (WFS), yields a unique 3-valued (skeptical) solution of an abstract argumentation framework (AF). An argument x is defeated (OUT) if there exists an undefeated argument y that attacks it. For 2-valued (stable) solutions, this is the case iff y is accepted (IN), i.e., if all of y's attackers are defeated. Under WFS, arguments that are neither accepted nor defeated are undecided (UNDEC). As shown in prior work, well-founded solutions (a.k.a. grounded labelings) "explain themselves": The provenance of arguments is given by subgraphs (definable via regular path queries) rooted at the node of interest. This provenance is closely related to winning strategies of a two-player argumentation game. We present a novel approach for extending this provenance to stable AF solutions. Unlike grounded solutions, which can be constructed via a bottom-up alternating fixpoint procedure, stable models often involve non-deterministic choice as part of the search for models. Thus, the provenance of stable solutions is of a different nature, and reflects a more expressive generate & test paradigm. Our approach identifies minimal sets of critical attacks, pinpointing choices and assumptions made by a stable model. These critical attack edges provide additional insights into the provenance of an argument's status, combining well-founded derivation steps with choice steps. Our approach can be understood as a form of diagnosis that finds minimal "repairs" to an AF graph such that the well-founded solution of the repaired graph coincides with the desired stable model of the original AF graph.