Quantitative Reasoning over Incomplete Abstract Argumentation Frameworks

1 Introduction

Dung's Abstract Argumentation Framework (AAF [Dung, 1995]) has proved effective in supporting the reasoning in several scenarios, ranging from the analysis of disputes to process mining tasks [Fazzinga et al., 2022b] and chatbot services [Fazzinga et al., 2022c]. In order to widen the possible applications, several generalizations of AAFs have been proposed to model the uncertainty that may affect arguments and attacks. In fact, in real life disputes, it often happens that the participation of the agent who claims an argument a is not guaranteed (so a is uncertain), or that the existence of an attack (a, b) depends not only from the occurrence of a and b, but also on the subjective view of who analyzes the dispute (so (a, b) is uncertain). Incomplete AAFs (iAAFs) [Baumeister et al., 2018] are prominent representatives of qualitative approaches, where uncertain arguments and attacks can be specified, with no measure of the extent of this uncertainty. Recent proposals [Fazzinga et al., 2021b;

Fazzinga et al., 2021a] further extend iAAFs with "dependencies", expressing, for instance, that (the presence of) an argument is alternative to other arguments, that an attack implies another attack, and so on.

The fundamental notion of extension was adapted to iAAFs by taking into account the fact that, while a classical AAF represents a single scenario (in terms of a set of arguments and attacks), an iAAF encodes multiple scenarios (called completions), corresponding to the different combinations of presence/absence of the uncertain arguments and uncertain attacks satisfying the dependencies. Thus, based on the notion of completion, possible and necessary i∗ -extensions were introduced: a possible (resp., necessary) i∗ -extension is a set of arguments that is extension in at least one (resp., every) completion of the iAAF. Similarly, an argument a is accepted under the possible (resp., necessary) perspective if it is accepted in at least one (resp., every) completion.

Example 1 Seven agents have been asked for their opinion on which arguments will be claimed in a dispute, and which attacks should be considered. The agents have 7 different views, summarized by the iAAF IF in Figure 1 under the dependency NAND(e1, e2, e3) (meaning that, in the agents' opinions, e1, e2, e3 do not occur together). So, IF encodes the agent's views as 7 completions, that are the AAFs with the arguments a, b, plus a strict subset of {e1, e2, e3}, plus the attacks in IF between the arguments in the completions.

Under the complete semantics, there is no necessary extension, as no set of arguments is a complete extension in every completion. Examples of possible i∗ -extensions are the sets S1 = {a} (as it is extension in every completion but that where none of e1, e2, e3 occurs) and S2 = {a, b} (as it is extension in the only completion where e1, e2, e3 do not occur). Correspondingly, a is accepted under the possible and the necessary perspective, while b is accepted under the possible perspective, but not under the necessary perspective.

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 Example 1, the fact that S1 and S2 are not necessary i∗ - extensions but are possible i∗ -extensions simply tells us that they have some chance to meet the extension's requirements, but S1 and S2 are indistinguishable in terms of how risky it is to consider them as if they were extensions. In this regard, the analysis of the dispute would definitely benefit from knowing the number of completions where S1 and S2 are extensions. In this case, S1 = {a} is an extension in 6 of the 7 completions, while S2 = {a, b} only in 1 of the 7 completions: this tells us that, despite they are both possible i∗ -extensions, S1 has more chances than S2 to meet the extension's requirement when the actual scenario materializes. Similarly, the information that b is accepted under the possible perspective is much less insightful than knowing that b is accepted in 1 of the 7 completions, which tells us that its acceptance is unlikely. The point is that, 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 present a reasoning paradigm over iAAFs based on three problems, whose input includes an iAAF IF, a set of dependencies D, a set of arguments S, an argument a: 1) PERCVERσ (IF,D,S) and PERCACCσ (IF,D,a,X), asking for the percentages of completions of IF (satisfying D) where S is an extension and a accepted, respectively;

2) CNTCOM(IF,D), counting the completions of IF (satisfying D): this problem supports a preliminary analysis, as its answer is a measure of the uncertainty encoded in the iAAF and helps interpret the answers of PERCVER and PERCACC.

As a first contribution, we study the relationship between our framework and probabilistic AAFs in the constellations approach (prAAFs) [Fazzinga et al., 2019; Li et al., 2011; Hunter, 2014; Fazzinga et al., 2022a], that are iAAFs where a probability distribution function is defined over the completions (called possible worlds in the context of prAAFs). In particular, we focus on the relationship with the problems PROBVER and PROBACC over prAAFs, that ask for the overall probability of the possible worlds of a prAAF PF where a set is an extension and an argument accepted, respectively. We observe that, although in principle solving PERCVER and PERCACC is the same as solving PROBVER and PROBACC over a suitably constructed prAAF, constructing this "equivalent" prAAF can require a heavy computational cost (besides the fact that the so obtained prAAF is dramatically less compact and less user-friendly than the iAAF). We show that this issue holds also when no dependency is specified, which is somehow counterintuitive, since an iAAF without dependencies seems to be equivalent to a prAAF where arguments and attacks are independent and whose marginal probabilities are set equal to 1/2 (or some other constant). These results back the need of addressing PERCVER and PERCACC as new distinguished problems. Starting from this, we thoroughly investigate the computational complexity of the quantitativereasoning paradigm, and show that CNTCOM is #P-complete and PERCVER and PERCACC are FP#P -complete, with islands of tractability depending on the semantics of extensions and the size of S or the structural properties of the iAAF. The example below helps the reader better appreciate the relevance of studying PERCVER and PERCACC as new problems over iAAFs, distinguished from the classical verification and acceptance problems over prAAFs.

Example 2 A group of volunteers have been asked to analyze a text in ancient Greek, whose sentences are the claims of the participants to a philosophical discussion. The text consists of 10 sentences. For each sentence, the volunteers have been called for choosing the most accurate among 3 alternative translations in English. Moreover, they have been asked to specify the pairs of sentences between which, in their opinion, an attack relationship holds. The result of this process is as follows: for each sentence, each of the 3 possible translations has been chosen by some volunteer, and 92 different attacks have been specified. In particular, 90 attacks have been detected unanimously, while other 2 attacks (namely, δ1, δ2) have been recognized by some volunteers. As for δ1 and δ2, no volunteer has specified that both of them hold.

In order to reason on the semantics of the text, the result of the interviews might be represented as a prAAFs: this would require enumerating the subjective views (i.e. the different combinations of the attacks with the alternative translations of the 10 sentences), encoding them as distinguished possible worlds, and assigning the same probability to each of them. Indeed, this is a heavy task, since enumerating the possible worlds means considering at least 310 combinations of arguments, where some combination must be considered in up to 3 variants (that are the ways of combining δ1 and δ2 while forbidding their coexistence). On the other hand, resorting to iAAFs as a representation paradigm makes things much easier: the set of alternative possible worlds can be compactly encoded by marking all the arguments providing the translations of the sentences as uncertain, the 90 attacks shared by the volunteers as certain, and the two attacks δ1, δ2 as uncertain. Then, in order to make the set of completions exactly model the subjective views, it suffices to specify the dependency NAND(δ1, δ2) and, for each sentence, the dependency CHOICE(a1, a2, a3), meaning that, in each completion, exactly one of the arguments a1, a2, a3 providing alternative translations occurs. Starting from this, without the need of enumerating the subjective views (which would be necessary for both defining the possible worlds and their probability), an analysis of the original text can be accomplished by solving instances of PERCVER and PERCACC. This way, in the challenging scenario where each sentence has no certain meaning (as witnessed by the existence of different subjective views), the "robustness" of any group of sentences S or any single sentence s can be assessed, in terms of the percentage of subjective views where S is an extension or s is accepted.

2 Preliminaries

Abstract Argumentation Frameworks (AAFs). An abstract argumentation framework (AAF) is a pair F = ⟨A, D⟩, where A is a finite set, whose elements are called arguments, and D ⊆ A × A is a binary relation over A, whose elements are called attacks. Given a set of arguments S and an argument a, we say that "S attacks a" if there is an argument b in S such that b attacks a, and that "a attacks S" if there is an argument b ∈ S such that a attacks b. We say that an argument a (resp., a set of arguments S) "defends b against c's attack" if c attacks b, while a (resp., S) attacks c. Moreover, we say that a is acceptable w.r.t. S if S defends a against every attack, and that S is conflict-free if there is no attack between its arguments. An AAF F can be viewed as a directed graph (called "argumentation graph") whose nodes are the arguments and whose edges the attacks.

Several semantics for AAFs have been proposed to identify "reasonable" sets of arguments, called extensions [Dung, 1995]. A set S ⊆ A is: an admissible extension (ad) iff S is conflict-free and its arguments are acceptable w.r.t. S; a stable extension (st) iff S is conflict-free and S attacks every a ∈ A \ S; a complete extension (co) iff S is admissible and contains all the arguments acceptable w.r.t. S; a grounded extension (gr) iff S is a minimal (w.r.t. ⊆) complete extension; a preferred extension (pr) iff S is a maximal (w.r.t. ⊆) complete extension. ad, st, gr, co, pr will be also referred to as Dungean semantics. Arguments belonging to at least one (resp., every) extension are said to be Credulously (or Cr-) accepted (resp., Skeptically (or Sk-) accepted). The fundamental problems supporting the reasoning over AAFs are the verification that a set S is an extension and that an argument a is X-accepted, with X ∈ {Cr, Sk}.

Incomplete AAFs (iAAFs). iAAFs [Baumeister et al., 2018] allow the uncertainty affecting the real presence of arguments and attacks to be qualitatively modeled.

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 for the argumentation, i.e. all the possible combinations of arguments and attacks that can occur according to what is certain and uncertain. Each scenario is called completion.

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 take into account the presence of multiple completions when adapting the notions of extension (now 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 [Fazzinga et al., 2021a; Fazzinga et al., 2021b], the possibility of restricting the set of completions (in order to make it better fit the alternative scenarios) via OR, NAND, CHOICE, IMPLY dependencies involving arguments/attacks was studied (this set was proved to be sufficient to encode any propositional constraint over the completions, expressing which combinations of arguments or of attacks can/cannot occur). Given two sets of arguments Y , Z, the semantics is:

• OR(Y ): (the completions to be considered are all and only those where) at least one argument in Y occurs,
• NAND(Y ): at least one argument in Y does not occur,
• CHOICE(Y ): exactly one argument in Y occurs,
• IMPLY(Y,Z): if every argument in Y occurs, then all the arguments in Z occur.

If Y and Z are sets of attacks, the semantics is analogous, but, when checking if a completion satisfies a dependency, only the attacks in Y and Z between arguments that both belong to the completion are considered (this means conditioning the dependencies to the presence of the arguments involved in the attacks). In the presence of a set of dependencies D, the set of completions of an iAAF IF satisfying D will be denoted as C(IF,D), and the problems of checking, under the perspective P ∈ {Possible, Necessary}, if S is an i∗ -extension and a X-accepted (with X ∈ {Cr, Sk}) as IVERσ (IF,D, S, P) and IACCσ (IF,D, a, P,X), respectively.

Probabilistic Abstract Argumentation Frameworks (prAAFs). We consider prAAFs following the "constellations approach", where probabilities quantitatively model the uncertainty affecting 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 PF is a tuple ⟨A,D,PW, p⟩, where A is a set of arguments, D ⊆ A × A a set of attacks, PW a set of possible worlds over A and D, and p is a pdf over PW.

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

which means that the marginal probability of an attack (a, b) is interpreted as the probability that the attacks 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 → [0, 1]. In this case, the prAAF will be called IND-prAAF and denoted as a tuple PF = ⟨A, D, µ⟩.

As observed above, prAAFs are a generalization of iAAFs, where the uncertainty is modeled quantitatively, via probabilities. So, when moving from iAAFs to prAAFs, the problems IVER and IACC, that are intrinsically decision problems, become the research problems PROBVERσ (PF, S) and PROBACCσ (PF, a,X), asking for the probability that S is an extension and a X-accepted (with X ∈ {Cr, Sk}), i.e. the overall probability of the possible worlds where S is an extension and a X-accepted, respectively.

Counting and functional complexity classes. We assume familiarity with the complexity classes for decision problems in the polynomial hierarchy PH (in particular, P, NP, coNP, Σp2 =NP NP ), and recall some complexity classes tailored at counting and functional problems. FP (resp., FPC ) is the class of the functional problems that can be solved in polynomial time by a deterministic Turing machine (resp., by a deterministic Turing machine with an oracle for the class C). #P is the class of the functions f counting the accepting paths of a nondeterministic polynomial-time Turing machine [Valiant, 1979]. More generally, for any class C in the polynomial hierarchy, #C is the class of the functions f counting the accepting paths of a nondeterministic polynomial-time with an oracle for the class C (for instance, #NP is the class of functions counting the accepting paths in a NP NP Turing machine). For proving the hardness of counting problems for #P, we resort to parsimonious reductions, i.e. (polynomial time) reductions that transform an instance I ′ of a counting problem to an instance I ′′ of another counting problem such as the answers of I ′ and I ′′ coincide. As for the hardness for FP#P , we use polynomial time 1-Turing reductions [Toda and Watanabe, 1992]: a polynomial time 1-Turing reduction from a problem A to a problem B is an algorithm R that solves A by calling at most once a subroutine solving B, such that R runs in polynomial time if the cost of this subroutine is not considered. It is worth noting that, despite #P and FP#P are different (as the functions in #P return counts, while those in FP#P return more general values), a function is FP#P -hard under polynomial time 1-Turing reductions iff it is #P-hard under the same type of reduction. So, sometimes, we prove the hardness for FP#P via reductions from #P-hard problems.

#P- or FP#P - completeness mean intractability, since PH⊆FP#P and the conjecture #P⊈FP is believed to hold (a consequence of its negation is P=NP).

3 Quantitative Reasoning Over iAAFs Vs. Probabilistic Reasoning Over prAAFs

We introduce the problems CNTCOM, PERCVER and PERCACC, as the core of a framework for quantitatively reasoning over iAAFs. Then, we investigate their relationship with PROBVER and PROBACC, the probabilistic counterparts of the verification and acceptance problems over prAAFs. In the rest of the paper, an iAAF IF = ⟨A,A? ,D,D? ⟩, a set of dependencies D, a set of arguments S of IF , and a semantics σ ∈ {ad, st, co, gr, pr}, are assumed to be given.

Definition 5 CNTCOM(IF,D) is the problem of computing |C(IF,D)|, and PERCACCσ (IF,D,a,X) (with X∈{Cr, Sk}) and PERCVERσ (IF,D,S) the problems of computing the percentage of completions in C(IF,D) where, under σ, a is Xaccepted and S is an extension, respectively. Conventionally, the answer of PERCVER and PERCACC is 0 if C(IF, D) = ∅.

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 PF = ⟨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 PW. Then PERCVERσ (IF,D,S)=PROBVERσ (PF, S) and PERCACCσ (IF,D,a,X)=PROBACCσ (PF, a, X).

Interestingly, although Proposition 1 states that the quantitative reasoning underlying PERCVER and PERCACC can be simulated via classical problems over a prAAF PF having a straightforward logical correspondence with IF, this does not diminish the reasonability of addressing PERCVER and PERCACC as new distinguished problems. In fact:

Issue 1: prAAFs are not compact, as they require the enumeration of the possible worlds (whose number can be exponential compared with the number of attributes and attacks) and the definition of the pdf over them: this makes their use much less user-friendly than iAAFs, where no pdf must be specified and the completions are not enumerated;

Issue 2: prAAFs are more expressive than iAAFs, so a general machinery solving PROBVER/PROBACC may not be capable of exploiting possible simplifications of the implemented computational mechanism allowed by the specificity of the considered prAAFs, that are prAAFs simulating iAAFs;

Issue 3: the definition of the pdf p of the prAAF (i.e. the probability value assigned by p to every possible world) is not trivial at all. On the contrary, 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. Proof sketch. CNTCOM can be viewed as the problem of counting the accepting paths in the non-deterministic polynomial time Turing machine guessing a set of arguments and attacks and checking if it is a completion, so it is in #P. Moreover, it can be shown that it is equivalent to the #Pcomplete problem of evaluating the overall weight of the homomorphisms between the argumentation graph and a specific weighted graph (see Appendix for details). ✷

Theorem 1 is of independent interest, since it characterizes a problem that can support the analysis of the real-world modeled by an iAAF: the answer of CNTCOM gives insights into the "extent of uncertainty" encoded in IF , and is a baseline that can help better understand the answers of PERCVER and PERCACC. In our current reasoning, Theorem 1 implies that constructing the prAAF PF defined in Proposition 1 is a heavy task (even if the possible worlds were not explicitly enumerated), so it is not reasonable to give up the quantitative framework based on PERCVER and PERCACC with the motivation that it can be simulated by a prAAF with a straightforward logical correspondence with IF .

However, one might wonder whether IF can be transformed into an "equivalent" prAAF using a strategy different from ensuring that the possible worlds are equiprobable

(that is computationally heavy, as explained above). Obviously, we consider translations towards a prAAF PF that can be easily interpreted by the analyst who is looking into the original iAAF IF, so IF should be defined over the same set of arguments as IF. In this regard, the following theorem states a strong negative result: 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σ (PF, S)= PERCVERσ (IF,D,S), or, for each argument a, PERCACCσ (IF,D,a,X)= PROBACCσ (PF, a,X) (except for the case σ = ad and X = Sk).

(Proof.) By contradiction, assume that there is an algorithm trans whose existence falsifies the part of the statement regarding PERCVER, for some σ ∈ {ad, st, co, gr, pr}. Let IF = ⟨A,A? ,D,D? ⟩ be an iAAF with A = D = ∅ such that: 1) the completion C 0 containing all the arguments in A? and no attack satisfies D, and 2) CNTCOM(IF,D) is a hard instance. Such an IF exists, since Theorem 1 guarantees that CNTCOM is #P-hard when D= ∅, and in this case every completion satisfies the dependencies. Let PF be the IND-prAAF obtained by running trans over IF . Let S = A? . It is easy to see that the only completion of IF where S is a σ- extension is C 0 . Thus, the answer of PERCVERσ (IF,D,S) is 1/CNTCOM(IF,D). On the other hand, the only possible world of PF where S is a σ-extension is ω0, coinciding with C0. Since PERCVERσ (IF,D,S)=PROBVERσ (PF, S) and PROBVERσ (PF, S)= p(ω0) (where p is the pdf of PF), we obtain CNTCOM(IF,D)= 1/p(ω0). Hence the overall procedure (running trans and then inverting p(ω0)) computes CNTCOM(IF,D) in polynomial time, contradicting (under the assumption #P⊈FP) Theorem 1. The statement for PERCACC can be proved analogously (see Appendix). ✷

However, the above theorem does not exclude forms of iAAFs for which the polynomial-time translation mentioned in Theorem 2 exists. A nice candidate seems the case where no dependencies are specified: at first sight, one may think that IF can be translated into an IND-prAAF PF over the same arguments and attacks as IF, where the marginal probabilities are suitably set so that the possible worlds are equiprobable. Such a translation would also fix Issue 1, since the resulting IND-prAAF would have the same size as IF (as now PW and the pdf p are represented implicitly). Unfortunately, the example below shows that this intuition is wrong.

Example 3 The different opinions of 5 agents on the arguments that will occur in a dispute and on the attacks that exist between them are encoded by the 5 completions of the IF having A = D = ∅, A? = {a, b}, and D? = {(a, b)}. At first sight, it may seem that reasoning on IF is the same as on the IND-prAAF PF = ⟨A? ,D? , µ⟩ with µ(·) = 1/2, as this choice for µ seems to imply that the possible worlds are equiprobable. Indeed, this is false: using Eq. (E1), we obtain that the possible worlds containing both a and b have lower probability than the others. As a matter of fact, there is no µ that implies a uniform pdf over the possible worlds: the reader can check that the system of equalities whose variables are the arguments' and attacks' marginal probabilities, and whose equations impose that all the possible worlds are assigned the same probability by Eq. (E1) has no solution.

However, also when D= ∅ (as discussed for the general case above), 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, that does not pursue the equivalence by making the possible worlds equiprobable. Unfortunately, analogously to the general case, computing such a translation (assuming that it exists) would require a huge computational effort, 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 PF over the arguments of IF such that, for any set of arguments S, PROBVERσ (PF, S)=PERCVERσ (IF,D,S), or, for any argument a, PERCACCσ (IF,D,a,X)= PROBACCσ (PF, a, X) (except for the case σ = ad,X = Sk).

(Proof.) The same strategy as Theorem 2's proof can be used: the difference is that now computing p(ω0) requires the polynomial time evaluation of Eq. (E1). ✷

Our investigation on the translatability of iAAFs in prAAFs continues with the following theorem, describing 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 PF = ⟨A ∪ A? , D ∪ D? , µ⟩ be the IND-prAAF where ∀a ∈ A µ(a) = 1, ∀δ ∈ D µ(δ) = 1, ∀δ ∈ D? µ(δ) = 12 , and ∀a ∈ A? µ(a) = 2|D? (a)| 1+2|D?(a)| , where D? (a) is the set of uncertain attacks involving a. Then, for any S ⊆ A ∪ A? , PERCVER(IF,D, S) = PROBVERσ (PF, S), and, for each a ∈ A ∪ A? , PERCACCσ (IF,D,a,X)= PROBACCσ (PF, a, X).

Proof sketch. It can be proven by showing that µ implies a uniform pdf over the possible worlds (see Appendix). ✷

Finally, Theorem 5 below (whose proof is in Appendix) gives an insight into the sufficient 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.

Concluding remarks. Overall, the results in this section, along with the motivations regarding the usefulness of accomplishing a quantitative reasoning over iAAFs, show the reasonability and relevance of studying PERCVER and PERCACC as new problems: even if there are restricted forms of iAAFs for which there is an easy-to-compute natural representation as a user-friendly prAAF that allows to simulate the reasoning underlying PERCVER and PERCACC, such a translation is not guaranteed to exist in the general case. Starting from this, in the following section we investigate the computational complexity of PERCVER and PERCACC.

4 Computational Complexity of Quantitative Reasoning Over iAAFs

We start our investigation by providing a general characterization of PERCVER and PERCACC.

Theorem 6 PERCACCσ (IF,D,a,X) (except for the case σ = ad and X =Sk) and PERCVERσ (IF,D,S) are FP#P - complete, even if D= ∅.

Proof. PERCVER is solved by a polynomial-time Turing machine returning y/x, where x is computed by an oracle solving CNTCOM(IF, D), and y by an oracle computing the number of accepting paths in a non-deterministic polynomial-time Turing machine guessing a completion C and then checking if S is a σ-extension of C. The oracle for x is in #P (Theorem 1), while that for y is in #P for σ ∈ {ad, st, gr, co} and in #NP for σ = pr (since verifying if a set is an extension of a completion is in P and in coNP in the two cases, respectively). This implies that PERCVER is in FP#P for σ ∈ {ad, st, gr, co} and in FP#NP for σ = pr. Since, for any C ∈ PH, FP#P coincides (via polynomial-time 1Turing reductions) with FP#C [Toda and Watanabe, 1992], the classes FP#P and FP#NP coincide. This implies the membership of PERCVER in FP#P under every semantics. The membership of PERCACC can be proved similarly, as testing if a is X-accepted in a completion is in PH [Dimopoulos and Torres, 1996; Dunne and Bench-Capon, 2002; Coste-Marquis et al., 2005]. The hardness can be proved via reductions from CNTCOM (see Appendix). ✷

Starting from this general result, we analyze the sensitivity of the computational complexity to the form of uncertainty encoded in the iAAF and to the semantics of extensions. A first result straightforwardly follows from Theorem 4, which states that, when D= ∅ and the uncertain attacks involve at least one certain argument, PERCVERσ (IF,D,S) is equivalent to PROBVERσ (PF, S), and PERCACCσ (IF,D,a,X) to PROBACCσ (PF, a,X), where PF is an IND-prAAFs obtained via a polynomial-time transformation from IF . Since, under σ ∈ {ad, st}, PROBVERσ (PF, S) is in FP over INDprAAFs (as shown in [Fazzinga et al., 2015]), we obtain:

Corollary 1 Assume that D= ∅ and IF is such that every uncertain attack involves at least one certain argument. Under σ ∈ {ad, st}, PERCVERσ (IF,D,S) is in FP.

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 [Fazzinga et al., 2015], and, under every Dungean semantics, PROBACC is FP#P -complete. Thus, Theorem 4 implies that PERCVER is in FP#P under σ ∈ {gr, co, pr} and PERCACC is in FP#P under σ ∈ {ad, st, gr, co, pr}. The following theorem states that these are also lower bounds, even if only the arguments or only the attacks are uncertain.

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

Proof sketch. The membership is implied by Theorem 6, and the hardness can be shown via reductions from problems counting the truth assignments making positive DNF or CNF formulas true (see Appendix). ✷

Fromwhat 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 (see Section 5 for a comprehensive discussion). 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.

Proof sketch. As the size of S is logarithmic, the completions of the portion In of IF consisting of the arguments and attacks inside S can be enumerated in polynomial time. The rest of the hypothesis avoids the need of evaluating the number the completions of IF \ S when computing the percentage of completions of the whole IF where S is an extension, since both the numerator and the denominator of this ratio are proportional to |C(IF \S, D)|, so this term can be simplified, while the other terms can be computed in polynomial time by exploiting the enumeration of the completions of In. ✷

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 (see Appendix) 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.

It is also worth noting that the assumption that D is satisfiable may be implied in practical scenarios (where the analyst knows that there are some completions satisfying the dependencies) and, in any case, can be preliminarily investigated: in [Fazzinga et al., 2021a], the computational complexity of the satisfiability of dependencies over iAAFs is studied, and shown to be trivial or in P for several combinations of dependencies, although it is NP-complete in the general case.

5 RelatedWork

Except for the case of Partial Argumentation Frameworks [Coste-Marquis et al., 2007; Cayrol et al., 2007] and their generalizations [Mailly, 2023], most of the works dealing with incompleteness in AAFs use the completion-based semantics adopted in this paper. In the light of the results in the literature, we can conclude that PERCVER is one of those functional problems that are hard to solve but having an easy decision version (when D= ∅). In fact, under all Dungean semantics but pr, PERCVER is FP#P -hard, while, as shown in [Fazzinga et al., 2020], deciding the existence of a completion where S is an extension is in P (under σ = pr, the decision problem is instead Σp2 -complete). On the other hand, in [Baumeister et al., 2021], the acceptance problem was shown to be hard already in the decision version, that ranges from NP-complete to Σp3 -complete, depending on the semantics and the perspective (Cr or Sk), except for the trivial case of the skeptical acceptance under σ = ad. As for the case D̸= ∅, in [Fazzinga et al., 2021b; Fazzinga et al., 2021a; Mailly, 2021] it was shown that specifying dependencies (OR, NAND, CHOICE, IMPLY) typically makes the complexity of the verification increase, for the semantics under which it was polynomial, to NP-complete. There are notable exceptions: the verification remains in P under σ ∈ {ad, st} when only arguments or only attacks are uncertain, and only OR or combinations of NAND and IMPLY are used. In this regard, we have shown that PERCVERσ (IF,D,S) is FP#P -complete under every semantics even if only arguments or attacks are uncertain and dependencies of only one form are used.

As for the relationship, in terms of complexity, with prAAFs in the constellations approach [Li et al., 2011], comparing our results with those on PROBVER and PROBACC in [Fazzinga et al., 2019; Fazzinga et al., 2015], we can draw these conclusions:

- if D = ∅ (when it makes sense to compare iAAFs with IND-prAAFs), some aspects of the quantitative reasoning over iAAFs are more complex than over IND-prAAFs: under σ ∈ {ad, st}, PERCVER is FP#P -complete while PROBVER is in FP. Under the other semantics, the complexity of PERCVER and PROBVER is the same. Instead, PERCACC and PROBACC have the same complexity under every Dungean semantics.

- if D ̸= ∅ (when it makes sense to compare iAAFs with prAAFs without the independence assumption), both PERCVER and PERCACC are FP#P -complete, so the complexity is higher than PROBVER (that is in FP under σ ∈ {ad, st, gr, co} and FP||NP -complete under σ = pr) and than PROBACC (that, under each semantics σ, is in FP||Cσ , where Cσ is the complexity class of the classical acceptance problem ACC under σ). Indeed, this was quite expected, since in prAAFs the possible worlds are enumerated, so the computational complexity benefits from some "discount" compared with iAAFs, where the completions are compactly encoded.

This work is also related to [Alfano et al., 2023a], where some relationships between prAAFs and iAAFs have been analyzed, and with prAAFs following the epistemic approach [Thimm, 2012; Hunter and Thimm, 2014], where, similarly to IND-prAAFs, arguments are associated with probabilities. However, these probabilities are degrees of belief in the acceptance of the arguments, so the reasoning paradigm does not take into account the possibility that the structure of the argumentation graph changes as the effect of considering the presence/absence of arguments or attacks.

Our framework is also related to the use of constraints, preferences, and/or explicit acceptance conditions to support the reasoning (as done in several frameworks where these constructs are used to filter out extensions [Alfano et al., 2023a; Alfano et al., 2023b; Alfano et al., 2023d; Alfano et al., 2023c; Alfano et al., 2024], rather than completions), to iAAFs with supports [Fazzinga et al., 2018; Fazzinga et al., 2023], to the credulous/skeptical conclusion problems in Control Argumentation Frameworks [Dimopoulos et al., 2018], and to revising AAFs to enforce the existence of an extension [Baumann and Ulbricht, 2019], or to make a set an extension [Coste-Marquis et al., 2015]. In this regard, if we interpret the uncertain arguments/attacks as elements that can be added or removed, the framework can be used to count the possible ways of making a set an extension (or an argument accepted) via insertions or removals.

Finally, this work is related to [Baroni et al., 2010; Dewoprabowo et al., 2022; Fichte et al., 2019], where the problem of counting the number of extensions in an AAF has been addressed. A nice direction of future work is integrating these paradigms with our framework into a new reasoning paradigm addressing questions like "How many sets of arguments are extensions in at least 80% of the completions?"

6 Conclusions and FutureWork

A new quantitative reasoning paradigm supporting the analysis of iAAFs has been introduced. Its core consists in the problems PERCVER and PERCACC, whose answers give insights into how likely it is that, once the dispute modeled by the iAAF takes place, a set is an extension or an argument is accepted. The relationship with the classical reasoning paradigm over prAAFs has been investigated, first in terms of translatability, and then of computational complexity, after having characterized this aspect for the introduced framework. Future work will investigate the possibility of simultaneously looking into the counts of completions and extensions, as sketched at the end of the previous section.

Acknowledgements

We acknowledge partial financial support fromMUR project PRIN 2022 EPICA (CUP H53D23003660006) funded by the European Union - Next Generation EU and from the PNRR project FAIR - Future AI Research (PE00000013), Spoke 9 - Green-aware AI, under the NRRP MUR program funded by the NextGenerationEU.