Revisiting initial sets in abstract argumentation

1.Introduction

Formal argumentation [3,6] encompasses approaches for non-monotonic reasoning that focus on the role of arguments and their interactions. The most well-known approach is that of abstract argumentation frameworks [19] that model arguments as vertices in a directed graph, where a directed edge from an argument a to an argument b denotes an attack from a to b. Although conceptually simple, abstract argumentation frameworks can be used in a variety of argumentative scenarios such as persuasion dialogues [16], explanations in recommendation systems [31], mathematical modelling [11], or as a target formalism of structured argumentation formalisms [28,35]. Formal semantics are given to abstract argumentation frameworks by extensions, i. e., sets of arguments that can jointly be accepted and represent a coherent standpoint on the conflicts between the arguments. Different variants of such semantics have been proposed [5], but there are also other (non set-based) approaches such as ranking-based semantics [1] and probabilistic approaches [26].

A particular advantage of approaches to formal argumentation is the capability to explain the reasoning behind certain conclusions using human-accessible concepts such as arguments and counterarguments. Works such as [2,27,29,31–33,36] have already explored certain aspects of the explanatory power of approaches to formal argumentation. Amgoud and Prakken [2] and Rago et. al [31] develop argumentation formalisms for decision-making that augment recommendations with arguments. In [33] an extension to abstract argumentation frameworks is developed that explicitly includes a relationship for an “explanation”, while Liao and van der Torre [27] define “explanation semantics” for ordinary abstract argumentation frameworks. Saribatur, Wallner, and Woltran [32] as well as Niskanen and Järvisalo [29] address computational problems and develop a notion for explaining non-acceptability of arguments to, e. g., verify results of an argumentation solver. Finally, [36] presents strong explanations as a mechanism to explain acceptability of (sets of) arguments.

In this paper, we revisit one of the fundamental concepts underlying approaches to formal argumentation (and abstract argumentation in particular) for the purpose of explaining, namely admissibility. Informally speaking, a set of arguments is admissible if each of its members is defended against any attack from the outside (we will provide formal details in Section 2). Many popular semantics for abstract argumentation rely on the notion of admissibility. In particular, a preferred extension is a maximal (wrt. set inclusion) admissible set and preferred semantics satisfies many desirable properties [5]. However, since a preferred extension is a maximal admissible set, it can hardly be used for explaining why a certain argument is acceptable: such an extension may contain many irrelevant arguments and its size alone distracts from the particular reasons why a certain member is acceptable. Our aim is to investigate why certain arguments are contained in, e. g., a preferred extension and how we can decompose such large extensions into smaller sets that allow us to justify the reasoning process behind such complex semantics. As a tool for our investigation, we consider initial sets, i. e., non-empty admissible sets that are minimal wrt. set inclusion. Initial sets have been introduced in [38] and further analysed in [39,40]. We contribute to this analysis with new insights on the structure of initial sets and, in particular, to the use of initial sets for the task of explanation. In fact, initial sets can exactly be used for the purpose mentioned before [38]: they allow us to decompose large extensions into smaller fragments, each of them representing a single resolved issue in the argumentation framework and thus showcases the reasoning behind certain semantics. This has been done already in some form in [38–40] but we present a new, and arguably more elegant, formalisation of that idea that allows us to derive new results as well. Using the notion of a reduct [8], we can concisely represent any admissible set as a sequence of initial sets of the original framework and derived reducts. Moreover, we characterise many admissibility-based semantics through a step-wise construction process using certain selections of initial sets (this has been hinted at using the original formalisation for complete and preferred semantics in [40]). We round up our analysis with a characterisation of the computational complexity of certain tasks related to initial sets, which is also missing so far from the literature.

In summary, the contributions of this paper are as follows:

Complete proofs can be found in the appendix. A short paper presenting the main ideas of this work has been published before in [34].

2.Abstract argumentation

Let A denote a universal set of arguments. An abstract argumentation framework AF is a tuple AF=(A,R) where A⊆A is a finite set of arguments and R is a relation R⊆A×A [19]. Let AF denote the set of all abstract argumentation frameworks. For two arguments a,b∈A the relation aRb means that argument a attacks argument b. For AF=(A,R) and AF′=(A′,R′) we write AF′⊑AF iff A′⊆A and R′=R∩(A′×A′). For a set X⊆A, we denote by AF|X=(X,R∩(X×X)) the projection of AF on X. For a set S⊆A we define

Different semantics can be phrased by imposing constraints on admissible sets [5]. In particular, an admissible set E

3.Revisiting initial sets

Admissibility captures the basic intuition for an explanation why a certain argument can be regarded as acceptable. More concretely, if S is an admissible set then a∈S is accepted because all arguments in S are accepted, every attacker of a is attacked back by some argument in S. However, admissibility alone is not sufficient to model explainability as it does not take relevance into account.

Fig. 1.

AF0 from example 1.

As the previous example shows, an initial set is not supposed to provide a “solution” to the whole argumentation represented in an abstract argumentation framework, but “solves” a single atomic conflict (or in the case of {h} points to an obvious deterministic inference step). In fact, we can identify three different types of initial sets.

Note that only unattacked initial sets have been considered explicitly in [40]; in particular, note that every unattacked initial set S is a singleton S={a}. Observe that the notions of unattacked, unchallenged, and challenged initial sets are mutually exclusive and exhaustive. Let IS↚(AF), IS↮(AF), and IS↔(AF) denote the set of unattacked, unchallenged, and challenged initial sets, respectively. So we have IS(AF)=IS↚(AF)∪IS↮(AF)∪IS↔(AF). Moreover, for S∈IS(AF) let

Before we continue with characterising arbitrary admissible sets using initial sets in Section 4, we first contribute some new results on the structure of initial sets, therefore extending the analysis from [38–40].

Initial sets have an interesting property with respect to strongly connected components as follows. Recall that we can decompose an abstract argumentation framework AF into its strongly connected components. More precisely, an abstract argumentation framework AF′=(A′,R′) is a strongly connected component (SCC) of AF, if AF′⊑AF s.t. there is a directed path between any pair a,b∈A′ in AF′ and there is no larger AF″ with that property. Let SCC(AF) be the set of SCCs of AF.

The following result shows that initial sets are always completely contained in a single SCC.

If S is an initial set let SCC(S) denote its SCC as in the above proposition. Initial sets can actually be characterised by their SCC as follows.

In other words, a set S is an initial set iff it is an initial set of a single SCC and it is not attacked by arguments outside of the SCC.

We close this investigation on the relationship of initial sets with SCCs by making some straightforward observations regarding the types of initial sets.

In particular, the final observation in the previous proposition states that conflicts between initial sets are always within a single SCC.

4.Characterising admissibility-based semantics through initial sets

In [38,40] it has been shown that any admissible set (and in particular every complete and preferred extension) can be constructed by (1) selecting a set of non-conflicting initial sets, (2) adding further defended arguments, and (3) iterating this procedure taking so-called “J-acceptable” sets into account. In particular, the described mechanism involves iterative application of the characteristic function [19], computation of the grounded extension, and said notion of J-acceptability to provide those characterisations (and some further concepts). In this section, we provide a (arguably) more elegant formalisation of these ideas that allows us to derive characterisations of further semantics as well as some impossibility results. Results that are (partly) due to works [38–40] are annotated as such, all remaining results are new.

Our characterisations rely on the notion of the reduct [8].

As a single initial set S solves an atomic conflict in an abstract argumentation framework AF, “committing” to it by moving to AFS may reveal further conflicts and thus new initial sets. We can make the following observations on this aspect.

The above observations give an impression on how initial sets behave under reducts. So unattacked initial sets are always retained (item 1), conflicting initial sets are always removed (item 2), and non-conflicting initial sets are “essentially” retained (item 3). More precisely, while it may not be guaranteed that non-conflicting initial sets are still initial sets in the reduct, their arguments are still potentially acceptable, as the following example shows.

Fig. 2.

AF1 from Example 5.

The following results show that by an iterative selection of initial sets on the corresponding reducts, we can re-construct every admissible set. These observations have been hinted at in [38–40], but no formal proof had been provided. We make up for that now.

By recursively applying the above theorem, we obtain the following corollary.

Note that a decomposition S=S1∪⋯∪Sn of an admissible set S from Corollary 1 is not necessarily uniquely determined. In the previous example, S1 could also have been constructed by selecting, e. g., {f} first.

Fig. 3.

Reducts obtained from AF0 for the construction of S1={b,e,f,h,i}.

Let us now discuss the wider significance of Theorem 1 and Corollary 1. For that, recall the standard approach to compute and justify the (uniquely determined) grounded extension of an argumentation framework AF=(A,R) [19], cf. also the discussion in [38]. Basically, the grounded extension E of AF can be computed by selecting any non-attacked argument a∈A, add it to E, remove a and all arguments attacked by a from AF (so move from AF to AF{a}), and continue the process until no further unattacked argument can be found. Observe the similarity of this procedure to the procedure indicated by Theorem 1: in order to construct any admissible set S of AF, first select any initial set S′ of AF, add it to S (which is initially empty), remove S′ and all arguments attacked by S′ from AF, and continue the process. Therefore, initial sets allow us to serialise the construction of any admissible set into smaller steps, each of these steps solving a single conflict in the framework under consideration. Depending on how initial sets are selected at each step and how we end the process, we can also recover different semantics. Let us now formalise these ideas. For that, we first need two functions that define the selection mechanism of initial sets and the termination criterion.

We will apply a selection function α in the form α(IS↚(AF),IS↮(AF),IS↔(AF)) (for some AF), so α selects a subset of the initial sets as eligible to be selected in the construction process. We explicitly differentiate the different types of initial sets as parameters here as a technical convenience.

A termination function β is used to indicate when a construction of an admissible set is finished (this will be the case if β(AF,S)=1).

We will now define a transition system on states that makes use of a selection and a termination function to constrain the construction of admissible sets. For some selection function α, consider the following transition rule:

Given concrete instances of α and β, let Eα,β(AF) be the set of all S with (AF,∅)⇝α,β(AF′,S) (for some AF′).

A direct consequence of Corollary 1 is the following.

In other words, any admissible set can be constructed by not constraining the selection of initial sets at all (αadm) and accepting every reachable state (βadm). We can also characterise most of the admissibility-based semantics from Section 2 through serialisation using specific selection and termination functions, as the following results show.

The following observation has been hinted at in [40], but not formally proven. Using the notions of selection and termination functions, we can make the construction principle of complete extensions explicit.

Note that βco only accepts those states, which cannot be extended by already defended arguments (which are those appearing in IS↚(AF)). The above theorem also allows us to characterise complete extensions in a similar manner as admissible sets in Theorem 1.

Grounded semantics has the same termination criterion as complete semantics, but constrains the selection of initial sets to those in IS↚(AF).

Note that αgr and βco formalise the algorithm to compute the grounded extension sketched before. Therefore, the non-deterministic algorithm realised by the transition rule (1) is a generalisation of this algorithm. Similarly as Corollary 2 we obtain the following characterisation of grounded semantics in terms of the reduct.

For stable semantics, we do not need to constrain the selection of initial sets but only ensure that all arguments are either included in or attacked by the constructed extension.

As before, we obtain the following characterisation of stable semantics in terms of the reduct.

For preferred semantics, we simply have to apply transitions exhaustively. Note that this result strengthens Proposition 3 from [40].

Our final positive result is about strong admissibility, which follows quite easily from the construction of the grounded extension.

A related result to the above observation is given by Baumann et. al in [9] (Definition 7 and Proposition 2). There, a strongly admissible extension E is characterised through the existence of pairwise disjoint sets A1,…,An such that E=A1∪…An, A1 is a set of unattacked arguments in AF and A1∪⋯∪Aj defends Aj+1 for all 1⩽j⩽n−1. Our construction above also implies the existence of these sets A1,…,An with the same properties, but with the additional feature that all Ai, i=1,…,n are singleton sets (since unattacked initial sets are always singleton sets).

Missing from our results so far are the ideal and semi-stable semantics. Both of them cannot be serialised.

The proof of the above theorem is given by the following counterexample.

Fig. 4.

The argumentation frameworks AF2 (top) and AF3 (bottom) from Example 7.

The above behaviour of ideal semantics is insofar surprising since the concept of unchallenged initial sets is closely related to the general idea of the ideal extension. Recall that the initial extension is the maximal admissible set contained in each preferred extension. This basically means that the arguments in the ideal extension are compatible with each admissible set and no admissible set attacks any argument in the ideal extension. On the other hand, an unchallenged initial set is likewise an undisputed admissible set, as there is no other initial set that attacks it. However, as the above example shows, unchallenged initial sets are not sufficient to characterise the ideal extension. We will discuss the relationship between unchallenged initial sets and the ideal extension a bit more below and in Section 5.

Likewise negative, but for somewhat different reasons, is the following result about semi-stable semantics.

The reason that semi-stable semantics is not serialisable is that it needs some form of “global” view on candidate extensions to judge whether a set of arguments is indeed a semi-stable extension. We illustrate this in the next example (which also serves as the proof of Theorem 9).

Fig. 5.

The argumentation frameworks AF4 (top), AF5 (middle), and AF6 (bottom) from Example 8.

The same argument from above can also be used to show that eager semantics is not serialisable. The eager extension is the maximal (wrt. set inclusion) admissible set contained in every semi-stable extension, see e. g. [5]. In Example 8, the eager extension of AF5 is {b} while it is ∅ for AF4 and AF6. No pair (α,β) can be defined to distinguish these cases as well.

The results of this section show that many admissibility-based semantics can be characterised through the notion of initial sets and a simple non-deterministic algorithm based on selecting initial sets at each step. This brings a new perspective on the rationality of admissibility-based semantics, as their basic construction principles are made explicit via an operational mechanism. This is similar in spirit to the purpose of discussion games [12] which model acceptability problems of individual arguments as an operational mechanism as well (here a dialogue between a proponent and an opponent). However, here we focused on the construction of whole extensions and not on acceptability problems of individual arguments.

The notion of serialisability also allows to define completely new semantics by defining only a selection and a termination function. For example, a straightforward idea for that would be the selection function α0 defined via

Consider the following examples showing the difference between the above semantics and ideal semantics.

Fig. 6.

The argumentation framework AF7 from Example 10.

For future work, we intend to investigate the above and further possibilities for serialisable semantics in more detail.

5.Computational complexity

In order to round up our investigation of initial sets, we now analyse them wrt. computational complexity. We assume familiarity with basic concepts of computational complexity and basic complexity classes such as P, NP, coNP, see [30] for an introduction. We also require knowledge of the “non-standard” classes DP (and its complement coDP), PNP, and P∥NP. The class DP is the class of decision problems that are a conjunction of a problem in NP and a problem in coNP, i. e., in language notation DP={L1∩L2∣L1∈NP,L2∈coNP}. The class PNP is the class of decision problems that can be solved by a deterministic polynomial-time algorithm that can make polynomially many adaptive queries33 to an NP-oracle. The class P∥NP [24] is the class of decision problems that can be solved by a deterministic polynomial-time algorithm that can make polynomially many non-adaptive queries to an NP-oracle. Note that P∥NP is sometimes denoted by Θ2P and is equal to PNP[log], i. e., the class of decision problems solvable by deterministic polynomial-time algorithm that can make logarithmically many adaptive NP-oracle calls [30]. Observe also that DP⊆P∥NP and coDP⊆P∥NP as well as P∥NP⊆PNP.

We consider the following computational tasks for σ∈{IS,IS↚,IS↮,IS↔}, cf. [22]:

Table 1 summarises our results on the complexity of the above tasks, all proofs can be found in the appendix.

The results for IS mirror the results on admissible sets [22], with a few exceptions. While the problem of deciding whether a set S is admissible can be solved in logarithmic space with polynomial time [22], we only showed that the problem of deciding whether a set S is an initial set can be solved in polynomial time. It is unlikely (though a formal proof is missing at the moment) that we can strengthen these results in the same way as for admissible sets, since the minimality condition of an initial set suggest that subsets (of linear size) have to be constructed in an algorithm. Moreover, while the problems Exists and Skept are trivial for admissible sets [22] (since the empty set is always admissible), they are intractable for initial sets. The problem UniqueIS is DP-complete (it is coNP-complete for admissible sets) since existence of initial sets is not guaranteed.

We get some different complexity characterisations for the different types of initial sets. All tasks for unattacked initial sets are tractable, as only unattacked arguments have to be considered. All tasks become harder (under standard complexity-theoretic assumptions) when only unchallenged initial sets are considered. In particular, Verσ is coNP-complete as it has to be verified that there is no other initial set attacking the set that is to be verified. Moreover, Theorem 10 already showed that there is some conceptual relation between unchallenged initial sets and the ideal extension. This is strengthened by our observation of the computational complexity of the other tasks pertaining to unchallenged initial sets, as all non-trivial tasks on ideal semantics are P∥NP-complete (under randomised reductions) [21]. We showed P∥NP-completeness (under polynomial reductions) for most of those tasks as well, with the exception being the problem UniqueIS↮, where we only showed DP-hardness and a P∥NP-hardness proof remains an open problem.

The complexity of the tasks for challenged initial sets are similar as in the general case, with two exceptions. Verification of challenged initial sets is intractable as another initial set has to found that attacks the set under consideration. Moreover, UniqueIS↔ has the trivial answer NO for all instances as the existence of one challenged initial set S1 implies the existence of another challenged initial set S2 that attacks (and is attacked by) S1.

6.Discussion

In this paper, we revisited the notion of initial sets, i. e., non-empty minimal admissible sets. We investigated their general properties and used them as basic building blocks to construct any admissible set. We have characterised many admissibility-based semantics via this approach and concluded our analysis with some notes on computational complexity.

Initial sets allow us to concisely explain why a certain argument can be accepted (e. g., whether it is contained in a preferred extension). We can deconstruct an extension via the characterisation of Corollary 1, justify the inclusion of initial sets along this characterisation – e. g., by pointing to the conflicts that had to be solved –, and arrive step by step at the argument in question.

A recent paper that addresses a similar topic as we do is [10]. There, Baumann and Ulbricht introduce explanation schemes as a way to explain the construction of extensions wrt. complete, admissible, and strongly admissible semantics. Let us consider the case of complete semantics. Given AF=(A,R), the construction follows basically three steps:44 (1) Determine the grounded extension E0 of AF, (2) select a conflict-free set E1 from the set of arguments appearing in some even-length cycle in the reduct AFE0, and (3) determine the grounded extension E2 of the reduct AFE0∪E1. If E=E0∪E1∪E2 defends E1 then E is a complete extension (and every complete extension can be decomposed in such a way). The overall construction is similar to our approach, in particular, it consists of a series of steps where we select a set of arguments and move to the reduct of the framework wrt. the arguments accumulated so far. However, our approach provides a more fine-grained way to construct extensions. In each step, we solve a single issue by selecting a single initial set. Step 2 of Baumann and Ulbricht’s approach possibly solves a series of different conflicts all at once. This may actually diffuse the goal to provide an explanation why a certain extension is constructed as it is, as a selection of a conflict-free set of arguments from all even cycles may not clearly show, which conflicts are actually resolved. Furthermore, we do not need to explicitly use the notion of grounded semantics (and the general possibility to include defended arguments) in our construction, as it arises naturally through selecting (unattacked) initial sets and moving to the reduct immediately.

As a by-product of our work, we introduced a new principle [37] for abstract argumentation semantics: serialisability. For future work, we aim at investigated relationships of this new principle to other existing principles listed in [37]. Another avenue for future work to investigate whether our characterisations of admissibility-based semantics can be exploited for algorithmic purposes [14]. It is clear, that there is no obvious advantage in terms of computational complexity by computing (for example) a preferred extension via our transition system as it involves the computation of initial sets at each step (which is an intractable problem as ExistsIS is already NP-complete). However, our characterisation of initial sets through strongly connected components (see Section 3) could be exploited to devise a parallel algorithm – see also [15] –, as initial sets can be calculated independently of each other in each strongly connected component.