On Merging Incompleteness and Bipolarity in Abstract Argumentation

Abstract

In this paper we discuss Incomplete Bipolar Argumentation Frameworks (iBAFs) proposed in [1]. iBAFs are the extension of Dung's Abstract Argumentation Frameworks (AAFs) allowing the simultaneous presence of supports (borrowed from BAFs - Bipolar AAFs) and of uncertain elements of the argumentation graph (borrowed from iAAFs - incomplete AAFs). We discuss the computational complexity of verification problem (under the possible perspective) and the acceptance problem, by showing how it varies depending on the semantics of supports and the semantics of extensions. On the one hand, we show that adding supports on top of incompleteness does not affect the complexity of the acceptance. On the other hand, surprisingly, we show that the joint use of bipolarity and incompleteness has a deep impact on the complexity of the verification: for the semantics under which the verification over AAFs is polynomialtime solvable, although moving from AAFs to BAFs or to iAAFs does not change the complexity, the complexity of the verification over iBAFs may increase up to NP-complete.

1. Introduction

In the recent years, owing to the usefulness exhibited by Dung’s Abstract Argumentation Framework (AAF [ 2 ]) in various contexts (ranging from legal disputes [ 3 ] to process mining [ 4 ]), many extensions of AAFs have been proposed to enhance their modeling capability. Two directions have attracted particular attention: encoding support relationships between arguments, and taking into account possible uncertainty involving arguments and attacks. The efforts in the former direction have led to Bipolar AAFs (BAFs), a family of variants of AAFs differing from one another in the semantics of supports. Two well-established semantics of supports (to which those in [ 5, 6, 7 ] are added) are the abstract semantics [ 8 ], where a support encodes a positive interaction between arguments (semantically opposite to the meaning of attack), and the deductive semantics [ 9 ], where supports encode a “deductive” correlation: “ supports ” means that the acceptance of implies the acceptance of . The introduction of supports following these semantics has called for extending the reasoning paradigm defined over AAFs, since combining supports and attacks yields “implicit” attacks, called supported and supermediated attacks, as shown in Example 1.

AAF, BAF iAAF d-iBAF s-iBAF P admissible s-ad P

P NP-compl P

NP-compl P

stable complete grounded c-ad d-st s-st c-st d-co s-co c-co d-gr s-gr

P P P P P P P NP-compl NP-compl P NP-compl in NP NP-compl in NP

preferred c-gr d-pr s-pr c-pr coNP-compl Σ2-compl Σ2-compl Σ2-compl

Example 1. The BAF in Figure 1() has “explicit” attacks (solid-line arrows) and supports (double-line arrows), as well as “implicit” attacks (not shown in the figure). In fact, whatever the semantics of supports (abstract or deductive), the facts that supports and that attacks imply the so called “supported attack” (, ). Moreover, under the deductive semantics, since the acceptance of a supporting argument implies the acceptance of the supported argument, also the so called “supermediated attack” (, ) should be considered, implied by the facts that is attacked by and supported by .

The second direction of research has led to several variants of AAFs, where the uncertainty affecting arguments and attacks is modeled qualitatively, by allowing the uncertain aspects of the dispute to be specified, or quantitatively, by also allowing the specification of the extent of this uncertainty. Incomplete AAFs (iAAFs) [ 10 ] are prominent representatives of qualitative approaches. Basically, an iAAF is an AAF where some arguments and/or attacks are marked as uncertain, as their occurrence in the dispute is not guaranteed. To address this form of incompleteness, the reasoning paradigm of AAFs has been refined to consider the multiple scenarios for the argumentation graph implied by the uncertainty, as shown in Example 2. Example 2. Figure 1(b) is an iAAF where the argument and the attack (, ) are uncertain. This iAAF compactly represents the four AAFs in Figure 1(c), called “completions”, representing the alternative combinations of presence/absence for and (, ). The existence of alternative scenarios has been taken into account in the literature by revising the notion of “extension” into “i* -extension”, under two perspectives: a set is a “possible” (resp., “necessary”) * -extension if it is an extension (in the classical sense) in at least one (resp., every) completion of the iAAF. Thus, under the complete semantics, {, } is a possible (but not necessary) i* -extension (as it is an extension only in the rightmost completion), while {, } is a necessary (thus, also possible) i* -extension.

e b c (a) a f d b ? a c (b) d ? b d b

d c c (c) b a c d b

d a c

In the literature, there are several works investigating suitable adaptions of the traditional extension-based reasoning paradigm to BAFs, iAAFs [ 10 ] and their variants. A fundamental result [ 11, 12 ] is that reasoning over BAFs, in terms of verifying extensions, is the same as over AAFs, under the so called “Dungean” semantics (i.e. the admissible, stable, grounded, complete, preferred semantics), independently from the semantics of supports (abstract or deductive) and the coherence condition underlying the semantics – in fact, in the presence of supports, it may make sense to consider more general coherence conditions than the coniflct-freeness. This means that the verification problem over BAFs is coNP-complete under the preferred semantics and in P under every other Dungean semantics. The same holds for iAAFs, with the only exception of the preferred semantics under the possible perspective [ 13 ]: in this particular case, the verification problem’s complexity moves from coNP-complete to Σ2-complete. In the other cases, the complexity is the same as over AAFs: it is in coNP under the preferred semantics in the necessary perspective, and in P under the other Dungean semantics, whatever the perspective. In other words, using BAFs to specify supports or iAAFs to specify uncertain arguments/attacks does not make the reasoning computationally more complex than over AAFs.

In this paper, we discuss Incomplete Bipolar AAFs (iBAFs), that, pushed by the popularity of BAFs and iAAFs, were recently proposed in [ 1 ]. Basically, iBAFs augment AAFs with (abstract or deductive) supports and the possibility of specifying which arguments, attacks, and supports are uncertain. The need for introducing uncertain supports was thoroughly discussed in [ 14 ], where an empirical study investigating how different people perceive the relationships between arguments was presented and showed that, analogously to the case of attacks, it often happens that, for a pair of arguments , , some people may see a support from to , while others may not. This clearly calls for resorting to the notion of uncertain support when merging different subjective views into a single AAF. As a real-life example motivating uncertain supports under the deductive perspective (the case of abstract supports is covered by several examples in [ 14 ]), consider the arguments below, claimed in a trial against a company PharmaX producing a vaccine: : “As drug preparations must be sterile, mercury was used by PharmaX as an excipient of the vaccine”; : “As the vaccine contains harmful ingredients, it should not have been used on humans.”

Now: 1) some jurors believing that mercury is harmful may see a deductive support (, ), as they believe that if is accepted then is accepted too; 2) other jurors believing that mercury is dangerous may not see this support, since they adopt a more ”scientific” reasoning: they think that even if is accepted, may not be accepted, since does not take into account that toxicity may be dosage-dependent; 3) jurors believing that mercury is safe probably see no correlation between and , and so on.

Starting from this, we review the results published in [ 1 ] on the computational complexity of the reasoning over iBAFs, and consider both the verification problem (for which we investigate the variant IBVER under the possible perspective) and the acceptance problem. Interestingly, we observe that, while adding bipolarity on top of incompleteness does not affect the complexity of the acceptance problem (as it can be easily shown to coincide with the case of iAAFs, where supports cannot be specified), the simultaneous presence of bipolarity and incompleteness makes things much more intricate for the verification than the case where these aspects do not occur or do not co-exist, as the complexity of IBVER depends on the combination ⟨semantics of supports, semantics of extensions⟩: 1) under the stable and the preferred semantics, IBVER is in P and Σ2-complete, respectively, meaning that there is no additional source of complexity compared with BAFs and iAAFs; 2) under the other Dungean semantics, IBVER may become intractable (NP-complete), depending on the semantics of supports and on the coherence condition underlying the semantics of extension, meaning that in these cases new sources of complexity can arise from the joint use of supports and incompleteness.

The results on the verification problem are summarized in Table 1, looking into which it is possible to appreciate that in some cases IBVER under the (variants of) the stable semantics is in P while it is NP-complete under (variants of) the admissible semantics. This is rather unusual in the context of frameworks generalizing AAFs, as typically the verification problems under the admissible and stable semantics lie in the same complexity class.

2. Preliminaries

We assume that the reader is familiar with Abstract Argumentation Frameworks (AAFs) and review Bipolar Abstract Argumentation Frameworks (BAFs). We do not provide specific preliminaries for incomplete AAFs (iAAFs) since what said in the introduction about them provides a sufficient background.

Definition 1 (BAF). A bipolar abstract argumentation framework (BAF) is a tuple ℱ = ⟨, ℛ, ℛ⟩, where is a set of arguments, while ℛ ⊆ × and ℛ ⊆ × are relations whose elements are called attacks and supports, respectively.

If ℛ (resp., ℛ) contains (, ), we say “ attacks ” or “ → ” (resp., “ supports ” or “ ⇒ ”). Moreover, for every (, ) in the closure of ℛ, we say that “ transitively supports ” or ⇒+ . Since in the following we will introduce forms of attack other than those encoded by ℛ, those in ℛ will be referred to as “direct attacks”. In what follows, all the definitions and notions regarding BAFs will be reviewed by assuming that a BAF ℱ = ⟨, ℛa, ℛs⟩ is given.

In the first proposal of BAF [ 8 ], supports were given an abstract semantics, that is the opposite of the traditional semantics of attack in AAFs. According to this semantics. the combination of supports and direct attacks implies further attacks, called supported attacks.

Definition 2 (Supported attack). Let , ∈ . There is a supported attack from to (written →s ) iff there is ∈ such that ⇒+ ∧ → .

Among the other semantics for supports in the literature, we consider the well-established deductive semantics [ 9 ]: “ supports ” means that if is accepted, then is accepted. As observed in [ 12 ], adopting this semantics calls for considering not only direct and supported attacks, but also supermediated attacks.

Definition 3 (Supermediated attack). Let , ∈ . There is a supermediated attack from to (written as →m ) iff there is an argument ∈ such that ⇒+ ∧ ( →s ∨ → ). Example 3. The BAF in Figure 1() has the “direct” attacks (, ), (, ), (, ), the supports (, ), (, ), the supported attack (, ), and the supermediated attacks (, ), (, ).

We partition BAFs into s-BAFs and d-BAFs: s-BAFs (resp., d-BAFs) adopt the abstract (resp., deductive) semantics, so only direct and supported attacks (resp., direct, supported and supermediated) are considered. In BAFs of any type, →* will denote the existence of a “generic attack” from to : that is, over s-BAFs, →* ≡ → ∨ →s , while, over d-BAFs, →* ≡ → ∨ →s ∨ →m .

The classical notion of defense becomes: given , ∈ such that →* , the set defends against if ∃ ∈ s.t. →* . In turn, ∈ is acceptable w.r.t. ⊂ if ∀ ∈ such that →* , defends against .

2.1. Semantics of extensions

Three different requirements for coherence were defined: “conflict-freeness”, “safety”, and “support closedness”.

Definition 4 (Conflict-freeness, safety, support closedness). A set of arguments is conflictfree iff ̸ ∃ ∈ such that →* , is safe iff ̸ ∃ ∈ such that →* ∧ ( ⇒+ ∨ ∈ ), and is closed for ℛ iff ̸ ∃ ∈ ∖ such that ⇒ .

When moving from AAFs to BAFs, the classical semantics of extensions can be adapted by imposing different combinations of coherence requirements. In particular, we consider the following classical semantics (denoted as “Dungean semantics”): admissible (ad), stable (st), complete (co), grounded (gr), preferred (pr), and start with reviewing the adaptions of the admissible one. A set ⊆ that defends all of its arguments is 1) a d-admissible (Dungadmissible) or d-ad extension iff is conflict-free; 2) an s-admissible (Safe-admissible) or s-ad extension iff is safe; 3) a c-admissible (Closure-admissible) or c-ad extension iff is conflict-free and closed for ℛ. Given this, is an extension of type: – d-complete or d-co (resp., s-co, c-co) iff is d-ad (resp., s-ad, c-ad) and contains every acceptable argument; – d-grounded or d-gr (resp., s-gr, c-gr) iff is a minimal (w.r.t. ⊆ ) d-co (resp., s-co, c-co) extension; – a d-preferred or d-pr (resp., s-pr, c-pr) iff is a maximal (w.r.t. ⊆ ) d-co (resp., s-co, c-co) extension.

Analogously, a set ⊆ is a d-stable or d-st (resp., s-st, c-st) extension iff ∀ ∈ ∖ →* and is conflict-free (resp., is safe; is conflict free and closed for ℛ). Example 4. In the BAF in Figure 1(), {, , } is conflict-free and safe, but is not a d-ad extension for s-BAF or d-BAF (since is not defended). Furthermore, for the s-BAF case, {, } is a s-ad, s-gr and s-pr extension, {, , } is a st, d-ad, d-gr, and d-pr extension, {, } is a c-pr and c-gr extension. For the d-BAF case {, } is the unique st extension, that is also c-pr and c-gr.

Remark 1. Safety implies conflict-freeness, and these two requirements are equivalent in dBAFs (but not in s-BAFs). So, in d-BAFs, the d- and s- variants of every semantics coincide. Furthermore, in d-BAFs, the three variants of the semantics st coincide, as the conflict-freeness and the requirement that an extension attacks every argument outside implies that can support no argument outside itself.

We denote as BVER (ℱ , ) the fundamental problem of verifying if the set of arguments is an extension over the BAF ℱ under the semantics . It is well known that the computational complexity of BVER under any x-variant (with x ∈ {s, d, c}) of a classical Dungean semantics is the same as the verification problem VER for AAFs under , as observed in [ 15 ]. The reason is that checking if is an extension of a BAF ℱ under x- can be done by first checking if is a -extension of the AAF obtained from ℱ by materializing all the implicit attacks and removing the supports, and then checking over ℱ the coherence requirements of x.

3. Incomplete BAFs (iBAFs)

We extend incomplete AAFs (iAAFs) [ 16, 10, 17, 18, 13, 19 ] to incomplete BAFs (iBAFs). Definition 5 (iBAF). An incomplete Bipolar Abstract Argumentation Framework is a tuple ⟨, ?, ℛ, ℛ?, ℛ, ℛ?⟩, where , ? are disjoint sets of arguments, ℛ and ℛ? disjoint sets of attacks between arguments in ∪ ?, and ℛ and ℛ? disjoint sets of supports between arguments in ∪ ?.

The arguments in are said to be certain (they are definitely known to exist), while those in ? uncertain (it is not known for sure if they occur in the argumentation or not). Analogously, the attacks in ℛ and the supports in ℛ are said to be certain (they are known to occur, if both the incident arguments exist), while those in ℛ? and ℛ? uncertain (they may not occur, even if both the incident arguments exist). An iBAF represents alternative scenarios, called completions, corresponding to the different combinations of occurrence/non-occurrence of uncertain arguments/attacks/supports.

Definition 6 (Completion). A completion for an iBAF ℐℱ = ⟨, ?, ℛ, ℛ, ℛ, ℛ?⟩ is a BAF ? ℱ = ⟨′, ℛ′, ℛ′⟩ where ⊆ ′ ⊆ (∪?) and ℛ ∩(′ × ′) ⊆ ℛ ′ ⊆ (ℛ ∪ℛ?)∩(′ × ′) ? and ℛ ∩ (′ × ′) ⊆ ℛ ′ ⊆ (ℛ ∪ ℛ) ∩ (′ × ′).

As happens for iAAFs, the notion of extension in AAFs can be adapted to iBAFs under a possible and a necessary perspective, where the condition imposed by the semantics is required to be true in at least one and every completion, respectively. This yields the definition of i * -extension below.

Definition 7 (i * -extension). Given an iBAF ℐℱ and a semantics , a set is a possible (resp., necessary) i* -extension for ℐℱ (under ) if, for at least one (resp., for every) completion of ℐℱ , is an extension of under .

We focus on possible i* -extensions, and address IBVER (ℐℱ , ), that is the adaption of the verification problem to iBAFs and asks if is a possible i* -extension of ℐℱ under . Example 5. Consider the iBAF ℐℱ obtained from the BAF in Figure 1 imposing that the argument , the attack (, ) and the support (, ) are uncertain. It is easy to see that, under both the abstract and deductive semantics of supports, {, , } is a possible i* -extension of ℐℱ under d-ad (as it is a d-ad extension in the completion where (, ) and (, ) are not present), but it is not a possible i* -extension under s-ad or c-ad (as, in every completion, → and ⇒ ).

Given an iBAF ℐℱ = ⟨, ?, ℛ, ℛ, ℛ, ℛ?⟩, every symbol ◇ ∈ {→ ,→* ,⇒,⇒+} introduced ? for BAFs will be used for ℐℱ with the semantics: ◇ over ℐℱ means that ◇ over the BAF ⟨ ∪ ?, ℛ ∪ ℛ?, ℛ ∪ ℛ?⟩. Moreover, we write ↠ * to say that →* in the BAF ℱ ′ = ⟨′, ℛ′, ℛ′⟩, where ′ = ∪ {, }, ℛ′ = ℛ ∩ (′ × ′), ℛ′ = ℛ ∩ (′ × ′), i.e. there is a generic attack from to even if every uncertain attack, support, and argument (different from both and ) is removed from ℐℱ . For instance, consider the d-iBAF obtained from the BAF in Figure 1() by adding the support (, ). Then, ↠ * , but not ↠ * (since if the uncertain attack (, ) is removed, the supported attack (, ) cannot be triggered).

Attacks and supports will be also considered from sets of arguments to arguments, and from arguments to sets of arguments: for any ◇ ∈ {→ ,→ ,→ ,→* ,⇒,⇒+,↠ * }, ◇ (resp., ◇ ) means s m that there is ∈ such that ◇ (resp., ◇ ). Moreover, we write ℐℱ ∖ , where ⊆ ?, to denote the iBAF obtained from ℐℱ by removing all the arguments in and the attacks and supports involving an argument in .

4. Computational Complexity of Verifying i* -extensions

We here provide a thorough analysis of the complexity of reasoning over iBAFs (in terms of solving IBVER), where the sensitivity to the semantics of supports and the semantics of extensions is studied. Theorem 1 states a general upper bound for the complexity of IBVER. Theorem 1. For both s- and d- iBAFS. IBVER (ℐℱ , ) is in NP under every semantics x- , with x ∈ {s, d, c} and ∈ {ad, st, co, gr}, and in Σ2 under every semantics x-pr, with x ∈ {s, d, c}.

Proof. IBVER (ℐℱ , ) can be solved by guessing a completion ℱ of ℐℱ and then solving BVER (ℱ , ). Thus, IBVER is in NP (resp., Σ2) when BVER is in P (resp., coNP). □ Under the variants of the preferred semantics, it is easy to see that the upper bound of Theorem 1 is tight, so IBVER is Σ2-complete. In fact, the Σ2-hardness holds for iAAFs [ 10 ], that are iBAFs where supports are not used. We now focus on the variants of the other semantics, and show when the upper bound is tight or not. We consider s-and d- iBAFs separately, in order to highlight the role of the supports’ semantics in the complexity.

4.1. Reasoning over s-iBAFs

Theorem 2 states under which semantics IBVER over s-iBAFs is NP-complete. Theorem 2. Over s-iBAFs, IBVER is NP-complete under ∈ {s-ad, d-co, s-co, d-gr, s-gr}.

We now address the semantics not covered above, and show that under them IBVER is in P. Preliminarily, we introduce some properties that may be satisfied or not by a given s-iBAF, and a lemma, that will help the reasoning in the main theorem’s proof.

Definition 8. Properties 1, 2, 3 are satisfied by an s-iBAF ℐℱ = ⟨, ?, ℛ, ℛ, ℛ, ℛ?⟩ ? and a set ⊆ ∪ ? iff: – 1: ℛ? ∩ ︀( ∪ ?)︀ × )︀ = ∅, i.e. there are no uncertain attacks towards ; – 2: ̸ ∃ ∈ ? ∖ s.t. ↠ * , i.e. there are no uncertain arguments that will (generically) attack even if every other uncertain argument/attack/support is removed; – 3: ̸ ∃(, ) ∈ ℛ? s.t. ∈ ∧ ↠ * , i.e. there are no uncertain supports towards certain arguments that will (generically) attack even if every other uncertain argument/attack/support is removed.

Lemma 1. Let ℐℱ = ⟨, ?, ℛ, ℛ?, ℛ, ℛ?⟩ be an s-iBAF and ⊆ ∪ ?. Then: ) under ∈ {d-ad, c-ad, d-st, s-st, c-st}, is a possible i* -extension of ℐℱ iff it is a possible i* -extension of ℐℱ ′ = ⟨, ?, ℛ, ℛ? ∖ ︀( ∪ ?)︀ × )︀ , ℛ, ℛ?⟩; ) under ∈ {d-ad, d-st}, if 1 is satisfied, then, ∀ ∈ ? ∖ s.t. ↠ * , is a possible i* -extension of ℐℱ iff is a possible i* -extension of ℐℱ ′ = ℐℱ ∖ {}; ) under ∈ {d-ad, d-st}, if 1, 2 are satisfied, then ∀(, ) ∈ ℛ? s.t. ∈ ∧ ↠ * , is a possible i* -extension of ℐℱ iff is a possible i* -extension of ℐℱ ′ = ℐℱ ∖ {(, )}.

The theorem below states under which semantics IBVER is in P. Its proof (for the case = d-ad) relies on the correctness of Algorithm 1, that first enforces properties 1 (line 1), 2 (lines 2-3), 3 (lines 4-5) by removing the uncertain attacks/arguments/supports making them violated, and then returns as answer the result of the verification performed over the completion containing all the uncertain arguments/attacks/supports that were not removed. The other cases can be solved via minor changes to the strategy of Algorithm 1.

As for c-co and c-gr, the general NP upper bound of Theorem 1 holds and a tighter characterization is left to future work.

Theorem 3. Over s-iBAFs, IBVER is in P under ∈ {d-ad, c-ad, d-st, s-st, c-st}. Proof. ( = d-ad, the other cases are analogous). We first prove that Algorithm 1 is correct Algorithm 1 Solving IBVER (ℐℱ , ) under = d-ad Input: ℐℱ = ⟨, ?, ℛ, ℛ?, ℛ, ℛ?⟩; ⊆ ∪ ? Output: TRUE iff is a possible i* -extension for ℐℱ under d-ad; 1: ℐℱ′ = ⟨ ′, ′?, ℛ′, ℛ′?, ℛ′, ℛ′?⟩, where

ℛ′′?==ℛ; ?∖′?︀( =∪?;ℛ?)︀ ′× =ℛ)︀; ℛ′ = ℛ; ℛ′? = ℛ? 2: while ∃ ∈ ′? ∖ s.t. ∃ ∈ where ↠ * in ℐℱ′ do 3: ℐℱ′ = ℐℱ′ ∖ {} 4: while ∃(, ) ∈ ℛ′? s.t. ∈ ′ ∧ ↠ * in ℐℱ′ do 5: ℛ′? = ℛ′? ∖ {(, )} 6: ℱ′ = ⟨′ ∪ ′?, ℛ′ ∪ ℛ′?, ℛ′ ∪ ℛ′?⟩ 7: return TRUE if is a d-ad extension of ℱ′; FALSE otherwise (i.e. it returns true iff is a possible i* -extension for ℐℱ under =d-ad). Lemma 1 implies that, under = d-ad, is a possible i* -extension for ℐℱ iff is a possible i* -extension for the iBAF ℐℱ ′ constructed by Lines 1- 5. Thus, to prove the correctness of Algorithm 1, it suffices to prove the equivalence EQ: “ is a d-ad extension of ℱ ′”⇔ “ is a possible i* -extension for ℐℱ ′ under d-ad”, where ℱ ′ is the BAF built at Line 6 and ℐℱ ′ the iBAF buillt by Lines 1- 5. The ⇒ direction is straightforward. We prove the ⇐ direction reasoning by contradiction. Assume that is a possible i* -extension for ℐℱ ′ under d-ad and is not a d-ad extension of ℱ ′. Let ℱ be a completion of ℐℱ ′ such that is a d-ad extension of ℱ . Since is not a d-ad extension of ℱ ′, (at least) one of the following holds: ) ∃, ∈ such that →* , ) ∃ ∈ and ∃ ∈ ′ ∖ such that →* and does not defend against . We show that ) and ) yield contradictions. If ) holds, →* also over ℱ , as all the supports/attacks and arguments that imply the presence of the attack (, ) over ℱ ′ are certain in ℐℱ ′, as implied by 1, 2, 3. Hence, is not a d-ad extension of ℱ , as it is not conflict free, which is a contradiction. If ) holds, properties 1, 2 and 3 imply that →* over ℱ . Hence, since is a d-ad extension of ℱ , → over ℱ , and this, in turn, implies that → over ℱ ′, as every uncertain attack in ℐℱ ′ from towards arguments not in is present in ℱ ′. Therefore, defends against , which is a contradiction. This completes the proof of EQ and of the correctness of Algorithm 1. Then, the statement follows from the fact that that Algorithm 1 runs in polynomial time. □

4.2. Reasoning over d-iBAFs

Theorem 4. Over d-iBAFs, IBVER is NP-complete under ∈ {d-ad, s-ad, d-co, s-co, c-co, d-gr, s-gr, c-gr}.

As for the other semantics, Theorem 5 below states that IBVER is in P for the semantics not considered in Theorem 4 (under which IBVER is NP-complete). For the case = c-ad, the core of the tractability result of Theorem 5 is Algorithm 2. This algorithm first computes the completion ℱ containing all the certain and uncertain arguments/attacks/supports except: 1) the uncertain attacks between arguments in , 2) the uncertain arguments that are supported (via certain supports) by , and 3) the uncertain supports from towards arguments outside . After checking in ℱ if is conflict free and closed for supports (otherwise, it returns FALSE), it considers every undefended attack (, ) towards and tries to remove it from ℱ : it accomplishes this in the two cases where (, ) was uncertain in ℐℱ (in this case, (, ) is directly removed from ℱ ) or was uncertain in ℐℱ (in this case, (, ) is removed as the side effect of removing ). Finally, it returns TRUE if and only if the so obtained ℱ contains no more undefended attacks towards . Basically, the proof of Theorem 5 consists in showing that this strategy is correct: as ℱ is obviously a completion for which is a c-ad extension, the hard part of the proof consists in showing that, if the algorithm returns FALSE, there is no completion (different from ℱ ) for which is a c-ad extension. Theorem 5. Over d-iBAFs, IBVER is in P under ∈ {c-ad, d-st, s-st, c-st}. Proof. Case = c-ad (the other cases can be proved with similar reasoning). We first prove that Algorithm 2 is correct (it returns TRUE iff is a possible c-ad i* -extension of ℐℱ ). The only if direction is straightforward as Algorithm 2 returns TRUE iff is a c-ad extension of ℱ ′, which is a completion of ℐℱ . We prove the if direction reasoning by contradiction. Assume that is a possible c-ad extension of ℐℱ , but Algorithm 2 returns FALSE. If FALSE is returned at line 3, at least one of the following cases holds: 1 : ∃(, ) ∈ ℛ ∩ ( × ); 2 : ∃(, ) ∈ ℛ ∩ ( × ( ∖ )).

1: ℱ′ = ⟨ ′, ℛ′, ℛ′⟩: where Algorithm 2 Verifying c-ad extensions over d-iBAFs Input: ℐℱ = ⟨, ?, ℛ, ℛ?, ℛ, ℛ?⟩; ⊆ ∪ ?; Output: TRUE iff is a possible i* -extension for ℐℱ under c-ad; ′ = ∪ ? ∖ return FALSE ︀( ︀( ℛ ∖ ( × ))︀ ? ? ℛ ∖ ( ×

(′ ∖ )))︀ 2: if is not conflict free and closed for ℛ′ in ℱ′ then 3: 6: 4: ℛ′ = ℛ′ ∖ {(, ) ∈ ℛ?| ∈ ∧ not →* } 5: while ∃(, ) ∈ ℛ′ s.t. ∈ and not →

* do if ∈ ? then ℱ

′ = ℱ′ ∖ {} else return FALSE 7: return TRUE returned at line 6. We use the following claim.

As in both cases there is no completion of ℐℱ where is conflict free and closed for supports, is not a possible c-ad extension of ℐℱ , which is a contradiction. This means that FALSE is c-ad extension of ℱ ′′.

Claim 1. Assume that Algorithm 2 returns FALSE at some iteration of the while loop (lines 5-6), and let be the iteration at which FALSE is returned. Let < and ℱ be the completion generated at the end of the -th step of the while loop. For any completion ℱ ′′ = ⟨′′, ℛ′′, ℛ′′⟩ of ℐℱ , if ′′ ∖ ̸= ∅ or ℛ′′ ∖ ℛ ̸= ∅ or ℛ′′ ∖ ℛ ̸= ∅, then is not a = ⟨, ℛ , ℛ⟩

Let be the while step before the one at which Algorithm 2 returns FALSE. Now, for any ′′ ∖ completion ℱ ′′ of ℐℱ such that ′′ ∖

̸= ∅ or ℛ′′ ∖ ℛ ̸= ∅ or ℛ′′ ∖ ℛ ̸= ∅, Claim 1 implies that is not a c-ad extension of ℱ ′′. Moreover, for any completion ℱ ′′ of ℐℱ such that = ∅ and ℛ′′ ∖ ℛ = ∅ and ℛ′′ ∖ ℛ = ∅, it holds that ∃(, ) ∈ ℛ′′ s.t. ∈ and not →* and (, ) ̸∈ ℛ? and ̸∈ ?, and then is not a c-ad extension of ℱ ′′ either, as attacks but is not attacked by in ℱ ′′. Thus, every completion ℱ ′′ of ℐℱ is such that is not a c-ad extension of ℱ ′′, which is a contradiction. This completes the proof of the correctness of Algorithm 2. The fact that Algorithm 2 runs in polynomial time concludes the proof for = c-ad. The proof for ∈ {d-st, s-st, c-st} is analogous. □

5. The Acceptance Problem

We start from the classical definitions of credulous acceptance (CA) and skeptical acceptance (SA) over AAFs: “CA (, ) (resp., SA (, )) is the problem of deciding if the argument is in at least one (resp., every) extension of the AAF ”.

Then, we consider the adaption of the acceptance problem introduced in [ 17 ] for iAAFs (where supports are not considered). That is, we consider the four variants of the acceptance problem PCA,PSA,NCA,NSA, where the credulous (C) and skeptical (S) perspectives implied by the presence of multiple extensions are combined with the possible (P) and necessary (N) perspectives implied by the presence of multiple completions: one (resp., every) completion of the answer of XA(, , ) is yes.” “PXA (, ) (resp., NXA (, )), where ∈ {C,S}, is the problem of deciding if in at least

Now, we naturally extend the acceptance problem to the case of iBAFs by using the same definition above, with the only difference that now is an iBAF.

In order to provide a complexity characterization of the acceptance problems over iBAFs, we start from what is known about the same problems over iAAFs. A complete picture of the complexity of PCA, NCA, PSA, NSA over iAAFs is given by Table 2, taken from [ 17 ]. From Table 2, it turns out that, except for the trivial case of PSA and NSA under =ad, under the other Dungean semantics PCA, NCA, PSA, NSA over iAAFs are complete for complexity classes above P in the polynomial hierarchy. An immediate consequence is that, except for the above mentioned trivial cases, PCA, NCA, PSA, NSA over (s- and d-) iBAFs are hard for the same classes as over iAAFs, since iAAFs are iBAFs without supports. Moreover, the guess-and-check strategies used in [ 17 ] to prove the memberships work also in the case of s- and d- iBAFs, after a minor change to the check phase. In fact, in the case of iBAFs, the guessed completion is a BAF (while in the case of iAAFs, the guessed completion is an AAF). Hence, the check phase over iBAFs simply consists in performing the same check phase done over iAAFs after two preliminary steps: 1) translating the guessed completion/BAF into an equivalent AAF where the implicit attacks are materialized; 2) checking the coherence condition (conflict-freeness, safety, or support closedness). Since 1) and 2) can be done in polynomial time, the check phase over iBAFs has the same complexity as over iAAFs, thus also the memberships reported in the table above hold for iBAFs.

What said above, along with the fact that, under = x-ad (with x ∈ {d, s, c}), it is straightforward to see that PSA and NSA over iBAFs are trivial (as over iAAFs), proves the following statement.

Theorem 6. The computational complexities of PCA, NSA, PSA and NSA over d-iBAFs and s-iBAFs and for all the coherence conditions (d-,s-,c-) are reported in Table 2.

6. Related Work

BAFs (along with the abstract semantics of supports) were first introduced in [ 8 ], and then revisited in [ 9, 20, 21 ], where the deductive, necessary, evidential semantics (that are comprehensively reviewed in [ 12 ]) were introduced, respectively. We observe that the results in this paper hold also under the necessary semantics, that is dual to the deductive one (as necessary supports are deductive supports in the opposite direction). More recently, alternative supports’ semantics have been proposed in [ 5, 6 ], where supporting arguments are capable of defending the supported arguments. Analogously, the semantics in [ 7 ] pursues the idea of enforcing some monotonicity, in the sense that supports are prevented from decreasing the acceptance degree of arguments (from skeptically to credulously accepted, or even rejected). In fact, the various semantics in the literature catch different intuitions on the meaning of supports, so there can hardly be consensus on which is the most natural one. In this context, this paper has focused on two traditional and well-established semantics of supports, and proposes a line of research that is worth investigating under the other semantics in the literature.

Further related works are those where correlations similar to supports have been investigated, such as the subarguments in [ 22 ] (which are closely related with necessary supports [ 23 ]), the dependencies in [ 24, 25 ], the pro arguments in [ 26 ], as well as the acceptance conditions of Abstract Dialectical Frameworks [ 24 ], that can express different forms of supports.

As for iAAFs, they were introduced in [ 10 ], and their semantics based on i* -extensions in [ 13 ]. Previously, Partial Argumentation Frameworks (PAFs) had been introduced in [ 27 ] to encode incompleteness affecting attacks. The possibility of specifying correlations over iAAFs between uncertain arguments/attacks was studied in [ 18, 19, 28 ], where correlations are expressed in terms of constraints restricting the set of completions to be considered in the reasoning (thus, in spirit, these constraints are different from constraints and preferences studied in the deterministic setting [29, 30, 31]). A recent survey discussing how iAAFs are related to the forms of incompleteness encoded in other variants of AAFs (such as Control Argumentation Frameworks [32]) can be found in [33]. The reasoning over AAFs in the presence of incompleteness is also related to revising AAFs to enforce the existence of an extension [34], or to make a set an extension [35], even when information on the agents who claimed the arguments is available [36]. In this regard, this paper suggests that the enforcement problem over BAFs is worth investigating, since it may raise issues that are not present over AAFs (as the enforcement over BAFs would require the insertion/removal of supports to be considered as a new primitive, that comprises the insertion/removal of groups of attacks).

iBAFs are also related to probabilistic BAFs (prBAFs) [ 15 ], that merge BAFs with prAAFs (i.e. probabilistic AAFs adopting the constellations approach [37, 38, 39, 40, 41, 42]): basically, iBAFs can be viewed as prBAFs where all the uncertain terms of the dispute are independent one from another, and no measure of this uncertainty is given. However, the results in this work are not subsumed by those in [ 15 ], where the problem P-EXT of computing the probability of extensions (that is the probabilistic counterpart of the verification) has been shown to be highly intractable under independence (i.e. FP# -complete) for every combination of semantics of supports and extensions. Indeed, the results obtained for prBAFs neither subsume those in this paper nor make them less surprising: on the one hand, the role of assembling supports and probabilities in the high complexity of P-EXT over prBAFs is blurred by the fact that P-EXT is already FP# -hard under most of Dungean semantics over prAAFs (without supports). On the other hand, the FP# -hardness of P-EXT gives no hint for a tight complexity characterization of IBVER, as the source of complexity related to the counting mechanism underlying probability evaluation is absent in the verification problem (in fact, the literature contains several functional problems complete for “hard” complexity classes, whose decision counterparts are in P).

Finally, the framework in [43] is related to iBAFs since it mixes probabilities, supports (in the form of subarguments [44]) and a form of incompleteness: it allows labelings where some arguments are marked as “OFF” (thus, excluded from the reasoning), but the semantics of “OFF” differs from iBAFs’ “non-occurrence”, since the “OFF” label is propagated to the supporting arguments (and this does not happen with non-occurrence).

7. Conclusions and Future Work

We have discussed iBAFs [ 1 ], that augment AAFs with the possibility of simultaneously specifying supports between arguments (according to the traditional abstract and deductive supports’ semantics) and the presence of uncertain elements of the argumentation graph. We have discussed the results in [ 1 ] on the computational complexity of fundamental reasoning problems, and in particular a surprising result regarding the verification problem under the possible semantics: that is, although bipolarity and incompleteness do not affect the complexity of this problem under the Dungean semantics (except for the preferred semantics) if considered separately, they may have a deep impact on the tractability/intractability of this problem when jointly used. Future work will focus on: 1) the two cases (under the variants c-co and c-gr of the complete and grounded semantics) for which the complexity characterization in this paper was not tight, and 2) extending the study to the necessary perspective of the verification problem, and 3) extending iBAFs with the possibility of specifying correlations between uncertain arguments/attacks/supports, as done in [ 18, 19 ] for arguments and attacks only. [28] J. Mailly, Constrained incomplete argumentation frameworks, in: Proc. Eur. Conf. on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU), 2021, pp. 103–116. [29] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On preferences and priority rules in abstract argumentation, in: Proc. of IJCAI, 2022, pp. 2517–2524. [30] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, Preferences and constraints in abstract argumentation, Preprint of IJCAI, 2023. [31] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, Abstract argumentation framework with conditional preferences, in: Proc. of AAAI, 2023, pp. 6218–6227. [32] A. Niskanen, D. Neugebauer, M. Järvisalo, Controllability of control argumentation frameworks, in: C. Bessiere (Ed.), Proc. Int. Joint Conference on Artificial Intelligence (IJCAI), 2020, pp. 1855–1861. [33] J. Mailly, Yes, no, maybe, I don’t know: Complexity and application of abstract argumentation with incomplete knowledge, Argument Comput. 13 (2022) 291–324. [34] R. Baumann, M. Ulbricht, If nothing is accepted - repairing argumentation frameworks, J.

Artif. Intell. Res. 66 (2019) 1099–1145. [35] S. Coste-Marquis, S. Konieczny, J.-G. Mailly, P. Marquis, Extension enforcement in abstract argumentation as an optimization problem, in: Proc. Int. Conf. on Artificial Intelligence (IJCAI), 2015, pp. 2876—-2882. [36] B. Fazzinga, S. Flesca, F. Furfaro, L. Pontieri, Process mining meets argumentation: Explainable interpretations of low-level event logs via abstract argumentation, Inf. Syst. 107 (2022) 101987. [37] G. Alfano, M. Calautti, S. Greco, F. Parisi, I. Trubitsyna, Explainable acceptance in probabilistic and incomplete abstract argumentation frameworks, Artificial Intelligence 323 (2023) 103967. [38] D. Doder, S. Woltran, Probabilistic argumentation frameworks - A logical approach, in:

Proc. of SUM, 2014, pp. 134–147. [39] B. Fazzinga, S. Flesca, F. Furfaro, Complexity of fundamental problems in probabilistic abstract argumentation: Beyond independence, Artif. Intell. 268 (2019) 1–29. [40] B. Fazzinga, S. Flesca, F. Furfaro, Abstract argumentation frameworks with marginal probabilities, in: Proc. 31st Int. Joint Conference on Artificial Intelligence (IJCAI), Vienna, Austria, 23-29 July 2022, 2022, pp. 2613–2619. [41] A. Hunter, Probabilistic qualification of attack in abstract argumentation, Int. J. Approx.

Reasoning 55 (2014) 607–638. [42] H. Li, N. Oren, T. J. Norman, Probabilistic argumentation frameworks, in: Proc.of TAFA, 2011. [43] R. Riveret, N. Oren, On probabilistic argumentation and subargument-completeness, J. Log.

Comput. 32 (2022) 115–128. [44] R. Riveret, On searching explanatory argumentation graphs, J. Appl. Non Class. Logics 30 (2020) 123–192.

References

[1] B. Fazzinga , S. Flesca , F. Furfaro , Incomplete bipolar argumentation frameworks , in: Proc. Eur. Conf. on Artificial Intelligence (ECAI) , Krakow, Poland, 2023 (IN PRESS).

[2] P. M. Dung , On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games , Artif. Intell . 77 ( 1995 ) 321 - 358 .

[3] H. Prakken , G. Sartor, Law and logic: A review from an argumentation perspective , Artificial Intelligence 227 ( 2015 ) 214 - 245 .

[4] B. Fazzinga , S. Flesca , F. Furfaro , Taking into account “who said what" in abstract argumentation: Complexity results , Artif. Intell . 318 ( 2023 ) 103885 .

[5] N. Potyka , Bipolar abstract argumentation with dual attacks and supports , in: Proc. Int. Conf. on Principles of Knowledge Representation and Reasoning (KR) , 2020 , pp. 677 - 686 .

[6] N. Potyka , Generalizing complete semantics to bipolar argumentation frameworks , in: Proc. Int. Conf. on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU) , 2021 , pp. 130 - 143 .

[7] A. Gargouri , S. Konieczny , P. Marquis , S. Vesic , On a notion of monotonic support for bipolar argumentation frameworks , in: Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS) , 2021 , pp. 546 - 554 .

[8] C. Cayrol , M.-C. Lagasquie-Schiex, On the acceptability of arguments in bipolar argumentation frameworks , in: Proc. of ECSQARU , 2005 , pp. 378 - 389 .

[9] G. Boella , D. M. Gabbay , L. W. N. van der Torre , S. Villata, Support in abstract argumentation , in: Proc. of COMMA 2010 , 2010 , pp. 111 - 122 . URL: https://doi.org/10.3233/ 978-1- 60750 -619-5-111. doi: 10 .3233/978-1- 60750 -619-5-111.

[10] D. Baumeister , D. Neugebauer , J. Rothe , H. Schadrack , Verification in incomplete argumentation frameworks , Artif. Intell . 264 ( 2018 ) 1 - 26 .

[11] C. Cayrol , M.-C. Lagasquie-Schiex, Bipolar abstract argumentation systems , in: Argum. in Artif. Intell., 2009 , pp. 65 - 84 .

[12] C. Cayrol , M.-C. Lagasquie-Schiex, Bipolarity in argumentation graphs: Towards a better understanding , Int. J. Approx. Reasoning 54 ( 2013 ) 876 - 899 .

[13] B. Fazzinga , S. Flesca , F. Furfaro , Revisiting the notion of extension over incomplete abstract argumentation frameworks , in: C. Bessiere (Ed.), Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI , 2020 , pp. 1712 - 1718 .

[14] S. Polberg , A. Hunter , Empirical evaluation of abstract argumentation: Supporting the need for bipolar and probabilistic approaches , Int. J. Approx. Reason . 93 ( 2018 ) 487 - 543 .

[15] B. Fazzinga , S. Flesca , F. Furfaro , Probabilistic bipolar abstract argumentation frameworks: complexity results , in: Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI) , 2018 , pp. 1803 - 1809 .

[16] G. Alfano , S. Greco , F. Parisi , I. Trubitsyna , Incomplete argumentation frameworks: Properties and complexity , in: Proc. of AAAI , 2022 , pp. 5451 - 5460 .

[17] D. Baumeister , M. Järvisalo , D. Neugebauer , A. Niskanen , J. Rothe , Acceptance in incomplete argumentation frameworks , Artif. Intell . 295 ( 2021 ) 103470 .

[18] B. Fazzinga , S. Flesca , F. Furfaro , Reasoning over argument-incomplete aafs in the presence of correlations , in: Z. Zhou (Ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021 , Virtual Event / Montreal, Canada, 19 - 27 August , 2021 , pp. 189 - 195 .

[19] B. Fazzinga , S. Flesca , F. Furfaro , Reasoning over attack-incomplete aafs in the presence of correlations , in: M. Bienvenu , G. Lakemeyer , E. Erdem (Eds.), Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning , KR 2021, Online event , November 3 - 12 , 2021 , 2021 , pp. 301 - 311 .

[20] F. Nouioua , V. Risch , Bipolar argumentation frameworks with specialized supports , in: Proc. of ICTAI , 2010 , pp. 215 - 218 . URL: https://doi.org/10.1109/ICTAI. 2010 . 37 . doi: 10 . 1109/ICTAI. 2010 . 37 .

[21] N. Oren , T. J. Norman , Semantics for evidence-based argumentation , in: Proc. of COMMA , 2008 , pp. 276 - 284 .

[22] D. C. Martínez , A. J. García , G. R. Simari , On acceptability in abstract argumentation frameworks with an extended defeat relation , in: Proc. of COMMA , 2006 , pp. 273 - 278 . URL: http://www.booksonline.iospress.nl/Content/View.aspx?piid= 1948 .

[23] A. Cohen , S. Gottifredi , A. J. García , G. R. Simari , A survey of different approaches to support in argumentation systems , Know. Eng. Review 29 ( 2014 ) 513 - 550 .

[24] G. Brewka , S. Woltran , Abstract dialectical frameworks , in: Proc. of KR , 2010 , pp. 102 - 111 . URL: http://aaai.org/ocs/index.php/KR/KR2010/paper/view/1294.

[25] B. Verheij , The toulmin argument model in artificial intelligence , in: Argum. in Artificial Intelligence , 2009 , pp. 219 - 238 .

[26] B. Irwin , A. Rago , F. Toni , Forecasting argumentation frameworks , in: Proc. Int. Conf. on Principles of Knowledge Representation and Reasoning , (KR) , 2022 .

[27] C. Cayrol , C. Devred , M. Lagasquie-Schiex , Handling ignorance in argumentation: Semantics of partial argumentation frameworks , in: Proc. Conf . Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU), Hammamet , Tunisia, 2007 , pp. 259 - 270 .