Computing extensions’ probabilities over probabilistic Bipolar Abstract Argumentation Frameworks Bettina Fazzinga1 , Sergio Flesca2 , Filippo Furfaro2 , and Francesco Scala2 1 ICAR-CNR, Italy 2 DIMES - University of Calabria, Italy Abstract. Probabilistic Bipolar Abstract Argumentation Frameworks (prBAFs), combining the possibility of specifying supports between arguments with a prob- abilistic modeling of the uncertainty, have been recently considered [34, 35] and the complexity of the problem of computing extensions’ probabilities has been characterized [22]. In this paper we deal with the problem of computing exten- sions’ probabilities over prBAFs where the probabilistic events that arguments, supports and defeats occur in the real scenario are assumed to be independent probabilistic events (prBAFS of type IND). Specifically an algorithm for effi- ciently computing extensions’ probabilities under the stable and admissible se- mantics has been devised and its efficiency has been experimentally validated w.r.t. the exhaustive approach, i.e. the approach consisting in the generation of all the possible scenarios. 1 Introduction An abstract argumentation framework (AAF) represents a dispute as an argumenta- tion graph hA, Di, where A is the set of nodes (called arguments) and D is the set of edges (called defeats or attacks). Herein, an argument is an abstract entity that may attack and/or be attacked by other arguments, where “a attacks b” means that argu- ment a rebuts/weakens b. Reasoning on the possible strategies for winning the dispute typically requires looking into the extensions of the AAF. An extension S is a set of arguments that satisfies some properties certifying its “strength”, so that a party using the arguments in S has reasonable chances to win the dispute. Different semantics for AAFs (i.e., sets of properties assessing whether a set of arguments is an extension) have proven reasonable, such as admissible (ad), stable (st), preferred (pr), complete (co), grounded (gr), ideal (id) [14, 15, 2], and the complexity of the fundamental problem EXT of verifying whether a set is an extension has been studied under each of these semantics [19, 17]. Since the introduction of AAFs in [14], many variants have been proposed, with the aim of modeling disputes more accurately. Among these, Bipolar Abstract Argumenta- tion Frameworks (BAFs) allow supports, besides attacks, to be specified between argu- ments. Specifically, two alternative formal semantics of support have been introduced: in [6], the support is a generic “inverse” of the notion of attack (“abstract semantics”: “a supports b” means that a strengthens the validity of a), while, in [4], it is viewed as a “deductive” correlation between arguments (“deductive semantics”: if a supports b, the acceptance of a implies the acceptance of b). The various extensions’ semantics defined 2 B. Fazzinga et al. for AAFs have been shown to have a natural counterpart over BAFs, after noticing that combining attacks with supports (of any semantics) generates “implicit” attacks (see Example 1). Example 1. The graph in Figure 1 is a BAF with six arguments a, b, c, d, e, f . The dashed and the standard arrows denote supports and attacks, respectively. The co-existence of supports and attacks entails the existence of implicit attacks. For instance, under both the abstract and deductive semantics, the fact that a strengthens b and b attacks c implic- itly says that a attacks c. This kind of implicit attack is often called “supported attack”. If the deductive semantics is adopted, there are other forms of implicit attacks. For instance, since a supports b and e attacks b, there is an implicit attack from e to a. Oth- erwise, a would be acceptable while b would be not, thus contradicting the deductive support from a to b. Other variants of AAFs that, owing to their practical impact, have gained interest from the research community are those addressing the representation of uncertainty. In this regard, probabilistic AAFs (prAAFs) are a popular paradigm, and in particular those following the constellation approach. Here, the dispute is modeled as a set of possible scenarios, each consisting of a standard AAF (called possible AAF) associ- ated with a probability of representing all and only the arguments and attacks actually occurring in the dispute. In particular, two main paradigms have been adopted for spec- ifying the probability distribution function (pdf), called EX and IND. In the general case, the extensive form EX is used, where the composition of each possible AAF must be explicitly specified along with its probability. Otherwise, when independence between arguments/attacks is assumed, the form IND can be used, where the possible scenar- ios and their probabilities are represented compactly and implicitly by specifying the marginal probabilities of the arguments and attacks. Recently, for both EX and IND, the complexity of the probabilistic counterpart P - E XT of E XT (asking for the probability that a set of arguments is an extension) has been characterized for IND in [23] for prAFFs and in [22] for prBAFs. Interestingly, when considering IND and the stable or the admissible semantics, moving from prAAfs to prBAFs makes P -E XT intractable (F P #P -complete). In this paper, we consider the probabilistic Bipolar Argumentation Framework (prBAF), where the bipolarity of BAFs is combined with the probabilistic modeling of the uncer- tainty of prAAFs under the paradigm IND, and provide an efficient algorithm for solving P -E XT in the cases that the stable or the admissible semantics are considered. The al- gorithm is shown to be sound and its efficiency has been experimentally validated. Related Work. [6] first introduced BAFs, where supports have the general “abstract” semantics of positive interactions between arguments. Later, three more specific inter- pretations for supports have been proposed: [4], [32] and [33] introduced the deductive, e a b c d f Fig. 1: A bipolar abstract argumentation framework Computing extensions’ probabilities ... 3 necessary, and evidential semantics for the support relation, respectively. In this paper, we focus on the abstract and deductive semantics, but our results also hold for necessary supports (as shown in [8], they are dual to deductive ones). [8] reviews the four different semantics for supports, and discusses the similarities and differences among these inter- pretations. [9] introduces a more general framework that incorporates attacks, supports and a preference relation to decide between conflicting arguments. In [30], subargu- ments in AAF have been introduced, that in [10] have been shown to be closely related with the necessary support. Other related works are [5, 38] where, although supports are not mentioned, similar dependencies have been considered. A detailed survey over BAFs can be found in [10]. Regarding uncertainty in AAFs, the approaches based on probability theory can be classified in two categories: those adopting the classical constellations approach [26, 16, 36, 12, 13, 24, 29, 20, 21] and those adopting the recent epistemic one [37, 28, 27]. The former category has the two sub-categories EX [16, 36, 13] and IND [12, 29, 20, 21], described in the paper. The interested reader can find a more detailed comparative description of the two categories in [25]. Furthermore, many proposals have been made where uncertainty is represented by exploiting weights or preferences on arguments and/or defeats [3, 1, 31, 18, 11]. Although the approaches based on weights, preferences, or probabilities to model uncertainty have proved effective in different contexts, there is no common agreement on what kind of approach should be used in general. In this re- gard, [24, 25] observed that the probability-based approaches may take advantage from relying on a well-established and well-founded theory, whereas the approaches based on weights or preferences do not. As regards probabilistic Bipolar Argumentation Framework (prBAF) they have been recently introduced [34, 35] and the computational complexity of the problem of com- puting extensions’ probabilities has been characterized [22]. 2 Preliminaries We assume that the reader is familiar with the notions of Abstract Argumentation Frame- work (AAF), extension, and acceptability of arguments. We now review Bipolar Ab- stract Argumentation Frameworks (BAFs) and the concepts of support, attack and de- fense, along with the most popular extensions’ semantics over BAFs [6]. 2.1 Bipolar abstract argumentation frameworks Definition 1. [BAF] A bipolar abstract argumentation framework (BAF) is a tuple F = hA, Ra , Rs i, where A is a set of arguments, Ra ⊆ A × A is a defeat/attack relation and Rs ⊆ A × A is a support relation. In the first proposal of BAF [6], supports are given an abstract semantics, that is the opposite of the traditional semantics of attack, inherited from classical AAFs. This was shown to make the combination of supports and attacks imply the so-called supported attacks3 . 3 [6] discussed also indirect implicit attacks. W.l.o.g., as in [7], we disregard them, as their presence would not affect our results. 4 B. Fazzinga et al. Definition 2. [Supported attack] Let F = hA, Ra , Rs i be a BAF, and a, b ∈ A. There is a supported attack from a to b iff there is a sequence a1 R1 . . . Rn−1 an , with n ≥ 2, where a1 = a, an = b, ∀i ∈ [1..n − 2] Ri = Rs , and Rn−1 = Ra . Example 2. In the BAF in Figure 1, there is a supported attack from a to c. Also the three direct attacks (e, b), (b, c) and (f, d) are special cases of supported attack. Besides the abstract, other semantics have been proposed for supports (see Related Work). In particular, we consider the well-established deductive semantics, first pro- posed in [4]. Here, “a supports b” is interpreted as a strong correlation between a and b, meaning that if a is acceptable, then b is acceptable too. As observed in [8], under this semantics, a new form of implicit attack, called d-attack, must be considered. Definition 3. [d-attack] Given a BAF F = hA, Ra , Rs i and a, b ∈ A, there is a d- attack from a to b iff – aRa b, or – there is an argument a0 such that there is a path from a to a0 consisting of only support edges, and a0 attacks b, or – there is an argument a0 such that there is a path from b to a0 consisting of only support edges, and a attacks a0 . Example below shows that d-attacks include supported attacks, but can be also of the form of supermediated attacks (described by the last point in Definition 3). Example 3. Under the deductive semantics for supports, in the BAF of Figure 1, it is easy to see that the supported attacks reported in Example 2 are d-attacks. Further d- attacks are the supermediated attacks from e to a, and from f to c, that are not supported attacks. In order to analyze what changes when moving from one semantics of supports to the other (or, equivalently, from one form of implicit attacks to the other), we partition BAFs into two classes: s-BAFs and d-BAFs, where only supported attacks and d-attacks are considered, respectively. From now on, we assume the presence of a BAF F = hA, Ra , Rs i, and, when needed, we will specify whether F is an s- or a d- BAF. The concepts of support, attack and defense from sets of arguments are mandatory to define the extensions over BAFs. Definition 4. [Set-support] A set S ⊆ A set-supports an argument a ∈ A iff there is an argument a0 ∈ S such that there is a path from a0 to a consisting of only support edges. Definition 5. [Set-attack] Let F = hA, Ra , Rs i be an s-BAF (resp., d-BAF). A set S ⊆ A set-attacks a ∈ A iff there is a supported attack (resp., d-attack) from some b ∈ S to a. Definition 6. [Set-defense] A set S ⊆ A set-defends an argument a ∈ A iff, ∀b ∈ A, if {b} set-attacks a then ∃c ∈ S such that {c} set-attacks b. Computing extensions’ probabilities ... 5 Example 4. Consider the BAF F in Figure 1. Independently from supports’ semantics, {a, e} both set-supports and set-attacks b, and also set-attacks c. If F is an s-BAF, then {a, e} does not set-defend c, since there is a supported attack from a to c, and no attack from e to a. Observe that {a, e} does not set-defend c if F is a d-BAF either, since, although e d-attacks a, no argument in {a, e} d-attacks f , that in turn d-attacks c. 2.2 Semantics We first recall the notions of conflict-freeness and safety. Definition 7. [Conflict-free and safe sets of arguments] A set of arguments S ⊆ A is: – conflict-free iff 6 ∃ a, b ∈ S such that {a} set-attacks b; – safe iff 6 ∃ b ∈ A such that S set-attacks b and either S set-supports b or b ∈ S. Example 5. If the BAF F in Figure 1 is an s-BAF, both {a, e}, and {f, c} are conflict- free but not safe, while both {a, b, f } and {a, b, d} are conflict-free and safe. If F is a d-BAF, both {a, e}, and {f, c} are not conflict-free, while both {a, b, f } and {a, b, d} are still conflict-free and safe. All the most popular semantics of extensions of “standard” AAFs have been ex- tended to the case of BAFs [6]. We start with the stable semantics. Definition 8. [Stable extension] A set of arguments S ⊆ A is a stable extension iff S is conflict-free and ∀a ∈ A \ S it holds that S set-attacks a. The presence of supports and the fact that, in BAFs, conflict-freeness and safety do not coincide (while they do in AAFs) is at the basis of the fact that, for some AAF’s semantics, different variants are considered when moving to BAFs. This is the case of the admissible semantics. Definition 9. [Admissible extension] A set S ⊆ A is – a d-admissible extension iff S is conflict-free and set-defends all of its arguments; – an s-admissible extension iff S is safe and set-defends all of its arguments; – a c-admissible extension iff S is conflict-free, closed for Rs and set-defends all of its arguments. In turn, the other semantics subsuming the admissible one are defined as follows. A set S ⊆ A is said to be: – a d-complete (resp. s-complete, c-complete) extension iff S is d-admissible (resp., s-admissible, c-admissible) and S contains all the arguments set-defended by S; – a d-grounded (resp. s-grounded, c-grounded) extension iff S is a minimal (w.r.t. ⊆) d-complete (resp. s-complete, c-complete) extension; – a d-preferred (resp. s-preferred, c-preferred) extension iff S is a maximal (w.r.t. ⊆) d-complete (resp. s-complete, c-complete) extension; 6 B. Fazzinga et al. – a d-ideal (resp. s-ideal, c-ideal) extension iff S is a maximal (w.r.t. ⊆) d-admissible (resp. s-admissible, c-admissible) extension and S is contained in every d-preferred (resp. s-preferred, c-preferred) extension. We denote the set {d-ad, s-ad, c-ad, st, d-co, s-co, c-co, d-gr, c-gr, c-gr, d-pr, s-pr, c-pr, d-id, s-id, c-id} consisting of the above semantics as SEM (herein, st means stable, d-ad d-admissible, s-ad s-admissible, and so on). Example 6. Consider the BAF in Figure 1. Both {a, b, f } and {a, b, d}, although conflict- free and safe, are not d-ad extensions in both the cases of s-BAF and d-BAF (since b is not set-defended). Furthermore, for the s-BAF case, we have: both {a, f } and {e, f } are s-ad, s-gr and s-pr extensions, {a, e, f } is a st, d-ad, d-gr, d-pr, and d-id extension, {f } is an s-id extension, {e, f } is a c-pr, c-gr and c-id extension. For the d-BAF case we have: {e, f } is the unique stable extension, that is also c- preferred, c-grounded and c-ideal. The fundamental problem of verifying whether a set S of arguments is an extension over a given BAF under a semantics sem ∈ SEM will be denoted as E XTsem (S). Ba- sically, solving an instance of E XTsem (S) means checking whether a set of arguments is a reasonable strategy in the dispute, where the meaning of “reasonable” is encoded in the semantics. Given a BAF F = hA, Ra , Rs i, a set S ⊆ A, and a semantics sem ∈ SEM , we define the boolean function ext(α, sem, S) returning true iff S is an extension under sem. 3 Probabilistic BAFs (prBAFs) We now consider the extension of BAFs where uncertainty is addressed and modeled probabilistically as in “traditional” probabilistic Abstract Argumentation Frameworks - prAAFs (in particular, we refer to prAAFs employing the constellation approach re- called in the introduction and adopting the IND approach for specifying pdfs). A probabilistic BAF (prBAF) F of type IND is a tuple hA, Ra , Rs , PA , PR i where A = {a1 , . . . , am }, Ra = {δ1 , . . . , δn } and Rs = {σ1 , . . . , σk } are the sets of ar- guments, attacks and supports, respectively, and PA = {P (a1 ), . . . , P (am )}, PR = {P (δ1 ), . . . , P (δn ), P (σ1 ), . . . , P (σk )} are their marginal probabilities. A prBAF F is used to represent a set of possible BAFs, that is the alternative cases of dispute that may occur, and their probabilities. More in detail P S = {α = hA0 , R0a , R0s i | A0 ⊆ A∧ R0a ⊆ (A0 × A0 ) ∩ Ra ∧ R0s ⊆ (A0 × A0 ) ∩ Rs } is the set of possible BAFs represented by F and the pdf P over the possible scenarios that is implied by the independence assumption and the marginal probabilities PA , PR is as follows. For each possible BAF α0 = hA0 , R0a , R0s i, the probability P (α0 ) is:   P (α0 ) = a∈A0 P (a)× a∈A\A0 1−P (a) × Q Q Q Q   δ∈R0a P (δ)× δ∈(Rs ∩(A0 ×A0 ))\R0a 1−P (δ) × (1) Q Q   σ∈R0s P (σ)× σ∈(Rs ∩(A0 ×A0 ))\R0s 1−P (σ) . The size of a prBAF of type IND is O(|A| + |Ra | + Rs | + |PA | + |PR |). Computing extensions’ probabilities ... 7 Example 7. Consider a prBAF F 0 of form IND, where A, Ra and Rs are those of Figure 1, and PA and PR are the following: P (a) = P (b) = P (c) = P (d) = P (f ) = 1, P (e) = 0.5, P (e, b) = 0.5 and the probabilities of the other supports and attacks are equal to 1. We have three possible scenarios: α1 = hA, Ra , Rs i, α2 = hA, Ra \ {(e, b)}, Rs i, α3 = hA \ {e}, Ra \ {(e, b)}, Rs i, whose probabilities are: P (α1 ) = 0.25, P (α2 ) = 0.25, P (α3 ) = 0.5. In what follows, given a prBAF F = hA, Ra , Rs , PA , PR i, we denote as F.α = α1 , . . . , αm the possible BAFs that are assigned non-zero probability by P, and as F.P = P (α1 ), . . . , P (αm ) their probabilities. The probabilistic versions of the two sub-classes s-BAF and d-BAF will be called s-prBAF and d-prBAF, respectively. When switching to the probabilistic setting, the decision problem E XTsem (S) makes no sense, since a number of different scenarios are possible, and a set of arguments can be an extension in a some scenarios, but not in others. Thus, the most natural “transla- tion” of the problem of examining the “reasonability” of a set of arguments S becomes the functional problem P-E XTsem (S) of evaluating the probability that S is an exten- sion, according to the following definition. Definition 10 (P-E XTsem (S) and P sem (S)). Given a prBAF F, a set S of arguments, and a semantics sem ∈ SEM , P-E XTsem (S) is the problem of computing the proba- bility PFsem (S) that S is an extension under sem, i.e. sem X PF (S) = F.P (α) (2) α ∈ F .α ∧ ext(α, sem, S) Example 8. Continuing examples 6 and 7, we now compute the probability that S = {a, e} is d-admissible in both the s-and d- prBAF cases. Case s-prBAF: S is d-admissible in both α1 and α2 (as e is missing in α3 ), thus P d-ad (S) = P (α1 ) + P (α2 ) = 0.5. Case d-prBAF: S is d-admissible only in α2 , as in α1 e d-attacks a and in α3 e is missing, thus we have P d-ad (S) = P (α2 ) = 0.25. 4 An algorithm for computing PFsem (S) We now provide our main contribution, that is the definition of an algorithm for effi- ciently computing the probability that a set of arguments is an extension according to a semantics sem ∈ {st, d-ad, s-ad, c-ad}. The algorithm is based on the following results, provided in [21], that hold for traditional prAAF of type IND. A PrAAf of type IND correspond to a prBAF of type IND where the support relation is empty. Fact 1 [21] Given a prAAF F = hA, Ra , ∅, PA , PR i and a set S ⊆ A of arguments, the probability that S is an admissible extension in F is equal to P1 (S) · P2 (S) · P3 (S), where4 : 4 Note that an empty product evaluates to 1. 8 B. Fazzinga et al. Q – P1 (S) = PA (a), Q a∈S  – P2 (S) = (a, b) ∈ Ra 1 − PR ((a, bi)) , and ∧a ∈ S ∧b ∈ S Q  – P3 (S) = d∈A\S P31 (S, d)+ P32 (S, d)+ P33 (S, d) , where: • P31 (S, d) = 1−PA (d),Q  • P32 (S, d) = PA (d) × (d, b) ∈ Ra 1−PR ((d, b)) , ∧b ∈ S  Q  • P33 (S, d) = PA (d) × 1 − (d, b) ∈ Ra 1−PR ((d, b)) × ∧b ∈ S  Q  1− (a, d) ∈ Ra 1−PR ((a, d)) ∧a ∈ S Fact 2 [21] Given a prAAF F = hA, Ra , ∅, PA , PR i and a set S ⊆ A of arguments, the probability that S is a stable extension in F is equal to P1 (S) · P2 (S) · P3 (S), where P1 (S) and P2 (S) are defined as in Fact 1 and Y  P3 (S) = P31 (S, d) + P32 (S, d) d∈A\S where: – P31 (S, d) = 1−PA (d), and  Q – P32 (S, d) = PA (d) × 1 − (1 − PR ((a, d))) (a, d) ∈ Ra ∧a ∈ S Before defining the algorithm we introduce some preliminary notations used in its definition. Formally, given a prBAF F = hA, Ra , Rs , PA , PR i, we consider the sets: – F.Ae = {a| ∃ha, bi ∈ Rs ∨ ∃hb, ai ∈ Rs } (called set of supp-arguments, as they are those involved in supports), and – F.Re = {ha, bi ∈ (Ra ∪ Rs ) | (a ∈ Ae ∨ b ∈ Ae } (called set of supp- attacks and supports, as they are attacks/supports incident to supp-arguments). The algorithm evaluation strategy is based on the notions of contraction and com- pletion. A contraction for a prBAF F = hA, Ra , Rs , PA , PR i is a prBAF F ∗ = hA∗ , R∗a , R∗s , PA ∗ ∗ , PR i where: – A∗ ⊆ A and A \ A∗ ⊆ F.Ae ; – R∗a ⊆ Ra ∩ (A∗ × A∗ ) and Ra \ R∗a ⊆ F.Re ; – R∗s ⊆ Rs ∩ (A∗ × A∗ ); ∗ ∗ – PA (a) = 1 if a ∈ F.Ae and PA (a) = PA (a) otherwise; ∗ ∗ – PR (ha, bi) = 1 if a ∈ F.Ae ∨ b ∈ F.Ae , and PR (ha, bi) = PR (ha, bi) otherwise. Basically, F ∗ ’s supports are a subset of F’s, and arguments (resp., attacks) are a subset of F’s containing at least the non supp-arguments (resp., the non supp-attacks). Then, the probabilities are copied from those specified in F, except for those over supp- argu- ments and attacks, that are overwritten with 1. Computing extensions’ probabilities ... 9 E(F) will denote the set of possible contractions of F. For F ∗ ∈ E(F), we define the probability of F ∗ given F as: Y Y P (F ∗ |F) = PF ∗ (a) × PF ∗ (δ), (3) a∈Ae δ∈Re ∩(A∗ ×A∗ ) where: – if a ∈ A∗ , PF ∗ (a) = PA (a); else, PF ∗ (a) = 1−PA (a); – if δ ∈ R∗a ∪ R∗s , PF ∗ (δ) = PR (δ); else, PF ∗ (δ) = 1−PR (δ). As regards completions, their definition uses the function cert(F), returning the BAF consisting of all and only the arguments in F.Ae plus the arguments in F in- volved in the attacks/supports in F.Re and the attacks/supports of F that appear in F.Re . More formally, given a prBAF F = hA, Ra , Rs , PA , PR i, cert(F) is the BAF hA0 , R0a , R0s i such that: – A = F.Ae ∪ {a | a ∈ A ∧ ∃b ∈ As.t.ha, bi ∈ F.Re ∨ hb, ai ∈ F.Re }, – R0a = Ra ∩ F.Re , – R0s = Rs ∩ F.Re . 0 Thus, the completion of F is the prBAF compl(F) = hA0 , R0a , R0s , PA 0 , PR i where: – A0 = A and R0s = Rs ; – R0a = Ra ∪R0 , where R0 consists of the s- or the d- attacks of cert(F), depending on whether F is an s- or a d- prBAF; 0 – ∀a ∈ A, PA (a) = PA (a); – ∀δ ∈ Ra , if δ ∈ R0 then PR 0 0 0 (δ) = 1, else PR (δ) = PR (δ). 0 0 – ∀δ ∈ Rs , PR (δ) = PR (δ). We now define Algorithm 1 that computes the probability that a set of arguments S is an extension for F according to the semantics sem ∈ {st, d-ad, s-ad, c-ad} for both s- and d-prBAFs by iterating over E(F). Algorithm 1 first computes the sets F.Ae and F.Re of supp-arguments and supp- attacks and supports of F (Lines 2-3) and it initializes P r to 0. Then it iterates over the possible contractions of F by iterating over the subsets of F.Ae (Line 4) and then for each subset A0e of F.Ae iterating over the subsets of Re ∩ (A0e × A0e ) (Line 5). The contraction F ∗ o f F corresponding to the sets A0e and R0e is generated by call- ing function contract (Line 6) and its probability P (F ∗ |F) is computed using Equa- tion 3 (Line 7). Then the completion F 0 of F ∗ is computed as by calling function complete (Line 8). Then the variable P r0 is computed according to the following definition (Lines 9- 19): – P r0 = 0.0 if sem = s-ad and S is not safe in cert(F 0 ), – P r0 = 0.0 if sem = s-ad and S is not closed for supports over cert(F 0 ), – P r0 = 1.0, otherwise. Next, the probability P r that S is an admissible/stable extension in the prAAF ob- tained removing supports by F 0 (F) is computed according to the formulas reported in Facts 1 and 2 (Lines 20- 26). Specifically function computePrAAF is responsible for computing the probability P r that S is an admissible/stable extension in F and P r is added to the probability P r. Finally P r is returned. 10 B. Fazzinga et al. sem Algorithm 1 Computing P rF (S) by enumerating contractions Require: A prBAF F = hA, Ra , Rs , PA , PR i A set S ⊆ A A semantics sem ∈ {st, d-ad, s-ad, c-ad} sem Ensure: P rF (S) 1: P r = 0.0 2: Ae = computeAe (F) 3: Re == computeRe (F, Ae ) 4: for A∗e ⊆ Ae do 5: for R∗e ⊆ Re ∩ (A∗e × A∗e ) do 6: F ∗ = contract(F, A∗e , R∗e ,Q Ae , Re ) P r∗ = a∈Ae PF ∗ (a) × δ∈Re ∩(A∗ ×A∗ ) PF ∗ (δ) Q 7: e e 8: F 0 = complete(F ∗ , A∗e , R∗e ) 9: if sem = s-ad then 10: if not safe(F 0 , S, A∗e , R∗e ) then 11: P r0 = 0.0 12: end if 13: else if sem = c-ad then 14: if not supclosed(F 0 , S) then 15: P r0 = 0.0 16: end if 17: else 18: P r0 = 1.0 19: end if 20: F = toPrAAF(F ∗ ) 21: if sem = st then 22: aaf sem = st 23: else 24: aaf sem = ad 25: end if 26: P r = computePrAAF(F, S, aaf sem) 27: P r = P r + P r∗ × P r0 × P r 28: end for 29: end for 30: return P r 4.1 Correctness of Algorithm 1 In this section we show that Algorithm 1 is sound and characterize its computational complexity. First we introduce a lemma (which straightforwardly follows from the def- inition of P (F ∗ |F)) that allows for decomposing the evaluation of PFsem (S) into eval- ∗ uating PFsem ∗ (S) over each contraction F . Lemma 1. Let F be a prBAFP and S a set of its arguments. For sem ∈ {d-ad, s-ad, c-ad, st}, it holds that PFsem (S) = F ∗ ∈E(F ) P (F ∗ |F) × PFsem ∗ (S). ∗ The following lemma state that the method for computing PFsem ∗ (S) for each F ∈ sem E(F) used in Algorithm 1 is correct. Indeed, it states that PF ∗ (S) can be computed by taking the prAAF F obtained by removing the supports from the completion of Computing extensions’ probabilities ... 11 F ∗ , and then using over F any state-of-the-art algorithm for computing the extensions’ probabilities over “traditional” prAAFs (e.g. using the formulas reported in Facts 1 and 2). Lemma 2. Let F be a prBAF, F ∗ a contraction for F, F the prAAF obtained from compl(F ∗ ) by removing the supports, and S a set of arguments of F ∗ . Then: 0 – For sem ∈ {d-ad, st} PFsem ∗ (S) = P sem F (S), where sem0 ∈ {ad, st} respectively; – PF ∗ (S) = 0 if S is not safe over cert(compl(F ∗ )); otherwise, PFs-ad s-ad ∗ (S) = ad PF (S); – PFc-ad ∗ (S) = 0 if S is not closed for Rs over cert(compl(F ∗ )); otherwise, PFc-ad ∗ (S) = ad PF (S). Proof (Sketch). The statement can be proved by exploiting the fact that, since supp- ar- guments and attacks in contractions are certain, safeness and closure for Rs hold over F ∗ iff they hold over cert(compl(F ∗ )). The detailed proof is omitted for space rea- sons. 2 Theorem 1. For sem ∈ {d-ad, s-ad, c-ad, st}, Algorithm 1 computes PFsem (S) for both s- and d- prBAFs in time O(2|F .Ae |+F .Ee | × F (|F|)), F is a polynomial function. Proof.P The fact that Algorithm 1 computes PFsem (S) followos form the fact that it com- putes F ∗ ∈E(F ) P (F ∗ |F) × PFsem ∗ (S). Specifically, Lemma 1 ensures that PF sem (S) ∗ sem ∗ P can be computed as F ∗ ∈E(F ) P (F |F) × PF ∗ (S), where for each F ∈ E(F). Moreover, for each F ∗ ∈ E(F) Algorithm 1 computes PFsem ∗ (S) as specified by Lemma 2. Finally, it is straightforward to see that computing PFsem ∗ (S) as done by Algorithm 1 (i.e., following Lemma 2 and applying the formulas reported in Facts 1 and 2) is fea- sible in time O(F (|F|)), where F is a polynomial function. Hence, since |E(F)| ≤ 2|F .Ae |+F .Ee | , it follows that Algorithm 1 runs in time O(2|F .Ae |+F .Ee | × F (|F|)), which completes the proof. 2 4.2 Experimental validation In this section we report a preliminary experimental assessment of the efficiency of Algorithm 1. To this end we compared running times of Algorithm 1 (denoted as CON - sem TRACT in what follows) with a naive algorithm that computes PF (S) by directly applying Equation 2 of Definition 10 (denoted as NAIVE in what follows). We perform experiments over 100 prBAFs with a number of arguments ranging over {6, 8, 10, 12, 14}. Specifically we randomly generate 20 prBAFs for every num- ber of arguments in {6, 8, 10, 12, 14}. Figure 2 reports the average running times of CONTRACT and NAIVE vs the number of arguments in the prBAFs. From the experiments it follows that CONTRACT outperforms NAIVE for all the con- sidered number of arguments. However, it is worth noting that even using CONTRACT computing PFsem (S) requires a large amount of time (the algorithm was halted after 30 minutes) on prBAFs with more than 14 arguments. 12 B. Fazzinga et al. CONTRACT NAIVE 1×106 100000 10000 1000 100 10 6 8 10 12 14 Num. of Arguments Fig. 2: Average running times of CONTRACT and NAIVE (msec) vs number of arguments 5 Conclusions In this paper we devised an algorithm for computing extensions’ probabilities over prBAFs of type IND when the stable, d-admissible, s-admissible or c-admissible se- mantics are considered. The correctness of the algorithm has been formally proved and its efficiency experimentally validated w.r.t. the naive computation based on the enu- meration of possible BAFs. The gain in efficiency of the proposed algorithm is due to the fact that it enumerates contractions rather than possible BAFs and in most cases the number of possible contractions is much smaller than the number of possible BAFs. However, from the experiments it turns out that the algorithm is not able to deal with large prBAFs in reasonable time. Hence, for large prBAFs resorting to estimating ex- tensions’ probabilities is reasonable. An interesting research direction for future work is that of applying the approach based on enumerating contractions to improve the effi- ciency of estimation algorithms. References 1. Amgoud, L., Vesic, S.: A new approach for preference-based argumentation frameworks. A. Math. Artif. Intell. 63(2), 149–183 (2011) 2. Baroni, P., Giacomin, M.: Semantics of abstract argument systems. In: Argum. in Artif. In- tell., pp. 25–44 (2009) 3. Bench-Capon, T.J.M.: Persuasion in practical argument using value-based argumentation frameworks. J. Log. Comput. 13(3), 429–448 (2003) 4. Boella, G., Gabbay, D.M., van der Torre, L.W.N., Villata, S.: Support in abstract argumenta- tion. In: Proc. of COMMA 2010. pp. 111–122 (2010) 5. Brewka, G., Woltran, S.: Abstract dialectical frameworks. In: Proc. of KR (2010), http://aaai.org/ocs/index.php/KR/KR2010/paper/view/1294 6. Cayrol, C., Lagasquie-Schiex, M.C.: On the acceptability of arguments in bipolar argumen- tation frameworks. In: Proc. of ECSQARU. pp. 378–389 (2005) 7. Cayrol, C., Lagasquie-Schiex, M.C.: Bipolar abstract argumentation systems. In: Argum. in Artif. Intell., pp. 65–84 (2009) Computing extensions’ probabilities ... 13 8. Cayrol, C., Lagasquie-Schiex, M.C.: Bipolarity in argumentation graphs: Towards a better understanding. Int. J. Approx. Reasoning 54(7), 876–899 (2013) 9. Cohen, A., Garcı́a, A.J., Simari, G.R.: Backing and undercutting in abstract argumentation frameworks. In: Proc. of FoIKS. pp. 107–123 (2012) 10. Cohen, A., Gottifredi, S., Garcı́a, A.J., Simari, G.R.: A survey of different approaches to support in argumentation systems. Know. Eng. Review 29(5), 513–550 (2014) 11. Coste-Marquis, S., Koniec-zny, S., Marquis, P., Ouali, M.: Weighted attacks in argumentation frameworks. In: Proc. of KR (2012) 12. Doder, D., Woltran, S.: Probabilistic argumentation frameworks - A logical approach. In: Proc. of SUM. pp. 134–147 (2014) 13. Dondio, P.: Toward a computational analysis of probabilistic argumentation frameworks. Cybernetics and Systems 45(3), 254–278 (2014) 14. Dung, P.M.: On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell. 77(2), 321–358 (1995) 15. Dung, P.M., Mancarella, P., Toni, F.: Computing ideal sceptical argumentation. Artif. Intell. 171(10-15), 642–674 (2007) 16. Dung, P.M., Thang, P.M.: Towards (probabilistic) argumentation for jury-based dispute res- olution. In: Proc. of COMMA. pp. 171–182 (2010) 17. Dunne, P.E.: The computational complexity of ideal semantics. Artif. Intell. 173(18) (2009) 18. Dunne, P.E., Hunter, A., McBurney, P., Parsons, S., Wooldridge, M.: Weighted argument systems: Basic definitions, algorithms, and complexity results. Artif. Intell. 175(2) (2011) 19. Dunne, P.E., Wooldridge, M.: Complexity of abstract argumentation. In: Argum. in Artif. Intell., pp. 85–104 (2009) 20. Fazzinga, B., Flesca, S., Parisi, F.: On the complexity of probabilistic abstract argumentation. In: Proc. of IJCAI (2013) 21. Fazzinga, B., Flesca, S., Parisi, F.: On the complexity of probabilistic abstract argumentation frameworks. ACM Trans. Comput. Log. 16(3), 22 (2015) 22. Fazzinga, B., Flesca, S., Furfaro, F.: Probabilistic bipolar abstract argumentation frame- works: complexity results. In: Proceedings of IJCAI 2018. pp. 1803–1809 (2018) 23. Fazzinga, B., Flesca, S., Furfaro, F.: Complexity of fundamental problems in probabilistic abstract argumentation: Beyond independence. Artificial Intelligence 268, 1 – 29 (2019). https://doi.org/https://doi.org/10.1016/j.artint.2018.11.003 24. Hunter, A.: Some foundations for probabilistic abstract argumentation. In: Proc. of COMMA. pp. 117–128 (2012) 25. Hunter, A.: A probabilistic approach to modelling uncertain logical arguments. Int. J. Ap- prox. Reasoning 54(1), 47–81 (2013) 26. Hunter, A.: Probabilistic qualification of attack in abstract argumentation. Int. J. Approx. Reasoning 55(2), 607–638 (2014) 27. Hunter, A., Thimm, M.: Probabilistic argumentation with epistemic extensions. In: Proc. of DARe@ECAI (2014) 28. Hunter, A., Thimm, M.: Probabilistic argumentation with incomplete information. In: Proc. of ECAI. pp. 1033–1034 (2014) 29. Li, H., Oren, N., Norman, T.J.: Probabilistic argumentation frameworks. In: Proc.of TAFA (2011) 30. Martı́nez, D.C., Garcı́a, A.J., Simari, G.R.: On acceptability in abstract argumentation frame- works with an extended defeat relation. In: Proc. of COMMA. pp. 273–278 (2006) 31. Modgil, S.: Reasoning about preferences in argumentation frameworks. Artif. Intell. 173(9- 10), 901–934 (2009) 32. Nouioua, F., Risch, V.: Bipolar argumentation frameworks with specialized supports. In: Proc. of ICTAI. pp. 215–218 (2010) 33. Oren, N., Norman, T.J.: Semantics for evidence-based argumentation. In: Proc. of COMMA. pp. 276–284 (2008) 14 B. Fazzinga et al. 34. Polberg, S., Hunter, A.: Empirical evaluation of abstract argumentation: Supporting the need for bipolar and probabilistic approaches. Int. J. Approx. Reasoning 93, 487–543 (2018) 35. Proietti, C.: Polarization and bipolar probabilistic argumentation frameworks. In: Proc. of Work. AI3 . pp. 22–27 (2017) 36. Rienstra, T.: Towards a probabilistic dung-style argumentation system. In: Proc. of AT. pp. 138–152 (2012) 37. Thimm, M.: A probabilistic semantics for abstract argumentation. In: Proc. of ECAI. pp. 750–755 (2012) 38. Verheij, B.: The toulmin argument model in artificial intelligence. In: Argum. in Artif. Intell., pp. 219–238 (2009)