=Paper=
{{Paper
|id=Vol-2012/paper_05
|storemode=property
|title=Credulous Acceptability in Probabilistic Abstract Argumentation: Complexity Results
|pdfUrl=https://ceur-ws.org/Vol-2012/AI3-2017_paper_5.pdf
|volume=Vol-2012
|authors=Bettina Fazzinga,Sergio Flesca,Filippo Furfaro
|dblpUrl=https://dblp.org/rec/conf/aiia/FazzingaFF17
}}
==Credulous Acceptability in Probabilistic Abstract Argumentation: Complexity Results ==
https://ceur-ws.org/Vol-2012/AI3-2017_paper_5.pdf
Credulous acceptability in probabilistic abstract
argumentation: complexity results
Bettina Fazzinga, Sergio Flesca, and Filippo Furfaro
DIMES, University of Calabria, Italy
ICAR-CNR, Italy
{flesca,furfaro}@dimes.unical.it
{fazzinga}@icar.cnr.it
Abstract. Probabilistic abstract argumentation combines Dung’s ab-
stract 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. Specifically, we
focus on the most popular semantics (i.e., admissible, stable, semi-stable,
complete, grounded, preferred, ideal, ideal-set), and show that comput-
ing the probability that an argument is credulously accepted is FP #P -
complete independently from the adopted semantics.
Keywords: Acceptability, Probabilistic Abstract Argumentation, Com-
plexity
1 Introduction
Several argumentation frameworks have been proposed, with the aim of suitably
modeling disputes between two or more parties. Typically, argumentation frame-
works 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 sem-
inal 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 argu-
ments can be profitably 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 “conflict-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
2 Bettina Fazzinga et al.
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 uncer-
tain. For instance, consider an argument a (or a defeat δ) encoding an interpre-
tation 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 Argu-
mentation 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 differ in the assumption
on how the probability distribution function (pdf) over the scenarios is speci-
fied. For instance, in [12], the pdf is defined “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 specified:
the pdf is not explicitly specified, 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) sup-
ports the decision on whether presenting a set of arguments in a dispute is a
reasonable strategy, while solving CAsem focuses this analysis on single argu-
ments. 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 oth-
ers. 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 verified.
The complexity of Extsem (S) and P-Extsem (S) has been deeply investi-
gated. Specifically, 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].
Credulous acceptability... 3
As regards CAsem , its P
complexity has been deeply investigated, showing that
p
it ranges from PTIME to 2 -complete, depending on the adopted semantics [6,
14, 5, 13]. Detailed complexity results from the literature are reported in the first
column of Table 1.
However, to the best of our knowledge no work has been done for character-
izing 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 col-
umn 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.
Table 1: Complexity of CAsem and P-CAsem .
sem CAsem P-CAsem
admissible NP -complete F P #P -complete
stable NP -complete F P #P -complete
complete NP -complete F P #P -complete
grounded PTIME F P #P -complete
Pp #P
semi-stable 2 -complete F P -complete
preferred NP -complete F P #P -complete
ideal-set in Θ2p , coNP -h F P #P -complete
ideal in Θ2p , coNP -h F P #P -complete
2 Preliminaries
In this section, we briefly recall some basic notions about computational com-
plexity, and concisely overview Dung’s abstract argumentation framework, and
its probabilistic extension introduced in [30].
2.1 Complexity
The computational complexity of the problem addressed in this paper is re-
lated to the complexity classes of counting problems. A counting problem f is a
function from strings over a finite 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 be-
long 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 polynomial-
time Turing machine with a #P oracle. In this regard, note that a function is
4 Bettina Fazzinga et al.
F P #P -hard iff it is #P -hard, and thus to prove that a problem is F P #P -hard
it suffices to reduce a #P -hard problem to it.
2.2 Abstract Argumentation
An abstract argumentation framework [10] (AAF ) is a pair hA, Di, where A
is a finite 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 ∈ A, we say that a defeats b iff there is (a, b) ∈ D.
Similarly, a set S ⊆ A defeats an argument b ∈ A iff there is a ∈ S such that a
defeats b.
A set S ⊆ A of arguments is said to be conflict-free if there are no a, b ∈ S
such that a defeats b. An argument a is said to be acceptable w.r.t. S ⊆ A iff
∀b ∈ A such that b defeats a, there is c ∈ S such that c defeats b. Given a set
S ⊆ A of arguments, we define S + as the set of arguments that are defeated by
S, that is, S + = {a ∈ A s.t. S defeats a}.
Several semantics for AAFs have been proposed to identify “reasonable”
sets of arguments, called extensions. We consider the following well-known se-
mantics [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 iff S is conflict-free and all its arguments are accept-
able w.r.t. S;
– a stable extension iff S is conflict-free and S defeats each argument in A \ S;
– a complete extension iff S is admissible and S contains all the arguments
that are acceptable w.r.t. S;
– a grounded extension iff S is a minimal (w.r.t. ⊆) complete set of arguments;
– a semi-stable extension iff S is a complete extension where S ∪S + is maximal
(w.r.t. ⊆);
– a preferred extension iff S is a maximal (w.r.t. ⊆) admissible set of argu-
ments;
– an ideal-set extension iff S is admissible and S is contained in every preferred
set of arguments;
– an ideal extension iff S is a maximal (w.r.t. ⊆) ideal-set extension;
Example 1. Consider the AAF hA, Di, where the set A of arguments is {a, b, c}
and the set D of defeats is {δ1 = (b, a), δ2 = (b, c), δ3 = (c, b)}, where δ2 and
δ3 encode the fact that arguments b and c attack each other. A graphical rap-
resentation of the AAF hA, Di is reported in Figure 1, where arguments are
represented as nodes and defeats are represented as edges between nodes. As
S = {a, c} is conflict-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 {b}, {c}, and ∅
Credulous acceptability... 5
are admissible extensions as well. Since S is conflict-free and defeats b (the only
argument in A\S) it is also a stable extension. As S is maximally admissible,
it a preferred extension, while {c} is not, since a is acceptable w.r.t {c}. 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 {b} which is a preferred extension). 2
a b c
Fig. 1: The AAF hA, Di
Given an AAF A, a set S ⊆ Arg(A) of arguments, an argument a ∈ Arg(A)
and a semantics sem ∈{ad, st, gr, co, sst, pr, ids, ide}, we define the function
acc(A, sem, a) that returns true if ∃S ⊆ Arg(A) such that a ∈ S and S is an
extension according to sem, false otherwise.
Example 2. Consider the AAF hA, Di 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].
Definition 1 (PrAAF). A probabilistic argumentation framework (PrAAF) is
a tuple hA, PA , D, PD i 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 proba-
bility 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, PD i, a possible world w of F is an AAF hA0 , D0 i 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.
6 Bettina Fazzinga et al.
Example 3. As a running example, consider the PrAAF F = hA, PA , D, PD i
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 = h{a}, ∅i w3 = h{b}, ∅i w4 = h{c}, ∅i
w5 = h{a, b}, ∅i w6 = h{a, c}, ∅i w7 = h{b, c}, ∅i w8 = hA, ∅i
w9 = h{a, b}, {δ1 }i w10 = h{b, c}, {δ3 }i w11 = h{b, c}, {δ2 }i w12 = h{b, c}, {δ2 , δ3 }i
w13 = hA, {δ1 }i w14 = hA, {δ1 , δ3 }i w15 = hA, {δ1 , δ2 }i w16 = hA, Di
w17 = hA, {δ2 }i w18 = hA, {δ3 }i w19 = hA, {δ2 , δ3 }i
.9 1.0
a b c
.9 .7 .2
1.0
Fig. 2: The PrAAF hA, PA , D, PD i
2
An interpretation for a PrAAF F = hA, PA , D, PD i is a probability distri-
bution function I over the set pw(F) of the possible worlds. Assuming that ar-
guments 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, PD i is as
follows. For each possible world w ∈ pw(F), w is assigned by I the probability:
Q Q
I(w) = a∈Arg(w) PA (a)× a∈A\Arg(w) (1 − PA (a))×
Q Q
× δ∈Def (w) PD (δ) × δ∈D(w)\Def (w) (1 − 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 ∈ pw(F), if both
arguments b and c belong to Arg(w) and δ2 6∈ Def (w) or δ3 6∈ Def (w), then
I(w) = 0. The probabilities of the other possible worlds are the following:
Credulous acceptability... 7
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
The probability that an argument a is acceptable according to a given se-
mantics sem is defined 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.
Definition 2 (P rCAsem
F (a)). Given a PrAAF F = hA, PA , D, PD i, an argu-
ment a ∈ A, and a semantics sem, the probability P rCAsem
F (a) that a is accept-
able under sem is X
P rCAsem
F (a) = I(w),
w∈pwAcc(F ,a)
where pwAcc(F, a) = {w ∈ pw(F) |acc(w, sem, a) =true}.
The following example shows usages of this definition.
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 rCAad
F (a) = I(w2 ) +I(w5 ) +I(w6 ) +I(w16 ) +I(w19 ) = .4464
P rCAad
F (b) = I(w3 )+ I(w5)+ I(w9)+ I(w12)+ I(w16)+ I(w19) = .8134
2
Obviously, computing P rCAsem F (a) by directly applying Definition 2 would
require exponential time, since it relies on summing the probabilities of an expo-
nential number of possible worlds. However, this does not rule out the possibility
that efficient strategies for computing P rCAsemF (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 F (S) is F P
#P
-complete.
Definition 3 (P-CAsem ). Given a PrAAF F = hA, PA , D, PD i, an argument
a ∈ A, and a semantics sem, P-CAsem is the problem of computing the proba-
bility P rCAsem
F (a).
3 Complexity of credulous acceptability in probabilistic
abstract argumentation
In this section we characterize the complexity of P-CAsem , by first showing that
it is in F P #P and then showing that it is F P #P -hard.
8 Bettina Fazzinga et al.
3.1 Upper bound
Theorem 1. For sem ∈ {ad, st, co, gr, sst, pr, ids, ide }, it holds that
P-CAsem is in F P #P .
Proof. First, observe that P rCAsem
F (a) with sem ∈ {ad, st, co, gr, sst, pr,
ids, ide }, 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 first prove the statement for sem = gr. First observe that CAsem is
gr
in PTIME for sem = gr. We show that PrCAF (a) can be computed by a
polynomial time algorithm A with access to a #P oracle. Algorithm A first
computes d in polynomial time w.r.t. the size of F, then calls a #P oracle
gr
to determine the numerator of PrCAF (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 ∈ pw(F);
(ii) At each leaf, let w be the guessed world, and I(w) its probability, the com-
putation tree is then split again d · I(w) times to reflect the probability of
the guessed world (for each w ∈ 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.
gr
Thus, the number of accepting paths of M is d· PrCAF (a) that is the numerator
gr
n of PrCAF (a). As a final step, algorithm A returns both n and d.
To prove the statement for sem ∈{ad, st, co, sst, pr, ids, ide} it suffices
to reason analogously to the membership proof for the grounded semantics,Pby
p
considering that CAsem for those semantics is either in NP, or in Θ2p , or in 2 .
sem
Specifically, for sem ∈{ad, st, co, sst, pr, ids, ide}, PrCAF (a) can be
computed by an algorithm A0 which behaves as follows. A0 first computes (in
sem 0
polynomial time) the
p Ppdenominator d of PrCAF (a). Then A invokes a #N P ,
or a #Θ2 or a # 2 oracle that counts the number of accepting paths of a
non-deterministic Turing machine M 0 defined in the same way of M with the
difference that the step (iii ) of P
the computation of M is replaced by the invoca-
p
tion of either an N P , a Θ2p or a 2 oracle that checks whether a is an acceptable
argument w.r.t. sem in the world w obtained as final leaf of the computation
tree. p Pp
Therefore, since F P #P = F P #N P = F P #Θ2 = F P # 2 , 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
Credulous acceptability... 9
assignments of a CN F formula where each clause consists of exactly 2 positive
literals, to P-CAsem .
Definition 4. Let φ = C1 ∧ C2 ∧ . . . Ck be a P 2CN F , where X = {X1 , . . . , Xn }
is the set of its propositional variables.
We define the PrAAF associated to φ (F(φ) = hA, PA , D, PD i) as follows:
– A = {a, c1 , . . . , ck , x1 , . .S
. , xn };
– D = {(ci , a) | i ∈ [1..k]} (Ch =Xi ∨Xj )∈φ {(xi , ch ), (xj , ch )};
– PA (a) = 1.0, ∀i ∈ [1..k]PA (ci ) = 1.0, and ∀j ∈ [1..n]PA (xj ) = 12 ;
– PD (δ) = 1.0 for each δ ∈ D.
Moreover, let γ be a truth assignment for the propositional variables x1 , . . . , xn .
We define as w(γ, F(φ)) the possible world w = hAw , Dw i ∈ pw(F(φ)) defined
as follows:
– Aw = A \ {xi | i ∈ [1..n] ∧ γ(xi ) =false};
– Dw = D \ {(xi , cj ) | i ∈ [1..n] ∧ j ∈ [1..k] ∧ γ(xi ) = false} ;
It is easy to see that given a possible world w ∈ 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 different 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 x1 x2
(a) (b)
Fig. 3: Graphical representation of the PrAAF F(φ) (a) and the possible world
w(γ, F(φ)) (b).
Lemma 1. Let φ = C1 ∧ C2 ∧ . . . Ck be a P 2CN F , where X = {X1 , . . . , Xn } is
the set of its propositional variables.
For each truth assignment γ for the propositional variables X1 , . . . , Xn it
holds that CAad w(γ,F (φ)) (a) is true iff γ(φ) is true.
10 Bettina Fazzinga et al.
Proof. We first prove that for each truth assignment γ for X1 , . . . , Xn the fact
that CAad w(γ,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 CAad w (a) is true while γ(φ) is false.
Since CAad w (a) is true there exists an admissible extension S for w such
that a ∈ S. It is easy to see that S ∩ {c1 , . . . , ck } = ∅, as otherwise S would
not be an admissible extension (S would not be conflict-free). Moreover, it is
easy to see that there exists a subset {xi1 , . . . , xih } of {x1 , . . . , xn } such that
{xi1 , . . . , xih } ⊆ S and for each j ∈ [1..k] there is l ∈ [1..h] such that:
1. xil ∈ Aw , and
2. (xil , cj ) ∈ 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 ∈ [i..k] such that
Cj = Xl ∨ Xh and γ(Xl ) = γ(Xh ) =false. This implies that xl 6∈ Aw , xh 6∈
Aw , (xl , cj ) 6∈ Dw and (xh , cj ) 6∈ Dw , thus contradicting the fact that S is
an admissible extension. Hence, it holds that for each truth assignment γ for
x1 , . . . , xn the fact that CAadw(γ,F (φ)) (a) is true implies that γ(φ) is true.
We now prove that for each truth assignment γ for x1 , . . . , xn the fact that
γ(φ) is true implies that CAad w(γ,F (φ)) (a) is true. Reasoning by contradiction
assume that there exists a truth assignment γ for x1 , . . . , xn such that w =
w(γ, F(φ)) and CAad w (a) is false while γ(φ) is true.
Let S be the set of arguments {a} ∪ {xi | i ∈ [1..n] ∧ γ(Xi ) = true}. 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 ∈ [1..k] such
that Cj = Xh ∨ Xl and both xh ∈ / S and xl ∈ / 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 CAad w(γ,F (φ)) (a) is true.
Lemma 2. Let φ = C1 ∧ C2 ∧ . . . Ck be a P 2CN F , where X = {X1 , . . . , Xn } is
the set of its propositional variables.
For a possible world w ∈ pw(F(φ)) CAad sem
w(γ,F (φ)) (a) is true iff CAw(γ,F (φ)) (a),
where sem ∈{st, co, gr, sst, pr, ids, ide}, is true.
Proof. The if part is straightforward since stable, complete, grounded, semi-
stable, 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 ∈ S and there is no extension S 0
according to sem, where sem ∈{st, co, gr, sst, pr, ids, ide }, such that a ∈ S 0 .
Consider the set of arguments Ŝ = S ∪ (Arg(w) ∩ {x1 , . . . , xn }), and note
that Arg(w) \ Ŝ = {c1 , . . . , ck }. It is straightforward to see that, since S is an
admissible extension then Ŝ is an admissible extension. Moreover, it is easy to see
Credulous acceptability... 11
that (i) Ŝ is a stable extension since it defeats each argument in Arg(w) \ Ŝ, (ii)
Ŝ is a complete extension since it contains all the argument that are acceptable
w.r.t. Ŝ, (iii) Ŝ is a preferred extension since Ŝ is an admissible extension and
any argument in Arg(w)\ Ŝ attacks an argument in Ŝ, so that for each argument
α ∈ Arg(w) \ Ŝ it holds that Ŝ ∪ α is not conflict-free. Moreover, observe that Ŝ
is the unique preferred extension for w.
Furthermore, since Ŝ is a complete extension and since removing any argu-
ment from Ŝ make it loose the property that it contains all the arguments that
are acceptable w.r.t. it, it holds that Ŝ is a grounded extension.
Moreover, since Ŝ ∪ Ŝ + = Arg(w) then there is no complete extension S such
+
that S ∪ S ⊃ Ŝ ∪ Ŝ + . Therefore, since Ŝ is a complete extension it follows that
Ŝ is a semi-stable extension.
Finally, it is straightforward to see that Ŝ is an ideal-set and ideal extension
for w as it is the unique preferred extension for w.
Hence, for possible world w ∈ pw(F(φ)) CAad w(γ,F (φ)) (a) is true only if
CAsemw(γ,F (φ)) (a) is true, where sem ∈ {st, co, gr, sst, pr, ids, ide}, which
completes the proof.
Theorem 2. For sem ∈{ad, st, co, gr, sst, pr, ids, ide}, it holds that P-
CAsem is F P #P -hard.
Proof. Given an instance φ of #P 2CN F , we construct an instance of P-
CAsem by defining a PrAAF F = F(φ) as in Definition 4, and we return
2n · (P rCAsem
F (a)).
Since for each possible world w ∈ pw(F(φ)) we have that I(w) = 21n , from
Lemmas 1 and 2 it follows that 2n · (P rCAsem F (a)) is the number of satisfying
assignments of φ.
Hence, as the above described reduction from the #P -hard problem
#P 2CN F to P-CAsem is a Cook reduction, this suffices to prove that P-CAsem
is F P #P -hard, since a problem is F P #P -hard iff it is #P -hard.
4 RELATED WORK
The main state-of-the-art approaches for handling uncertainty in AAFs by rely-
ing on probability theory can be classified 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 re-
cent epistemic one [33, 29, 28]. As regards the epistemic approach, probabilities
and extensions have a different semantics, compared with the constellations ap-
proach. Specifically, 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
12 Bettina Fazzinga et al.
are believed to be true to some degree. The interested reader can find a more
detailed comparative description of the two categories in [26].
We now focus our attention on the approaches classified 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 prob-
ability 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] defined 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 prob-
ability 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).
Differently 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 as-
sumed. 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 ev-
ery semantics, [30] proposed a Monte-Carlo simulation approach to approximate
P sem (S). [7, 19, 20] build upon [30]: [7] characterizes different semantics from the
approach of [30] in terms of probabilistic logic, as a first step in the direction
of creating a uniform logical formalization for all the proposed AAFs of the lit-
erature, in order to understand and compare the different 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 efficiently estimate P sem (S) based on the polynomial-
ity results of [19, 20]. In [30], as well as in [12] and [32], P sem (S) is defined 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 fundamen-
tal 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 justification and the premise perspectives of probabilities of ar-
guments are introduced. According to the former perspective the probability of
an argument indicates the probability that it is justified in appearing in the
argumentation system. In contrast, the premise perspective views the probabil-
Credulous acceptability... 13
ity 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 con-
nection among argumentation theory, classical logic, and probability theory was
investigated. Furthermore, qualification of attacks is addressed in [27], where an
investigation of the meaning of the uncertainty concerning defeats in probabilis-
tic 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 se-
mantics (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 admis-
sible, 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 com-
puting 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
finding 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 se-
mantics. Knowledge Eng. Review 26(4), 365–410 (2011)
2. Baroni, P., Giacomin, M.: Semantics of abstract argument systems. In: Argumen-
tation in Artificial 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)
14 Bettina Fazzinga et al.
7. Doder, D., Woltran, S.: Probabilistic argumentation frameworks - A logical ap-
proach. 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 argumen-
tation 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 frame-
works. Cybernetics and Systems 45(3), 254–278 (2014)
10. Dung, P.M.: On the acceptability of arguments and its fundamental role in non-
monotonic 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 finite 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 Ar-
tificial Intelligence (JELIA). pp. 153–165 (2008)
16. Dunne, P.E., Wooldridge, M.: Complexity of abstract argumentation. In: Argu-
mentation in Artificial Intelligence, pp. 85–104 (2009)
17. Dvorák, W., Woltran, S.: Complexity of semi-stable and stage semantics in argu-
mentation frameworks. Inf. Process. Lett. 110(11), 425–430 (2010)
18. Fazzinga, B., Flesca, S., Parisi, F.: Efficiently estimating the probability of ex-
tensions 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 Artificial 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 efficiently 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
efficiently 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 exten-
sion’s probabilities over structured probabilistic argumentation frameworks. Spe-
cial 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. Com-
put. 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)
Credulous acceptability... 15
26. Hunter, A.: A probabilistic approach to modelling uncertain logical arguments. Int.
J. Approx. Reasoning 54(1), 47–81 (2013)
27. Hunter, A.: Probabilistic qualification 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 Artificial 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. Euro-
pean Conf. on Artificial Intelligence (ECAI). pp. 750–755 (2012)
34. Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci.
(TCS) 8, 189–201 (1979)