Abstract Argumentation Frameworks with Marginal Probabilities

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 (prAAF), 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. prAAFs 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 prAAFs 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 possible 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 prAAF, called AAF with marginal probabilities (mAAF), 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 prAAFs in the literature, where a single (explicitly or implicitly encoded) pdf over the possible worlds is considered: in mAAFs 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 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.

Let S={a, b}. The only ωi where S is admissible is ω5. As in prAAFs 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].

1.1 Contributions

We introduce mAAFs along with the problems of maximizing and minimizing the probability that a set is an extension over an mAAF. 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 Σp2 -complete. For the PTIME cases, we provide elegant closed formulas returning the maximum probability value. Furthermore, we show the relation between mAAFs and the several prAAFs 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 withMarginal Probabilities (mAAFs)

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 (mAAF) An AAF with marginal probabilities (mAAF) 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 mAAF 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), mAAFs 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 ′ ) = ∑ω∈PW ′ π(ω) 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) = ∑ω∈PW(F)|a∈ω π(ω) (resp., P(δab) =

∑ω∈PW(F)|δ∈ω π(ω)/ ∑ω∈PW(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, σ) = ∑ω|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 mAAF, 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 mAAF 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 mAAF 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 Σp2 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| + ∑a∈X P (a)} the minimum probability that, consistently with the marginal probabilities, the arguments in X occur simultaneously.

Theorem 1 Given an mAAF 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) + ∑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}) + ∑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 .

Proof of Case 2. (Sketch) For every a ∈ A\S, the term M ′ (a)= 1-P (a)+∑s∈S P (δ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) = ∑t∈S P(δ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 on whether the uncertainty involves the arguments or the attacks, since in both cases the problem becomes NP -complete under σ ∈ {co, gr} and Σp2 -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 mAAF 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 ∑ωi∈PW(F) π(ωi) = 1 (stating that the overall probability of the possible worlds is 1);
2. ∀a ∈ A the equality ∑ωi∈PW(F)|a∈ωi π(ωi) = P(a) and, ∀δab ∈ D, the equality ∑ωi∈PW(F)|δab∈ωi π(ωi) = P(δab) · ∑ωi∈PW(F)|a,b∈ωi π(ωi) (imposing π |= P);

3) the inequality ∑ωi∈PW(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 mAAF 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 ∨kj h=1 ljh , and each ljh 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 mAAF 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(φ).

We show a reduction from NAE3SAT. Given an instance ϕ of NAE3SAT, let ˆ ϕ = ϕ ∧ ϕ ∧ ϕX, where: ϕ = ∧kj=1 (¬lj1 ∨ ¬lj2 ∨ ¬lj3 ) and ϕX = ∧ni=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)) = 12 , thus we reach the contradiction 12 + 12 < 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 mAAF 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 (lj1 , cj), (lj2 , cj), (lj3 , 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 (iAAF), 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 mAAFs 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 mAAF 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ω∈PW(F) π(ω) = ( 1 2 )|A? | × ( 12 )|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 Σp2 -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 Σp2 -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 mAAF 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) - ∑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 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 mAAF 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

mAAFs are in the family of probabilistic AAFs adopting the constellations approach (denoted as prAAFs), 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 prAAFs in the literature typically consider a single pdf over the possible worlds and differ in how this pdf is encoded. Exhaustive prAAFs (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 mAAFs: in particular, it is easier under σ ∈ {co, gr} (where it is in P over EX and NP-complete over mAAFs) and under σ∈{pr} (where it is in P ||NP over EX and NP NP -complete over mAAFs). 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 mAAFs, 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 prAAFs (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 mAAFs may be in P , NP -complete or Σp2 -complete, depending on σ). Finally, independence-based prAAFs (IND [Li et al., 2011; Fazzinga et al., 2015]) share with mAAFs 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 mAAFs) 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 mAAFs (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 .

mAAFs are also related to iAAFs [Baumeister et al., 2018; Alfano et al., 2022]: Proposition 2 states the reducibility of the verification problem INCVER over iAAFs to MAXP-VER. From our results, it turns out that reasoning over iAAFs is of the same complexity as over mAAFs under σ ∈ {cf, ad, st} and σ = pr, where both problems are in P and Σp2 -complete, respectively, while, under σ ∈ {co, gr}, reasoning over iAAFs is strictly simpler than over mAAFs (as INCVER is in P [Fazzinga et al., 2020] while MAXP-VER is NPcomplete). Overall, mAAFs are between iAAFs and IND: introducing measures of uncertainty on top of iAAFs (thus obtaining mAAFs) can increase the computational complexity, as well as introducing the independence assumption on top of mAAFs (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 [BenchCapon, 2003; Atkinson and Bench-Capon, 2016].

6 Conclusions and FutureWork

We have introduced AAFs with marginal probabilities (mAAFs), 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 mAAFs with the specification of correlations among arguments/attacks, as done for iAAFs [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.