Credulous acceptability in probabilistic abstract argumentation: complexity results

Abstract

Probabilistic abstract argumentation combines Dung's abstract argumentation framework with probability theory in order to model uncertainty in argumentation. In this setting, we address the fundamental problem of computing the probability that an argument is (credulously) acceptable according to a given semantics. Speci cally, we focus on the most popular semantics (i.e., admissible, stable, semi-stable, complete, grounded, preferred, ideal, ideal-set ), and show that computing the probability that an argument is credulously accepted is FP #P complete independently from the adopted semantics.

Keywords

• Acceptability
• Probabilistic Abstract Argumentation
• Complexity

Introduction

Several argumentation frameworks have been proposed, with the aim of suitably modeling disputes between two or more parties. Typically, argumentation frameworks model both the possibility of parties to present arguments supporting their theses, and the possibility that some arguments rebut other arguments.

A powerful yet simple argumentation framework is that proposed in the seminal paper [ 10 ], called abstract argumentation framework (AAF). An AAF is a representation of a dispute in terms of an argumentation graph hA; Di, where A is the set of nodes (each called argument ) and D is the set of edges (each called defeat or, equivalently, attack ). Basically, an argument is an abstract entity that may attack and/or be attacked by other arguments, and an attack expresses the fact that an argument rebuts/weakens another argument.

Several semantics for AAFs, such as admissible, stable, preferred, complete, grounded, semi-stable, ideal-set and ideal, have been proposed [ 10, 11, 2, 4 ] to identify \reasonable" sets of arguments, called extensions. Basically, each of these semantics corresponds to some properties that \certify" whether a set of arguments can be pro tably used to support a point of view in a discussion. For instance, under the admissible semantics, a set S of arguments is an extension if S is \con ict-free" (i.e., there is no defeat between arguments in S) and is \robust" against the other arguments (i.e., every argument outside S attacking an argument in S is counterattacked by an argument in S). This means that one using the set of arguments S in a discussion does not contradict her/himself, and can rebut to the arguments possibly presented by the other parties.

As a matter of fact, in the real world, arguments and defeats are often uncertain. For instance, consider an argument a (or a defeat ) encoding an interpretation or a translation of the description of a fact reported in a reference text. Then, a (or ) may be uncertain in the sense that the original paragraph may have interpretations other than that encoded by a (or ).

Thus, several proposals have been made to model uncertainty in AAFs, by considering weights, preferences, or probabilities associated with arguments and/or defeats. One of the most popular approaches based on probability theory for modeling the uncertainty is the so called constellations approach [ 12, 32, 7, 9, 25, 27, 30, 19, 20 ]: the dispute is represented by means of a Probabilistic Argumentation Framework (PrAAF), that consists in a set of alternative scenarios, each represented by an argumentation graph associated with a probability. The various works in the literature investigating PrAAFs can di er in the assumption on how the probability distribution function (pdf) over the scenarios is specied. For instance, in [ 12 ], the pdf is de ned \extensively", by enumerating all the possible scenarios and, for each of them, the value of its probability. On the other hand, in [ 30 ], the restriction that arguments and defeats are independent is assumed, and this is exploited to simplify the way probabilities are speci ed: the pdf is not explicitly speci ed, as it is implied by the marginal probabilities associated with arguments and defeats.

As regards reasoning over an argumentation framework, in the deterministic setting, two classical problems supporting the reasoning over AAFs have been deeply investigated and used in practical applications: { Extsem(S): the problem of deciding whether a set of arguments S is an extension according to the semantics sem; { CAsem: the problem of deciding whether the argument a is acceptable, i.e., it belongs to at least one extension under the semantics sem.

Basically, the relevance of these problems is that solving Extsem(S) supports the decision on whether presenting a set of arguments in a dispute is a reasonable strategy, while solving CAsem focuses this analysis on single arguments. In the probabilistic setting, there are multiple scenarios to be taken into account, and an argument a can be acceptable in some scenarios, but not in others. Thus, the natural probabilistic counterparts P-Extsem(S) and P-CAsem of the above-mentioned problems Extsem(S) and CAsem consist in evaluating the overall probability that S is an extension and a is acceptable, respectively, where \overall" means summing the probabilities of the scenarios where the property is veri ed.

The complexity of Extsem(S) and P-Extsem(S) has been deeply investigated. Speci cally, in the probabilistic setting the complexity of P-Extsem(S) has been investigated both in the case that the assumption that arguments and defeats are independent holds [19{22] and in more general cases [ 23 ].

As regards CAsem, its complexity has been deeply investigated, showing that it ranges from PTIME to P2p-complete, depending on the adopted semantics [ 6, 14, 5, 13 ]. Detailed complexity results from the literature are reported in the rst column of Table 1.

However, to the best of our knowledge no work has been done for characterizing the complexity of P-CAsem.

In this paper we focus on the constellations approach with independence proposed in [ 30 ] and analyze the complexity of P-CAsem showing that it is F P #P -complete independently from the adopted semantics (see the second column of Table 1). Proving that the problem is intractable backs the usage of alternative strategies for solving P-CAsem, such as resorting to Monte-carlo based probability estimation approaches. In this section, we brie y recall some basic notions about computational complexity, and concisely overview Dung's abstract argumentation framework, and its probabilistic extension introduced in [ 30 ]. The computational complexity of the problem addressed in this paper is related to the complexity classes of counting problems. A counting problem f is a function from strings over a nite alphabet into integers. #P is the complexity class of the functions f such that f counts the number of accepting paths of a nondeterministic polynomial-time Turing machine [ 34 ]. Although the problem addressed in the paper is closely related to #P , strictly speaking, it cannot belong to it, since the outputs of our problem are not integers. In fact, we deal with the class F P #P , that is, the class of functions computable by a polynomialtime Turing machine with a #P oracle. In this regard, note that a function is

F P #P -hard i it is #P -hard, and thus to prove that a problem is F P #P -hard it su ces to reduce a #P -hard problem to it. 2.2 An abstract argumentation framework [ 10 ] (AAF ) is a pair hA; Di, where A is a nite set, whose elements are referred to as arguments, and D A A is a binary relation over A, whose elements are referred to as defeats (or attacks). An argument is an abstract entity whose role is entirely determined by its relationships with other arguments. Given an AAF A, we also refer to the set of its arguments and the set of its defeats as Arg(A) and Def (A), respectively.

Given arguments a; b 2 A, we say that a defeats b i there is (a; b) 2 D. Similarly, a set S A defeats an argument b 2 A i there is a 2 S such that a defeats b.

A set S A of arguments is said to be con ict-free if there are no a; b 2 S such that a defeats b. An argument a is said to be acceptable w.r.t. S A i 8b 2 A such that b defeats a, there is c 2 S such that c defeats b. Given a set S A of arguments, we de ne S+ as the set of arguments that are defeated by S, that is, S+ = fa 2 A s.t. S defeats ag.

Several semantics for AAFs have been proposed to identify \reasonable" sets of arguments, called extensions. We consider the following well-known semantics [ 10, 11, 4 ]: admissible (ad), stable (st), complete (co), grounded (gr), semi-stable (sst), preferred (pr), ideal-set (ids), and ideal (ide). A set S A is said to be: { an admissible extension i S is con ict-free and all its arguments are acceptable w.r.t. S; { a stable extension i S is con ict-free and S defeats each argument in A n S; { a complete extension i S is admissible and S contains all the arguments that are acceptable w.r.t. S; { a grounded extension i S is a minimal (w.r.t. ) complete set of arguments; { a semi-stable extension i S is a complete extension where S [S+ is maximal (w.r.t. ); { a preferred extension i S is a maximal (w.r.t. ) admissible set of arguments; { an ideal-set extension i S is admissible and S is contained in every preferred set of arguments; { an ideal extension i S is a maximal (w.r.t. ) ideal-set extension; Example 1. Consider the AAF hA, D i, where the set A of arguments is fa; b; cg and the set D of defeats is f 1 = (b; a); 2 = (b; c); 3 = (c; b)g, where 2 and 3 encode the fact that arguments b and c attack each other. A graphical rapresentation of the AAF hA, D i is reported in Figure 1, where arguments are represented as nodes and defeats are represented as edges between nodes. As S = fa; cg is con ict-free and every argument in S is acceptable w.r.t. S, it is the case that S is admissible. It is easy to see that the sets fbg, fcg, and ; are admissible extensions as well. Since S is con ict-free and defeats b (the only argument in AnS) it is also a stable extension. As S is maximally admissible, it a preferred extension, while fcg is not, since a is acceptable w.r.t fcg. It is easy to check that S is complete, while it neither is grounded (since it is not minimally complete, as the emptyset is complete) nor ideal or ideal-set (since it is not contained in fbg which is a preferred extension). 2

Fig. 1: The AAF hA, Di

Given an AAF A, a set S Arg(A) of arguments, an argument a 2 Arg(A) and a semantics sem 2fad, st, gr, co, sst, pr, ids, ideg, we de ne the function acc(A; sem; a) that returns true if 9S Arg(A) such that a 2 S and S is an extension according to sem, false otherwise.

Example 2. Consider the AAF hA, D i introduced in Example 1. The argument a is credulously accepted under the admissible, stable, complete, semi-stable and preferred semantics. a is not credulousy accepted under the grounded, ideal-set and ideal semantics. 2 2.3

Probabilistic Abstract Argumentation

We now review the probabilistic abstract argumentation framework proposed in [ 30 ].

De nition 1 (PrAAF). A probabilistic argumentation framework (PrAAF) is a tuple hA; PA; D; PDi where hA; Di is an AAF, and PA and PD are, respectively, functions assigning a non-zero1 probability value to each argument in A and defeat in D, that is, PA : A ! (0; 1] \ Q and PD : D ! (0; 1] \ Q.

Basically, the value assigned by PA to an argument a represents the probability that a actually occurs, whereas the value assigned by PD to a defeat (a; b) represents the conditional probability that a defeats b given that both a and b occur.

The meaning of a PrAAF is given in terms of possible worlds, each of them representing a scenario that may occur in the reality. Given a PrAAF F , a possible world is modeled by an AAF which is derived from F by considering only a subset of its arguments and defeats. More formally, given a PrAAF F = hA; PA; D; PDi, a possible world w of F is an AAF hA0; D0i such that A0 A and D0 D \ (A0 A0). The set of the possible worlds of F will be denoted as pw(F ). 1 Assigning probability equal to 0 to arguments/defeats is useless.

Example 3. As a running example, consider the PrAAF F = hA; PA; D; PDi reported in Figure 2, where A and D are those of Example 1, and PA(a) = :9; PA(b) = :7; PA(c) = :2; PD( 1) = :9 and PD( 2) = PD( 3) = 1. The set pw(F ) contains the following possible worlds:

w1 = h;; ;i w2 = hfag; ;i w3 = hfbg; ;i w4 = hfcg; ;i w5 = hfa; bg; ;i w6 = hfa; cg; ;i w7 = hfb; cg; ;i w8 = hA; ;i w9 = hfa; bg; f 1gi w10 = hfb; cg; f 3gi w11 = hfb; cg; f 2gi w12 = hfb; cg; f 2; 3gi w13 = hA; f 1gi w14 = hA; f 1; 3gi w15 = hA; f 1; 2gi w16 = hA; Di w17 = hA; f 2gi w18 = hA; f 3gi w19 = hA; f 2; 3gi a .9 .9 b .7 1.0 1.0 c .2 Fig. 2: The PrAAF hA; PA; D; PDi

An interpretation for a PrAAF F = hA; PA; D; PDi is a probability distribution function I over the set pw(F ) of the possible worlds. Assuming that arguments represent pairwise independent events, and that each defeat represents an event conditioned by the occurrence of its argument events but independent from any other event, the interpretation for the PrAAF F = hA; PA; D; PDi is as follows. For each possible world w 2 pw(F ), w is assigned by I the probability: I(w) = Qa2Arg(w) PA(a)

Q

a2AnArg(w)(1 Q 2Def(w) PD( )

Q 2D(w)nDef(w)(1

PA(a))

PD( )) where D(w) is the set of defeats that may appear in the possible world w, that is D(w) = D \ (Arg(w) Arg(w)). Hence, the probability of a possible world w is given by the product of four contributions: (i ) the product of the probabilities of the arguments belonging to w; (ii ) the product of the one's complements of the probabilities of the arguments that do not appear in w; (iii ) the product of the conditional probabilities of the defeats in w (recall that a defeat = (a; b) may appear in w only if both a and b are in w); (iv ) the product of the one's complements of the conditional probabilities of the defeats that, though they may appear in w, they do not.

Example 4. Continuing our running example, the interpretation I for F is as follows. First of all, observe that, for each possible world w 2 pw(F ), if both arguments b and c belong to Arg(w) and 2 62 Def (w) or 3 62 Def (w), then I(w) = 0. The probabilities of the other possible worlds are the following:

I(w1) = :024 I(w2) = :216 I(w3) = :056 I(w4) = :006 I(w5) = :0504 I(w6) = :054 I(w9) = :4536 I(w12) = :014 I(w16) = :1134 I(w19) = :0126 2 2

The probability that an argument a is acceptable according to a given semantics sem is de ned as the sum of the probabilities of the possible worlds w for which a is acceptable according to sem, i.e., acc(w; sem; a) = true. De nition 2 (P rCAsem(a)). Given a PrAAF F = hA; PA; D; PDi, an argu

F ment a 2 A, and a semantics sem, the probability P rCAsem(a) that a is acceptF able under sem is

P rCAsem(a) =

F

X w2pwAcc(F;a)

I(w); where pwAcc(F ; a) = fw 2 pw(F ) jacc(w; sem; a) =trueg.

The following example shows usages of this de nition.

Example 5. In our running example, the probabilities that the arguments a and b are acceptable w.r.t. the admissible semantics are as follows:

P rCAaFd(a) = I(w2) +I(w5) +I(w6) +I(w16) +I(w19) = :4464

P rCAaFd(b) = I(w3)+ I(w5)+ I(w9)+ I(w12)+ I(w16)+ I(w19) = :8134 Obviously, computing P rCAsem(a) by directly applying De nition 2 would

F require exponential time, since it relies on summing the probabilities of an exponential number of possible worlds. However, this does not rule out the possibility that e cient strategies for computing P rCAsFem(a) exist. Unfortunately, this is not true in the general case. Indeed, in the next section we show that the problem of computing P rCAsem(S) is F P #P -complete.

F De nition 3 (P-CAsem). Given a PrAAF F = hA; PA; D; PDi, an argument a 2 A, and a semantics sem, P-CAsem is the problem of computing the probability P rCAsem(a).

F 3

Complexity of credulous acceptability in probabilistic abstract argumentation

In this section we characterize the complexity of P-CAsem, by rst showing that it is in F P #P and then showing that it is F P #P -hard. 3.1

Upper bound

Theorem 1. For sem 2 fad, st, co, gr, sst, pr, ids, ide g, it holds that P-CAsem is in F P #P .

Proof. First, observe that P rCAsem(a) with sem 2 fad, st, co, gr, sst, pr,

F ids, ide g, can be expressed as a rational number whose denominator d is the product of the denominators of the probabilities of arguments in A and defeats in D.

We rst prove the statement for sem = gr. First observe that CAsem is ipnolPynToImMiEal ftoi mreseamlgo=ritghrm. WAewsihthowactcheasts PtorCaA#gFrP(ao)raccalne. bAelgcoormitphumtedA byrsat computes d in polynomial time w.r.t. the size of F , then calls a #P oracle to determine the numerator of PrCAgFr(a). The oracle counts the number of accepting paths of a nondeterministic polynomial-time Turing machine M such that: (i) M nondeterministically guesses a subset of arguments in A and defeats in D so that each leaf of the resulting computation tree is a possible world w 2 pw(F ); (ii) At each leaf, let w be the guessed world, and I(w) its probability, the computation tree is then split again d I(w) times to re ect the probability of the guessed world (for each w 2 pw(F ), I(w) is a rational number whose denominator is d, and I(w) can be computed in polynomial time w.r.t. the size of F ); (iii) Finally, M checks in polynomial time if a is an acceptable argument in the world w w.r.t. the grouded semantics.

Thus, the number of accepting paths of M is d PrCAgFr(a) that is the numerator n of PrCAgFr(a). As a nal step, algorithm A returns both n and d.

To prove the statement for sem 2fad, st, co, sst, pr, ids, ideg it su ces to reason analogously to the membership proof for the grounded semantics, by considering that CAsem for those semantics is either in NP, or in 2p, or in P2p.

Speci cally, for sem 2fad, st, co, sst, pr, ids, ideg, PrCAsem(a) can be F computed by an algorithm A0 which behaves as follows. A0 rst computes (in polynomial time) the denominator d of PrCAsFem(a). Then A0 invokes a #N P , or a # 2p or a # P2p oracle that counts the number of accepting paths of a non-deterministic Turing machine M 0 de ned in the same way of M with the di erence that the step (iii ) of the computation of M is replaced by the invocation of either an N P , a 2p or a P2p oracle that checks whether a is an acceptable argument w.r.t. sem in the world w obtained as nal leaf of the computation tree.

Therefore, since F P #P = F P #NP = F P # 2p = F P # P2p , then P-CAsem is in F P #P . 2 3.2

Lower bound

To prove that P-CAsem is F P #P -hard we show a reduction from the #P -hard problem #P 2CN F , that is the problem of counting the number of satisfying assignments of a CN F formula where each clause consists of exactly 2 positive literals, to P-CAsem. { A = fa; c1; : : : ; ck; x1; : : : ; xng; { D = f(ci; a) j i 2 [1::k]g S(Ch=Xi_Xj)2 f(xi; ch); (xj ; ch)g; { PA(a) = 1:0, 8i 2 [1::k]PA(ci) = 1:0, and 8j 2 [1::n]PA(xj ) = 12 ; { PD( ) = 1:0 for each 2 D.

Moreover, let be a truth assignment for the propositional variables x1; : : : ; xn. We de ne as w( ; F ( )) the possible world w = hAw; Dwi 2 pw(F ( )) de ned as follows: { Aw = A n fxi j i 2 [1::n] ^ (xi) =falseg; { Dw = D n f(xi; cj ) j i 2 [1::n] ^ j 2 [1::k] ^ (xi) = falseg ;

It is easy to see that given a possible world w 2 pw(F ( )) the probability of w is I(w) = 21n .

Example 6. Consider the P 2CN F formula = (X1 _ X3) ^ (X2 _ X3). The PrAAf F ( ) is reported in Figure 3(a), where probabilities di erent from 1:0 are reported next to each node and edge. Moreover, consider the truth assignment for X1; X2 and X3 such that (X1) =true, (X2) =true and (X3) =false. The possible world w( ; F ( )) is reported in Figure 3(b). 2 a c1 c2 a c1 c2 1 1 1 x1 2 x2 2 x3 2 (a) x1 (b) x2

Lemma 1. Let = C1 ^ C2 ^ : : : Ck be a P 2CN F , where X = fX1; : : : ; Xng is the set of its propositional variables.

For each truth assignment for the propositional variables X1; : : : ; Xn it holds that CAawd( ;F( ))(a) is true i ( ) is true.

Proof. We rst prove that for each truth assignment for X1; : : : ; Xn the fact ad that CAw( ;F( ))(a) is true implies that ( ) is true.

Reasoning by contradiction assume that there exists a truth assignment for X1; : : : ; Xn such that w = w( ; F ( )) and CAawd(a) is true while ( ) is false.

Since CAawd(a) is true there exists an admissible extension S for w such that a 2 S. It is easy to see that S \ fc1; : : : ; ckg = ;, as otherwise S would not be an admissible extension (S would not be con ict-free). Moreover, it is easy to see that there exists a subset fxi1 ; : : : ; xih g of fx1; : : : ; xng such that fxi1 ; : : : ; xih g S and for each j 2 [1::k] there is l 2 [1::h] such that: 1. xil 2 Aw, and 2. (xil ; cj) 2 Dw, as otherwise S would not be an admissible extension as there would be a cj attacking a which is not attacked by any argument in S.

Since ( ) is false it must be the case that there is a j 2 [i::k] such that Cj = Xl _ Xh and (Xl) = (Xh) =false. This implies that xl 62 Aw, xh 62 Aw, (xl; cj) 62 Dw and (xh; cj) 62 Dw, thus contradicting the fact that S is an admissible extension. Hence, it holds that for each truth assignment for ad x1; : : : ; xn the fact that CAw( ;F( ))(a) is true implies that ( ) is true.

We now prove that for each truth assignment for x1; : : : ; xn the fact that ad ( ) is true implies that CAw( ;F( ))(a) is true. Reasoning by contradiction assume that there exists a truth assignment for x1; : : : ; xn such that w = w( ; F ( )) and CAawd(a) is false while ( ) is true.

Let S be the set of arguments fag [ fxi j i 2 [1::n] ^ (Xi) = trueg. We show that S is an admissible extension reasoning by contradiction. Since S is not an admissible extension it must be the case that there is a j 2 [1::k] such that Cj = Xh _ Xl and both xh 2= S and xl 2= S. Hence, by construction of S it holds that (Xh) = (Xh) = false which, in turn, implies that ( ) = false, thus contradicting that is a truth assignment for x1; : : : ; xn such that ( ) is true. This implies that for each truth assignment for x1; : : : ; xn the fact that ( ) is true implies that CAawd( ;F( ))(a) is true.

Lemma 2. Let = C1 ^ C2 ^ : : : Ck be a P 2CN F , where X = fX1; : : : ; Xng is the set of its propositional variables.

For a possible world w 2 pw(F ( )) CAawd( ;F( ))(a) is true i CAswe(m;F( ))(a), where sem 2fst, co, gr, sst, pr, ids, ideg, is true.

Proof. The if part is straightforward since stable, complete, grounded, semistable, preferred, ideal-set and ideal extensions are admissible extensions. As regards the proof of the only if part, reasoning by contradiction we assume that there is an admissible extension S such that a 2 S and there is no extension S0 according to sem, where sem 2fst, co, gr, sst, pr, ids, ide g, such that a 2 S0.

Consider the set of arguments S^ = S [ (Arg(w) \ fx1; : : : ; xng), and note that Arg(w) n S^ = fc1; : : : ; ckg. It is straightforward to see that, since S is an admissible extension then S^ is an admissible extension. Moreover, it is easy to see that (i) S^ is a stable extension since it defeats each argument in Arg(w) n S^, (ii) S^ is a complete extension since it contains all the argument that are acceptable w.r.t. S^, (iii) S^ is a preferred extension since S^ is an admissible extension and any argument in Arg(w)nS^ attacks an argument in S^, so that for each argument 2 Arg(w) n S^ it holds that S^ [ is not con ict-free. Moreover, observe that S^ is the unique preferred extension for w.

Furthermore, since S^ is a complete extension and since removing any argument from S^ make it loose the property that it contains all the arguments that are acceptable w.r.t. it, it holds that S^ is a grounded extension.

Moreover, since S^ [ S^+ = Arg(w) then there is no complete extension S such that S [ S+ S^ [ S^+. Therefore, since S^ is a complete extension it follows that S^ is a semi-stable extension.

Finally, it is straightforward to see that S^ is an ideal-set and ideal extension for w as it is the unique preferred extension for w.

Hence, for possible world w 2 pw(F ( )) CAawd( ;F( ))(a) is true only if CAswe(m;F( ))(a) is true, where sem 2 fst, co, gr, sst, pr, ids, ideg, which completes the proof.

Theorem 2. For sem 2fad, st, co, gr, sst, pr, ids, ideg, it holds that PCAsem is F P #P -hard.

Proof. Given an instance of #P 2CN F , we construct an instance of PCAsem by de ning a PrAAF F = F ( ) as in De nition 4, and we return 2n (P rCAsFem(a)).

Since for each possible world w 2 pw(F ( )) we have that I(w) = 21n , from Lemmas 1 and 2 it follows that 2n (P rCAsem(a)) is the number of satisfying F assignments of .

Hence, as the above described reduction from the #P -hard problem #P 2CN F to P-CAsem is a Cook reduction, this su ces to prove that P-CAsem is F P #P -hard, since a problem is F P #P -hard i it is #P -hard. 4

RELATED WORK

The main state-of-the-art approaches for handling uncertainty in AAFs by relying on probability theory can be classi ed in two categories, based on the way they interpret the probabilities of the arguments: those adopting the classical constellations approach [ 27, 12, 32, 7, 9, 25, 30, 19, 20 ] and those adopting the recent epistemic one [ 33, 29, 28 ]. As regards the epistemic approach, probabilities and extensions have a di erent semantics, compared with the constellations approach. Speci cally, the probability of an argument represents the degree of belief in the argument (the higher the probability, the more the argument is believed), and a key concept is the \rational" probability distribution, that requires that if the belief in an argument is high, then the belief in the arguments attacked by it is low. In this approach, epistemic extensions are considered rather than Dung's extensions, where an epistemic extension is the set of arguments that are believed to be true to some degree. The interested reader can detailed comparative description of the two categories in [ 26 ]. nd a more

We now focus our attention on the approaches classi ed as constellations, as the complexity characterization provided in our work refers to this class of PrAAFs. [ 12 ] addressed the modeling of jury-based dispute resolutions, and proposed a prAAF where uncertainty is taken into account by specifying probability distribution functions (pdfs) over possible AAFs and showing how an instance of the proposed prAAF can be obtained by specifying a probabilistic assumption-based argumentation framework (introduced by themselves). In the same spirit, [ 32 ] de ned a prAAF as a pdf over the set of possible AAFs, and introduced a probabilistic version of a fragment of the ASPIC framework [ 31 ] that can be used to instantiate the proposed prAAF. [ 8 ] addresses the problem of computing all the subgraphs of an AAF in which an argument a belongs to the grounded extension, and [ 9 ] extends it by focusing on computing the probability that an argument a belongs to the grounded extension of a probabilistic abstract argumentation framework. In particular, [ 9 ] assumes to receive a joint probability distribution over the arguments as input. In fact, providing a joint probability distribution usually means specifying the probability values for all the possible correlations, i.e., P (a), P (a ^ b), P (a ^ b ^ c)::: and so on. This is analogous to providing the probabilities for all the possible AAFs (since defeats are considered as certain).

Di erently from [ 12 ] and [ 32 ], [ 30 ] proposed a prAAF where probabilities are directly associated with arguments and defeats, instead of being associated with possible AAFs, and independence among pairs of arguments/defeats is assumed. After claiming that computing the probability P sem(S) that a set S of arguments is an extension according to sem requires exponential time for every semantics, [ 30 ] proposed a Monte-Carlo simulation approach to approximate P sem(S). [ 7, 19, 20 ] build upon [ 30 ]: [ 7 ] characterizes di erent semantics from the approach of [ 30 ] in terms of probabilistic logic, as a rst step in the direction of creating a uniform logical formalization for all the proposed AAFs of the literature, in order to understand and compare the di erent approaches. [ 19, 20 ], instead, showed that computing P sem(S) is actually tractable for the admissible and stable semantics, but it is F P #P -complete for other semantics, including complete, grounded, preferred and ideal-set. Furthermore, [ 18, 21 ] proposed a Monte-Carlo approach to e ciently estimate P sem(S) based on the polynomiality results of [ 19, 20 ]. In [ 30 ], as well as in [ 12 ] and [ 32 ], P sem(S) is de ned as the sum of the probabilities of the possible AAFs where S is an extension according to semantics sem.

In the above-cited works, probability theory is recognized as a fundamental tool to model uncertainty. However, a deeper understanding of the role of probability theory in abstract argumentation was developed only later in [ 25, 26 ], where the justi cation and the premise perspectives of probabilities of arguments are introduced. According to the former perspective the probability of an argument indicates the probability that it is justi ed in appearing in the argumentation system. In contrast, the premise perspective views the probability of an argument as the probability that the argument is true based on the degrees to which the premises supporting the argument are believed to be true. Starting from these perspectives, in [ 26 ], a formal framework showing the connection among argumentation theory, classical logic, and probability theory was investigated. Furthermore, quali cation of attacks is addressed in [ 27 ], where an investigation of the meaning of the uncertainty concerning defeats in probabilistic abstract argumentation is provided.

The computational complexity of computing extensions has been thoroughly investigated for classical AAFs [ 15, 16, 13, 17, 24, 3 ] with respect to several semantics (a comprehensive overview of argumentation semantics can be found in [ 1 ]). In particular, [ 15 ] presents a number of results on the complexity of some decision questions for semi-stable semantics, while [ 13 ] focuses on ideal semantics; complexity results for preferred semantics can be found in [ 16 ].

Complexity results about skeptical and credulous acceptance under admissible, complete, grounded, stable and preferred semantics have been provided in [ 6, 14, 5 ], while [ 13 ] characterizes the complexity of skeptical and credulous acceptance under ideal and ideal-set. 5

Conclusion and future works

Focusing on the constellations approach with independence proposed in [ 30 ], in this paper we characterized the complexity of P-CAsem showing that it is F P #P -complete independently from the adopted semantics. Future work will be devoted to the characterization of the complexity of the problem of computing the probability that an argument is skeptically acceptable w.r.t. a given semantics sem. Moreover, another interesting direction for future work is that of nding tractable cases for P-CAsem by identifying structural properties of the argumentation graph that will ensure that P-CAsem is solvable in polynomial time.

References

1. Baroni , P. , Caminada , M. , Giacomin , M.: An introduction to argumentation semantics . Knowledge Eng. Review 26 ( 4 ), 365 { 410 ( 2011 )

2. Baroni , P. , Giacomin , M. : Semantics of abstract argument systems . In: Argumentation in Arti cial Intelligence , pp. 25 { 44 ( 2009 )

3. Booth , R. , Caminada , M. , Dunne , P.E. , Podlaszewski , M. , Rahwan , I. : Complexity properties of critical sets of arguments . In: Proc. of Computational Models of Argument (COMMA) . pp. 173 { 184 ( 2014 )

4. Caminada , M. : Semi-stable semantics . In: Proc. Int. Conf. Computational Models of Argument (COMMA) . pp. 121 { 130 ( 2006 )

5. Coste-Marquis , S. , Devred , C. , Marquis , P. : Symmetric argumentation frameworks . In: Proc. of Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU) . pp. 317 { 328 ( 2005 )

6. Dimopoulos , Y. , Torres , A. : Graph theoretical structures in logic programs and default theories . Theor. Comput. Sci . 170 ( 1-2 ), 209 { 244 ( 1996 )

7. Doder , D. , Woltran , S. : Probabilistic argumentation frameworks - A logical approach . In: Proc. Int. Conf. on Scalable Uncertainty Management (SUM) . pp. 134 { 147 ( 2014 )

8. Dondio , P. : Computing the grounded semantics in all the subgraphs of an argumentation framework: An empirical evaluation . In: Proc. Int. Workshop Computational Logic in Multi-Agent Systems (CLIMA) . pp. 119 { 137 ( 2013 )

9. Dondio , P. : Toward a computational analysis of probabilistic argumentation frameworks . Cybernetics and Systems 45 ( 3 ), 254 { 278 ( 2014 )

10. 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 )

11. Dung , P.M. , Mancarella , P. , Toni , F. : Computing ideal sceptical argumentation . Artif. Intell . 171 ( 10 - 15 ), 642 { 674 ( 2007 )

12. Dung , P.M. , Thang , P.M.: Towards (probabilistic) argumentation for jury-based dispute resolution . In: Proc. Int. Conf. Computational Models of Argument (COMMA) . pp. 171 { 182 ( 2010 )

13. Dunne , P.E. : The computational complexity of ideal semantics . Artif. Intell . 173 ( 18 ) ( 2009 )

14. Dunne , P.E. , Bench-Capon , T.J.M.: Coherence in nite argument systems . Artif. Intell . 141 ( 1 /2), 187 { 203 ( 2002 )

15. Dunne , P.E. , Caminada , M. : Computational complexity of semi-stable semantics in abstract argumentation frameworks . In: Proc.European Conf. on Logics in Arti cial Intelligence (JELIA) . pp. 153 { 165 ( 2008 )

16. Dunne , P.E. , Wooldridge , M. : Complexity of abstract argumentation . In: Argumentation in Arti cial Intelligence , pp. 85 { 104 ( 2009 )

17. Dvorak , W. , Woltran , S. : Complexity of semi-stable and stage semantics in argumentation frameworks . Inf. Process. Lett . 110 ( 11 ), 425 { 430 ( 2010 )

18. Fazzinga , B. , Flesca , S. , Parisi , F.: E ciently estimating the probability of extensions in abstract argumentation . In: Proc. Int Conf. on Scalable Uncertainty Management (SUM) . pp. 106 { 119 ( 2013 )

19. Fazzinga , B. , Flesca , S. , Parisi , F. : On the complexity of probabilistic abstract argumentation . In: Proc. Int. Joint Conference on Arti cial Intelligence (IJCAI) ( 2013 )

20. Fazzinga , B. , Flesca , S. , Parisi , F. : On the complexity of probabilistic abstract argumentation frameworks . ACM Trans. Comput. Log. (TOCL) 16(3) , 22 ( 2015 )

21. Fazzinga , B. , Flesca , S. , Parisi , F. : On e ciently estimating the probability of extensions in abstract argumentation frameworks . Int. J. Approx. Reasoning 69 , 106 { 132 ( 2016 )

22. Fazzinga , B. , Flesca , S. , Parisi , F. , Pietramala , A. : PARTY: A mobile system for e ciently assessing the probability of extensions in a debate . In: Proc. Int. Conf. on Database and Expert Systems Applications (DEXA) . pp. 220 { 235 ( 2015 )

23. Fazzinga , B. , Flesca , S. , Parisi , F. , Pietramala , A. : Computing or estimating extension's probabilities over structured probabilistic argumentation frameworks. Special Issue on Probabilistic and other Quantitative Approaches to Computational Argumentation of the IfCoLog Journal of Logics and their Applications 3 ( 2 ), 177 { 200 ( 2016 )

24. Gaggl , S.A. , Woltran , S.: The cf2 argumentation semantics revisited . J. Log. Comput . 23 ( 5 ), 925 { 949 ( 2013 )

25. Hunter , A. : Some foundations for probabilistic abstract argumentation . In: Proc. Int. Conf. Computational Models of Argument (COMMA) . pp. 117 { 128 ( 2012 )

26. Hunter , A. : A probabilistic approach to modelling uncertain logical arguments . Int. J. Approx. Reasoning 54 ( 1 ), 47 { 81 ( 2013 )

27. Hunter , A. : Probabilistic quali cation of attack in abstract argumentation . Int. J. Approx. Reasoning 55 ( 2 ), 607 { 638 ( 2014 )

28. Hunter , A. , Thimm , M. : Probabilistic argumentation with epistemic extensions . In: Proc. Int. Workshop on Defeasible and Ampliative Reasoning (DARe@ECAI) ( 2014 )

29. Hunter , A. , Thimm , M. : Probabilistic argumentation with incomplete information . In: Proc. European Conf. on Arti cial Intelligence (ECAI) . pp. 1033 { 1034 ( 2014 )

30. Li , H. , Oren , N. , Norman , T.J.: Probabilistic argumentation frameworks . In: Proc. Int. Workshop on Theorie and Applications of Formal Argumentation (TAFA) ( 2011 )

31. Prakken , H. : An abstract framework for argumentation with structured arguments . Argument & Computation 1 ( 2 ), 93 { 124 ( 2010 )

32. Rienstra , T. : Towards a probabilistic dung-style argumentation system . In: AT . pp. 138 { 152 ( 2012 )

33. Thimm , M.: A probabilistic semantics for abstract argumentation . In: Proc. European Conf. on Arti cial Intelligence (ECAI) . pp. 750 { 755 ( 2012 )

34. Valiant , L.G. : The complexity of computing the permanent . Theor. Comput. Sci. (TCS) 8 , 189 { 201 ( 1979 )