Reasoning over Argument-Incomplete AAFs in the Presence of Correlations

1 Introduction

Incomplete Abstract Argumentation Frameworks (iAAF) are an extension of Dung's Abstract Argumentation Frameworks (AAFs) enabling a "qualitative" representation of the uncertainty involving arguments and attacks. Basically, an iAAF is an AAF where the set of arguments (resp., attacks) is partitioned into the sets of certain and uncertain arguments (resp., attacks): certain arguments/attacks are those whose presence in the argumentation is sure, while uncertain arguments/attacks may not occur in the argumentation. As observed in [Baumeister et al., 2018; Coste-Marquis et al., 2007; Cayrol et al., 2007], iAAFs are well-suited for modeling a number of situations. For instance, when representing a dispute that may be participated by several agents, it is natural to model the arguments claimed by agents whose participation is not guaranteed as uncertain. Analogously, arguments encoding alternative interpretations of the same claim should be considered as uncertain, when it is not known which of them catches the intended meaning of the claim.

An iAAF compactly encodes the set of the alternative combinations of arguments and attacks that can actually occur in the argumentation. Each combination is called "completion" and is an AAF containing all the certain arguments/attacks of the iAAF plus a subset of its uncertain arguments/attacks. In order to take into account the possibility of different scenarios for the argumentation (as represented by the completions), the traditional notion of extension for an AAF has been re-formulated in terms of i∗ -extension [Fazzinga et al., 2020]: A set of arguments S is a possible (resp., necessary) i∗ -extension of the iAAF IF if, for some (resp., every) completion F of IF, the set S is an extension of F.

∗Contact Author

Example 1 Consider the iAAF IF over the arguments a, b, c, d and the attacks (a, b), (c, d), (d, c) depicted in Fig. 1 (disregard the dotted edges for now). Arguments a, b, c are the only uncertain terms of the argumentation, so IF has 8 completions (denoted as pairs 〈 arguments, attacks 〉):

F1= 〈{d}, ∅〉; F2= 〈{a, d}, ∅〉; F3= 〈{a, b, d}, {(a, b)}〉;

F4 = 〈{a, c, d}, {(c, d), (d, c)}〉;

F5= 〈{a, b, c, d}, {(a, b), (c, d), (d, c)}〉; F6= 〈{b, d}, ∅〉;

F7 = 〈{b, c, d}, {(c, d), (d, c)}〉;

F8 = 〈{c, d}, {(c, d), (d, c)}〉.

The set {a, c} is a possible i∗ -extension (under the admissible semantics), since it is an admissible extension in at least one completion of IF (such as F4 and F5). It is easy to see that, among others, also {b, d} and {b, c} are possible admissible i∗ -extensions. Under the necessary perspective, the only admissible i∗ -extensions are ∅ and {d}.

A limit of the reasoning paradigm over iAAFs is that it does not take into account possible correlations between arguments/attacks. In fact, there can be dependencies between the arguments/attacks implying that some completions represent scenarios that cannot actually occur, and this may deeply affect the reasoning process, as shown in Example 2.

Example 2 Assume that the iAAF IF of Example 1 models the arguments that can be introduced during a trial, and that the uncertain arguments a, b, c are not independent. In particular, b and c are alternative interpretations of the same fact given by the two experts Xb and Xc, and the defendant has to choose who between Xb and Xc will testify: thus, exactly one argument in {b, c} will occur in the argumentation. Moreover, the analyst knows that if b occurs in the argumentation, also a will occur, since a is claimed by an expert Xa that the prosecutor always uses to disqualify what said by Xb. The analyst thinks that the prosecutor may put Xa on the stand even if Xb is not called by the defendant, thus the implication between b and a in one way only. These dependencies can be formally written as CHOICE(b, c) and b ⇒ a, and are depicted in Fig. 1 as suitably labeled dotted edges.

It is easy to see that some of the completions enumerated in Example 1 encode scenarios that cannot occur. Specifically, F1, F5, F7 are not possible, since they violate the fact that exactly one expert will be called by the defendant (i.e. CHOICE(b, c)), and F6 is not possible as well, since it violates the constraint that if b occurs, also a occurs (i.e. b ⇒ a). Hence, the only "valid" completions are F3, F4 and F8.

This entails that some of the conclusions drawn in Example 1 must be revised: when verifying if a set is an i∗ - extension, one should focus only on the valid completions. Hence, under the possible perspective, {b, d} is not an admissible i∗ -extension, since in all the valid completions where b and d occur together, the attack from a to b is not counterattacked. Analogously, {b, c} is not an admissible i∗ -extension, since there is no valid completion containing b and c.

Example 2 shows that disregarding the correlations between the terms of the argumentation can yield wrong assessments: for instance, under the possible perspective, it may happen that the completions witnessing that a set S is an i∗ - extension are not scenarios that can occur in practice. Hence, disregarding the correlations may lead the analyst to wrongly consider S as a reasonably "robust" set of arguments (as happens in examples 1 and 2 for {b, d} and {b, c}).

The main contribution of this paper is a study of fundamental problems supporting the reasoning over iAAFs in the presence of correlations. In particular, we focus on the case of argument-incomplete AAFs (aiAAFs) [Baumeister et al., 2015], i.e. iAAFs where the uncertainty involves only the arguments, as in examples 1, 2. Starting from them, we introduce "aiAAFs with dependencies" (daiAAFs), where the analyst is allowed to specify correlations involving the uncertain arguments. We consider a practical setting, where correlations can be expressed in a user-friendly manner: the analyst can specify a set of logical dependencies, where each dependency is the application of one n-ary logical connective (namely, OR, CHOICE, NAND, or ⇒) over a set of arguments. This way of specifying the correlations is prone to be implemented in an intuitive visual interface: binary dependencies (like the CHOICE and ⇒ of Example 2) can be naturally depicted as (possibly oriented) labeled edges between the involved arguments, while more general n-ary correlations can be depicted by circling the involved sets of arguments (see Fig. 2).

Given this, we characterize the complexity of two problems:

• DSAT: is there a "valid" completion (i.e. where no dependency is violated) of a given daiAAF? This means deciding if the specified correlations "make sense";
• PDVERσ (S): the verification problem for possible i∗ - extensions for a daiAAF under a semantics σ.

In particular, we study the sensitivity of the complexity of the two problems to the form of dependency used to specify the correlations, and, for the case of PDVERσ (S), also to the semantics of extensions (we consider admissible, complete, grounded, stable and preferred semantics). Table 1 summarizes our results. Interestingly, after observing that DSAT is itself a source of complexity of PDVERσ (S), we show that when DSAT is trivial or polynomial-time solvable, the complexity of PDVERσ (S) depends on the combination 〈 dependency, semantics 〉. For some combinations, the complexity is P , the same as the verification problem over iAAFs in the absence of correlations, while for others the complexity moves to NP -complete.

2 Preliminaries

An abstract argumentation framework (AAF) is a pair 〈A, D〉, where A is a finite set, whose elements are called arguments, and D ⊆ A × A is a binary relation over A, whose elements are called defeats or attacks. Given a set of arguments S and an argument a, we say that "S attacks a" if there is an argument b in S such that b attacks a, and that "a attacks S" if there is an argument b ∈ S such that a attacks b. Moreover, we say that a is acceptable w.r.t. S if every argument attacking a is attacked by S, and say that S is conflict-free if there is no attack between its arguments.

Several semantics for AAFs have been proposed to identify "reasonable" sets of arguments, called extensions [Dung, 1995]. A set S ⊆ A is: an admissible extension (ad) iff S is conflict-free and all its arguments are acceptable w.r.t. S; a stable extension (st) iff S is conflict-free and S attacks each argument in A\S; a complete extension (co) iff S is admissible and S contains all the arguments that are acceptable w.r.t. S; a grounded extension (gr) iff S is a minimal (w.r.t. ⊆) complete set of arguments; a preferred extension (pr) iff S is a maximal (w.r.t. ⊆) complete set of arguments.

We recall the notion of argument-incomplete Abstract Argumentation Framework (aiAAF) [Baumeister et al., 2015].

Definition 1 (aiAAF) An argument-incomplete Abstract Argumentation Framework is a tuple 〈A, A? , D〉, where A and A? are disjoint sets of arguments and D is a set of attacks between arguments in A ∪ A? . The arguments in A (resp., A? ) are said to be certain (resp., uncertain), i.e. they are guaranteed (resp., not guaranteed) to occur in the argumentation.

An aiAAF compactly represents the alternative scenarios for the argumentation, i.e. all the possible combinations of arguments and attacks that can occur according to what is certain and uncertain. Each scenario is called completion.

Definition 2 (Completion) Given an aiAAF IF = 〈A,A? ,D〉, a completion for IF is an AAF F = 〈A′ ,D′ 〉 where A ⊆ A′ ⊆ (A ∪ A? ) and D′ = D ∩ (A′ × A′ ).

In [Fazzinga et al., 2020], i∗ -extensions were introduced to adapt the notion of extension to the case of iAAFs (and, consequently, to aiAAFs). Specifically, since an iAAF encodes several alternative scenarios, i∗ -extensions were defined under both the possible and the necessary perspective, where the condition of being extension is required to be true in at least one and every scenario, respectively. Example 1 contains examples of possible and necessary i∗ -extensions over aiAAFs.

Definition 3 (i∗ -extension) Given an aiAAF IF and a semantics σ, a set S is a possible (resp., necessary) i∗ -extension for IF (under σ) if, for at least one (resp., for every) completion F of IF, the set S is an extension of F under σ.

3 Specifying Correlations over aiAAFs

The reasoning paradigm based on i∗ -extensions considers the uncertain arguments as "independent": the presence/absence of an argument is not supposed to influence the presence of other arguments. In fact, when addressing the verification problem, every completion is a potential witness (resp., counter-witness) of the fact that S is an i∗ -extension under the possible (resp., necessary) perspective. However, the independence assumption may not be reasonable, since some correlation is known to exist between uncertain arguments, and this has important consequences, as discussed below.

Impact of the correlations on the reasoning. As shown in Example 2, introducing dependencies may have the effect of discarding some completions, as they turn out to describe scenarios that cannot occur. This has a strong impact on the reasoning. In fact, under the possible perspective, a set that is an i∗ -extension when dependencies are not considered may be no longer an i∗ -extension when dependencies are taken into account (Example 2 shows that this happens with {b, c} and {b, d}, since the completions witnessing that they are extensions are impossible scenarios, according to the CHOICE- and IMPLY- dependencies). Under the necessary perspective, a set that, with no dependency, is not an i∗ -extension may become an i∗ -extension when the dependencies are considered. For instance, consider an aiAAF consisting in a conflict-free set S of certain arguments and two uncertain arguments a and b attacking each other. If no dependency is considered, S is not a necessary complete i∗ -extension, as there are two completions F1 and F2 where S is not complete (i.e. the completions where either b or a is missing). Consider now the two IMPLY-dependencies a ⇒ b and b ⇒ a. It is easy to see that, considering these dependencies, F1 and F2 cannot be considered as possible scenarios, and S becomes a necessary complete i∗ -extension.

Embedding correlations into aiAAFs. We now introduce the forms of dependency that we allow to use for encoding the known correlations. In order to make the task of specifying them easy and intuitive, we consider dependencies expressed by commonly used logical connectives.

Definition 4 (Dependency) A dependency δ over an aiAAF IF = 〈A,A? ,D〉 is an expression X ⇒ Y (IMPLY∨- dependency) or OP(X) (OP-dependency), where OP ∈ {OR, NAND, CHOICE} and X, Y are non-empty subsets of A? .

Imposing dependencies allows the user to distinguish "valid" completions from "invalid" completions (i.e. scenarios that can actually occur from impossible scenarios).

Definition 5 (Valid completion) A completion F =

〈A′ ,D′ 〉 is valid w.r.t a dependency δ (written F |= δ) iff

• δ is OR(X) and X ∩A′ ̸= ∅,
• δ is NAND(X) and X ∩A′ ⊂X,
• δ is CHOICE(X) and |X ∩A′ | = 1,
• δ is X ⇒ Y and, if X ⊆ A′ , then Y ∩A′ ̸= ∅.

F is valid w.r.t. a set of dependencies ∆ if ∀δ ∈ ∆ F |= δ.

Thus, an OR- (resp., CHOICE-) dependency imposes that at least (resp., exactly) one of the specified arguments is in the completion; a NAND-dependency imposes that the specified arguments cannot occur all together; IMPLY∨ means that if a completion contains all the arguments on the left-hand side, then it must contain at least one of the arguments of the right-hand side. We did not consider AND and NOR as here they make no sense: an AND- (resp., NOR-) dependency requires that each (resp., none) of the specified arguments is in the completion, but this can be done by putting these arguments in A (resp., removing these arguments from A? ).

Definition 6 (daiAAF) An argument-incomplete Abstract Argumentation Framework with dependencies (daiAAF) is a pair DIF = 〈IF, ∆〉, where IF is an aiAAF and ∆ a set of dependencies over IF .

The completions of a daiAAF DIF = 〈IF,∆〉 are the completions of IF, and the valid completions of DIF are the completions valid w.r.t. ∆. The notion of i∗ -extension is naturally adapted to daiAAFs to take into account in the reasoning only the valid completions.

Definition 7 (i∗ -extensions over daiAAFs) Given a daiAAF DIF and a semantics σ, a set of arguments S is a possible (resp., necessary) i∗ -extension for DIF (under σ) if, for at least one (resp., for every) valid completion F of DIF, the set S is an extension of F under σ.

Motivation of the forms of the dependencies and their expressiveness. In the context of abstract argumentation, since the structure of arguments is not modeled, it is reasonable to model correlations as propositional formulae over sets of variables representing the presence of arguments. Now, any propositional formula Φ of this kind can be expressed as a set of dependencies of our form. In fact, every clause C of a CNF Φ can be translated into a single dependency, reasoning by cases on the form of C:

• C = x1 ∨ · · · ∨ xn (i.e. C contains only positive literals): C is equivalent to OR(x1, · · · , xn),
• C = ¬x1 ∨ · · · ∨ ¬xn (i.e. C contains only negative literals): C is equivalent to NAND(x1, . . . , xn),
• C = ¬x1 ∨ · · · ∨ ¬xm ∨ xm+1 ∨ · · · ∨ xn (i.e. C contains both positive and negative literals): C is equivalent to x1, . . . , xm ⇒ xm+1, . . . , xn

Thus, a first motivation for considering these forms of dependency is that they are "maximally" expressive (w.r.t. what is reasonably supposed to be expressible).

Observe that what said above means that CHOICEdependencies are not strictly necessary, as they could be translated into sets of dependencies of the other forms. However, our choice to include CHOICE as a form of dependency is aligned with the rationale of expressing the correlations as a set of dependencies rather than as a propositional formula with ∧, ∨, ¬ and brackets: providing the analyst with a set of "intuitive" primitives, whose name explicitly describes the semantics of the correlations. Furthermore, in practical cases, encoding the correlations into the set ∆ gives the possibility to distinguish the various forms of correlations imposed by the analyst, which could be otherwise "hidden" if a general propositional formula were used. This allows us to provide the contribution presented in the next section: a finegrained analysis of the impact of correlations on the computational complexity of the fundamental reasoning problems over aiAAFs. This contribution is still of interest if a propositional formula is used to encode correlations instead of the set of dependencies: our study can be viewed as a sensitivity analysis of the complexity of the reasoning tasks w.rt. some syntactic restrictions of practical interest.

4 Reasoning over daiAAFs

We first introduce two fundamental problems that support the reasoning over daiAAFs and that are the object of our study.

Definition 8 (DSAT) DSAT is the problem of verifying the existence of a valid completion of a given daiAAF DIF .

Definition 9 (PDVERσ (S)) Let DIF be a daiAAF, S a set of arguments, and σ a semantics. PDVERσ (S) is the problem of verifying if S is a possible i∗ -extension for DIF under σ.

Basically, DSAT is the problem of deciding if the set of dependencies specified in a daiAAF is not contradictory, and is somehow preliminary to the reasoning task encoded by the verification problem PDVERσ (S). As for the latter, observe that we focus on the possible perspective, and defer the study of the verification of necessary i∗ -extensions to future work.

We thoroughly analyze the complexity of DSAT and PDVERσ (S): we investigate its sensitivity to the form of dependencies appearing in the daiAAF and, for PDVERσ (S), also to the semantics σ. In order to obtain fine-grained insights on the sources of complexity, we include in our analysis two restrictions of the dependencies of Definition 4, namely CHOICE2 -dependency (i.e. an CHOICE over a pair of arguments) and IMPLY-dependency (i.e. a⇒with a singleton on the right-hand side, thus no disjunction in the head).

The results are summarized in Table 1. Here, EMPTY means ∆ = ∅, and the corresponding row is a result from [Fazzinga et al., 2020], where the verification problem over iAAFs (with no dependencies) was shown to be in P for σ ∈ {ad, st, co, gr} and Σp2 -complete for σ = pr. ANY OTHER stands for "any combination of 2, 3, or more forms of dependencies different from the combinations in the other rows". The combinations summarized in ANY OTHER are those whose complexity is implied by the other rows. This does not happen, for instance, for OR+NAND, that is in a distinguished row: in this case, the NP-completeness of DSAT and of PDVERσ (S) under σ ∈ {ad, st} is not implied by the polynomiality of these problems with only OR or only NAND.

The relevance of our sensitivity analysis is that, besides giving an insight on the sources of complexity of DSAT and PDVERσ (S), it highlights the presence of restrictions (to the set of logical connectives) that are of practical interest (as they still allow the analyst to model several scenarios) and that make reasoning over daiAAFs an efficient task.

Complexity of DSAT. The correctness of the results in Table 1 on DSAT is stated in the following theorem. Observe that, in Table 1, "Trivial" means that DSAT is always true.

This is obvious for the case where ∆ = ∅, and can be straightforwardly seen in the other cases: when at most IMPLY∨ and OR are allowed, the completion containing all the uncertain arguments is always valid; when at most IMPLY∨ and NAND are allowed, the completion where all the uncertain arguments are discarded is valid.

Theorem 1 The complexity of DSAT, for the various restrictions on the set of allowed forms of dependencies, is that reported on the second column of Table 1.

Complexity of PDVERσ (S). We first introduce general upper bounds for PDVERσ (S) that are independent from the allowed forms of dependencies.

Theorem 2 PDVERσ (S) is in NP for σ ∈ {ad, st, co, gr} and in Σp2 for σ = pr.

The following two theorems distinguish two cases where this upper bound is not strict, as PDVERσ (S) is in P.

Theorem 3 PDVERσ (S) is in P if σ ∈ {ad, st} and only IMPLY+NAND or only one among OR, NAND, IMPLY, CHOICE2 is allowed.

Theorem 4 PDVERσ (S) is in P when σ = co and only OR dependencies are allowed.

We now move to the cases not covered by Theorems 3, 4, showing that the upper bounds of Theorem 2 become strict. For some rows of Table 1 (i.e. 6, 8, 9, 10, 11, 16), this is implied by the following proposition, entailing that if DSAT is NP- hard, also PDVERσ (S) is NP-hard.

Proposition 1 For any σ ∈ {ad, st, co, gr, pr}, there is a Karp-reduction from DSAT to PDVERσ (S), where the dependencies allowed in PDVERσ (S) and DSAT are the same.

Proof. Given an instance I sat of DSAT consisting in the daiAAF 〈IF,∆〉, consider the instance I ver of PDVERσ (S) consisting in the pair 〈〈IF ′ ,∆〉, S〉, where IF ′ is IF augmented with a new argument x attacking all the arguments in IF, and S = {x}. It is easy to see that the answer of I sat coincides with the answer of I ver for any σ. ✷

We now consider the cases where DSAT is not NP-hard, thus the NP lower bound for PDVERσ (S) must be proved.

Theorem 5 If only OR-dependencies are allowed, PDVERσ (S) is NP -hard under σ = gr.

Proof. We show a reduction from SAT. Let Φ be a 3CNF and DIF(Φ) = 〈〈A,A? ,D〉,∆〉 be the daiAAF constructed as follows. For each variable xi in Φ, A contains the pair of arguments i, i′ and A? the pair of arguments xi, ¬xi, while D contains the four attacks (xi, i), (i, ¬xi), (¬xi, i′ ), (i′ , xi), and ∆ contains the dependency OR(xi, ¬xi). Moreover, for each clause Cj = lj1 ∨ lj2 ∨ lj3 in Φ (where every lj i is a literal), ∆ contains OR(lj1 , lj2 , lj3 ). See the left-hand side of Fig. 2 for an example of construction. We prove the equivalence: "Φ is satisfiable" ⇔ "S = {1, 1′ , 2, 2′ , . . . , n, n′ } is a possible i∗ -extension of DIF (Φ) under σ = gr".

⇒: Given a truth assignment ta making Φ true, let F be the completion of IF(Φ) containing, for each i ∈ [1..n], the argument xi if ta(xi)= true, and ¬xi otherwise. Obviously, F is a valid completion. Moreover, S is the grounded extension for F since, for each i ∈ [1..n], one of the arguments i, i′ is attacked by no argument, and defends the other one.

⇐: Let F be a valid completion whose grounded extension is S. Since S contains, for each i ∈ [1..n], both i and i′ , at least one of the arguments xi, ¬xi must not belong to F. Combining this with what imposed by dependency OR(xi, ¬xi), we have that F contains exactly one of these arguments, for each i ∈ [1..n]. Hence, F encodes a truth assignment ta for x1, . . . , xn, where ta(xi) = true iff xi belongs to F. As F is valid, the OR-dependencies encoding the clauses of Φ are satisfied, thus ta is a truth assignment making Φ satisfied. ✷

Theorem 6 If only IMPLY-dependencies are allowed, PDVERσ (S) is NP -hard under σ ∈ {co, gr}.

Proof. We prove the case σ = co (the same reasoning works for σ = gr). We show a reduction from SAT. Let Φ be a 3CNF and DIF(Φ) = 〈〈A,A? ,D〉,∆〉 the daiAAF constructed as follows. For each variable xi, A? contains the two arguments xi, ¬xi, and the argument 2vi (meaning that two truth values have been assigned to xi), while A contains the argument nai (meaning that xi has not been assigned a truth value). In turn, D contains the attacks (xi, xi), (¬xi, ¬xi), as well as (xi, nai) and (¬xi, nai). Moreover, for each clause Cj = lj1 ∨ lj2 ∨ lj3 , A? contains the argument ¬Cj , and ∆ the dependency lj1 , lj2 , lj3 ⇒ ¬Cj, where ljk is the argument representing the negation of ljk , for each k ∈ [1..3]. Finally, ∆ contains xi, ¬xi ⇒ 2vi, for each i ∈ [1..n]. See the righthand side of Fig. 2 for an example of construction. We prove the equivalence: "Φ is satisfiable" ⇔ "∅ is a complete i∗ - extension for DIF (Φ)".

⇒: Given a truth assignment ta for x1, . . . , xm making Φ true, let F be the completion of DIF(Φ) containing, for each i ∈ [1..n], the argument xi if ta(xi) = true, and ¬xi otherwise, but no other argument from A? . Obviously, F is valid, since: 1) putting in F exactly one between xi and ¬xi does not trigger any implication xi, ¬xi ⇒ 2vi (which would have required the presence of 2vi in F); 2) as ta makes Φ true, no implication lj1 , lj2 , lj3 ⇒ ¬Cj is triggered in F. Moreover, F admits no admissible extension other than ∅: an admissible extension S can contain no argument of the form xi or ¬xi (since they are self-attacking arguments), and no argument nai (since these arguments cannot be defended from the attacks from xi or ¬xi).

⇐: Let F be a valid completion whose complete extension is S = ∅. The validity of F and the fact that S = ∅ imply that, for each i ∈ [1..n], F contains at most one between xi and ¬xi (otherwise, the dependency xi, ¬xi ⇒ 2vi would have implied the presence of 2vi in F, and since this argument is not attacked, it should belong to S). Moreover, since ∅ is complete, there can be no unattacked nai. Since the only attacks towards nai in D are from xi and ¬xi, this means that F, for each i ∈ [1..n], contains exactly one between xi and ¬xi. Hence, F encodes a truth assignment ta for x1, . . . , xn, where ta(xi) = true iff xi belongs to F. Since ∅ is a complete extension, it means that F contains no argument ¬Cj (if there were some ¬Cj in F, it would be not attacked and thus present in S). This means that, for every clause Cj, no IMPLY-dependency with ¬Cj on its right-hand side is triggered in F, thus ta makes all the clauses true. ✷

The remaining NP -hard cases are stated in the Theorem 7.

Theorem 7 If only NAND- or only CHOICE2 - dependencies are allowed, PDVERσ (S) is NP-hard under σ ∈ {co, gr}. If only IMPLY∨- or only IMPLY+OR- dependencies are allowed, PDVERσ (S) is NP-hard under σ ∈ {ad, st, co, gr}.

Finally, we consider the preferred semantics. Here, the lower bound is implied by the literature of aiAAFs without dependencies [Baumeister et al., 2018].

Theorem 8 PDVERσ (S) is Σp2 -hard under σ = pr.

4.1 Summary and Discussion of the Results

As for DSAT, the satisfiability for some forms of dependencies (see rows 1-5, 12-15 of Table 1) is always guaranteed, for others (CHOICE2 ) it can be checked in polynomial time, and for all the other cases DSAT is NP-complete. Observe that the expressiveness of the (combined) forms of dependencies for which DSAT is NP -complete is not necessarily the same: for instance, it is easy to see that our CHOICE-dependencies (for which DSAT is NP-complete) are not sufficient to express some correlations encoded by a propositional formula.

As for PDVERσ (S), our analysis highlights three sources of complexity: 1) the forms of dependencies, 2) the semantics of extensions, and 3) the combination of 1) and 2). In fact, when DSAT is NP-hard, also PDVERσ (S) is NPhard. However, even for the (combined) forms of dependencies making DSAT trivial or in P, PDVERσ (S) may be hard. Specifically, whatever the form of dependency is, PDVERσ (S) is Σp2 -complete under σ = pr, and NPcomplete under σ = gr. However, the Σp2 -hardness under σ = pr is independent from the presence of dependencies (since it holds even over "traditional" aiAAFs, where ∆ = ∅), while under σ = gr PDVERσ (S) is in P if ∆ = ∅. The remaining combinations 〈 form of dependency, semantics 〉 are more intricate. Specifically, under σ = co, PDVERσ (S) is in P only if we restrict ∆ to contain only OR-dependencies. Under σ ∈ {ad, st}, PDVERσ (S) is in P only if we restrict ∆ to contain OR-dependencies, or CHOICE2 -dependencies, or combinations of IMPLY- and NAND- dependencies. Allowing combinations of dependencies behind these polynomial cases makes the complexity explode.

5 RelatedWork

i∗ -extensions have been introduced in [Fazzinga et al., 2020] as a revision of the i-extensions defined in [Baumeister et al., 2018]. The difference between i∗ - and i- extension is in the set used to decide if S is an extension: in the latter, the projection of S over the completions is used, rather than S. This projection can cause counter-intuitive side-effects, e.g., even a conflicting set can be an i-extension. In fact, the notion of accepted arguments used in the literature of iAAFs [Baumeister et al., 2021] corresponds to argument belonging to some (or every) i∗ -extension (and not i-extension). Our sensitivity analysis does not apply to i-extensions as PDVERσ (S) in that case is already NP -complete for σ = ad.

Constraints in argumentation have been little investigated. In [Coste-Marquis et al., 2006], AAFs are augmented with a propositional formula with the aim of refining the set of extensions. They do not consider uncertain terms. In the dynamic scenario, [Wallner, 2020] considers constraints to limit the admitted structural modifications when the sets of arguments and attacks are updated on abstract dialectical frameworks (ADFs) [Brewka et al., 2017]. In this regard, the general relationship between argument-incomplete AAFs and ADFs needs some further investigation as the latter may be capable of encoding uncertain arguments and correlations.

Beside the already mentioned, other works dealing with uncertainty in AAFs are the following. The Partial Argumentation Framework (PAF) [Cayrol et al., 2007] mainly differs from iAAFs since the semantics of extensions is not based on completions, but on a revised notion of admissibility (where, depending on the desired level of cautiousness, only certain attacks or also uncertain attacks must be defended). Reasoning over iAAFs' extensions is also related to revising AAFs to enforce the existence of an extension [Baumann and Ulbricht, 2019], or to make a set an extension [Coste-Marquis et al., 2015] (where, however, only minimal sets of changes are considered), and to the credulous/skeptical conclusion problems in Control Argumentation Frameworks (CAFs) [Dimopoulos et al., 2018]. In this regard, embedding correlations in CAFs is an interesting research direction.

Several variants of AAFs where the uncertainty is quantitatively specified have been proposed. Some of them allow the specification of preferences and/or weights [BenchCapon, 2003; Amgoud and Vesic, 2011; Modgil, 2009; Dunne et al., 2011; Coste-Marquis et al., 2012; Brewka et al., 2014]. In other approaches, uncertainty is specified via probabilities, according to the "epistemic" [Thimm, 2012; Hunter and Thimm, 2014]), or the "constellation" paradigm (prAAFs) [Hunter, 2014; Dung and Thang, 2010; Doder and Woltran, 2014; Dondio, 2014; Hunter, 2012; Li et al., 2011; Fazzinga et al., 2015]. The last ones are the most related to our framework, as prAAFs can be seen as iAAFs where a probability distribution (pdf) is defined over the completions. Typically, the correlations are hidden in the specified pdf, that is defined by enumerating the completions and explicitly assigning a probability to each of them. Up to our knowledge, the only form of prAAF allowing the explicit specification of correlations is IND-D [Fazzinga et al., 2019], but only mutual exclusion and co-existence can be expressed.

6 Conclusions

An extension of argument-incomplete AAFs has been investigated, where the analyst is allowed to specify correlations among the uncertain arguments by imposing different forms of dependencies. The impact of the presence of correlations on the complexity of the satisfiability and the verification problems (under the possible perspective and for Dung's semantics) has been thoroughly investigated, by studying the sensitivity of the complexity to the form of dependencies used to define the correlations. Future directions of research stemming from this work are extending our study to characterize the complexity of the verification problem under the necessary perspective, and the search for islands of tractability for the NP-hard cases related to syntactic restrictions of the logical connectives that are still of practical interest.