You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Revisiting initial sets in abstract argumentation

Abstract

We revisit the notion of initial sets by Xu and Cayrol (In Proceedings of the 1st Chinese Conference on Logic and Argumentation (CLAR’16) 2016), i. e., non-empty minimal admissible sets in abstract argumentation frameworks. Initial sets are a simple concept for analysing conflicts in an abstract argumentation framework and to explain why certain arguments can be accepted. We contribute with new insights on the structure of initial sets and devise a simple non-deterministic construction principle for any admissible set, based on iterative selection of initial sets of the original framework and its induced reducts. In particular, we characterise many existing admissibility-based semantics via this construction principle, thus providing a constructive explanation on the structure of extensions. We also investigate certain problems related to initial sets with respect to their computational complexity.

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,3133,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 [3840] 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:

  • (1) We revisit initial sets and investigate further properties (Section 3)

  • (2) We provide a characterisation result of admissible sets and many admissibility-based semantics (Section 4)

  • (3) We analyse certain computational problems wrt. their complexity (Section 5)

Section 2 introduces preliminaries on abstract argumentation and Section 6 concludes this paper.

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 AA is a finite set of arguments and R is a relation RA×A [19]. Let AF denote the set of all abstract argumentation frameworks. For two arguments a,bA the relation aRb means that argument a attacks argument b. For AF=(A,R) and AF=(A,R) we write AFAF iff AA and R=R(A×A). For a set XA, we denote by AF|X=(X,R(X×X)) the projection of AF on X. For a set SA we define

S+={aAbS:bRa}S={aAbS:aRb}
If S is a singleton set, we omit brackets for readability, i. e., we write a (a+) instead of {a} ({a}+). For two sets S and S we write SRS iff S+S. We say that a set SA is conflict-free if for all a,bS it is not the case that aRb. A set S defends an argument bA if for all a with aRb there is cS with cRa. A conflict-free set S is called admissible if S defends all aS. Let adm(AF) denote the set of admissible sets of AF.

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

  • is a complete (co) extension iff for all aA, if E defends a then aE,

  • is a grounded (gr) extension iff E is complete and minimal,

  • is a stable (st) extension iff EE+=A,

  • is a preferred (pr) extension iff E is maximal.

  • is a semi-stable (sst) extension iff EE+ is maximal,

  • is an ideal (id) extension iff E is the maximal admissible set with EE for each preferred extension E.

  • is a strongly admissible (sa) extension iff E= or each aE is defended by some strongly admissible EE{a}.

All statements on minimality/maximality are meant to be with respect to set inclusion. For σ{co,gr,st,pr,sst,id,sa} let σ(AF) denote the set of σ-extensions of AF. We say a semantics σ is admissibility-based if σ(AF)adm(AF) for all AF. Note that all semantics above are admissibility-based but there are also others such as CF2 semantics [7] and weak admissibility-based semantics [8].

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 aS 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.

Example 1.

Consider the argumentation framework AF0 depicted in Fig. 1. There are eight admissible sets containing the argument e:

S1={b,e,f,h,i}S2={b,e,f,i}S3={b,e,h,i}S4={e,f,h,i}S5={b,e,i}S6={f,e,i}S7={h,e,i}S8={e,i}
S1 is also a preferred extension. However, it is also clear that arguments b, f, and h are not integral for defending e and the set S8 presents a concise description of what is needed in order to deem e as acceptable (wrt. admissibility), namely only e and i.

In the following, we take relevance into account by considering minimal (wrt. set inclusion) admissible sets. Of course, a notion of minimal admissible set without further constraints is not a useful concept as the empty set is always admissible and constitutes the unique minimal admissible set. Non-empty minimal admissible sets have been coined initial sets by Xu and Cayrol in [38].

Fig. 1.

AF0 from example 1.

AF0 from example 1.
Definition 1

Definition 1([38]).

For AF=(A,R), a set SA with S is called an initial set if S is admissible and there is no admissible SS with S. Let IS(AF) denote the set of initial sets of AF.

Example 2.

We continue Example 1. There are four initial sets of AF0: {f}, {h}, {d,j}, and {e,i}.

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.

Definition 2.

For AF=(A,R) and SIS(AF), we say that

  • (1) S is unattacked iff S=,

  • (2) S is unchallenged iff S and there is no SIS(AF) with SRS,

  • (3) S is challenged iff there is SIS(AF) with SRS.

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 SIS(AF) let

conflicts(S,AF)={SIS(AF)SRS}
denote the set of conflicting initial sets of S, which is always empty in the case of unattacked and unchallenged initial sets. Note that SRS implies SRS for any S,SIS(AF) as S is admissible and therefore defends itself.

Example 3.

We continue Example 2. Here we have

IS(AF)={{h}}IS(AF)={{f}}IS(AF)={{d,j},{e,i}}
and {d,j} and {e,i} are in conflict with each other, i. e., conflicts({d,j},AF)={{e,i}} and conflicts({e,i},AF)={{d,j}}.

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 [3840].

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 AFAF s.t. there is a directed path between any pair a,bA in AF and there is no larger AF with that property. Let SCC(AF) be the set of SCCs of AF.

Example 4.

Consider again the argumentation framework AF0 from Fig. 1. AF0 decomposes as follows into SCCs: SCC(AF0)={AF0|{d,e,i,j},AF0|{c},AF0|{h},AF0|{g,f,a},AF0|{b}}

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

Proposition 1.

If S is an initial set of AF then there is AF=(A,R)SCC(AF) s.t. SA.

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.

Proposition 2.

S is an initial set of AF if and only if S is an initial set of SCC(S)=(A,R) and SA.

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.

Proposition 3.

Let SIS(AF) and SCC(S)=(A,R).

  • (1) If S is unattacked then |A|=1.

  • (2) If S is challenged or unchallenged then |A|>1.

  • (3) If S is challenged and Sconflicts(S,AF) then SCC(S)=SCC(S).

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 [3840] are annotated as such, all remaining results are new.

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

Definition 3.

For AF=(A,R) and SA, the S-reduct AFS of AF is defined via AFS=AF|A(SS+).

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.

Proposition 4.

Let AF=(A,R) be an abstract argumentation framework and S,SIS(AF) with SS.

  • (1) If SIS(AF) then SIS(AFS)

  • (2) If Sconflicts(S,AF) then SIS(AFS)

  • (3) If Sconflicts(S,AF) then SIS(AFS)

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.

Example 5.

Consider the argumentation framework AF1 depicted in Fig. 2. We have

IS(AF1)={{a,c},{b,d},{e}}
and {b,d} and {e} are conflicting (there are no further conflicts). Now we have
IS(AF1{e})={{c}}
So the initial set {a,c} of AF1 is not retained in AF1{e}, despite {a,c} and {e} not being in conflict. However, we have that {c}{a,c} is an initial set of AF1{e}. Furthermore, {a} (the “remaining” argument of the initial set {a,c}) is actually the unique initial set of (AF1{e}){c}.

Fig. 2.

AF1 from Example 5.

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 [3840], but no formal proof had been provided. We make up for that now.

Theorem 1.

Let AF=(A,R) be an abstract argumentation framework and SA. S is admissible if and only if either

  • S= or

  • S=S1S2, S1IS(AF) and S2 is admissible in AFS1.

Proof.

Let S be an admissible set and S. By definition of initial sets, there is S1IS(AF) with S1S. It remains to show that S2=SS1 is admissible in AFS1. Let aS2 and let b1,,bnA be the attackers of a in AF. Since S is admissible, there are arguments c1,,cnS so that ci attacks bi, i=1,,n (possibly some of the ci are identical). Without loss of generality, assume c1,,ckS1 for some kn. Then b1,,bk are not present in AFS1, thus a must only be defended against bk+1,,bn in AFS1. However, since S2=SS1 we have that ck+1,,cnS2, showing that a is defended by S2 in AFS1 and, thus, S2 is admissible in AFS1.

For the other direction,1 if S= then S is also admissible. Assume S=S1S2, S1IS(AF) and S2 is an admissible set of AFS1. We have to show that S is admissible. Let aS and let b1,,bn be the attackers of a in AF. If aS1 then there are c1,,cnS1S such that ci attacks bi since S1 is admissible. If aS2, assume for the sake of contradiction that there is an attacker b of a such that there is no bS that attacks c in AF. It follows that b is also in AFS1 and a is undefended by S2 in AFS1. This contradicts the assumption that S2 is admissible in AFS1. □

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

Corollary 1.

Every non-empty admissible set S can be written as S=S1Sn with pairwise disjoint Si, i=1,,n, S1 is an initial set of AF and every Si, i=2,,n is an initial set of AFS1Si1. Furthermore, only non-empty admissible sets S can be written in such a fashion.

Example 6.

Consider again the argumentation framework AF0 from Fig. 1 and recall that

S1={b,e,f,h,i}
is an admissible set of AF0 (and actually a preferred extension). S1 can be written as
S1={h}{f}{e,i}{b}
where
  • {h} is an initial set of AF0 (Fig. 1),

  • {f} is an initial set of AF0{h} (Fig. 3(a)),

  • {e,i} is an initial set of AF0{h,f} (Fig. 3(b)), and

  • {b} is an initial set of AF0{e,i,h,f} (Fig. 3(c)).

Note that a decomposition S=S1Sn 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}.

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 aA, 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.

Definition 4.

A state T is a tuple T=(AF,S) with AFAF and SA.

Definition 5.

A selection function α is any function α:2A×2A×2A2A with α(X,Y,Z)XYZ for all X,Y,ZA.

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.

Definition 6.

A termination function β is any function β:AF×2A{0,1}.

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:

(1)(AF,S)Sα(IS(AF),IS(AF),IS(AF))(AFS,SS)
If (AF,S) can be reached from (AF,S) via a finite number of steps (this includes no steps at all) with the above rule we write (AF,S)α(AF,S). If, in addition, the state (AF,S) also satisfies the termination criterion of β, i. e., β(AF,S)=1, then we write (AF,S)α,β(AF,S).

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

Definition 7.

A semantics σ is serialisable with a selection function α and a termination function β if σ(AF)=Eα,β(AF) for all AF.

A direct consequence of Corollary 1 is the following.

Theorem 2.

Admissible semantics2 is serialisable with

αadm(X,Y,Z)=XYZβadm(AF,S)=1

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.

Theorem 3.

Complete semantics is serialisable with αadm and

βco(AF,S)=1if IS(AF)=0otherwise

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.

Corollary 2.

Let AF=(A,R) be an abstract argumentation framework and SA. S is complete if and only if either

  • S= and IS(AF)= or

  • S=S1S2, S1IS(AF) and S2 is complete in AFS1.

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

Theorem 4.

Grounded semantics is serialisable with

αgr(X,Y,Z)=X
and βco.

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.

Corollary 3.

Let AF=(A,R) be an abstract argumentation framework and SA. S is grounded if and only if either

  • S= and IS(AF)= or

  • S=S1S2, S1IS(AF) and S2 is grounded in AFS1.

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.

Theorem 5.

Stable semantics is serialisable with αadm and

βst(AF,S)=1if AF=(,)0otherwise

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

Corollary 4.

Let AF=(A,R) be an abstract argumentation framework and SA. S is stable if and only if either

  • S= and A= or

  • S=S1S2, S1IS(AF) and S2 is stable in AFS1.

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

Theorem 6.

Preferred semantics is serialisable with αadm and

βpr(AF,S)=1if IS(AF)=0otherwise

Corollary 5.

Let AF=(A,R) be an abstract argumentation framework and SA. S is preferred if and only if either

  • S= and IS(AF)= or

  • S=S1S2, S1IS(AF) and S2 is preferred in AFS1.

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

Theorem 7.

Strong admissibility semantics is serialisable with αgr and βadm.

Corollary 6.

Let AF=(A,R) be an abstract argumentation framework and SA. S is strongly admissible if and only if either

  • S= or

  • S=S1S2, S1IS(AF) and S2 is strongly admissible in AFS1.

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=A1An, A1 is a set of unattacked arguments in AF and A1Aj defends Aj+1 for all 1jn1. 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.

Theorem 8.

Ideal semantics is not serialisable.

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 argumentation frameworks AF2 (top) and AF3 (bottom) from Example 7.
Example 7.

Consider the two argumentation frameworks AF2 and AF3 in Fig. 4. We have

id(AF2)={b}id(AF3)={b,e}
and
IS(AF2)=IS(AF3)=IS(AF2)=IS(AF3)={{b},{e}}IS(AF2)=IS(AF3)=
So no selection function α can distinguish these frameworks and should return either
  • (1) α(,{{b},{e}},)= or

  • (2) α(,{{b},{e}},)={{b},{e}}.

Note also that α cannot return just one of the two initial sets as they cannot be distinguished. In case 1, the ideal extensions of both AF2 and AF3 cannot be constructed. So assume case 2 and select {e} in the first transition. Observe that AF2{e}=AF3{e}, so further constructions will be identical. Since the ideal extensions of AF2 and AF3 differ and no β can distinguish these cases, ideal semantics is not serialisable.

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.

Theorem 9.

Semi-stable semantics is not serialisable.

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 argumentation frameworks AF4 (top), AF5 (middle), and AF6 (bottom) from Example 8.
Example 8.

Consider the three argumentation frameworks AF4, AF5, AF6 in Fig. 5. Observe that

sst(AF4)={{a,c},{b}}sst(AF5)={{b}}sst(AF6)={{a},{b}}
However,
IS(AF4)=IS(AF5)=IS(AF6)=IS(AF4)=IS(AF5)=IS(AF6)=IS(AF4)=IS(AF5)=IS(AF6)={{a},{b}}
First, no selection function α can distinguish these frameworks (as it only operates on the sets IS(·), IS(·), and IS(·)) and would either return
  • (1) α(,,{{a},{b}})=,

  • (2) α(,,{{a},{b}})={{a}},

  • (3) α(,,{{a},{b}})={{b}}, or

  • (4) α(,,{{a},{b}})={{a},{b}}.

In cases 1–3, not all semi-stable extensions can be constructed for, e. g., AF4. For case 4 and AF5, a valid transition would then produce the state T1=(({c},{(c,c)}),{a}) from which no further transition is possible. A β function for semi-stable semantics should now determine that T1 is not a terminating state (since {a} is not a semi-stable extension of AF5). However, the same state T1 can also be reached for AF6, but here {a} is a semi-stable extension. Since β cannot distinguish these two scenarios at T1, there is no such β.

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

α0(X,Y,Z)=XY
and the termination function β0 defined via
β0(AF,S)=1if IS(AF)IS(AF)=0otherwise
which amounts to exhaustively adding unattacked and unchallenged initial sets. This yields a semantics that is more skeptical than the preferred semantics but less skeptical than the ideal semantics as the following result shows.

Theorem 10.

For every E with (AF,)α0,β0(AF,E)

  • (1) EE for some preferred extension E and

  • (2) EidE for the ideal extension Eid.

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

Example 9.

Consider again AF2 from Example 7 and depicted in Fig. 4. There are two extensions E1 and E2 wrt. to the serialisable semantics defined by α0 and β0:

E1={b}E2={b,e}
where the extension E2 can be constructed by first selecting the initial set {e} (which is unchallenged in AF2) and then {b}.

Example 10.

Consider AF7 depicted in Fig. 6. There are four preferred extensions E1, E2, E3, and E4 in AF7 defined via

E1={a,e}E2={a,d,f}E3={b,e}E4={b,d,f}
and the ideal extension Eid is empty:
Eid=
However, there is one extension E5 wrt. to the serialisable semantics defined by α0 and β0:
E5={d,f}
The reason for that is that both {d} and {f} are unchallenged initial sets in AF7 (and once one is selected the other becomes an unattacked initial set and can be selected as well).

Fig. 6.

The argumentation framework AF7 from Example 10.

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 PNP. 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={L1L2L1NP,L2coNP}. 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 queries3 to an NP-oracle. The class PNP [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 PNP 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 DPPNP and coDPPNP as well as PNPPNP.

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

  • Verσ Given AF=(A,R) and SA,

    decide whether Sσ(AF).

  • Existsσ Given AF=(A,R),

    decide whether σ(AF).

  • Uniqueσ Given AF=(A,R),

    decide whether |σ(AF)|=1.

  • Credσ Given AF=(A,R) and aA,

    decide whether there is Sσ(AF) with aS.

  • Skeptσ Given AF=(A,R) and aA,

    decide whether for all Sσ(AF), aS.

Note that we do not consider the problems Existsσ¬ [22] (which asks whether there is a non-empty (initial) set) as these are equivalent to Existsσ due to the non-emptiness of all types of initial sets.

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

Table 1

Complexity of computational tasks related to initial sets. An attached “-h” refers to hardness for the class and an attached “-c” refers to completeness for the class. All hardness results are wrt. polynomial reductions

σISISISIS
Verσin Pin PcoNP-cNP-c
ExistsσNP-cin PPNP-cNP-c
UniqueσDP-cin Pin PNP, DP-htrivial
CredσNP-cin PPNP-cNP-c
SkeptσcoNP-cin PPNP-ccoNP-c

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 PNP-complete (under randomised reductions) [21]. We showed PNP-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 PNP-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:4 (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 AFE0E1. If E=E0E1E2 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.

Notes

1 Note that this direction can also be shown by using the fact that admissible “semantics” is fully decomposable [4], but we explicitly prove it for matters of simplicity.

2 Although admissible sets are usually not regarded as a semantics, we can treat the function adm(·) as such.

3 A query is adaptive if it may depend on a previous query; queries are non-adaptive if they can be posed in any order or in parallel.

4 Although an abbreviated two-step procedure is also discussed.

5 I am very grateful to an anonymous reviewer for pointing out that characterisation.

6 Note that this algorithm is inspired by an algorithm for determining the ideal extension, cf. [20,21].

Acknowledgements

I am thankful to the anonymous reviewers who commented on a previous version of this paper, in particular by giving valuable hints that allowed me to strengthen the results on computational complexity.

Appendices

Appendix

AppendixProofs of technical results

Proposition 1.

If S is an initial set of AF then there is AF=(A,R)SCC(AF) s.t. SA.

Proof.

If S is a singleton the claim is trivially true. So let S be an initial set of AF with |S|>1. Assume there are two different AF=(A,R)SCC(AF) and AF=(A,R)SCC(AF) with SA and SA and also S=(SA)(SA) (the following proof generalises easily if S is spanned across more than two SCCs). If (SA)(SA)+ then SA is admissible, contradicting the fact that S is an initial set. So there is at least one a(SA) with a(SA)+ since the complete set S is admissible. With the same reasoning there must be a b(SA) with b(SA)+. Then there is a closed circuit: from a there is an edge to an element c in (SA). Since (SA) is part of an SCC, there is a path from c to any other argument in (SA), in particular, also to an attacker d of b. From d we can go to b and then to an element in (SA). Again through the SCC of (SA) we can reach a. This contradicts the assumption, so S is contained in a single SCC. □

Proposition 2.

S is an initial set of AF if and only if S is an initial set of SCC(S)=(A,R) and SA.

Proof.

Let S be an initial set of AF. As S is admissible, all arguments aE are attacked by some bE. Proposition 1 already established that SA. Since each aS attacks and is attacked by S, SA as well. It follows that S is an initial set of SCC(S) as well as SSA and verifying whether a set is initial only needs to consider the relationships of those arguments. This also proves the other direction. □

Proposition 3.

Let SIS(AF) and SCC(S)=(A,R).

  • (1) If S is unattacked then |A|=1.

  • (2) If S is challenged or unchallenged then |A|>1.

  • (3) If S is challenged and Sconflicts(S,AF) then SCC(S)=SCC(S).

Proof.

Let SIS(AF) and SCC(S)=(A,R).

  • (1) Since S={a} is not attacked there is no other argument b with a path to a. It follows directly |A|=1.

  • (2) As S is admissible and there is at least one b that attacks S, one argument in S must attack b. It follows S{b}SCC(S) and therefore |A|>1.

  • (3) Let Sconflicts(S,AF). As SRS and SRS as well as both S and S are completely in one SCC, it follows SCC(S)=SCC(S).

 □

Proposition 4.

Let AF=(A,R) be an abstract argumentation framework and S,SIS(AF) with SS.

  • (1) If SIS(AF) then SIS(AFS)

  • (2) If Sconflicts(S,AF) then SIS(AFS)

  • (3) If Sconflicts(S,AF) then SIS(AFS)

Proof.

Let AF=(A,R) be an abstract argumentation framework and S,SIS(AF) with SS

  • (1) Let SIS(AF), so S={a}. As a is not attacked in AF, it is also not attacked by S and it follows aA for AFS=(A,R). It also follows that a is not attacked in AFS and therefore {a}IS(AFS).

  • (2) If Sconflicts(S,AF) then there is aS and bS with aRb. It follows bA for AFS=(A,R). So SIS(AFS).

  • (3) As Sconflicts(S,AF) it follows that SS is conflict-free and therefore SA for AFS=(A,R). Furthermore, since S is admissible in AF, SA remains admissible in AFS. By definition, it follows that there is an initial set S of AFS with SS, proving the claim.

 □

Corollary 1.

Every non-empty admissible set S can be written as S=S1Sn with pairwise disjoint Si, i=1,,n, S1 is an initial set of AF and every Si, i=2,,n is an initial set of AFS1Si1. Furthermore, only non-empty admissible sets S can be written in such a fashion.

Proof.

This follows by iterative application of Theorem 1. □

Theorem 2.

Admissible semantics is serialisable with

αadm(X,Y,Z)=XYZβadm(AF,S)=1

Proof.

Follows from Corollary 1. □

Theorem 3.

Complete semantics is serialisable with αadm and

βco(AF,S)=1if IS(AF)=0otherwise

Proof.

We have to show that E is a complete extension if and only if (AF,)αadm,βco(AF,E) for some AF. Let AF=(A,R).

  • “⇒”:

    Let E be a complete extension. By Corollary 1 and the fact that αadm does not constrain the selection of initial sets, it is clear that there is AF with (AF,)α(AF,E). It remains to show that βco(AF,E)=1. As E is complete, there is no argument aA s.t. all attackers of a (in AF) are contained in E. This is equivalent to stating that there is no unattacked argument a in AFE and therefore IS(AFE)=. As AFE=AF the claim follows.

  • “⇐”:

    Let (AF,)αadm,βco(AF,E) for some AF=(A,R). By Corollary 1, E is admissible. Since IS(AF)= there is no argument aA that is defended by E. Therefore, E is complete.

 □

Corollary 2.

Let AF=(A,R) be an abstract argumentation framework and SA. S is complete if and only if either

  • S= and IS(AF)= or

  • S=S1S2, S1IS(AF) and S2 is complete in AFS1.

Proof.

If IS(AF)= then S= is obviously a complete extension. Let S be any non-empty complete extension. Due to Theorem 1 there are sets S1, S2 with S=S1S2, S1IS(AF) and S2 is admissible in AFS1. Assume S2 is not complete in AFS1. Then there is an argument a in AFS1 that is defended by S2 but aS2. But then aS1 and aS1+ (otherwise it would not be in AFS1) and S defends a as well in AF. This contradicts the assumption that S is complete. So S2 is complete in AFS1.

For the other direction, let S be any set with S=S1S2, S1IS(AF) and S2 is complete in AFS1. Assume that S is not complete in AF. Then there is an argument a that is defended by S but aS. Since a is not contained in S1 nor attacked by it, it follows that a is contained in AFS1. Let T be the attackers of a in AF. Since S attacks all arguments in T let T1T be those arguments in T attacked by some bS1 and T2=TT1. It follows that no argument of T1 is contained in AFS1 but all arguments in T2 are contained in AFS1 and are necessarily attacked by S2. It follows that a is defended by S2 in AFS1, contradicting the fact that S2 is complete in AFS1. It follows that S is indeed complete. □

Theorem 4.

Grounded semantics is serialisable with

αgr(X,Y,Z)=X
and βco.

Proof.

Let Egr be the grounded extension of AF=(A,R) and let Ek be such that

(AF,)αgr(AF1,E1)αgrαgr(AFk,Ek)
so that βco(AFk,Ek)=1. We first show EiEgr, for i=1,,k, by induction on i.
  • i=1: By definition of αgr we have E1={a} for some unattacked argument aA. Since Egr is complete, it contains all unattacked arguments of A, therefore E1Egr.

  • i>1: By definition of αgr we have Ei={a}Ei1 for some unattacked argument aA in AFi. Since a is unattacked in AFi, all attackers of a in AF must be attacked by Ei1. By assumption, Ei1Egr and a is defended by Egr as well. Since Egr is complete it follows EiEgr.

Since Theorem 3 already established that Ek is complete and Egr is the smallest complete extension, from EkEgr is follows Ek=Egr and therefore the claim. □

Corollary 3.

Let AF=(A,R) be an abstract argumentation framework and SA. S is grounded if and only if either

  • S= and IS(AF)= or

  • S=S1S2, S1IS(AF) and S2 is grounded in AFS1.

Proof.

If IS(AF)= then S= is obviously the grounded extension. Assume S is the non-empty grounded extension of AF. Then there must be an argument aS that is not attacked in AF. It follows {a}IS(AF). Let S be the grounded extension of AF{a}. Then S{a} is complete in AF:

  • (1) S{a} is admissible due to Theorem 1.

  • (2) a is defended by S{a} as it is not attacked.

  • (3) every bS is defended by S{a} as all attackers of b are either attacked by a (and therefore not in the reduct AF{a}) or some argument in S (since S is grounded in AF{a}).

Assume there is a proper subset SS{a} that is complete. Since a is not attacked, aS. It can easily be seen that SS would be complete in AF{a} and SSS, contradicting the fact that S is the grounded extension of AF{a}. It follows that S=S{a}.

The other direction is analogous. □

Theorem 5.

Stable semantics is serialisable with αadm and

βst(AF,S)=1if AF=(,)0otherwise

Proof.

Let S be a stable extension. By Theorem 2 it is clear (since any stable extension is admissible) that there is AF with (AF,)αadm(AF,S). As SS+=A it follows AF=(,) and therefore βAF,S=1. Furthermore, for any S with (AF,)αadm,βst((,),S) it follows that S is admissible and there is no aA with aS+ or aS. This is equivalent to stating that S is stable. □

Corollary 4.

Let AF=(A,R) be an abstract argumentation framework and SA. S is stable if and only if either

  • S= and A= or

  • S=S1S2, S1IS(AF) and S2 is stable in AFS1.

Proof.

If A= then S= is obviously the (only) stable extension. Assume S is a non-empty stable extension of AF. Due to Theorem 1 there are sets S1, S2 with S=S1S2, S1IS(AF) and S2 is admissible in AFS1. Assume S2 is not stable in AFS1=(A,R). Then there is aA that is not attacked by S2. Since aA, a is also not attacked by S1. It follows that S is not a stable extension, in contradiction to the assumption. It follows that S2 is stable in AFS1.

For the other direction, let S=S1S2, S1IS(AF) and S2 is stable in AFS1=(A,R). By Theorem 1, S is admissible. Assume S is not stable, then there is aA that is not attacked by S. It follows that aA, so a is also not attacked by S2 in AFS1, in contradiction to the assumption that S2 is stable in AFS1. It follows that S is stable in AF. □

Theorem 6.

Preferred semantics is serialisable with αadm and

βpr(AF,S)=1if IS(AF)=0otherwise

Proof.

Let S be preferred. Due to Theorem 2 it follows that there is AF with (AF,)αadm(AF,S). If IS(AF) then there is another admissible set S with (AF,S)αadm(AF,S) and SS, in contradiction to the assumption that S is preferred. It follows IS(AF)= and therefore (AF,)αadm,βpr(AF,S).

For the other direction, let (AF,)αadm,βpr(AF,S). By Theorem 2 it is clear that S is admissible. Assume S is not preferred, so there is admissible S with SS. Define S=SS. We show now that S is an admissible set of AF=AFS. First, since S is conflict-free so is S. Let now aS. As S is admissible we have a(S)+. Let a=X1X2 with disjoint sets X1 and X2 such that X1=aS+ and X2=aX1. As AF=AFS, those attackers of a in X1 are not present in AF anymore, so there is no need to defend against them. However, since S is admissible, X2(S)+ and it follows X2(S)+ (as arguments in X2 are not attacked by arguments in S). So S defends a and S is therefore admissible. As S is a (non-empty) admissible set of AF, it follows that IS(AF). This contradicts the assumption that (AF,)αadm,βpr(AF,S) and it follows that S is indeed a preferred extension. □

Corollary 5.

Let AF=(A,R) be an abstract argumentation framework and SA. S is preferred if and only if either

  • S= and IS(AF)= or

  • S=S1S2, S1IS(AF) and S2 is preferred in AFS1.

Proof.

If IS(AF)= then S= is obviously the only preferred extension, since it is the only admissible set. Assume S is a non-empty preferred extension of AF. Due to Theorem 1 there are sets S1, S2 with S=S1S2, S1IS(AF) and S2 is admissible in AFS1. Assume S2 is not preferred in AFS1. Then there is admissible S2 with S2S2. By Theorem 1, S1S2 is admissible in AF and S=S1S2S1S2, contradicting the fact that S is preferred. It follows that S2 is preferred in AFS1.

For the other direction, let S=S1S2, S1IS(AF) and S2 is preferred in AFS1. By Theorem 1, S is admissible. Assume S is not preferred, then there is admissible S with SS. Since S1S, SS1 must be completely contained in AFS1 (otherwise S would not be conflict free) and S2SS1. SS1 is also necessarily admissible in AFS1, contradicting the fact that S2 is preferred in AFS1. It follows that S is preferred. □

Theorem 7.

Strong admissibility semantics is serialisable with αgr and βadm.

Proof.

Let S be a strongly admissible set. We show (AF,)αgr(AF,S) (note that we do not have to consider βadm as this function always returns 1) by induction on the size of S.

  • (1) |S|=0: trivial as (AF,)α(AF,) for any α via zero steps.

  • (2) |S|=n: Let aS such that S=S{a} is strongly admissible (the existence of such a is guaranteed as a direct corollary of Theorem 5 in [13] and the definition of strong admissibility). By induction hypothesis (AF,)αgr(AF,S). As S is strongly admissible, it follows that a cannot be attacked in AF (otherwise a is not defended by (a subset of) S’). So we have {a}IS(AF) and (AF,)αgr(AF,S)αgr(AF,S).

For the other direction, let (AF,)αgr(AF,S). We show that S is strongly admissible by induction on the size of S.
  • (1) |S|=0: the empty set is by definition strongly admissible.

  • (2) |S|=n: Consider the final step in the construction of S, i. e., (AF,)αgr(AF,S)αgr(AF,S). As αgr returns only singleton sets, we have S=S{a} for some aA. As a is unattacked in AF, S defends a in AF. By induction hypothesis, S is strongly admissible, showing that S is strongly admissible.

 □

Corollary 6.

Let AF=(A,R) be an abstract argumentation framework and SA. S is strongly admissible if and only if either

  • S= or

  • S=S1S2, S1IS(AF) and S2 is strongly admissible in AFS1.

Proof.

Since is always strongly admissible, we only consider the second case. Assume S is a non-empty strongly admissible set. Since SEgr, where Egr is the grounded extension of AF, there is an unattacked aS and {a}IS(AF). Let S2=S{a} and bS2. Since S is strongly admissible in AF, there is SS{b} that is strongly admissible and defends b. If aS then S{a} is strongly admissible in AF{a} and defends b. If aS then S remains strongly admissible in AF{a} and defends b. In any case, it follows that S2 is strongly admissible in AF{a}.

The other direction is analogous. □

Theorem 10.

For every E with (AF,)α0,β0(AF,E)

  • (1) EE for some preferred extension E and

  • (2) EidE for the ideal extension Eid.

Proof.

  • (1) Note that α0(X,Y,Z)αadm(X,Y,Z) for all X, Y, Z. So if (AF,)α0(AF,E) then (AF,)αadm(AF,E). Furthermore, (AF,E)αadm,βpr(AF,E) eventually with a preferred extension E due to Theorem 6. This shows EE.

  • (2) Let Eid be the ideal extension of AF and let Eid=S1Sn with Si being an initial set of AFS1Si1 for all i=1,,n (this representation exists due to Corollary 1 and the fact that Eid is admissible).

    Let E with (AF,)α0,β0(AFE,E). Assume that EidE and let k{1,,n} be the smallest integer such that SkE. Let Sˆk=ESk. We show now that Sˆk is admissible in AFE=(A,R):

    • (a) SˆkA: For the sake of contradiction, assume there is aSˆk with aA. Due to Sˆk=ESk it follows that a is attacked by E. Then the admissible set E attacks Eid, contradicting the fact that Eid is the ideal extension.

    • (b) Sˆk is conflict-free: clear since SˆkEid.

    • (c) Sˆk defends all its elements (in AFE): recall that S1Sk is an admissible set in AF (due to Corollary 1) and that S1Sk1(SkSˆk)E. Let a be an attacker of Sˆk in AF and bS1Sk that attacks a. Then either bE (meaning that aA and Sˆk does not need to defend against a in AFE) or bSˆk (meaning that Sˆk defends against a in AFE).

    It follows that Sˆk is admissible in AFE. Then there must be an initial set SˆkSˆk. Assume Sˆk is challenged by another initial set T. Then TE would be an admissible set that attacks Eid. It follows Sˆk is unattacked or unchallenged in AFE. This contradicts the fact that (AF,)α0,β0(AFE,E). Therefore we have EidE.

 □

Lemma 1.

Let S be conflict-free and aS. Deciding whether there is an admissible set SS with aS can be decided in polynomial time.

Proof.

In polynomial time we can check first whether S is already admissible. If not, define S1 via

S1=FAF(S)S
Note that S1S (if S1=S then S would already have been admissible). Furthermore, all aSS1 are not defended by arguments in S and can therefore not be a member of any admissible set SS. It follows that, if there is an admissible set SS with aS then SS1. So if aS1 or (aS1 and S1 is admissible), we are finished. Otherwise define S2 via
S2=FAF(S1)S1
and continue as before. Note that moving from Si to Si+1 at least one argument is discarded (otherwise we have found an admissible set). So we have to compute at maximum S1,,S|S| and all computations are polynomial. □

Proposition 5.

VerIS is in P.

Proof.

In polynomial time we can check first whether the input S is admissible. Then, for each a,bS with ab we can test whether S{b} contains an admissible set including a (see Lemma 1). If this is the case for one pair a, b, S cannot be an initial set. If this is not the case for any a, b then S is an initial set. All checks are in polynomial time. □

Proposition 6.

ExistsIS is NP-complete.

Proof.

Equivalence of ExistsIS and Existsadm¬ follows from the fact that every non-empty admissible set contains an initial set [38]. Existsadm¬ is NP-complete [22]. □

Proposition 7.

UniqueIS is DP-complete.

Proof.

Let AF be the input argumentation framework. Note that UniqueIS can be solved by solving the two problems:

  • (1) decide whether AF has at least one initial set and

  • (2) decide whether AF has at most one initial set.

Problem 1 is ExistsIS and therefore NP-complete. The complement of problem 2 can be solved by non-deterministically guessing two different sets S1 and S2 and verifying that both are initial sets. Problem 2 is therefore in coNP and this shows DP-membership of UniqueIS.

For hardness, we provide a reduction from the problem Uniquest, i. e., the problem of deciding whether an argumentation framework has a unique stable extension, cf. [18,22]. For that, we directly use construction Tr4 from [23], which translates (with polynomial overhead) an argumentation framework AF into an argumentation framework Tr4(AF) such that st(AF)=adm(Tr4(AF)){}, cf. Lemma 5 and Theorem 4 in [23]. Since for every pair of stable extensions E1, E2 it holds E1E2 and E2E1, it follows that E1,E2adm(Tr4(AF)){}, E1E2 and E2E1, and therefore adm(Tr4(AF)){}=IS(Tr4(AF)). It follows st(AF)=IS(Tr4(AF)) and |st(AF)|=1 if and only if |IS(Tr4(AF))|=1 and therefore the claim. □

Proposition 8.

CredIS is NP-complete.

Proof.

For NP-membership consider the following algorithm. Upon input aA we guess a set SA with aS and verify in polynomial time that S is an initial set (see Proposition 5). It follows that a is credulously accepted wrt. initial sets. This shows NP-membership.

For NP-hardness we do a reduction from Credst, i. e., the problem of deciding whether an argument is credulously accepted wrt. stable semantics. We use the same reduction as in the proof of Proposition 7, namely the construction Tr4 from [23]. We already established in the proof of Proposition 7 that st(AF)=IS(Tr4(AF)). It follows that an argument a is credulously accepted wrt. stable semantics in AF if and only if it is credulously accepted wrt. initial sets in Tr4(AF). □

Proposition 9.

SkeptIS is coNP-complete.

Proof.

For coNP-membership consider the following algorithm, which solves the complement problem in NP. Upon input aA we guess a set SA with aS and verify in polynomial time that S is an initial set (see Proposition 5). It follows that a is not skeptically accepted wrt. initial sets. This shows coNP-membership for SkeptIS.

For coNP-hardness we do a reduction from Skeptst, i. e., the problem of deciding whether an argument is skeptically accepted wrt. stable semantics. We use the same reduction as in the proof of Proposition 7, namely the construction Tr4 from [23]. We already established in the proof of Proposition 7 that st(AF)=IS(Tr4(AF)). It follows that an argument a is skeptically accepted wrt. stable semantics in AF if and only if it is skeptically accepted wrt. initial sets in Tr4(AF). □

Proposition 10.

VerIS, ExistsIS, UniqueIS, CredIS, and SkeptIS are in P.

Proof.

Note that all these problems only have to make a simple check on the input:

  • VerIS: Verifying whether a single argument is unattacked is in P.

  • ExistsIS: Checking whether there is an unattacked argument in a given input framework AF is in P.

  • UniqueIS: Checking whether there is a single unattacked argument in a given input framework AF is in P.

  • CredIS: this is equivalent to VerIS with input AF and {a}.

  • SkeptIS: checking whether a is the only unattacked argument in AF is in P.

 □

Proposition 11.

VerIS is coNP-complete.

Proof.

For coNP-membership, we consider the complement problem of verifying that input S is not an unchallenged initial set in NP. We first check in polynomial time whether the input S is an initial set at all, see Proposition 5. Then we check whether S is an unattacked initial set, see Proposition 10. If it is not, we guess another set S with SRS and verify in polynomial time that S is an initial set. This shows that S is not an unchallenged initial set in NP.

Fig. 7.

The argumentation framework AFϕ for ϕ={{a,¬b,c},{¬a,¬b,c},{¬a,b,¬c}}.

The argumentation framework AFϕ′ for ϕ={{a,¬b,c},{¬a,¬b,c},{¬a,b,¬c}}.

For coNP-hardness, we do a reduction from 3UNSAT, i. e., the problem of deciding whether a propositional formula in conjunctive normal form with exactly three literals per clause is unsatisfiable. For that, we extend Reduction 3.6 from [22]. Let ϕ be an instance of 3UNSAT in set notation, i. e., ϕ={C1,,Cn} and Ci={l1,i,l2,i,l3,i} with literals l1,i, l2,i, l3,i from a set of atoms At, for i=1,,n. Define an abstract argumentation framework AFϕ=(Aϕ,Rϕ) via

Aϕ={ϕ,ϕ˜,ψ}{C1,,Cn}{a,¬aaAt}Rϕ={(C1,ϕ),,(Cn,ϕ)}Rϕ={(l,Ci)lC,i{1,,n}}Rϕ={(a,¬a),(¬a,a)aAt}Rϕ={(ϕ˜,a),(ϕ˜,¬a)aAt}Rϕ={(ϕ,ϕ˜),(ϕ,ψ),(ψ,ϕ)}
Figure 7 shows an example of the reduction. We first show that there is an initial set containing ϕ if and only if ϕ is satisfiable. For that, assume first that ϕ is satisfiable and let I:At{true,false} be a model of ϕ. Consider the set
SI={aI(a)=true}{¬aI(a)=false}{ϕ}
First observe that SI is conflict-free: as I is an interpretation it is not the case that a,¬aS for some aAt. Furthermore, there are no attacks between any argument from {a,¬aaAt} to ϕ and vice versa. Now observe that SI is admissible (in fact SI is stable):
  • (1) each aS defends itself against ¬a (for aAt),

  • (2) each ¬aS defends itself against a (for aAt),

  • (3) each Ci is attacked by some aS or ¬aS (since I is a model, every clause is satisfied), and

  • (4) ϕ˜ is attacked by ϕ.

However, SI is not necessarily an initial set. Consider the example in Fig. 7 again: here, I with I(a)=I(b)=I(c)=false is a model of ϕ and we have
SI={¬a,¬b,¬c,ϕ}
Furthermore, SI={¬a,¬b,ϕ}SI is also admissible (this happens when the truth value of one or more atoms does not matter for satisfiability). However, due to the fact that every non-empty admissible set contains an initial set, there is always an initial set SISI and SI must always contain ϕ as this is the only argument defending all arguments in {a,¬aaAt}. It follows that if ϕ is satisfiable then there is an initial set containing ϕ. The other direction is analogous.

We now claim that ϕ is unsatisfiable if and only if {ψ} is an unchallenged initial set. First, it is clear that {ψ} is an initial set since ψ counterattacks the only attack. Moreover, we established above that ϕ is satisfiable if and only if there is an initial set S containing ϕ. So if ϕ is satisfiable {ψ} is challenged by S. If ϕ is unsatisfiable then {ψ} is clearly unchallenged. □

Proposition 12.

ExistsIS is in PNP-complete.

Proof.

In order to show PNP-completeness, we use a characterisation of PNP from [17].5 More precisely, Theorem 9 of [17] establishes that a problem X is PNP-complete if and only if

  • (1) XPNP,

  • (2) X is NP-hard,

  • (3) X is coNP-hard,

  • (4) Two problem instances i1 and i2 of X can be polynomially reduced to a problem instance i3 of X such that i3 is a positive instance if and only if both i1 and i2 are positive instances.

  • (5) A set of problem instances I={i1,,ik} of X can be polynomially reduced to a problem instance i of X such that i is a positive instance if and only if there is at least one positive instance in I.

We now show that properties 1–5 above hold for the problem ExistsIS.
  • (1) For PNP-membership, consider the following algorithm.6 Let AF=(A,R) be the input argumentation framework.

    • 1. For each argument aA, check whether a is not attacked by an initial set

    • 2. For each argument aA, check whether a is contained in an initial set

    • 3. Let M be the set of arguments for which both checks 1 and 2 were positive

    • 4. Remove all unattacked arguments from M, yielding a new set M

    • 5. Compute the maximal admissible set M in M (which is uniquely determined)

    • 6. If M return Yes, otherwise return No

    First observe that the above algorithm runs in PNP. All checks in steps 1 and 2 can be solved by an NP-oracle:
    • (a) The check in step 1 is a decision problem in coNP as the complement problem (i. e., checking whether a is attacked by an initial set) can be solved by guessing a set S that attacks a and verifying in polynomial time (see Proposition 5) that it is an initial set.

    • (b) The check in step 2 is a decision problem in NP: it can be solved by guessing a set S that contains a and verifying in polynomial time (see Proposition 5) that it is an initial set.

    All checks in step 1 and 2 are non-adaptive, so they can be done in parallel (and there are linearly many of them). For step 4, observe that identifying unattacked arguments can be done in polynomial time. For step 5, note that M is conflict-free (if there would be two arguments a,bM with aRb, it means that both a and b are in some (possibly different) initial sets and that b is in some initial set that is attacked by some other initial set, which cannot be due to step 1). Determining the maximal admissible set in M can be done similarly as in the proof of Lemma 1 in polynomial time.

    Now we claim that the above algorithm returns Yes if and only if the answer to ExistsIS upon input AF is Yes.

    • “⇒”: Let M be the admissible set computed in step 5 and let SM be an initial set contained in M (which necessarily exists since M is admissible and non-empty). Observe that S is not an unattacked initial set as we removed all unattacked arguments in step 4. Assume S is a challenged initial set. Then there exists another initial set S which attacks some argument bS. This is in contradiction to the fact that SMM and M contains only arguments that are not attacked by an initial set (see step 1). So S is an unchallenged initial set and the answer to ExistsIS upon input AF is Yes.

    • “⇐”: Assume the answer to ExistsIS upon input AF is Yes. Then there exists an unchallenged initial set S. By definition, every argument aS is contained in an initial set and not attacked by an initial set, so SM in step 3 of the above algorithm. Since S is unchallenged (but not unattacked), every argument in S is attacked and we have SM in step 4. As S is admissible (and in no conflict with any other argument in M) we also have SM in step 5 of the above algorithm. As S it follows M as well and the algorithm return Yes.

    In conclusion, ExistsIS is in PNP.

  • (2) We show DP-hardness (which entails NP-hardness) instead. For that we use the same reduction from Uniquest as in the proof of Proposition 7, i. e., the construction Tr4 from [23]. In particular, observe that if Tr4(AF) has exactly one initial set S then S is unchallenged. Furthermore, if Tr4(AF) has no initial sets then it obviously also has no unchallenged initial sets. If Tr4(AF) has at least two initial sets, then all these initial sets are challenged (as they are all stable extensions of the original framework and two different stable extensions necessarily attack each other). This shows DP-hardness of ExistsIS.

  • (3) Since ExistsIS is DP-hard (see above) it is also coNP-hard.

  • (4) Let AF1=(A1,R1) and AF2=(A2,R2) be two argumentation frameworks and assume A1A2= (otherwise rename arguments accordingly). Construct AF3=(A3,R3) as follows (let a1, a2 be fresh arguments):

    A3=A1A2{a1,a2}R3=R1R2{(a1,a1),(a2,a2)}R3={(a,a1)aA1,a}{(a1,b)bA2,b}R3={(b,a2)bA2,b}{(a2,a)aA1,b}
    The intuition behind the above construction is that the two frameworks AF1 and AF2 are arranged in a circle where every (already attacked) argument of AF1 attacks a1, a1 attacks every (already attacked) argument of AF2, which in turn all attack a2, which in turn attacks all (already attacked) arguments of AF1. Obviously, the construction of AF3 is polynomial in the size of AF1 and AF2.

    We now show that AF3 has an unchallenged initial set if and only if both AF1 and AF2 have unchallenged initial sets. Let M be an unchallenged initial set of AF3. Since a1 and a2 attack themselves, a1, a2M. Assume MA1. Since M is unchallenged and not unattacked, all aM are attacked. It follows that a2 attacks M. Since only arguments in AF2 attack a2, M cannot defend itself from a2. It follows that A2M. For the same reason and using a1 instead of a2, it follows A1M. Let M1=MA1 and M2=MA2. Assume M1 is challenged in AF1 and let M1 be an initial set in conflict with M1 in AF1. Then M1M2 is also an initial set of AF3 and in conflict with M, contradicting the assumption that M is unchallenged. It follows that both M1 and (with the same argument) M2 are unchallenged in AF1 and AF2, respectively. For the other direction, given that M1 and M2 are unchallenged initial sets of AF1 and AF2, respectively, it is also clear that M1M2 is an unchallenged initial set of AF3.

  • (5) Let AF1=(A1,R1),,AFn=(An,Rn) be argumentation frameworks and assume AiAj= for all i,j=1,,n and ij (otherwise rename arguments accordingly). Observe that AF=(A1An,R1Rn) has an unchallenged initial set M if and only if at least one of AF1,,AFn has an unchallenged initial set (since necessarily MAi for some i due to the disconnectedness of AF).

 □

Proposition 13.

UniqueIS is in PNP and DP-hard.

Proof.

For PNP-membership, we use a similar algorithm as in the proof of Proposition 12. Let AF=(A,R) be the input argumentation framework.

  • 1. For each argument aA, check whether a is not attacked by an initial set

  • 2. For each argument aA, check whether a is contained in an initial set

  • 3. Let M be the set of arguments for which both checks 1 and 2 were positive

  • 4. Remove all unattacked arguments from M, yielding a new set M

  • 5. Compute the maximal admissible set M in M (which is uniquely determined)

  • 6. If M= return No

  • 7. For each argument aM, let Ma=M{a}

  • 8. For each argument aM, let Ma be the maximal admissible set in Ma (which is uniquely determined)

  • 9. If for all aM, Ma, return No

  • 10. Let S={aMa=}

  • 11. If S is an initial set return Yes, otherwise return No

First observe that the above algorithm runs in PNP. Steps 1–6 run in PNP as already shown in the proof of Proposition 12. Furthermore, steps 7–11 run in (deterministic) polynomial time (in particular, step 8 runs in polynomial time by leveraging a similar algorithm as in the proof of Lemma 1 and step 11 because of Proposition 5).

We now claim that the above algorithm returns Yes if and only if AF has a unique unchallenged initial set.

  • “⇒”: If the algorithm returns Yes, we have obviously found an initial set S in step 11. As SM we also have that S is an unchallenged initial set (see the proof of Proposition 12). Assume there exists an unchallenged initial set S with SS. Note that both SS and SS since both are initial sets and SM (again, see the proof of Proposition 12). Let xSS. Then Mx as Mx completely contains S. This contradicts the fact that xS due to step 10. It follows that AF has the unique unchallenged initial set S.

  • “⇐”: Assume AF has the unique unchallenged initial set M. By the argumentation in the proof of Proposition 12 we have that MM in step 6. Then for all aM we have that

    • Ma= if and only if aM since Ma would imply that there is another unchallenged initial set contained in Ma.

    • Ma if and only if aM as M is contained in Ma.

    By the definition of S in step 10 it follows S=M. As M is an initial set, the algorithm returns Yes in step 11.

For showing DP-hardness we use the same reduction from Uniquest as in the proof of Proposition 7, i. e., the construction Tr4 from [23]. In particular, note that AF has exactly one stable extension if and only if Tr4(AF) has exactly one (unchallenged) initial set. □

Proposition 14.

CredIS is PNP-complete.

Proof.

In order to show PNP-completeness, we again use the characterisation of PNP from [17] (see also Proposition 12). So we show that is CredIS is PNP-complete by showing that

  • (1) CredISPNP,

  • (2) CredIS is NP-hard,

  • (3) CredIS is coNP-hard,

  • (4) Two problem instances (AF1,a1) and (AF2,a2) of CredIS can be polynomially reduced to a problem instance (AF3,a3) of CredIS such that (AF3,a3) is a positive instance if and only if both (AF1,a1) and (AF2,a2) are positive instances.

  • (5) A set of problem instances I={(AF1,a1),,(AFk,ak)} of CredIS can be polynomially reduced to a problem instance (AF,a) of CredIS such that (AF,a) is a positive instance if and only if there is at least one positive instance in I.

We now show that properties 1–5 above hold:
  • (1) For showing PNP-membership, we use a similar algorithm as in the proof of Proposition 12. Let AF=(A,R) be the input argumentation framework and x the input argument..

    • 1. For each argument aA, check whether a is not attacked by an initial set

    • 2. For each argument aA, check whether a is contained in an initial set

    • 3. Let M be the set of arguments for which both checks 1 and 2 were positive

    • 4. Remove all unattacked arguments from M, yielding a new set M

    • 5. Compute the maximal admissible set M in M (which is uniquely determined)

    • 6. If there is an initial set SM with xS, return Yes, otherwise return No

    First observe that the above algorithm runs in PNP using two consecutive rounds of parallel calls (which is still in PNP due to Proposition 2.1 of [24]): steps 1–5 run in PNPPNP as already shown in the proof of Proposition 12, and step 6 can be solved by one further NP-oracle call (non-deterministically guess SM and verify that it is an initial set with xS). The above algorithm also solves CredIS as M contains all (and only) unchallenged initial sets.

  • (2) We show DP-hardness (which entails NP-hardness) instead. For that, we use the same reduction from Uniquest as in the proof of Proposition 7, i. e., the construction Tr4 from [23], but first augment the input argumentation framework AF=(A,R) with a fresh argument a (without any additional attacks), yielding an argumentation framework AFˆ=(A{a},R). Note that E is a stable extension of AF if and only if E{a} is a stable extension of AFˆ. By the same argumentation as in the proof of Proposition 7, AF has a unique stable extension E if and only if Tr4(AFˆ) has the unique (and unchallenged) initial set E{a}. So AF has a unique stable extension if and only if a is credulously accepted wrt. unchallenged initial sets in Tr4(AFˆ).

  • (3) Since CredIS is DP-hard (see above) it is also coNP-hard.

  • (4) Let AF1=(A1,R1) and AF2=(A2,R2) be two argumentation frameworks and assume A1A2= (otherwise rename arguments accordingly) and let (AF1,a1) and (AF2,a2) be two instances for CredIS. Construct an instance (AF3,a3) with AF3=(A3,R3) for CredIS as follows (let a3 be a fresh argument):

    A3=A1{a1}A2{a2}{a3}R3={(b,c)R1ba1,ca1}R3={(b,c)R2ba2,ca2}R3={(a3,c)(a1,c)R1}{(b,a3)(b,a1)R1}R3={(a3,c)(a2,c)R2}{(b,a3)(b,a2)R2}
    Informally speaking, AF3 is simply the union of AF1 and AF2 where the two arguments a1 (from AF1) and a2 (from AF2) are merged into a new argument a3 that retains all previous attacks of a1 and a2.

    We now show that a3 is credulously accepted wrt. unchallenged initial sets in AF3 if and only if both a1 and a2 are credulously accepted wrt. unchallenged initial sets in AF1 and AF2, respectively. Without loss of generality, we assume that both a1 and a2 are attacked in AF1 and AF2, respectively (otherwise the problem trivialises since {a1} and/or {a2} are then unattacked initial sets). Assume now that a3 is credulously accepted wrt. unchallenged initial sets in AF3 and let M be an unchallenged initial set with a3M. Consider M1=MA1{a1} and observe

    • M1 is admissible in AF1: let cA1 be attacking M1. Then c also attacks M in AF3 and M defends itself in AF3 through some dM. Since there are no attacks between AF1 and AF2 either d=a3 or dA1. In the first case, a1M1 then attacks c. In the second case dM1 attacks c. It follows that M1 is admissible in AF1.

    • M1 is an initial set in AF1: Assume there exists non-empty initial M1M1. If a1M1 then M1M as well, contradicting the fact that M is initial. If a1M1, it is also easy to see that M1{a1}{a3}(MA2)M must be an initial set of AF3.

    • M1 is unchallenged: Suppose there is another initial set M1 in conflict with M1 in AF1. If a1M1 then M1 also is in conflict with M in AF3, contradicting the fact that M is unchallenged. The same follows for a1M1 with the same argumentation as above.

    For the same reason it follows that M2=MA2{a2} is an unchallenged initial set in AF2 and, therefore, both a1 and a2 are credulously accepted wrt. unchallenged initial sets in AF1 and AF2, respectively. The other direction is analogous.

  • (5) Let AF1=(A1,R1),,AFn=(An,Rn) be argumentation frameworks and assume AiAj= for all i,j=1,,n and ij (otherwise rename arguments accordingly). Let I={(AF1,a1),,(AFk,ak)} be a set of instances of CredIS. Construct AF=(A,R) as follows (let a, b, c be fresh arguments):

    A=A1Ak{a,b,c}R=R1Rk{(a,a),(a,b),(b,c),(c,c),(a1,a),,(ak,a),(c,a1),,(c,ak)}
    A sketch of the construction is shown in Fig. 8. We now show that b is credulously accepted wrt. unchallenged initial sets in AF if and only if there is ai (i=1,,k) that is credulously accepted wrt. unchallenged initial sets in AFi. Again, without loss of generality, we assume that all ai (i=1,,k) are attacked in AFi, respectively. Assume that b is credulously accepted wrt. unchallenged initial sets in AF and let M be an unchallenged initial set with bM. Since M is admissible and b is attacked by a, there must be aiM for some i=1,,k. Let Mi=M{b}. Then Mi is necessarily an unchallenged initial set in AFi (if, e. g., Mi is challenged in AFi then M would also be challenged in AF). It follows that ai is credulously accepted wrt. unchallenged initial sets in AFi. The other direction is analogous.

 □

Fig. 8.

A sketch of the argumentation framework AF from the proof of Proposition 14.

A sketch of the argumentation framework AF from the proof of Proposition 14.
Proposition 15.

SkeptIS is PNP-complete.

Proof.

In order to show PNP-completeness, we use a characterisation of PNP from [25], in particular Corollary 8. This allows us to show PNP-completeness of SkeptIS by showing that

  • (1) SkeptISPNP,

  • (2) SkeptIS is coDP-hard,

  • (3) A set of problem instances I={(AF1,a1),,(AFk,ak)} of SkeptIS can be polynomially reduced to a problem instance (AF,a) of SkeptIS such that (AF,a) is a positive instance if and only if all instances in I are positive.

We now show that properties 1–3 above hold:
  • (1) For PNP-membership, we use a similar algorithm as in the proof of Proposition 12. Let AF=(A,R) be the input argumentation framework and x the input argument.

    • 1. For each argument aA, check whether a is not attacked by an initial set

    • 2. For each argument aA, check whether a is contained in an initial set

    • 3. Let M be the set of arguments for which both checks 1 and 2 were positive

    • 4. Remove all unattacked arguments from M, yielding a new set M

    • 5. Compute the maximal admissible set M in M (which is uniquely determined)

    • 6. If M= return Yes

    • 7. Let Mx=M{x}

    • 8. Let Mx be the maximal admissible set in Mx (which is uniquely determined)

    • 9. If Mx= return Yes, otherwise return No

    First observe that the above algorithm runs in PNP. Steps 1–6 run in PNP as already shown in the proof of Proposition 12. Furthermore, steps 7–9 run in (deterministic) polynomial time (in particular, step 8 runs in polynomial time by leveraging a similar algorithm as in the proof of Lemma 1).

    We now claim that the above algorithm returns Yes if and only if x is skeptically accepted wrt. unchallenged initial sets in AF.

    • “⇒”: Assume the algorithm returns Yes. First, assume the algorithm terminates in step 6. M= means that AF does not contain any unchallenged initial set (see the proof of Proposition 12). Then all arguments (including x) are trivially skeptically accepted. Now, assume the algorithm terminates in step 9. Since M is non-empty it contains unchallenged initial sets S1,,Sn (which are all unchallenged initial sets of AF, cf. the proof of Proposition 12). Since Mx= it follows SiMx for all i=1,,n. It follows xSi for all i=1,,n and x is skeptically accepted.

    • “⇐”: Assume x is skeptically accepted wrt. unchallenged initial sets. Consider the following case differentiation:

      • There is no unchallenged initial set: in that case M= in step 6 (see again the proof of Proposition 12) and the algorithm returns Yes in step 6.

      • There are unchallenged initial sets S1,,Sn: since xSi for all i=1,,n we have that Mx= (all unchallenged initial sets are “broken” by removing x). Then the algorithm returns Yes in step 9.

  • (2) For showing coDP-hardness, we provide a reduction from the problem ¬Uniquest, i. e., the problem of deciding whether an argumentation framework AF does not have a unique stable extension (which is naturally coDP-complete as its complement Uniquest is DP-complete). We use a similar approach as in the proof of Proposition 14, see also the proof of Proposition 7, again using the construction Tr4 from [23]. For an input argumentation framework AF=(A,R) and a fresh argument a, we construct

    AF˜=(A{a},R{(b,a)bA})
    In other words, we add an argument a and attacks from each original argument to a. Note that E is a stable extension of AF if and only if E is a stable extension of AF˜. We now claim that an input argumentation framework AF does not possess a unique stable extension if and only if a is skeptically accepted wrt. unchallenged initial sets in AF˜.
    • Assume AF has no stable extension. Then Tr4(AF˜) has no initial set (see the proof of Proposition 7) and also no unchallenged initial set. Then every argument (including a) is trivially skeptically accepted wrt. unchallenged initial sets.

    • Assume AF has a unique stable extension E. Then Tr4(AF˜) has the unique (and unchallenged) initial set E that does not contain a. So a is not skeptically accepted, as desired.

    • Assume AF has more than one stable extension. Then Tr4(AF˜) has the same sets as (challenged) initial sets (as all these sets attack each other) and no unchallenged initial set. Then every argument (including a) is trivially skeptically accepted wrt. unchallenged initial sets.

    For the other direction, assume a is skeptically accepted wrt. unchallenged initial sets. As observed above, this can only happen if there are no unchallenged sets and this can only happen if AF does not have a unique stable extension. This shows coDP-hardness of SkeptIS.

  • (3) Let AF1=(A1,R1),,AFn=(An,Rn) be argumentation frameworks and assume AiAj= for all i,j=1,,n and ij (otherwise rename arguments accordingly). Let I={(AF1,a1),,(AFk,ak)} be a set of instances of SkeptIS. We again assume that each ai is attacked in each AFi. Consider the argumentation framework AF following the construction in the proof of Proposition 14, item (5), see also Fig. 8. We claim that b is skeptically accepted wrt. unchallenged initial sets in AF if and only if a1,,ak are skeptically accepted wrt. unchallenged initial sets in AF1,,AFk, respectively. Without loss of generality, assume that a1 is not skeptically accepted wrt. unchallenged initial sets in AF1. Then there is an unchallenged initial set M in AF1 with a1M. Observe that M is also necessarily an unchallenged initial set in AF (since a1M there is no interaction with the rest of AF). Since bM it follows that b is also not skeptically accepted wrt. unchallenged initial sets in AF. The argument generalises naturally to all i=1,,k. The other direction is analogous.

 □

Proposition 16.

VerIS is NP-complete.

Proof.

For NP-membership, on input AF and S1 we guess a set S2 that attacks S1 and verify in polynomial time that S2 is an initial set, cf. Proposition 5. This shows that S1 is a challenged initial set.

To show NP-hardness, we use the same reduction as in the proof of Proposition 11 but using an instance of 3SAT. It is easy to see that an input instance ϕ is satisfiable if and only if {ψ} is a challenged initial set in AFϕ. □

Proposition 17.

ExistsIS is NP-complete.

Proof.

For NP-membership, we guess two sets S1 and S2 that attack each other and verify in polynomial time that both are initial sets, cf. Proposition 5. This shows actually that both S1 and S2 are challenged initial sets.

To show NP-hardness, we use the same reduction as in the proof of Proposition 11 but using an instance of 3SAT. It is easy to see that an input instance ϕ is satisfiable if and only if there is a challenged initial set (concretely, {ψ}) in AFϕ. □

Proposition 18.

CredIS is NP-complete.

Proof.

For NP-membership, on input AF and a we guess two sets S1 and S2 with aS1, S1 and S2 attack each other and verify in polynomial time that both are initial sets, cf. Proposition 5. This shows actually that both S1 and S2 are challenged initial sets and a is credulously accepted wrt challanged initial sets (as aS1).

To show NP-hardness, we use the same reduction as in the proof of Proposition 11 but using an instance of 3SAT. It is easy to see that an input instance ϕ is satisfiable if and only if ψ is credulously accepted wrt. challenged initial sets in AFϕ. □

Proposition 19.

SkeptIS is coNP-complete.

Proof.

For coNP-membership, we show that the complement problem, i. e., the problem of deciding whether an input argument a is not skeptically accepted wrt. initial sets, is in NP. For that we guess two sets S1 and S2 with aS1, S1 and S2 attack each other and verify in polynomial time that both are initial sets, cf. Proposition 5. This shows that a is not skeptically accepted and therefore SkeptIS is in coNP.

To show coNP-hardness, we use the same reduction as in the proof of Proposition 11. It is easy to see that an input instance ϕ is unsatisfiable if and only if ψ is skeptically accepted wrt. challenged initial sets in AFϕ. □

References

[1] 

L. Amgoud and J. Ben-Naim, Ranking-based semantics for argumentation frameworks, in: Proceedings of the 7th International Conference on Scalable Uncertainty Management (SUM 2013), W. Liu, V.S. Subrahmanian and J. Wijsen, eds, Lecture Notes in Artificial Intelligence, Vol. 8078, Washington, DC, USA, 2013.

[2] 

L. Amgoud and H. Prade, Using arguments for making and explaining decisions, Artificial Intelligence 173(3–4) (2009), 413–436. doi:10.1016/j.artint.2008.11.006.

[3] 

K. Atkinson, P. Baroni, M. Giacomin, A. Hunter, H. Prakken, C. Reed, G.R. Simari, M. Thimm and S. Villata, Toward artificial argumentation, AI Magazine 38(3) (2017), 25–36. doi:10.1609/aimag.v38i3.2704.

[4] 

P. Baroni, G. Boella, F. Cerutti, M. Giacomin, L. van der Torre and S. Villata, On the input/output behavior of argumentation frameworks, Artificial Intelligence 217 (2014), 144–197. doi:10.1016/j.artint.2014.08.004.

[5] 

P. Baroni, M. Caminada and M. Giacomin, Abstract argumentation frameworks and their semantics, in: Handbook of Formal Argumentation, P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre, eds, College Publications, 2018, pp. 159–236.

[6] 

P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre (eds), Handbook of Formal Argumentation, College Publications, 2018.

[7] 

P. Baroni, M. Giacomin and G. Guida, SCC-recursiveness: A general schema for argumentation semantics, Artificial Intelligence 168(1–2) (2005), 162–210. doi:10.1016/j.artint.2005.05.006.

[8] 

R. Baumann, G. Brewka and M. Ulbricht, Revisiting the foundations of abstract argumentation – semantics based on weak admissibility and weak defense, in: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI’20), 2020.

[9] 

R. Baumann, T. Linsbichler and S. Woltran, Verifiability of argumentation semantics, in: Proceedings of the 6th International Conference on Computational Models of Argument (COMMA’16), 2016, pp. 83–94.

[10] 

R. Baumann and M. Ulbricht, Choices and their consequences – explaining acceptable sets in abstract argumentation frameworks, in: Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning (KR’21), 2021.

[11] 

N. Boudjani, A. Gouaïch and S. Kaci, CLEAR: Argumentation frameworks for constructing and evaluating deductive mathematical proofs, in: Proceedings of the 7th International Conference on Computational Models of Argument (COMMA’18), 2018, pp. 281–288.

[12] 

M. Caminada, Argumentation semantics as formal discussion, in: Handbook of Formal Argumentation, P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre, eds, College Publications, 2018.

[13] 

M. Caminada and P.E. Dunne, Strong admissibility revisited: Theory and applications, Argument & Computation 10(3) (2019), 277–300. doi:10.3233/AAC-190463.

[14] 

F. Cerutti, S.A. Gaggl, M. Thimm and J.P. Wallner, Foundations of implementations for formal argumentation, in: Handbook of Formal Argumentation, P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre, eds, College Publications, 2018, Chapter 15. Also appears in IfCoLog Journal of Logics and their Applications 4(8):2623–2706, October 2017.

[15] 

F. Cerutti, I. Tachmazidis, M. Vallati, S. Batsakis, M. Giacomin and G. Antoniou, Exploiting parallelism for hard problems in abstract argumentation, in: Proceedings of the 29th AAAI Conference (AAAI’15), 2015.

[16] 

L.A. Chalaguine and A. Hunter, A persuasive chatbot using a crowd-sourced argument graph and concerns, in: Proceedings of the 8th International Conference on Computational Models of Argument (COMMA’20), 2020, pp. 9–20.

[17] 

R. Chang and J. Kadin, On computing Boolean connectives of characteristic functions, Mathematical systems theory 28(3) (1995), 173–198. doi:10.1007/BF01303054.

[18] 

Y. Dimopoulos and A. Torres, Graph theoretical structures in logic programs and default theories, Theoretical Computer Science 170(1–2) (1996), 209–244. doi:10.1016/S0304-3975(96)80707-9.

[19] 

P.M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence 77(2) (1995), 321–358. doi:10.1016/0004-3702(94)00041-X.

[20] 

P.M. Dung, P. Mancarella and F. Toni, Computing ideal sceptical argumentation, Artificial Intelligence 171(10) (2007), 642–674. doi:10.1016/j.artint.2007.05.003.

[21] 

P.E. Dunne, The computational complexity of ideal semantics, Artificial Intelligence 173(18) (2009), 1559–1591. doi:10.1016/j.artint.2009.09.001.

[22] 

W. Dvořák and P.E. Dunne, Computational problems in formal argumentation and their complexity, in: Handbook of Formal Argumentation, P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre, eds, College Publications, 2018, Chapter 14.

[23] 

W. Dvořák and S. Woltran, On the intertranslatability of argumentation semantics, Journal of Artificial Intelligence Research 41 (2011), 45–475.

[24] 

T. Eiter and G. Gottlob, The complexity class Theta2p: Recent results and applications in AI and modal logic, in: Proceedings of the 11th International Symposium on Fundamentals of Computation Theory (FCT’97), Springer-Verlag, Berlin, Heidelberg, 1997, pp. 1–18.

[25] 

F. Frei, E. Hemaspaandra and J. Rothe, Complexity of stability, Journal of Computer and System Sciences 123 (2022), 103–121. doi:10.1016/j.jcss.2021.07.001.

[26] 

A. Hunter and M. Thimm, Probabilistic reasoning with abstract argumentation frameworks, Journal of Artificial Intelligence Research 59 (2017), 565–611. doi:10.1613/jair.5393.

[27] 

B. Liao and L. van der Torre, Explanation semantics for abstract argumentation, in: Proceedings of the 8th International Conference on Computational Models of Argument (COMMA’20), 2020.

[28] 

S. Modgil and H. Prakken, The ASPIC+ framework for structured argumentation: A tutorial, Argument & Computation 5 (2014), 31–62. doi:10.1080/19462166.2013.869766.

[29] 

A. Niskanen and M. Järvisalo, Smallest explanations and diagnoses of rejection in abstract argumentation, in: Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR’20), 2020, pp. 667–671.

[30] 

C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.

[31] 

A. Rago, O. Cocarascu, C. Bechlivanidis and F. Toni, Argumentation as a framework for interactive explanations for recommendations, in: Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR’20), 2020, pp. 805–815.

[32] 

Z.G. Saribatur, J.P. Wallner and S. Woltran, Explaining non-acceptability in abstract argumentation, in: Proceedings of the 24th European Conference on Artificial Intelligence (ECAI’20), 2020.

[33] 

D. Seselja and C. Straßer, Abstract argumentation and explanation applied to scientific debates, Synthesis 190(12) (2013), 2195–2217. doi:10.1007/s11229-011-9964-y.

[34] 

M. Thimm, Revisiting minimal admissible sets in abstract argumentation, in: Proceedings of the Second Workshop on Explainable Logic-Based Knowledge Representation (XLoKR’21), 2021.

[35] 

F. Toni, A tutorial on assumption-based argumentation, Argument & Computation 5(1) (2014), 89–117. doi:10.1080/19462166.2013.869878.

[36] 

M. Ulbricht and J.P. Wallner, Strong explanations in abstract argumentation, in: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI’21), 2021.

[37] 

L. van der Torre and S. Vesic, The principle-based approach to abstract argumentation semantics, in: Handbook of Formal Argumentation, Vol. 1, College Publications, 2018.

[38] 

Y. Xu and C. Cayrol, Initial sets in abstract argumentation frameworks, in: Proceedings of the 1st Chinese Conference on Logic and Argumentation (CLAR’16), 2016.

[39] 

Y. Xu and C. Cayrol, Initial sets in abstract argumentation frameworks, Journal of Applied Non-Classical Logics 28(2–3) (2018), 260–279. doi:10.1080/11663081.2018.1457252.

[40] 

Y. Xu, L. Xu and C. Cayrol, On structural analysis of extension-based argumentation semantics, in: The Second Chinese Conference on Logic and Argumentation (CLAR’18), 2018.