We recall percVer and percAcc, the problems asking for the percentages of the completions of an incomplete Abstract Argumentation Framework (iAAF) where a set S is an extension and an argument a is accepted, respectively, introduced in [1]. Specifically, we recall the relationship between the proposed framework and probabilistic AAFs (prAAFs) under the constellations approach and the complexity characterization of both problems.
Incomplete AAFs (iAAFs) [
The main reason for the popularity of iAAFs is their simplicity, mostly deriving from the fact that they do not require a quantitative modeling of the uncertainty. Nevertheless, some quantitative reasoning over iAAFs is likely to be useful when analyzing the dispute modeled by an iAAF. For instance, in the absence of quantitative measures implying a rank of the completions, it is reasonable to consider them “alternative scenarios that may occur with the same probability", and, in turn, to measure the closeness of a set (resp. an argument) to being an extension (resp., accepted) as the percentage of completions where this happens.
In this paper, we recall the reasoning paradigm over iAAFs proposed in [
We first recall the relationship between this framework and probabilistic AAFs in the constellations
approach (prAAFs) [
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). tractability depending on the semantics of extensions and the size of S or the structural properties of the iAAF.
Incomplete AAFs (iAAFs). Assuming familiarity with Abstract Argumentation Frameworks (AAFs),
we recall the Incomplete AAFs (iAAFs) [
Definition 1 (iAAF). An incomplete AAF (iAAF) is a tuple ⟨A, A?, D, D?⟩, where A and A? are disjoint sets of arguments, and D and D? disjoint sets of attacks between arguments in A ∪ A?. The arguments and attacks in A and D (resp., A? and D?) are said to be certain (resp., uncertain), i.e. they are (resp., are not) guaranteed to occur.
An iAAF compactly represents the alternative scenarios (completions) for the argumentation. Definition 2 (Completion). Given an iAAF IF = ⟨A, A?, D, D?⟩, a completion of IF is an AAF F = ⟨A′, D′⟩ where A ⊆ A′ ⊆ (A ∪ A?) and D ∩ (A′ × A′) ⊆ D′ ⊆ (D ∪ D?) ∩ (A′ × A′). The possible and necessary perspectives are natural ways to deal with multiple completions when adapting the notions of extension (renamed “i∗ -extension") and accepted argument to iAAFs: Definition 3. Let IF be an iAAF, S a set of arguments and a an argument. Under a semantics σ , S is an i∗ -extension and a an X-accepted argument (with X ∈ {Cr, Sk}) under the possible (resp., necessary) perspective if, for at least one (resp., every) completion F of IF , S is an extension of F and a an X-accepted argument of F , respectively.
In [
Probabilistic Abstract Argumentation Frameworks (prAAFs). We consider prAAFs following the “constellations approach", where probabilities quantitatively model the uncertainty afecting the knowledge of which “possible world" (i.e. combination of the arguments and attacks) actually occurs. In the context of prAAFs, “possible world" has the same meaning as “completion" in the context of iAAFs, so prAAFs can be viewed as iAAFs where a pdf (probability distribution function) is defined over the completions.
Definition 4. A prAAF P F is a tuple ⟨A, D, PW, p⟩, where A is a set of arguments, D ⊆ of attacks, PW a set of possible worlds over A and D, and p is a pdf over PW.
A × A a set
When independence between arguments/attacks is assumed, the pdf p can be encoded compactly, by specifying the marginal probabilities µ of the arguments/attacks, so that the probability of a possible world ω = ⟨A′, D′⟩ is
p(ω) = Πa∈A′ µ (a) × Πa∈A\A′ 1 − µ (a) × Π(a,b)∈D′ µ (a, b) × Π(a,b)∈ D∩(A′× A′) \D′ 1 − µ (a, b)
which means that the marginal probability of an attack (a, b) is interpreted as the probability that the
attack occurs assuming that a and b occur. Thus, under the independence assumption, PW and p can
be replaced by a marginal probability function µ : A ∪ D → [
We report the definitions of the problems cntCom, percVer and percAcc, and their relationship with
probVer and probAcc (the probabilistic counterparts of the verification and acceptance problems over
prAAFs), provided in [
Observe that percAccσ (IF,D,a,X) trivially returns 0 if σ = ad and X = Sk, as no argument can be skeptically accepted in any completion (as ∅ is always an admissible extension). Hence, in most of the results regarding percAcc, the combination σ = ad and X = Sk will not be considered.
The following proposition states that percVer and percAcc can be solved by viewing IF as a prAAF whose possible worlds are the completions of IF and whose pdf is the uniform distribution, and then reasoning on this prAAF via probVer and probAcc. Obviously, translating iAAFs to prAAFs makes sense if D is satisfiable, as prAAFs are not defined if there is no possible world.
Proposition 1. Assume C(IF, D) ̸= ∅. Let P F = ⟨A ∪ A?, D ∪ D?, PW, p⟩ be the prAAF where PW = C(IF, D) and p is the pdf that assigns 1/|PW| to every possible world of P W . Then percVerσ (IF,D,S)=probVerσ (P F, S) and percAccσ (IF,D,a,X)=probAccσ (P F, a, X).
The theorem below states that cntCom(IF, D) (which returns 1/p) is #P-complete. Theorem 1. cntCom(IF, D) is #P-complete, even if D = ∅ and IF contains no certain argument and no certain attack.
The following theorem states that, under the hypothesis #P⊈ FP, there is no polynomial time transformation of an iAAF into a prAAF over the same arguments that allows for solving any instance of percVer via an instance of probVer.
Theorem 2. Under the hypothesis #P⊈ FP, for every σ ∈ {ad, st, co, gr, pr}, there is no algorithm taking as input an iAAF IF that runs in polynomial time and translates IF into a prAAF over the same arguments as IF such that, for every set of arguments S, probVerσ (P F, S)= percVerσ (IF,D,S), or, for each argument a, percAccσ (IF,D,a,X)= probAccσ (P F, a, X) (except for the case σ = ad and X = Sk).
It is natural to wonder whether there is some general easy-to-compute translation from IF into an equivalent IND-prAAF over the same arguments. Unfortunately, even if D= ∅, computing such a translation (assuming that it exists) would require a huge computational efort, as formally stated below. Theorem 3. Under the hypothesis #P⊈ FP, even if D= ∅, under σ ∈ {ad, st, co, gr, pr}, there is no polynomial-time algorithm translating any iAAF IF into an IND-prAAF P F over the arguments of IF such that, for any set of arguments S, probVerσ (P F, S)=percVerσ (IF,D,S), or, for any argument a, percAccσ (IF,D,a,X)= probAccσ (P F, a, X) (except for the case σ = ad,X = Sk).
The following theorem describes a form of iAAF for which the polynomial-time translation mentioned in Theorem 3 exists.
Theorem 4. Assume that D = ∅ and every uncertain attack in IF involves at least one certain argument. Let P F = ⟨A ∪ A?, D ∪ D?, µ ⟩ be the IND-prAAF where ∀a ∈ A µ (a) = 1, ∀δ ∈ D µ (δ ) = 1, ∀δ ∈ D? µ (δ ) = 12 , and ∀a ∈ A? µ (a) = 1+2|2D|D?(?a()a|)| , where D?(a) is the set of uncertain attacks involving a. Then, for any S ⊆ A ∪ A?, percVer(IF, D, S) = probVerσ (P F, S), and, for each a ∈ A ∪ A?, percAccσ (IF,D,a,X)= probAccσ (P F, a, X).
Finally, Theorem 5 below gives an insight into the suficient condition of Theorem 4, as it states that this condition makes cntCom tractable too.
Theorem 5. cntCom(IF, D) is in P if D= ∅ and every uncertain attack of IF involves at least one certain argument.
We start by recalling the general characterization of percVer and percAcc done in [
Starting from this general result, we recall the sensitivity analysis of the computational complexity to
the form of uncertainty encoded in the iAAF and to the semantics of extensions done in [
Under the Dungean semantics other than ad and st, probVer over IND-prAAFs is not known to be in
FP but is FP#P-complete [
Theorem 7. If D= ∅ and IF contains no uncertain argument or no uncertain attacks, then: 1) under σ ∈ {gr, co, pr}, percVerσ (IF,D,S) is FP#P-complete, and 2) under σ ∈ {ad, st, gr, co, pr}, percAccσ (IF,D,a,X) is FP#P-complete (except for the case σ = ad and X = Sk).
From what shown so far, it is natural to wonder whether the tractability islands of Theorem 5 for cntCom and of Corollary 1 for percVer can be extended to the case D ̸= ∅. The following theorem gives a negative answer: even in the simpler case where the uncertainty involves only arguments or only attacks, specifying any form of dependency makes cntCom and percVer under σ ∈ {ad, st} intractable.
Theorem 8. If IF contains no uncertain arguments or no uncertain attacks, and D contains dependencies of only one of the forms or, nand, choice, imply, then cntCom(IF, D) is #P-hard and percVerσ (IF,D,S) is FP#P-hard.
Theorem 8 does not mention percAcc, as it is already FP#P-hard with D= ∅ (Theorem 7). As for percVer, Theorem 8 interestingly states that percVer is FP#P-hard whatever the form of dependencies, even when its decision counterpart (iVer) is tractable. We conclude by locating an island of tractability of percVer under σ = ad, that depends on the size of S and how S is connected to the rest of the iAAF. The tractability holds for a form of iAAF for which cntCom is not tractable (as no restriction is imposed on the portion of IF outside S). To state the result, we denote as fr(S) the frontier of S, i.e. the set of arguments outside S attacking or attacked by S. Moreover, we denote as IF \ S the iAAF obtained from IF by removing every argument in S and every attack to/from S.
Theorem 9. Assume that the size of S is logarithmic w.r.t. size of IF , that the arguments in fr(S) are certain, that, for each dependency d ∈ D, d involves only arguments/attacks in S or only arguments/attacks in IF \ S, and that |C(IF, D)| > 0. Then, under σ = ad, percVerσ (IF,D,S) is in FP.
It is worth noting that this tractability result cannot be extended to the other semantics. In fact: 1) under σ ∈ {co, gr, pr}, the proof of Theorem 7 shows that percVer is FP#P-hard even in the restricted case where D= ∅, fr(S) = ∅, and S is of constant size; 2) under σ = st, a minor change of the reduction used in the proof of Theorem 6 (consisting in adding no attack involving the fresh argument a) shows that percVer is FP#P-hard even when D= ∅, fr(S) = ∅, and S is of constant size.
The above theorem is the only statement regarding the computational complexity where the satisfiability of the dependencies (i.e. |C(IF, D)| > 0) is a prerequisite. Observe that the general hardness results of Theorem 8 hold even when D is known to be satisfiable, as they can be proved via parsimonious reductions to cntCom from counting problems that always return a value greater than 0. This means that cntCom and percVer have sources of complexity other than the uncertainty on the existence of at least one completion. In turn, this means that, in the general case, assuming D satisfiable cannot imply that percVer becomes tractable, and makes the result of Theorem 9 relevant.
We have recalled the new quantitative reasoning paradigm supporting the analysis of iAAFs and its
computational complexity characterization, provided in [