Complexity of Fundamental Problems in Probabilistic Abstract Argumentation: Beyond Independence (Extended Abstract)

1 Introduction

In the last decade, several argumentation frameworks have been proposed for suitably modeling disputes between two or more parties. A powerful yet simple argumentation framework is that proposed in the seminal paper [Dung, 1995], called abstract argumentation framework (AAF). An AAF is a pair 〈A, D〉 consisting of a set A of arguments and a binary relation D over A, whose pairs are called defeats and express the fact that an argument rebuts/weakens another argument.

Example 1 Mary and Marc's defense attorney is reasoning on the trial of a robbery case involving her clients. The arguments are the following, where Ann is a potential witness:

• a: "Mary says that she was at the park at the time of the robbery, and thus denies being involved in the robbery";
• b: "Marc says he was at home when the robbery took place, and therefore denies being involved in the robbery";
• c: "Ann says that she certainly sawMary near the bank just before the robbery, and possibly saw Marc there too".

This scenario can be modeled by the AAF A, whose arguments are {a, b, c}, and whose defeats are δac = (a, c), δca =

∗This paper is an extended abstract of the Artificial Intelligence article Complexity of Fundamental Problems in Probabilistic Abstract Argumentation: Beyond Independence [Fazzinga et al., 2019]

(c, a), δbc = (b, c) and δcb = (c, b), meaning that arguments a and b are both attacked by c and they both counter-attack c.

Several semantics for AAFs, such as admissible, stable, preferred, complete, grounded, and ideal-set, have been proposed [Dung, 1995; Dung et al., 2007; Baroni and Giacomin, 2009] to identify "reasonable" sets of arguments, called extensions. Each semantics is a way of "certifying" that a set of arguments can robustly support a point of view in a discussion. For instance, a set S of arguments is an admissible extension if it is "conflict-free" (i.e., there is no defeat between arguments in S), and every argument attacking arguments in S is counterattacked by an argument in S.

In the literature, there are several proposals for modeling the uncertainty of arguments/defeats in AAFs, using different paradigms (e.g., weights, preferences, probabilities). In this regard, [Dung and Thang, 2010; Li et al., 2011; Thimm, 2012; Rienstra, 2012] have extended the original Dung framework into the probabilistic Abstract Argumentation Framework (prAAF), where the uncertainty is modeled by exploiting the probability theory. In particular, [Li et al., 2011] proposed a form of prAAF (here denoted as IND, shorthand for "independence") where each argument/defeat can be associated with a probability (and arguments and defeats are viewed as independent events), whereas [Dung and Thang, 2010] proposed a form of prAAF (here denoted as EX, shorthand for "extensive") where uncertainty can be taken into account by extensively specifying a probability distribution function (pdf) over the possible scenarios.

Example 2 (continuing Example 1) In the case of modeling the uncertainty by assigning probabilities to possible scenarios, as done in prAAFs of form EX, suppose that the lawyer thinks that only the following 4 scenarios are possible:

S1: "Ann does not testify";

S2: "Ann testifies, and the jury will deem that argument c undermines Mary and Marc's arguments a, b, and vice versa"; S3: "Ann testifies, and the jury will deem that her argument c undermines Mary and Marc's arguments a, b, while, owing to the bad reputations of Mary and Marc, a and b will be not perceived as strong enough to undermine argument c";

S4: "Ann testifies, and the jury will deem that her argument c undermines Mary's argument a but not Marc's argument b, as Ann is uncertain about Marc's presence. Vice versa, a and b will be not perceived as strong enough to undermine c".

Each Si is encoded by the AAF αi in the following list:

Basically, the form EX allows the lawyer to define, one by one, which scenarios are possible, and then to assign a probability to the AAF corresponding to each scenario, on the basis of her/his perception of how likely the scenario is. For instance, the pdf set by the lawyer could be: P(α1) = 0.1 and P (α2) = P (α3) = P (α4) = (1-P (α1))/3 = 0.3, meaning that the lawyer thinks that there is 10% probability that Mary will not testify (owing to her ill-health), and that, in the case she testifies, the other three scenarios are equi-probable.

Example 3 (cont. Example 1) If the form IND is used, the lawyer can associate each argument and defeat with a probability. For instance, the lawyer may set P(c) = 0.9 (meaning that there is 10% probability that Mary will not testify) and P(a) = P(b) = 1 (meaning that Mary and Marc will certainly testify). Moreover, she/he could set P(δca) = 1 (meaning that she/he is certain that the jury will consider Ann's argument as a solid rebuttal of Mary's argument). Analogously, she/he could set P (δcb) = 0.8 and P (δac) = P (δbc) = 0.4.

Given this, since the arguments are considered independent, the possible scenarios modeled by IND are all the AAFs 〈Ai,Di〉 where Ai is a subset of the arguments and Di a subset of the defeats between the arguments in Ai. Specifically, there are 9 possible AAFs, where 4 out of 9 are equal to α1, . . . α4 of the previous example, and the others are α5 = 〈{a, b, c}, {δac, δca}〉, α6 = 〈{a, b, c}, {δca, δbc}〉, α7 = 〈{a, b, c}, {δca, δcb, δac}〉, α8 = 〈{a, b, c}, {δca, δcb, δbc}〉, α9 = 〈{a, b, c}, {δca, δac, δbc}〉. The probability assigned to each AAF 〈A,D〉 is the result of a product, whose factors are the probabilities (resp., the complements of the probabilities) of the arguments in A (resp., not in A) and the probabilities (resp., the complements of the probabilities) of the defeats in D (resp., not in D). For instance, P(α1) = P (a)×P (b)×(1-P (c)) = 0.1 and P (α3) = P (a)×P (b)× P (c)×P (δca)×P (δcb)×(1-P (δac))×(1-P (δbc)) = 0.26.

1.1 Contribution

Reasoning over AAFs typically requires dealing with two fundamental problems: the problem EXTsem(S) of verifying whether S is a sem extension, and the problem ACCsem(a) of deciding whether argument a is acceptable (i.e., it belongs to some sem extension). In the literature, the complexity of EXTsem(S) and ACCsem(a) has been extensively studied (see tables 1 and 2), but much less is known about the complexity of the counterparts P-EXTsem(S) and P-ACCsem(a) of the same problems in the probabilistic setting. Basically, P-EXTsem(S) asks for the probability that S is an extension, and P-ACCsem(a) for the probability that a is accepted. The only results in the literature regarding P-EXTsem(S) and PACCsem(a) are those in [Fazzinga et al., 2015] and [Fazzinga et al., 2017], referring to the complexity of P-EXTsem(S) and P-ACCsem(a) over prAAFs of the form IND. In this regard, our first contribution is the complexity characterization of P-EXTsem(S) and P-ACCsem(a) over the form EX: we show that, depending on the semantics of the extension, P-EXTsem(S) and P-ACCsem(a) are in FP or FP ||NP - complete or in FP ||Σp2 . Starting from this, we give an insight on the sources of complexity of the considered problems by studying the sensitivity of the complexity to the correlations between arguments and/or defeats encoded in the prAAF. To accomplish this, we introduce a new prAAF (called GEN) where the constructs used for defining the pdf over the possible scenarios allow for explicitly specifying correlations, such as mutual exclusion and co-occurrence between arguments/defeats. This framework is based on the well-known paradigm of world-set descriptors (wsds) and ws-sets, that was shown to be a complete and succinct formalism for specifying pdfs over possible worlds in [Antova et al., 2008; Koch and Olteanu, 2008] in the context of probabilistic databases. Interestingly, we exploit the fact that different syntactic restrictions of the form GEN allow different correlations between arguments/defeats to be expressed, and provide a complexity analysis of P-EXTsem(S) and P-ACCsem(a) for each syntactic class, thus showing the sensitivity of the complexity to the presence of different correlations.

2 Preliminaries

An abstract argumentation framework [Dung, 1995] (AAF) is a pair 〈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 defeats (or attacks). Given a, b ∈ A, we say that a defeats b iff (a, b) ∈ D. A set S ⊆ A defeats an argument b ∈ A iff there is a ∈ S that defeats b. An argument a defeats S iff there is b ∈ S defeated by a. Given S ⊆ A, we define S+ as the set of arguments defeated by S.

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.

An extension is a set of arguments that is considered "reasonable" according to some semantics. In particular, we consider the following popular semantics from the literature:

• admissible (ad): S is an admissible extension iff S is conflict-free and its arguments are acceptable w.r.t. S;
• stable (st): S is a stable extension iff S is conflict-free and S defeats each argument in A \ S;
• complete (co): S is a complete extension iff S is admissible and every argument acceptable w.r.t. S is in S;
• grounded (gr): S is a grounded extension iff S is a minimal (w.r.t. ⊆) complete set of arguments;
• semi-stable (sst): S is a semi-stable extension iff S is a complete extension where S ∪ S+ is maximal (w.r.t. ⊆);
• preferred (pr): S is a preferred extension iff S is a maximal (w.r.t. ⊆) complete set of arguments;
• ideal-set (ids): S is an ideal-set extension iff S is admissible and S is contained in every preferred extension;
• ideal (ide): S is an ideal extension iff S is a maximal (w.r.t. ⊆) ideal-set extension.

An argument a is acceptable w.r.t. a semantics sem iff a belongs to some sem extension. Given an AAF, a semantics sem, a set of arguments S and an argument a, the fundamental problems of verifying whether S is a sem extension and whether a is acceptable (w.r.t sem) will be denoted as EXTsem(S) and ACCsem(a), respectively.

3 Probabilistic AAFs (prAAFs)

A well-established way of modeling uncertainty in abstract argumentation is that of considering alternative possible scenarios, and assigning probabilities to them. Basically, given a set A of possible arguments and a set D of possible defeats, each scenario (called "possible AAF") is an AAF whose arguments and defeats are subsets of A and D that can be viewed as a hypothesis on which arguments/defeats will actually occur in the dispute. Thus, a probabilistic AAF is a tuple F = 〈A, D, ⃗α, P 〉 where ⃗α = α1, . . . , αm is a set of possible AAFs taking arguments and defeats from A and D, while P is a probability distribution function (pdf) over ⃗α such that P(α) represents a measure of how likely the arguments and defeats occurring in the dispute are exactly those in α.

Several forms of prAAFs exist in the literature, differing in the paradigm used to encode the pdf P: different paradigms have different expressiveness, and this influences the correlations that can be imposed between arguments/defeats.

3.1 The Extensive Paradigm EX

EX is a form of prAAF (at the basis of the frameworks in [Dung and Thang, 2010; Rienstra, 2012; Thimm, 2012; Dondio, 2014]) where the pdf over the possible AAFs is specified "extensively", by indicating one by one the scenarios with non-zero probability, and the probability of each of them. The size of a prAAF 〈A,D, ⃗α, P〉 of form EX is thus O ((|A| + |D|) · |⃗α| + |P |).

In the prAAF of form EX of Example 2, A = {a, b, c}, D = {δca, δcb, δac, δbc}, ⃗α = [α1, . . . , α4] and P is such that P (α1) = 0.1, P (α2) = P (α3) = P (α4) = 0.3.

3.2 The Independence-Based Paradigm IND

In prAAFs of form IND [Fazzinga et al., 2015; Fazzinga et al., 2016], the possible AAFs and the pdf over them are implicitly defined, as they are implied by assigning marginal probabilities to arguments and defeats, and assuming independence between them. Thus, ⃗α and P are encoded as a pair 〈PA, PD〉, where PA and PD denote the marginal probabilities of the arguments and the defeats, respectively. In turn, given a pair 〈PA, PD〉, the corresponding set ⃗α and pdf P are as follows. As regards ⃗α, it contains every AAF αi = 〈Ai,Di〉 such that Ai ⊆ A, and Di ⊆ (Ai × Ai) ∩ D. In turn, owing to the independence assumption, the probability implicitly assigned to each αi = 〈Ai,Di〉 is: P(αi) = ∏a∈Ai PA(a)× ∏a∈A\Ai (1 - PA(a)) × ∏δ∈Di PD(δ) × ∏δ∈D(αi)\Di (1 - PD(δ)), where D(αi) = D∩(Ai×Ai). For instance, considering the possible AAFs of Example 3, we have that P (α5) = P (〈{a, b, c}, {δac, δca}〉) = P (a) × P (b) × P (c) × P (δac) × P (δca) × (1 - P (δbc)) × (1 - P (δcb)) = 0.043. The size of a prAAF of form IND is thus O(|A| + |D| + |PA| + |PD|).

3.3 ANewGeneral and Compact Paradigm: GEN

We here introduce the new paradigm GEN for specifying the pdf over the possible scenarios. It has three main amenities: 1) it generalizes EX, since it also enables an "extensive" definition of the pdf over the possible AAFs; 2) it generalizes IND, since it also allows us to impose independence between arguments/defeats; 3) in order to encode a pdf over the possible AAFs, it exploits the representation model of world-set descriptors and world-set sets, that is a succinct and complete model for representing possible worlds and probabilities over them [Antova et al., 2008; Koch and Olteanu, 2008]. According to this paradigm, any set of possible worlds and any pdf f over them can be defined by means of a suitable set V of independent discrete random variables. A single possible world is encoded by a valuation of the variables in V , and its probability is given by the product of the probabilities of each assignment. For instance, if V = {X, Y }, where X, Y are binary random variables with probability function p, then ω1 = {X = 0, Y = 0} is a possible world, with probability f(ω1) = p(X = 0) · p(Y = 0), as well as ω2 = {X = 0, Y = 1}, with f(ω2) = p(X = 0) · p(Y = 1). In this case, we have other 2 possible worlds, corresponding to the other valuations of X and Y . In turn, a set of possible worlds can be defined by either a worldset descriptor (wsd) or a world-set set (wss). A wsd d is a valuation for a subset of V , and represents the set ω(d) of possible worlds compatible with these valuations. For instance, d = {X = 0} is a wsd, and it represents the set ω(d) = {ω1, ω2}. In turn, a wss is a set of wsds, and it encodes the set of possible worlds that are represented by some wsd inside it. The probability of a wsd or a wss is the sum of the probabilities of the possible worlds that they represent.

In our context, the set ⃗α of possible AAFs and the pdf P over them can be easily represented by associating each argument/defeat x with a wss: this wss describes the set of possible worlds where x occurs, and the probability of each possible AAF α is the overall probability of the possible worlds containing the arguments/defeats in α.

The major benefit of using the paradigm GEN is that it is as expressive as EX, as it allows any pdf to be encoded, but it is more compact (there is no P that requires a longer encoding in GEN than in EX, while in several cases the encoding in GEN is strictly shorter than in EX). Compared with IND, GEN is more expressive, and when used to represent the independence between arguments/defeats, it is as compact as IND. From a "modeling" perspective, resorting to GEN can make it easier to specify the correlations between the arguments/defeats: for instance, the co-existence between two arguments can be expressed by associated the same wss to them, while an XOR relationship can be expressed by associating them with wsss with empty intersection.

The aspects discussed above make GEN a standalone contribution as a new expressive yet succinct form of prAAF. Moreover, they back the use of GEN to perform a complexity analysis of the fundamental problems regarding the reasoning over prAAFs, since it allows an analysis of sensitivity to the forms of correlations specified over the arguments/defeats.

4 The Complexity of Reasoning Over prAAFs

In the probabilistic setting, EXTsem(S) and ACCsem(a) naturally turn into the functional problems P-EXTsem(S) and P-ACCsem(a) of evaluating the probabilities P sem(S) that S is an extension and P sem(a) that a is acceptable, respectively. In particular, these probabilities are the sums of the probabilities of the possible AAFs where these properties hold.

Example 4 Consider Example 2. The probability P ad ({a, b}) that set {a, b} (resp., {c}) is an admissible extension is P(α1) + P(α2) = 0.4. Analogously, P ad ({c}) = P(α2) + P(α3) + P(α4) = 0.9. Consider now Example 3. We have P ad ({a, b}) = P(α1) + P(α4) + P(α5) + P(α6)+P(α7)+P(α8)+P(α9) = 0.676, and P ad ({c}) = P (α2)+P (α3)+P (α4)+P (α5)+P (α7)+P (α8) = 0.829.

In our analysis, in order to study the sources of complexity, we consider not only EX, IND and GEN, but also IND-A and IND-D, two subclasses of GEN sharing these restrictions: 1) the variables occurring in the wsds are boolean; 2) every argument/defeat is associated with a wss consisting of a unique wsd, where only one variable occurs. These two restrictions preserve the possibility of specifying correlations of practical importance, such as XOR relationships and coexistence. Moreover, in IND-A (resp., IND-D), the wss associated to any argument (resp., defeat) contains a variable occurring nowhere else, meaning that the arguments (resp., defeats) are independent from the other terms of the dispute.

Tables 1 and 2 provide a synopsis of our complexity results (see [Fazzinga et al., 2019] for the proofs). Looking into them, we can observe that, except for the tractable cases, P-EXTsem(S) and P-ACCsem(a) over IND, GEN and its subclasses belong to a complexity class harder than over EX (since FP #P ⊇ FP C , for any C in the polynomial hierarchy). This must be read by keeping in mind that the input encoding in EX contains the enumeration of the possible AAFs, while in IND and GEN the possible AAFs are implicitly defined by the marginal probabilities and the wsss, respectively. Hence, solving a problem over EX may benefit from saving a "level of exponentiality", compared with GEN or IND.

Another interesting point is that the presence of different forms of correlations has an impact on the complexity of P-EXTsem(S) under the admissible and stable semantics. In fact, in these cases, P-EXTsem(S) can be polynomially solved when defeats are independent, and correlations (in terms of co-existence and XOR constraints) are expressed between arguments (see column IND-D in Table 1). Interestingly, switching things, by making arguments independent and defeats correlated, makes the complexity explode. Observe that this is not implied by the fact that EXTsem(S) is in P under sem ∈ {ad, st}. In fact, P-EXTsem(S) over INDD is FP #P -complete under the complete and the grounded semantics, under which EXTsem(S) is polynomially decidable. As for P-ACCsem(a), the sensitivity analysis to the subclasses of GEN does not allow us to find tractability islands related to the types of correlations imposed over the terms of the dispute, since P-ACCsem(a) is already FP #P -complete under every semantics over IND. However, the result that PACCsem(a) over GEN is still in FP #P implies that imposing correlations does not further increase the complexity.

5 RelatedWork

The computational complexity of computing extensions and of arguments' acceptability has been investigated for classical AAFs [Dunne and Caminada, 2008; Dunne and Wooldridge, 2009; Dunne, 2009; Dvor´ak and Woltran, 2010; Gaggl and Woltran, 2013; Booth et al., 2014] under several semantics (a comprehensive overview of argumentation semantics can be found in [Baroni et al., 2011]). In particular, [Dunne and Caminada, 2008] presents a number of results on the complexity of some decision questions for semi-stable semantics, while [Dunne, 2009] focuses on ideal semantics; complexity results for preferred semantics can be found in [Dunne and Wooldridge, 2009]. [Dvor´ak and Woltran, 2010] provides complexity results for AAFs in terms of skeptical and credulous acceptance under the semi-stable semantics, while [Gaggl and Woltran, 2013] analyzes CF2 semantics. [Booth et al., 2014] has studied the computational complexity of different decision problems focused on critical sets of arguments whose status (i.e., membership to an extension) is sufficient to determine uniquely the status of every other argument. The complexity of computing extensions over AAFs with weights has been investigated in [Dunne et al., 2011; Coste-Marquis et al., 2012], while AAFs with preferences are studied in [Amgoud and Vesic, 2011; Kim et al., 2011].

The only results in the literature about the complexity of P-EXTsem(S) and/or P-ACCsem(a) regard IND [Fazzinga et al., 2015; Fazzinga et al., 2018a]. Recently, the complexity of P-EXTsem(S) over bipolar prAAFs of forms IND and EX has been investigated in [Fazzinga et al., 2018b].

6 Conclusion

A thorough characterization of the complexity of the fundamental problems of evaluating the probabilities of extensions and of the acceptability of arguments in prAAFs has been provided. The results reported in this paper give an insight on the sensitivity of the complexity to the semantics of extensions and the forms of correlations between arguments/defeats. This fills a gap in the research literature, where the complexity of P-EXTsem(S) and P-ACCsem(a) was studied only in specific cases (where arguments/defeats are independent), or for the deterministic counterparts.