Probabilistic Bipolar Abstract Argumentation Frameworks (prBAFs), combining the possibility of specifying supports between arguments with a probabilistic 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 extensions' 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 efficiently computing extensions' probabilities under the stable and admissible semantics 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.
An abstract argumentation framework (AAF) represents a dispute as an
argumentation 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
argument 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) [
Since the introduction of AAFs in [
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 implicitly 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. Otherwise, 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) associated 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 specifying 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 scenarios 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
PEXT of EXT (asking for the probability that a set of arguments is an extension) has
been characterized for IND in [
In this paper, we consider the probabilistic Bipolar Argumentation Framework (prBAF),
where the bipolarity of BAFs is combined with the probabilistic modeling of the
uncertainty of prAAFs under the paradigm IND, and provide an efficient algorithm for solving
P-EXT in the cases that the stable or the admissible semantics are considered. The
algorithm is shown to be sound and its efficiency has been experimentally validated.
Related Work. [
f
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 [
Regarding uncertainty in AAFs, the approaches based on probability theory can be
classified in two categories: those adopting the classical constellations approach [
As regards probabilistic Bipolar Argumentation Framework (prBAF) they have been
recently introduced [
We assume that the reader is familiar with the notions of Abstract Argumentation
Framework (AAF), extension, and acceptability of arguments. We now review Bipolar
Abstract Argumentation Frameworks (BAFs) and the concepts of support, attack and
defense, along with the most popular extensions’ semantics over BAFs [
Definition 1. [BAF] A bipolar abstract argumentation framework (BAF) is a tuple F = hA; Ra; Rsi, 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 [
Definition 2. [Supported attack] Let F = hA; Ra; Rsi be a BAF, and a; b 2 A. There is a supported attack from a to b iff there is a sequence a1R1 : : : Rn 1an, with n 2, where a1 = a, an = b, 8i 2 [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
proposed in [
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 dattacks 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; Rsi, 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 2 A iff there is an argument a0 2 S such that there is a path from a0 to a consisting of only support edges. Definition 5. [Set-attack] Let F = hA; Ra; Rsi be an s-BAF (resp., d-BAF). A set S A set-attacks a 2 A iff there is a supported attack (resp., d-attack) from some b 2 S to a.
fbg set-attacks a then 9c 2 S such that fcg set-attacks b.
fa; eg both set-supports and set-attacks b, and also set-attacks c. If F is an s-BAF, then fa; eg does not set-defend c, since there is a supported attack from a to c, and no attack from e to a. Observe that fa; eg does not set-defend c if F is a d-BAF either, since, although e d-attacks a, no argument in fa; eg d-attacks f , that in turn d-attacks c. 2.2
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 9 a; b 2 S such that fag set-attacks b; – safe iff 6 9 b 2 A such that S set-attacks b and either S set-supports b or b 2 S.
free but not safe, while both fa; b; f g and fa; b; dg are conflict-free and safe. If F is a d-BAF, both fa; eg, and ff; cg are not conflict-free, while both fa; b; f g and fa; b; dg are still conflict-free and safe.
All the most popular semantics of extensions of “standard” AAFs have been
extended to the case of BAFs [
Definition 8. [Stable extension] A set of arguments S conflict-free and 8a 2 A n S it holds that S set-attacks a.
A is a stable extension iff S is
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; – 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 fd-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-idg consisting of the above semantics as SEM (herein, st means stable, d-ad d-admissible, s-ad s-admissible, and so on).
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 fa; f g and fe; f g are s-ad, s-gr and s-pr extensions, fa; e; f g is a st, d-ad, d-gr, d-pr, and d-id extension, ff g is an s-id extension, fe; f g is a c-pr, c-gr and c-id extension.
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 2 SEM will be denoted as EXTsem(S). Basically, solving an instance of EXTsem(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; Rsi, a set S A, and a semantics sem 2 SEM , we define the boolean function ext( ; sem; S) returning true iff S is an extension under sem. 3
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 recalled in the introduction and adopting the IND approach for specifying pdfs).
A = fa1; : : : ; amg, Ra = f 1; : : : ; ng and Rs = f 1; : : : ; kg are the sets of arguments, attacks and supports, respectively, and PA = fP (a1); : : : ; P (am)g, PR = fP ( 1); : : : ; P ( n); P ( 1); : : : ; P ( k)g are their marginal probabilities.
cases of dispute that may occur, and their probabilities. More in detail P S = f = hA0; R0a; R0si j A0 A^ R0a (A0 A0) \ Ra ^ R0s (A0 A0) \ Rsg 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; R0si, the probability P ( 0) is: P ( 0) =Qa2A0 P (a)
Qa2AnA0 1 P (a) Q 2R0a P ( ) Q 2R0s P ( )
Q Q 2(Rs\(A0 A0))nR0a
1 P ( ) 2(Rs\(A0 A0))nR0s 1 P ( ) :
(1)
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; Rsi, 2 = hA; Ra n f(e; b)g; Rsi, 3 = hA n feg; Ra n f(e; b)g; Rsi, 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; PRi, we denote as F : =
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 EXTsem(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 “translation” of the problem of examining the “reasonability” of a set of arguments S becomes the functional problem P-EXTsem(S) of evaluating the probability that S is an extension, according to the following definition.
Definition 10 (P-EXTsem(S) and P sem(S)). Given a prBAF F , a set S of arguments, and a semantics sem 2 SEM , P-EXTsem(S) is the problem of computing the probability P sem(S) that S is an extension under sem, i.e.
F
P sem(S) =
F
X
F :P ( ) 2 F: ^ ext( ; sem; S) (2) Example 8. Continuing examples 6 and 7, we now compute the probability that S = fa; eg is d-admissible in both the s-and d- prBAF cases.
Case s-prBAF: S is d-admissible in both P d-ad(S) = P ( 1) + P ( 2) = 0:5.
Case d-prBAF: S is d-admissible only in 2, as in missing, thus we have P d-ad(S) = P ( 2) = 0:25. 1 and 2 (as e is missing in
3), thus 1 e d-attacks a and in 3 e is 4
An algorithm for computing P sem(S)
F We now provide our main contribution, that is the definition of an algorithm for efficiently computing the probability that a set of arguments is an extension according to a semantics sem 2 fst; d-ad; s-ad; c-adg.
The algorithm is based on the following results, provided in [
Fact 1 [
P31(S; d) = 1 PA(d), P32(S; d) = PA(d)
Q (d; b) 2 Ra 1 PR((d; b)) ,
^b 2 S P33(S; d) = PA(d)
1 1
Q (a; d) 2 Ra ^a 2 S
Q (d; b) 2 Ra 1 PR((d; b))
^b 2 S
1 PR((a; d))
Fact 2 [
Y d2AnS P3(S) =
P31(S; d) + P32(S; d)
Before defining the algorithm we introduce some preliminary notations used in its definition. Formally, given a prBAF F = hA; Ra; Rs; PA; PRi, we consider the sets: – F :Ae = faj 9ha; bi 2 Rs _ 9hb; ai 2 Rsg (called set of supp-arguments, as they are those involved in supports), and – F :Re = fha; bi 2 (Ra [ Rs) j (a 2 Ae _ b 2 Aeg (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 completion. A contraction for a prBAF F = hA; Ra; Rs; PA; PRi is a prBAF F = hA ; Ra; Rs; PA; PRi where: – A A and A n A F :Ae; – Ra Ra \ (A A ) and Ra n Ra F :Re; – Rs Rs \ (A A ); – PA(a) = 1 if a 2 F :Ae and PA(a) = PA(a) otherwise; – PR(ha; bi) = 1 if a 2 F :Ae _ b 2 F :Ae, and PR(ha; bi) = PR(ha; bi) otherwise.
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- arguments and attacks, that are overwritten with 1. (3)
P (F jF ) = Y PF (a) a2Ae
Y 2Re\(A
A )
PF ( );
– A = F :Ae [ fa j a 2 A ^ 9b 2 As:t:ha; bi 2 F :Re _ hb; ai 2 F :Reg, – R0a = Ra \ F :Re, – R0s = Rs \ F :Re.
Thus, the completion of F is the prBAF compl(F ) = hA0; R0a; R0s; PA0; PR0i 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; – 8a 2 A, PA0(a) = PA(a); – 8 2 R0a, if 2 R0 then PR0( ) = 1, else PR0( ) = PR( ). – 8 2 R0s, PR0( ) = 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 2 fst; d-ad; s-ad; c-adg for both s- and d-prBAFs by iterating over E (F ).
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).
ing function contract (Line 6) and its probability P (F jF ) is computed using Equation 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 919): – 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 obtained 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. Lemma 1. Let F be a prBAF and S a set of its arguments. For sem 2 fd-ad; s-ad; c-ad; stg, it holds that PFsem(S) = PF 2E(F) P (F jF ) PFsem(S).
The following lemma state that the method for computing P sem(S) for each F 2 E (F ) used in Algorithm 1 is correct. Indeed, it states that P semF(S) can be computed F by taking the prAAF F obtained by removing the supports from the completion of
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: Proof (Sketch). The statement can be proved by exploiting the fact that, since supp- arguments and attacks in contractions are certain, safeness and closure for Rs hold over
sons. 2 Theorem 1. For sem 2 fd-ad; s-ad; c-ad; stg, Algorithm 1 computes P sem(S) for both s- and d- prBAFs in time O(2jF:Aej+F:Eej F (jF j)), F is a polynomiFal function. Proof. The fact that Algorithm 1 computes P sem(S) followos form the fact that it computes PF 2E(F) P (F jF ) PFsem(S). SpeFcifically, Lemma 1 ensures that PFsem(S) can be computed as PF 2E(F) P (F jF ) PFsem(S), where for each F 2 E (F ). 2M. oreover, for each F 2 E (F ) Algorithm 1 computes PFsem(S) as specified by Lemma Finally, it is straightforward to see that computing P sem(S) as done by Algorithm 1 F (i.e., following Lemma 2 and applying the formulas reported in Facts 1 and 2) is feasible in time O(F (jF j)), where F is a polynomial function. Hence, since jE (F )j 2jF:Aej+F:Eej, it follows that Algorithm 1 runs in time O(2jF:Aej+F:Eej F (jF j)), which completes the proof. 2 4.2
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 CONTRACT in what follows) with a naive algorithm that computes P sem(S) by directly F 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 f6; 8; 10; 12; 14g. Specifically we randomly generate 20 prBAFs for every number of arguments in f6; 8; 10; 12; 14g. 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 considered number of arguments. However, it is worth noting that even using CONTRACT computing P sem(S) requires a large amount of time (the algorithm was halted after 30
F minutes) on prBAFs with more than 14 arguments.
1×106 100000 10000 1000 100 10
CONTRACT
NAIVE 6 8 10 12
14
Num. of Arguments 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 semantics 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 enumeration 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 extensions’ probabilities is reasonable. An interesting research direction for future work is that of applying the approach based on enumerating contractions to improve the efficiency of estimation algorithms.