# abstract_argumentation_frameworks_with_marginal_probabilities__2843fa13.pdf

Abstract Argumentation Frameworks with Marginal Probabilities

Bettina Fazzinga1,2 and Sergio Flesca3 and Filippo Furfaro3

1DICES - University of Calabria, Italy 2ICAR - CNR, Italy 3DIMES - University of Calabria, Italy {bettina.fazzinga, sergio.flesca, filippo.furfaro}@unical.it

In the context of probabilistic AAFs, we introduce AAFs with marginal probabilities (m AAFs) requiring only marginal probabilities of arguments/attacks to be specified and not relying on the independence assumption. Reasoning over m AAFs requires taking into account multiple probability distributions over the possible worlds, so that the probability of extensions is not determined by a unique value, but by an interval. We focus on the problems of computing the max and min probabilities of extensions over m AAFs under Dung s semantics, characterize their complexity, and provide closed formulas for polynomial cases.

1 Introduction Several frameworks based on the probability theory have extended Dung s Abstract Argumentation Framework (AAF [Dung, 1995]) to take into account the uncertainty possibly affecting the occurrence of arguments and attacks in the argumentation. In particular, in the constellations approach [Hunter, 2012; Hunter, 2014; Dondio, 2014; Doder and Woltran, 2014; Rienstra, 2012; Dung and Thang, 2010; Li et al., 2011; Fazzinga et al., 2015] the dispute is represented with a probabilistic AAF (pr AAF), that encodes the alternative possible worlds for the argumentation as a set of (deterministic) AAFs, where each AAF is associated with the probability of being the AAF actually occurring. pr AAFs can be divided in two categories: those relying on the independence assumption (i.e. arguments are independent from one another, and the occurrence of attacks is conditioned only to the occurrence of the related arguments), and those not. The latter allow the analyst to specify any probability distribution function (pdf) over the possible worlds, but, in fact, can be hardly used in complex scenarios: defining such a pdf may require reasoning on a number of possible worlds exponential w.r.t. the number of arguments and attacks, and this in turn may require a strong effort and a deep knowledge of the correlations between arguments and attacks, that often is not available. On the other hand, the pr AAFs assuming independence are compact and user-friendly, as they require only the specification of the marginal probabilities of arguments/attacks (which implicitly define a pdf over the possi-

ble worlds). In fact, assigning suitable marginal probabilities calls for reasoning over one argument/attack at the time, so is much less burdensome than explicitly describing a pdf over the possible worlds and does not require to have a precise picture of how the arguments/attacks are correlated. For instance, the probability of an argument (resp., attack) can be modeled by looking into statistics about occurrences of single arguments/attacks or by reasoning on the chances of participating to the dispute of the agents who propose the arguments or perceive the attacks. Unfortunately, assuming independence is often inadequate, since the existence of correlations between arguments/attacks cannot be excluded. In this paper, we introduce a new pr AAF, called AAF with marginal probabilities (m AAF), that is in between these two categories: it requires to specify no pdf over the possible worlds, but only the marginal probabilities of arguments and attacks, while not assuming independence. This calls for a reasoning paradigm different from the pr AAFs in the literature, where a single (explicitly or implicitly encoded) pdf over the possible worlds is considered: in m AAFs several pdfs may be consistent with the marginal probabilities, thus the probability of being extensions cannot measured by a unique value. The following example clarifies this aspect, and gives an insight on why assuming independence when correlations are not known may result in incautious conclusions.

Example 1 Consider the argumentation graph below, reporting the marginal probabilities of arguments and attacks.

The numbers besides nodes and edges are the marginal probabilities returned by a function P ( )

As the three arguments are the only uncertain portions of the argumentation, we have the 23 = 8 possible worlds reported in the first column of the table below. The other columns report three (out of many other) pdfs consistent with the marginal probabilities. Specifically, π1 corresponds to assuming independence between arguments/attacks, as it assigns to every possible world ωi the product of the marginal probabilities (resp., complements of marginal probabilities) of the arguments/attacks in ωi (resp., not in ωi). As for π3, it corresponds to the case where a, b are positively correlated and are in mutual exclusion with c (so that the only possible scenarios for the argumentation are ω4 and ω5), while π2 to the case where either a, b, c coexist, or at most one between

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

a or b occurs. Observe that π2 (resp., π3) is a pdf minimizing (resp., maximizing) the probability of ω5 (0 and 0.6 are the min and max values since no pdf can assign to ω5 a probability lower than 0 and higher than any of P(a), P(b), 1 P(c)).

possible world π1 π2 π3 ω1 = , 0.096 0.2 0 ω2 = {a}, 0.144 0.2 0 ω3 = {b}, 0.144 0.2 0 ω4 = {c}, 0.064 0 0.4 ω5 = {a, b}, 0.216 0 0.6 ω6 = {a, c}, {(c, a)} 0.096 0 0 ω7 = {b, c}, {(c, b)} 0.096 0 0 ω8 = {a, b, c}, {(c, a), (c, b)} 0.144 0.4 0

Let S ={a, b}. The only ωi where S is admissible is ω5. As in pr AAFs the probability that a set is an extension is the sum of the probabilities of the possible worlds where the extension s conditions are met, the probability P(S) that S is admissible is the probability of ω5. Therefore, from what said above on the minimum and maximum probability of ω5, we conclude that P(S) is in the range [π2(ω5)..π3(ω5)]= [0..0.6]. Now, suppose that the analyst is a lawyer, and that a, b are arguments possibly claimed by the counterpart s witnesses. If the lawyer trusted the analysis under independence, they would conclude that {a,b} is not a robust set of arguments, since P(S) = π1(ω5) = 0.216 is rather low. Instead, taking into account all the possible pdfs consistent with the marginal probabilities, the lawyer would be aware that P(S) can be rather high, as P(S) may be up to π3(ω5) = 0.6, thus they can make more cautious decisions regarding the trial strategy.

1.1 Contributions We introduce m AAFs along with the problems of maximizing and minimizing the probability that a set is an extension over an m AAF. We first focus on MAXP-VER, the decision counterpart of the maximization problem, and provide a thorough complexity analysis under Dung s semantics for extensions. We show that, depending on the semantics, MAXP-VER can be polynomial-time solvable, NP-complete or Σp 2-complete. For the PTIME cases, we provide elegant closed formulas returning the maximum probability value. Furthermore, we show the relation between m AAFs and the several pr AAFs proposed in the literature. Finally, we also analyze the dual problem MINP-VER referring to the minimum probability, providing a tight characterization under some semantics and showing an interesting asymmetry w.r.t. MAXP-VER.

2 Preliminaries

An abstract argumentation framework (AAF) is a pair F = A, D , where A is a set of abstract elements, called arguments, and D a binary relation over arguments, called attack relation. Given a A and S A, we say: a is acceptable w.r.t. S if for every (c, a) D there is some (s, c) D with s S. An attack (a, b) will be also denoted as δab. Several semantics for AAFs have been proposed to identify reasonable sets of arguments, called extensions [Dung, 1995]. A set S A is: a conflict-free extension (cf) iff there is no attack involving arguments in S; 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 attacks each argument in A \ S; a complete extension (co) iff S is admissible and contains all the arguments that are acceptable w.r.t. S; a grounded extension (gr) iff S is a minimal (w.r.t. ) complete set of arguments; a preferred extension (pr) iff S is a maximal (w.r.t. ) complete set of arguments. The set of extensions of an AAF F under a semantics σ is denoted as Ext(F, σ). The verification problem of deciding if S Ext(F, σ) and is denoted as VER(F, S, σ).

3 AAFs with Marginal Probabilities (m AAFs) We consider the case where the arguments and attacks that may occur in the argumentation are known, but the exact composition of the argumentation is not certain, as it is not known which of the possible worlds (i.e. sets of arguments and attacks) will be the actual argumentation. In particular, we consider the scenario where a probabilistic measure of the uncertainty is available, in terms of the marginal probabilities of the arguments and attacks. Basically, the marginal probability of an argument represents the overall probability of the possible worlds where the argument occurs. The meaning of the marginal probability of an attack is analogous, but its value is conditioned to the occurrence of the involved arguments (e.g. (a, b) has probability 1 means that the attack occurs in all the scenarios where both a and b occur). This naturally gives rise to the formal definition below.

Definition 1 (m AAF) An AAF with marginal probabilities (m AAF) is a tuple A, D, P , where A, D is an AAF and P : (A D) [0, 1] associates arguments and attacks with probabilities. Arguments and attacks are said to be certain is they are assigned probability 1 by P, uncertain otherwise.

Formally, given an m AAF F = A, D, P , a possible world of F is any AAF ω = A , D with A A, D (A A ) D. We denote as PW(F) the set of the possible worlds of F. Given two possible worlds ω = A, D , ω = A , D , we say that ω expands ω if (A D) (A D ). Differently from the probabilistic extensions of AAFs in the literature (see the discussion on constellations approaches in Section 5), m AAFs do not rely on a unique probability distribution function (pdf) over the possible worlds: different pdfs may be consistent with the marginal probabilities characterizing arguments and attacks, as discussed in Example 1 and below.

Example 2 Continuing Example 1, it is easy to see that also π4, that assigns 0.4 to both ω2 and ω7, 0.2 to ω5 and 0 to all the other possible worlds, is consistent with the marginal probabilities. Observe that π4 maximizes the probability of ω2 (containing only a): no consistent pdf can assign to ω2 a value higher than any of P(a), 1 P(b), 1 P(c).

Given a pdf π over PW(F) and a set of possible worlds PW PW(F), π(PW ) = P

ω P W π(ω) denotes the overall probability assigned by π to the possible worlds in PW . Then, we say that π is consistent with the marginal probability of argument a (resp., attack δab), written as π |= P(a) (resp., π |= P(δab)) if P(a) = P ω P W (F )|a ωπ(ω) (resp., P(δab) =

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

P ω P W (F )|δ ωπ(ω)/ P ω P W (F )|a ω b ωπ(ω)). In turn, π is consistent with P (π |= P) if it is consistent with the marginal probabilities of F s arguments/attacks. We denote as Π(F) the set of pdfs over PW(F) consistent with P. The presence of multiple possible worlds for the argumentation, along the fact that each possible world may be associated with different probabilities (since different pdfs over PW(F) may be consistent with F), naturally call for revisiting the traditional way of considering extensions. In this spirit, given a pdf π in Π(F) and a semantics σ, we define the probability that S is a σ-extension of F according to π as: π(F, S, σ) = P ω|S Ext(ω,σ) π(w), that is the sum of the probabilities assigned by π to the possible worlds where S is a σ-extension. Then, in order to take into account that several probability assignments to the possible worlds can be consistent with the marginal probabilities, we define: Pmin(F, S, σ) = minπ Π(F ) π(F, S, σ) and Pmax(F, S, σ) = maxπ Π(F ) π(F, S, σ), i.e. the minimum and maximum probabilities that S is a σ-extension. Proposition 1 states two general properties: 1) there is always a pdf over PW(F) consistent with P, and 2) the set of probabilities that S is a σ-extension of F is a closed interval. Proposition 1 Let F be an m AAF, S a set of arguments and σ {cf, st, ad, co, gr, pr}. Then: 1) Π(F) = , and 2) for every p [Pmin(F, S, σ)..Pmax(F, S, σ)] there is a pdf π Π(F) such that p = π(F, S, σ). 1) follows from the existence of the pdf implied by assuming independence, while 2) is a straightforward consequence of the theory of probabilistic logics in [Nilsson, 1986], since the probabilities of sentences entailed by a probabilistic sentence are known to compose a closed interval. Reasoning over Pmin(F, S, σ) and Pmax(F, S, σ) is obviously relevant for an analyst looking into an argumentation modeled via an m AAF F, since this gives insights on the extent to which S can be considered robust . Thus, we address the decision problems MAXP-VER and MINP-VER, that are natural adaptions of the classical verification problem and that are the decision counterpart of finding Pmax(F, S, σ) and Pmin(F, S, σ): Problem statement: Let F be an m AAF F, σ a semantics, S a set of arguments, and p a probability value. MAXPVER(F, S, σ, p ) (resp., MINP-VER(F, S, σ, p )) is the problem of deciding if there is a pdf π in Π(F) such that π(F, S, σ) p (resp., π(F, S, σ) p ) .

4 Characterizing MAXP-VER and MINP-VER We start with the problem MAXP-VER and show that it can be solved in polynomial time under the conflict-free, admissible, and stable semantics, that it is complete for NP under the complete and grounded semantics, and for Σp 2 under the preferred semantics. In particular, for the polynomial-time cases, we provide closed formulas allowing an easy computation of Pmax(F, S, σ). In the following, given a set of arguments X, we denote with M(X) = max{0, 1 |X| + P a X P(a)} the minimum probability that, consistently with the marginal probabilities, the arguments in X occur simultaneously. Theorem 1 Given an m AAF F = A, D, P and S A:

1) Pmax(F, S, cf)=mins,t S 1 P(δst) min{P(s),P(t)}

2) Pmax(F, S, st) = min Pmax(F, S, cf), mina A\S{1 P(a) + P s S P(δsa) M({s, a}) .

3) Pmax(F, S, ad) = min Pmax(F, S, cf), mina A\S{(1 P(a))+mins S{(1 P(δas)) M({s, a})+P t S P(δta) M({t, a})}}

where min = 1 and P(δst) = 0 if δst D.

Proof of Case 1. Without loss of generality, we assume that A and S coincide, as it is easy to see that, denoting as F the projection of F over S, for each π Π(F ) there is a π Π(F) such that π (F , S,cf) = π(F, S,cf), and vice versa: π can be obtained from π by marginalization, while π can be obtained from π by distributing the marginal probabilities of the arguments and attacks in F but not in F over the possible worlds of F expanding the possible worlds of F . For any pair of (possibly coinciding) arguments s, t S, let Xst be the set of the possible worlds containing s, t, and no attack from s to t, and let Yst be the set of the possible worlds containing s, t. It is straightforward to see that, s, t S and π Π(F), the probability π(F, S, cf) that S is a cf-extension is not greater than the overall probability π(Xst), which, in turn, is equal to 1 P(δst) π(Yst). Herein, π(Yst) min{P(s), P(t)}, since Yst is a subset of the two sets Ys and Yt of the possible worlds containing s and t, respectively (where, obviously, π(Ys) = P(s) and π(Yt) = P(t)). Hence, we obtain that π Π(F) π(F, S, cf) mins,t S 1 P(δst) min{P(s), P(t)} . Since the right-hand side of this inequality (from now on denoted as MAX) coincides with the right-hand side of the formula for Pmax, it remains to be proved only that there is some π Π(F) for which this inequality holds as an equality. Let s1, . . . , sk be the arguments of S in ascending order of marginal probability. We consider the k + 1 sets of possible worlds: PW0, . . . , PWk where each PWi contains the possible worlds containing all the arguments si+1, . . . , sk (if i < k), but not s1, . . . , si (if i 1). Observe that PWk contains only the empty possible world, and that PW0 contains, among others, the possible world ωcf consisting of S and no attack between its arguments. Given this, in order to make π(F, S, cf) = MAX, we set π(ωcf) = MAX. Then, in order to guarantee that s S π |= P(s), it suffices to define π so that 1) π(PW0)=P(s1), 2) i [2..k] π(PWi 1) = P(si) P(si 1), 3) π(PWk) = 1 P(sk) and 4) π(ω) = 0 for each possible world ω not in any PWi. In particular, for each PWi, the overall probability π(PWi) is distributed among the possible worlds in PWi by making π consistent also with the attacks probabilities. To this aim, for each s, t S, we first compute P(δst)= P (δst) min{P (s),P (t)}

min{P (s),P (t)} π(ωcf), if P(δst) = 0, or P(δst)=0, otherwise, that is the (conditioned) marginal probability of δst rescaled against the overall probability of the possible worlds different from ωcf and containing s and t. Observe that, since π(ωcf) = MAX, P(δst) 1. Then, i [0..k], ω PWi with ω = ωcf, we set π(ω) = Xi Πδst ωP(δst) Πδst ω(1 P(δst)), where X0 = π(PW0) π(ωcf) and Xi =π(PWi), for i > 0, which ensures π|=P.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

Proof of Case 2. (Sketch) For every a A \ S, the term M (a)= 1 P(a)+P s SP(δsa) M {s, a} is the probability that a does not occur (as measured by 1 P(a)), or is attacked by S, assuming that the co-existence of a with each s S has minimum probability. Observe that, in M (a), the sum over the arguments in S means considering the attacks from different arguments in S to a as alternative, as this maximizes the probability that at least one of them occurs. Finally, taking the minimum between Pmax(F, S, cf) and mina A\S M (a) means maximizing the probability that S is conflict-free and, for each a A\S, either a does not occur or is attacked by S. Proof of Case 3. (Sketch) 1 P(δas) M {s, a} is the portion of the probability space occupied by the possible worlds where a does not attack s, when the probability that a and s coexist is minimized. Then, M (a) = mins S{(1 P(δas)) M {s, a} } is the maximum probability that a coexists with all the arguments in S, but a attacks no s S. Analogously, M (a) = P t SP(δta) M {t, a} is the maximum probability that some t S attacks a, provided that the probability that a and t coexist is minimized. Hence, M (a) = 1 P(a) +M (a)+M (a) is the maximum probability that a does not occur or does not attack S or is counterattacked by S. Correspondingly, min Pmax(F, S, cf), mina A\S M (a)

is the maximum probability that S is conflict free and every argument outside S either does not occur, or occurs but does not attack S, or occurs and is counterattacked by S.

Example 3 Applying the formulas above in Example 1, we obtain Pmax(F, {a, b}, cf) = min 1 P(δaa) min{P(a),P(a)}, 1 P(δbb) min{P(b),P(b)}, 1 P(δab) min{P(a),P(b)}, 1 P(δba) min{P(b),P(a)} = 0.6. As M({a, c})=M({b, c})= max 0, (0.6+0.4) 1 =0, the formulas for σ {ad, st} simplify to Pmax(F, {a, b}, ad) = min 0.6, (1 P(c)) = 0.6 and Pmax(F, {a}, st) = min Pmax(F, {a}, cf), min{1 P(c), 1 P(b))} =0.4.

As the formulas for Pmax in Theorem 1 can be evaluated in time O(|A|2), we obtain the following corollary.

Corollary 1 Under σ {cf, st, ad}, MAXP-VER is in P.

Under the other Dungean semantics, MAXP-VER becomes intractable. Interestingly, the intractability does not depend

Figure 1: (a) The m AAF F(φ) and (b) the m AAF F (φ) for φ = (x1 x2 x3) ( x1 x2 x3) (x1 x2 x3)

on whether the uncertainty involves the arguments or the attacks, since in both cases the problem becomes NP-complete under σ {co, gr} and Σp 2-complete under σ = pr. We start with showing the NP upper bound under σ {co, gr}, that will be proved similarly to what done in [Georgakopoulos et al., 1988] for proving that probabilistic SAT is in NP.

Theorem 2 Given an m AAF F = A, D, P and S A, MAXP-VER(F, S, σ, p ) is in NP under σ {co, gr}.

Proof. A π Π(F) such that π(F, S, σ) p can be found by solving a system of (in)equalities S with a positive variable π(ωi) for each ωi PW(F). S contains: 1) the equality P ωi P W (F ) π(ωi) = 1 (stating that the overall probability of the possible worlds is 1); 2) a A the equality P ωi P W (F )|a ωi π(ωi) = P(a) and, δab D, the equality P ωi P W (F )|δab ωi π(ωi) = P(δab) P ωi P W (F )|a,b ωi π(ωi) (imposing π |= P); 3) the inequality P ωi P W (F )|S Ext(S,σ) π(ωi) p (imposing that the overall probability of the possible worlds where S is a σ-extension is not less than p ). S has m = |A| + |D| + 2 (in)equalities and O(2|A D|) variables, thus, as entailed by linear programming theory, if it has a solution, it has a basic solution with at most m non zero values, where the size of each value is polynomially bounded by m and the size of the constants in S. Hence, MAXP-VER(F, S, σ) can be solved by guessing a polynomial-size π over PW(F) assigning a non-zero probability to at most m possible worlds, and then checking if π |= P and π(F, S, σ) p (this can be done in polynomial time, as VER is in P for σ {co,gr}). Theorem 3 states that NP is also a lower bound under σ {co, gr}. To prove this result, we rely on some symmetries that arise when reasoning over the pdfs consistent with P, that are exploited to obtain reductions from the NP-complete problem not-all-equals 3-SAT (NAE3SAT): Given a 3CNF formula ϕ, is there any truth assignment satisfying ϕ and such that no clause contains all the three literals set to true? .

Theorem 3 Given an m AAF F and S A, under σ {co, gr}, MAXP-VER(F, S, σ, p ) is NP-hard, even if: 1) all the arguments are certain, 2) all the attacks are certain.

Proof. In what follows, when referring to CNF formulas, we assume that their form is C1 Cm, where each clause Cj is the disjunction of kj literals Wkj h=1 lj h, and each lj h is a variable or its negation. We denote the variables as x1, . . . , xn. 3CNF denotes formulas where j [1..m] kj = 3. Case 1. We consider σ = co (an analogous reasoning on the same construction works for σ = gr). We first introduce the construction of the m AAF F(φ) = A, D, P encoding a generic CNF formula φ. Herein, A consists of an argument s, an argument cj for each clause Cj, and the arguments xi, xi for each variable xi; D contains, for each i [1..n], the defeats (s, xi), (s, xi), (xi, xi) and ( xi, xi), as well as, for each clause Cj and literal lj i in Cj, the attack (lj i , cj). Finally, P assigns probability 1

2 to the attacks (s, xi), (s, xi) (for i [1..n]), and 1 to all the other attacks and arguments. Fig. 1(a) depicts an example of F(φ).

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

We show a reduction from NAE3SAT. Given an instance ϕ of NAE3SAT, let ˆϕ = ϕ ϕ ϕX, where: ϕ = Vk j=1( lj 1 lj 2 lj 3) and ϕX = Vn i=1(xi xi). We now show the equivalence: The instance ϕ of NAE3SAT is true MAXP-VER(F(ˆϕ, {s}, co, 1) is true .

( ) As ϕ is a true instance of NAE3SAT, not only there is a truth assignment t satisfying ϕ, but also the complement t of t satisfies ϕ, and both t and t set at least one literal in every clause to false (with complement we mean: i [1..n], t (xi) = t(xi)). Hence, t and t make also ˆϕ satisfied. Let F(ˆϕ) = ˆA, ˆD, P and ω = A, D , ω = A , D be the possible worlds of F(ˆϕ) such that: 1) A = A = ˆA, and 2) D = ˆD \{(s, li) | (li = xi t(xi) = true) (li = xi t(xi) = false)}, and 3) D = ˆD\{(s, li) | (li =xi t (xi)= true) (li = xi t (xi)= false)}). Now, {s} is an extension in ω and ω , as t and t

make ˆϕ satisfied (thus every cj is attacked by some xi or xi not attacked by s). Let π be the pdf over PW(F(ˆϕ)) assigning probability 1

2 to both ω and ω , and 0 to the other possible worlds. By construction of ω, ω , it follows that π |= P. Hence, since {s} is a co-extension in ω and ω , and π(ω)+π(ω ) = 1, MAXP-VER(F(ˆϕ), {s}, co, 1) is true.

( ) As MAXP-VER(F(ˆϕ), {s}, co, 1) is true, there are k 0 possible worlds ω1, . . . , ωk of F(ˆϕ) such that 1) {s} is a complete extension of ω1, . . . , ωk, and 2) there is a pdf π Π(F(ˆϕ)) assigning non-zero probability only to ω1, . . . , ωk. We first prove that, for each i [1..n], j [1..k] ωj contains exactly one of the attacks (s, xi) or (s, xi). Reasoning by contradiction, assume that there is a ωj containing both (s, xi) and (s, xi). This implies that the argument corresponding to the clause (xi xi) ˆϕ is acceptable w.r.t. {s} in ωj, thus contradicting that {s} is a complete extension in ωj. Vice versa, assume that there is an ωj not containing (s, xi) and (s, xi). Since (s, xi) and (s, xi) do not occur simultaneously in any possible world in ω1, . . . , ωj 1, ωj+1, . . . , ωk, it follows that P((s, xi)) + P((s, xi)) = 1 π(ωj). But π(ωj) > 0 and P((s, xi)) = P((s, xi)) = 1

2, thus we reach the contradiction 1

2 < 1. Given that ω1 contains, for each variable xi, exactly one of the attacks (s, xi) or (s, xi), the relation t between the variables and the truth values true, false defined below is a truth assignment over x1, . . . , xn: xi {x1, . . . , xn}, t(xi) = true if (s, xi) ω1, and t(xi) = false if (s, xi) ω1. It is easy to see that t makes ˆϕ true, as for each Cj in ˆϕ there is at least one argument li (of the form xi or xi) attacking the argument cj such that (s, li) does not appear in ω1 (otherwise, {s} would not be a complete extension in ω1). This ends the proof, since the satisfiability of ˆϕ, by construction, implies that ϕ is a true instance of NAE3SAT. Case 2. We reason analogously to Case 1, but use a new construction. For any CNF formula φ, we consider the m AAF F (ϕ) = A, D, P where: A contains i [1..n] the arguments xi, xi, nai, and j [1..k] an argument cj; D contains, i [1..n], the attacks (xi, nai), ( xi, nai), (xi, xi) and ( xi, xi), and,

j [1..k], the attacks (lj 1, cj), (lj 2, cj), (lj 3, cj). P assigns 1 to every attack and to na1, . . . , nan, c1, . . . , ck, and 1 2 to x1, . . . , xn, x1, . . . , xn. An example of F (φ) is in Fig. 1(b). Then, similarly to Case 1, the equivalence An instance ϕ of NAE3SAT is true MAXP-VER(F (ϕ), , co, 1) is true can be proved. The difference here is that a truth assignment t can be encoded by a possible world containing, i [1..n], either xi or xi, where t(xi) = true (resp., false) is encoded by the presence of xi (resp., xi). Then, the fact that a clause Cj is made true by having assigned true (resp., false) to xi is encoded by the presence of the attack (xi, cj) (resp., ( xi, cj)).

Proposition 2 relates MAXP-VER with the verification problem INCVER over incomplete AAFs (i AAF), that are AAFs where some arguments and attacks are marked as uncertain (with no measure of their uncertainty). Herein, INCVER(F i, S, σ) asks if S is a σ-extension in some possible world of F i. This proposition states that INCVER can be reduced in polynomial time to MAXP-VER, and will be used to characterize the complexity of MAXP-VER under σ = pr. However, it is of independent interest, and it will be exploited in the next section, where we discuss the relationship between m AAFs and variants of AAFs dealing with uncertainty.

Proposition 2 There is a Karp reduction from INCVER to MAXP-VER adding no new uncertain arguments and attacks.

Proof. Given INCVER(F i, S, σ), where A and D (resp., A? and D?) are the certain (resp., uncertain) arguments and attacks of F i, let F = A A?, D D?, P be the m AAF where x A D P(x) = 1 and x A? D? P(x) = 1/2. Let π be the following pdf over PW(F): π(ω) = Πa A?1/2 Πδab D?|a,b ω1/2. Basically, π is the pdf entailed by assuming independence between the arguments and conditioned independence between attacks, thus

π |= P. Let p = minω P W (F ) π(ω) = 1

2 |D?|. It is easy to see that the answers of INCVER(F i, S, σ) and MAXP-VER(F, S, σ, p ) coincide.

Theorem 4 MAXP-VER(F, S, σ, p ) is Σp 2-complete under σ=pr, even if all the arguments or all the attacks are certain.

Proof. The membership proof is analogous to Theorem 2: solving VER over a possible world now requires an NP oracle, thus the problem is in NP NP . Proposition 2 and the Σp 2-hardness of INCVER (when the arguments or the attacks are certain [Baumeister et al., 2018]) imply the hardness. We now turn our attention to MINPVER, the dual problem referring to the minimum probability. Its complexity is characterized by the following theorem.

Theorem 5 Given an m AAF F = A, D, P and S A, 1) MINP-VER(F, S, cf, p ) is in P, and Pmin(F, S, σ) = max{0, M(S) P a,b S P(δab) M({a, b})}; 2) MINP-VER(F, S, pr, p ) is NP-complete; 3) MINP-VER is in NP under σ {ad, st, co, gr}.

Proof. 1) and 3) can be obtained reasoning analogously to the proofs of Theorems 1 and 2, respectively. As for σ = pr, the membership to NP follows from modifying the proving

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

strategy of Theorem 2 by replacing inequality I3 with an I 3 imposing that the overall probability that S is not preferred is not less than 1 p , and making the guess-phase include also a witness for each of the guessed π(ωi) involved in I 3 certifying that S is not preferred in ωi. A reduction from the complement of VER(F, S, pr) implies the hardness (it suffices to translate F into an m AAF F with no uncertain arguments/attacks and decide MINP-VER(F , S, pr, 1/2)). The case σ = pr is particularly interesting, since it shows an asymmetry between MAXP-VER and MINP-VER. We conjecture that an asymmetry holds also under σ {co, gr} as replacing the max operator with min when moving from MAXP-VER to MINP-VER does not allow the form of exclusive disjunction exploited in our reductions. Thus, overall, we conjecture that the upper bound in point 2) is not tight, and MINP-VER is in P under σ {ad, st, co, gr}.

5 Relationship with Probabilistic AAFs and Further Related Work m AAFs are in the family of probabilistic AAFs adopting the constellations approach (denoted as pr AAFs), as their semantics (differently from the epistemic approach [Hunter and Thimm, 2014; Hunter et al., 2020; Baier et al., 2021; Potyka, 2021], where probabilities are degrees of belief in arguments acceptance) is based on considering different possible worlds for the argumentation. The pr AAFs in the literature typically consider a single pdf over the possible worlds and differ in how this pdf is encoded. Exhaustive pr AAFs (EX [Dung and Thang, 2010]) enumerate the possible worlds ω1, . . . , ωk having a chance to be the actual argumentation, and assign a probability to each of them. Evaluating the probability of extensions over EX reduces to solving VER over every ωi (with i [1..k]). Hence, MAXP-VER over EX is in P under σ {cf, ad, st, co, gr}, for which VER is in P, and is in P ||NP under σ {pr}, as in this case it is solvable with k parallel invocations of an NP-oracle solving VER. This seems to mean that MAXP-VER over EX is never more complex than over m AAFs: in particular, it is easier under σ {co, gr} (where it is in P over EX and NP-complete over m AAFs) and under σ {pr} (where it is in P ||NP over EX and NP NP -complete over m AAFs). However, these differences in favor of EX follow from the explicit representation of the pdf in the encoding of EX. Thus, the measure of computational complexity over EX benefits from a discount of one exponential level compared with m AAFs, where enumerating the possible worlds has an exponential cost. In fact, such a discount is paid when an EX is defined, as the analyst is due to enumerate all the alternative scenarios, and this may be prohibitive when the possibilities are many. Things change significantly when considering general pr AAFs (GEN [Fazzinga et al., 2019]), where the pdf over the possible worlds is compactly encoded via world-sets descriptors: here, evaluating the probabilities of extensions becomes #P-hard for all the Dungean semantics (while MAXP-VER over m AAFs may be in P, NP-complete or Σp 2-complete, depending on σ). Finally, independence-based pr AAFs (IND [Li et al., 2011; Fazzinga et al., 2015]) share with m AAFs the specification of the marginal probabilities of arguments/attacks, but

they assume independence, thus a unique pdf over the possible worlds. Here, evaluating extensions probabilities can be done in PTIME under σ {cf, ad, st} (the same as MAXP-VER over m AAFs) and is FP #P -complete for the other semantics. Although a precise characterization of the decision problem MAXP-VER over IND is not in the literature, we can draw some conclusions: under σ {co, gr}, MAXP-VER over IND cannot be simpler than over m AAFs (where it is NP-complete), as the fact that the minimum difference between the probabilities of two possible worlds is known and of polynomial size allows for exploiting a polynomial number of invocations to a MAXP-VER s solver to obtain an extension probability. If MAXP-VER over IND were in NP, this would imply FP #P = FP NP . m AAFs are also related to i AAFs [Baumeister et al., 2018; Alfano et al., 2022]: Proposition 2 states the reducibility of the verification problem INCVER over i AAFs to MAXP-VER. From our results, it turns out that reasoning over i AAFs is of the same complexity as over m AAFs under σ {cf, ad, st} and σ = pr, where both problems are in P and Σp 2-complete, respectively, while, under σ {co, gr}, reasoning over i AAFs is strictly simpler than over m AAFs (as INCVER is in P [Fazzinga et al., 2020] while MAXP-VER is NPcomplete). Overall, m AAFs are between i AAFs and IND: introducing measures of uncertainty on top of i AAFs (thus obtaining m AAFs) can increase the computational complexity, as well as introducing the independence assumption on top of m AAFs (thus obtaining IND). Intuitively, a reason for the raise in complexity when moving to IND is that the independence assumption restricts Π(F) to a singleton, and this can allow, under some semantics, a form of counting (as the cardinality of a set of possible worlds can be inferred from its overall probability). Further works related to ours are those introducing probabilistic variants of AAFs generalizations (such as probabilistic bipolar AAFs [Fazzinga et al., 2018], probabilistic Control AFs [Gaignier et al., 2021], probabilistic Abstract Dialectical Frameworks [Polberg and Doder, 2014]) as well as those extending AAFs with preferences [Amgoud and Vesic, 2011], degrees of beliefs [Santini et al., 2018], social values [Bench Capon, 2003; Atkinson and Bench-Capon, 2016].

6 Conclusions and Future Work

We have introduced AAFs with marginal probabilities (m AAFs), where arguments and attacks are probabilistic events whose marginal probability is known (under no independence assumption). We have characterized the complexity of MAXP-VER and MINP-VER, that are the decision counterparts of maximizing and minimizing the probability that a set is an extension. In future work, we plan to prove our conjectures on the complexity of MINP-VER stated in Section 4, and to extend m AAFs with the specification of correlations among arguments/attacks, as done for i AAFs [Fazzinga et al., 2021a; Fazzinga et al., 2021b; Mailly, 2021]. This would exclude pdfs assigning non-zero probability to unrealistic possible worlds from the reasoning. Another interesting direction for future work is the investigation of constraintprogramming approaches for the NP-hard cases.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

References [Alfano et al., 2022] Gianvincenzo Alfano, Sergio Greco, Francesco Parisi, and Irina Trubitsyna. Incomplete argumentation frameworks: Properties and complexity. In Proc. of AAAI, 2022. [Amgoud and Vesic, 2011] Leila Amgoud and Srdjan Vesic. A new approach for preference-based argumentation frameworks. Ann. Math. Artif. Intell., 63(2), 2011. [Atkinson and Bench-Capon, 2016] Katie Atkinson and Trevor Bench-Capon. Value based reasoning and the actions of others. In Proc. European Conf. on Artificial Intelligence (ECAI), pages 680 688, 2016. [Baier et al., 2021] Christel Baier, Martin Diller, Clemens Dubslaff, Sarah Alice Gaggl, Holger Hermanns, and Nikolai K afer. Admissibility in probabilistic argumentation. In Proc, Conf. on Principles of Knowledge Representation and Reasoning, KR, pages 87 98, 2021. [Baumeister et al., 2018] Dorothea Baumeister, Daniel Neugebauer, J org Rothe, and Hilmar Schadrack. Verification in incomplete argumentation frameworks. Artif. Intell., 264:1 26, 2018. [Bench-Capon, 2003] Trevor J. M. Bench-Capon. Persuasion in practical argument using value-based argumentation frameworks. J. Log. Comput., 13(3):429 448, 2003. [Doder and Woltran, 2014] Dragan Doder and Stefan Woltran. Probabilistic argumentation frameworks - A logical approach. In Proc. Conf. Scalable Uncertainty Management (SUM), pages 134 147, 2014. [Dondio, 2014] Pierpaolo Dondio. Toward a computational analysis of probabilistic argumentation frameworks. Cybernetics and Systems, 45(3):254 278, 2014. [Dung and Thang, 2010] Phan Minh Dung and Phan Minh Thang. Towards (probabilistic) argumentation for jurybased dispute resolution. In Proc. Computational Models of Argument (COMMA), pages 171 182, 2010. [Dung, 1995] Phan Minh Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell., 77(2):321 358, 1995. [Fazzinga et al., 2015] Bettina Fazzinga, Sergio Flesca, and Francesco Parisi. On the complexity of probabilistic abstract argumentation frameworks. ACM Trans. Comput. Log., 16(3):22:1 22:39, 2015. [Fazzinga et al., 2018] Bettina Fazzinga, Sergio Flesca, and Filippo Furfaro. Probabilistic bipolar abstract argumentation frameworks: complexity results. In Proc. Joint Conf. on Artificial Intelligence (IJCAI), 2018. [Fazzinga et al., 2019] Bettina Fazzinga, Sergio Flesca, and Filippo Furfaro. Complexity of fundamental problems in probabilistic abstract argumentation: Beyond independence. Artif. Intell., 268:1 29, 2019. [Fazzinga et al., 2020] Bettina Fazzinga, Sergio Flesca, and Filippo Furfaro. Revisiting the notion of extension over incomplete abstract argumentation frameworks. In Proc. Joint Conf. on Artificial Intelligence (IJCAI), 2020.

[Fazzinga et al., 2021a] Bettina Fazzinga, Sergio Flesca, and Filippo Furfaro. Reasoning over argument-incomplete aafs in the presence of correlations. In Proc. Joint Conf. on Artificial Intelligence (IJCAI). ijcai.org, 2021. [Fazzinga et al., 2021b] Bettina Fazzinga, Sergio Flesca, and Filippo Furfaro. Reasoning over attack-incomplete aafs in the presence of correlations. In Proc. Principles of Knowledge Representation and Reasoning (KR), 2021. [Gaignier et al., 2021] Fabrice Gaignier, Yannis Dimopoulos, Jean-Guy Mailly, and Pavlos Moraitis. Probabilistic control argumentation frameworks. In Proc. of Conf. on Autonomous Agents and Multiagent Systems AAMAS, pages 519 527, 2021. [Georgakopoulos et al., 1988] George F. Georgakopoulos, Dimitris J. Kavvadias, and Christos H. Papadimitriou. Probabilistic satisfiability. J. Complex., 4(1):1 11, 1988. [Hunter and Thimm, 2014] Anthony Hunter and Matthias Thimm. Probabilistic argumentation with epistemic extensions. In Proc. of the International Workshop on Defeasible and Ampliative Reasoning, DARe@ECAI, 2014. [Hunter et al., 2020] Anthony Hunter, Sylwia Polberg, and Matthias Thimm. Epistemic graphs for representing and reasoning with positive and negative influences of arguments. Artif. Intell., 281:103236, 2020. [Hunter, 2012] Anthony Hunter. Some foundations for probabilistic abstract argumentation. In Proc. Computational Models of Argument (COMMA), pages 117 128, 2012. [Hunter, 2014] Anthony Hunter. Probabilistic qualification of attack in abstract argumentation. Int. J. Approx. Reasoning, 55(2):607 638, 2014. [Li et al., 2011] Hengfei Li, Nir Oren, and Timothy J. Norman. Probabilistic argumentation frameworks. In Proc. Int. Workshop on Theory and Applications of Formal Argumentation (TAFA), pages 1 16, 2011. [Mailly, 2021] Jean-Guy Mailly. Constrained incomplete argumentation frameworks. In Proc. of European Conf. on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU, pages 103 116, 2021. [Nilsson, 1986] Nils J. Nilsson. Probabilistic logic. Artif. Intell., 28(1):71 87, 1986. [Polberg and Doder, 2014] Sylwia Polberg and Dragan Doder. Probabilistic abstract dialectical frameworks. In Proc. European Conf. on Logics in Artificial Intelligence, JELIA, pages 591 599, 2014. [Potyka, 2021] Nico Potyka. From probabilistic programming to probabilistic argumentation. In Proc. of the International Conference on Logic Programming (ICLP), 2021. [Rienstra, 2012] Tjitze Rienstra. Towards a probabilistic dung-style argumentation system. In Proc. Int. Conf. on Agreement Technologies (AT), pages 138 152, 2012. [Santini et al., 2018] Francesco Santini, Audun Jøsang, and Maria Silvia Pini. Are my arguments trustworthy? abstract argumentation with subjective logic. In Proc. Int. Conf. on Information Fusion (FUSION), pages 1982 1989, 2018.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)