Dung's Argumentation Framework (AF) has been extended in several directions, including the possibility of representing unquantified uncertainty about the existence of arguments and attacks. The framework resulting from such an extension is called incomplete Argumentation Framework (iAF). In this paper, we discuss three satisfaction problems recently proposed for iAF, namely totality, determinism and functionality [1], and analyze their complexity under several semantics. We then show that any iAF can be rewritten into an equivalent one where either only (unattacked) arguments or only attacks are uncertain. Finally, we relate iAF to probabilistic argumentation framework, where uncertainty is quantified.
Formal argumentation has emerged as one of the important fields in Artificial Intelligence [
Various proposals have been made to extend the Dung framework with the aim of better
modeling the knowledge to be represented [
Example 1. Consider an iAF Δ = ⟨{a, b, c, d}, {e}, {(a, b), (b, a), (a, c), (b, d), (c, d), (d, c), (d, a), (e, a), (e, b)}, ∅⟩ whose corresponding graph is shown in Figure 1(left), where dashed nodes represent uncertain arguments (see Definition 1 for the formal definition). Δ describes the following scenario. A party planner invites Alice, Bob, Carl, David, and Erik to join a party. Due to their old rivalry (i) Alice replies that she will join the party if Bob, David and Erik do not; (ii) Bob replies that he will join the party if Alice and Erik do not; (iii) Carl replies that he will join the party if Alice and David do not; (iv) David replies that he will join the party if Bob and Carl do not; and (v) Erik replies that he is not sure whether he can join the party. This situation can be modeled by iAF Δ, where an argument x states that “(the person whose names’ initial is) x joins the party”, and argument e =“Erik joins the party" is uncertain. □
The semantics of an iAF is given by considering all completions, i.e. AFs obtained by removing consistent subsets of the uncertain elements, and for each completion its -extensions under a given semantics . The completions of iAF Δ of Example 1 are the AF Λ1 and Λ2 shown in Figure 1, center and right-hand side respectively, where Λ1 is the AF obtained from Δ by keeping all the arguments and attacks, while completion Λ2 is obtained from Δ by removing the uncertain argument e and, consistently with this, attacks (e, a) and (e, b) starting from e.
Since most of the argumentation semantics defined for AF are non-deterministic (i.e. multiplestatus, as they prescribe more than one extension), the notions of credulous and skeptical acceptance have been defined. Thus, given a semantics , an argument is credulously accepted if it occurs in at least one -extension, whereas it is skeptically accepted if all -extensions contain it. Acceptance problems have been recently extended to iAF: an argument is possibly credulously (resp. skeptically) accepted if there exists a completion where it is credulously (resp. skeptically) accepted; an argument is necessarily credulously (resp. skeptically) accepted if for all completions it is credulously (resp. skeptically) accepted.
Contributions.
Our main contributions are as follows.
We present three satisfaction problems for iAF called determinism (DS), totality (TS), and functionality (FS) (Section 3). Intuitively, totality tells us if an argument can be decided whatever the considered scenario (i.e. completion/world) is, while determinism tells us if we can safely make a decision in every scenario. Functionality combines totality and determinism and thus tells us if an argument can be firmly decided whatever the considered scenario is, that is if the information at hand is sufficient to make a decision in every possible scenario.
We investigate the complexity of the problems of checking determinism, totality, and functionality for general iAF and odd-cycle free iAF (a summary of the results is reported in Table 1). We show that an iAF Δ can be rewritten into an “equivalent” one Δ′, such that for every -extension of Δ, there is a -extension ′ of Δ′ coinciding with , modulo some metaarguments added in the rewriting (Section 4). Particularly, Δ′ can be of one of the following forms: ) only arguments or only attacks are uncertain (Δ′ is said to be an arg-iAF or attiAF, respectively); or ) uncertainty is only on arguments that are not attacked by any other argument (Δ′ is said to be an farg-iAF). We show that an arg-iAF can be translated into an farg-iAF. It can be shown that the results in Table 1 also hold for these restricted forms of iAFs. Finally, we study the relationships between iAF and PrAF and relate the acceptance problems in iAF to probabilistic acceptance in PrAF (Section 5). We derive a PrAF corresponding a given iAF and show that computing the probability of acceptance of an argument is FP#P-hard even restricting to acyclic iAFs.
We assume the reader is familiar with the complexity classes used in the paper [20].
In this section we recall the (abstract) Argumentation Framework (AF) and the incomplete AF.
and ⊆ × is a set of attacks.
Given an AF Λ = ⟨, ⟩ and a set ⊆ of arguments, an argument ∈ is said to be i) defeated w.r.t. iff there exists ∈ such that (, ) ∈ , and ii) acceptable w.r.t. iff for every argument ∈ with (, ) ∈ , there is ∈ such that (, ) ∈ . The sets of arguments defeated and acceptable w.r.t. are as follows (where Λ is understood): • Def() = { ∈ | ∃ ∈ . (, ) ∈ }; • Acc() = { ∈ | ∀ ∈ . (, ) ∈ ⇒ ∈ Def()}.
Given an AF ⟨, ⟩, a set ⊆ of arguments is said to be conflict-free iff ∩ Def() = ∅. Moreover, a set ⊆ is said to be a complete (co) extension iff it is conflict-free and =
Def() = ; • semi-stable (sst) iff it is a preferred extension with a maximal set of decided elements; • grounded (gr) iff it is ⊆ -minimal.
CAgr ≡
For any AF Λ and semantics , (Λ) denotes the set of -extensions of Λ. All the
abovementioned semantics except the stable admit at least one extension (i.e. (Λ) ̸= ∅), and the
grounded admits exactly one extension (i.e. |gr(Λ)| = 1) [
In the following we consider the acceptability of argument literals (or simply literals). A literal is either an argument or its negation ¬. A set of literals is said to be consistent if it does not contain two literals and ¬. We use ¬ to denote the set {¬ | ∈ }, and * to denote ∪ ¬. To deal with literals, we define the notion of fulfillment of an extension. Given an AF Λ = ⟨, ⟩ and an extension for it, the fulfillment of is ∪ ¬Def(). Clearly, the fulfillment of an extension is a consistent set of literals. Herein, arguments in are represented as positive literals (i.e. interpreted as true), while arguments defeated by are represented as negative literals (i.e. interpreted as false). In the rest of the paper, with a little abuse of notation, whenever we refer to an extension we mean its fulfillment .
For any AF Λ = ⟨, ⟩, semantics , and literal ∈ * , we say that is credulously (resp. skeptically) accepted (under semantics ), denoted as (Λ, ) (resp. (Λ, )) if belongs to at least a (resp. every) -extension of Λ. We use CA (resp. SA ), or simply CA (resp. SA) whenever is understood, to denote the credulous (resp. skeptical) acceptance problem, that is, the problem of deciding whether a literal is credulously (resp. skeptically) accepted. Clearly, for the grounded semantics, which has exactly one extension, these problems are identical (i.e.
SAgr).
Example 2. Consider the AF Λ = ⟨{a, b, c, d}, {(a, b), (b, a), (a, c), (b, c), (c, d), (d, c)}⟩. Λ has 4 complete extensions: 0 = ∅, 1 = {a, ¬b, ¬c, d}, 2 = {¬a, b, ¬c, d} and 3 = {¬c, d}. That is, co(Λ) = {0, 1, 2, 3}. 0 is the grounded extension, 1 and 2 are stable (preferred and semi-stable) extensions. Thus, a, b, d, as well as ¬a, ¬b, ¬c, are credulously accepted for all semantics except the grounded; only d and ¬c are skeptically accepted for stable, preferred and semi-stable semantics. □
We now recall the incomplete Argumentation Framework (iAF) [15].
Definition 1 (Incomplete AF). An incomplete Argumentation Framework (iAF) is a tuple Δ = ⟨, , , ⟩, where and are disjoint sets of arguments, and and are disjoint sets of attacks between arguments in ∪ . Arguments in and attacks in are said to be certain, while arguments in and attacks in are said to be uncertain.
Certain arguments in are definitely known to exist, while uncertain arguments in are not known for sure: they may occur or may not. Analogously, certain attacks in are definitely known to exist if both the incident arguments exist, while for uncertain attacks in it is not known for sure if they hold, even if both the incident arguments exist.
An iAF compactly represents alternative AF scenarios, or possible worlds, called completions. Definition 2 (Completion). A completion for an iAF Δ = ⟨, , , ⟩ is an AF Λ = ⟨′, ′⟩ where ⊆ ′ ⊆ ∪ and ∩ (′ × ′) ⊆ ′ ⊆ ( ∪ ) ∩ (′ × ′).
The set of completions of Δ is denoted by (Δ).
An iAF ⟨, , , ⟩ is acyclic (resp. odd-cycle free) iff the AF ⟨ ∪ , ∪ ⟩ is acyclic (resp. odd-cycle free).
To define acceptability and properties satisfaction of literals for iAFs, we refine the definition of fulfillment of extensions. Given an iAF Δ = ⟨, , , ⟩ and an extension for a completion Λ = ⟨′, ′⟩ of Δ, the fulfillment of is ∪ ¬ () ∪ ¬( ∖ ′). Herein, arguments in are represented as positive literals (i.e. interpreted as true), while arguments attacked by as well as uncertain arguments not occurring in Λ are represented as negative literals (i.e. interpreted as false).
Example 3. The only preferred extension of the completion Λ2 for the iAF Δ of Example 1 is {b, c}, whose fulfillment is {¬a, b, c, ¬d, ¬e}. □ Acceptance problems. Credulous and skeptical acceptance for iAF have been recently proposed in [21], where the goal, i.e. the element for which acceptance is checked, is an argument. As we focus on fulfillment of extensions, our goal is a literal.
Definition 3 (Possible/Necessary Credulous/Skeptical Acceptance). Let Δ = ⟨, , , ⟩ be an iAF and ∈ {gr, co, st, pr, sst}. Then, a literal ∈ * ∪ * is said to be: 1. possibly credulously accepted under , denoted as (Δ, ), iff there exists a completion Λ of Δ and a -extension of Λ such that ∈ ; 2. possibly skeptically accepted under , denoted as (Δ, ), iff there exists a completion Λ of Δ such that occurs in every -extension of Λ; 3. necessarily credulously accepted under , denoted as (Δ, ), iff for every completion Λ of Δ, there exists a -extension of Λ such that ∈ ; 4. necessarily skeptically accepted under , denoted as (Δ, ), iff for every completion Λ of Δ, occurs in every -extension of Λ.
We use PCA (resp. PSA , NCA , NSA ), or simply PCA (resp. PSA, NCA, NSA) whenever is understood, to denote the problem of deciding acceptance according to Item 1 (resp. 2, 3, and
Example 4. Consider the iAF Δ = ⟨{a, b, d}, {c}, {(a, b), (b, a)}, ∅⟩ shown in Figure 2 (left), where bidirectional arrows represent mutual attacks. Δ has 2 completions: Λ1 = ⟨{a, b, d}, {(a, b), (b, a)}⟩ and Λ2 = ⟨{a, b, c, d}, {(a, b), (b, a)}⟩ (see Figure 2). Under semantics ∈ {st, pr, sst}, Λ1 has the two extensions 1′ = {a, ¬b, ¬c, d} and 1′′ = {¬a, b, ¬c, d}; moreover, Λ2 has the two extensions 2′ = {a, ¬b, c, d} and 2′′ = {¬a, b, c, d}. Thus, a, b, c, d, ¬a, ¬b, ¬c satisfy PCA; c, d, ¬c satisfy PSA; a, b, d,¬a,¬b satisfy NCA and only d satisfies NSA. □ a c b d a b d a c b d
In this section we present three satisfaction problems for iAF called determinism (DS), totality
(TS), and functionality (FS) that have been recently proposed in [
Note that such questions cannot be answered by possible/necessary credulous/skeptical acceptance. In fact, a is functional but not possible credulously accepted, and b is functional but not necessary skeptically accepted. □ Definition 4 (Total, deterministic, functional literals). Let Δ = ⟨, , , ⟩ be an iAF, ∈ {gr, co, st, pr, sst}, and ∈ * ∪ * a goal literal. We say that is: • total under , denoted as (Δ, ), if for each Λ ∈ (Δ), i) (Λ) ̸= ∅ and ii) for each ∈ (Λ), either ∈ or ¬ ∈ ; • deterministic under , denoted as (Δ, ), if for each Λ ∈ (Δ), i) (Λ) ̸= ∅, and ii) either (Λ, ) or (Λ, ¬) or (¬ (Λ, ) ∧ ¬ (Λ, ¬)); • functional under , denoted as (Δ, ), if is total and deterministic under , that is, for each Λ ∈ (Δ), i) (Λ) ̸= ∅ and ii) either (Λ, ) or (Λ, ¬).
The next result immediately derives from definitions.
Fact 1. Let Δ be an iAF, ∈ {gr, co, st, pr, sst} and a literal. We have that i) (Δ, ) ≡ (Δ, ¬), ii) (Δ, ) ≡ (Δ, ¬), and iii) (Δ, ) ≡ (Δ, ¬) hold. a b c a b c
Example 6. Consider the iAF Δ = ⟨ = {a, b, c}, = {d}, = {(a, b), (b, a), (b, c), (c, c), (d, a), (d, b)}, = ∅⟩ reported in Figure 3, left side. Δ has two completions Λ1 = ⟨, ∖ {(d, a), (d, b)}⟩ and Λ2 = ⟨ ∪ , ⟩, also shown in Figure 3 (center). For Λ1 there are three complete extensions (recall that we refer to the fulfillments): 0 = {¬d}, 1 = {a, ¬b, ¬d} and 2 = {¬a, b, ¬c, ¬d}. The grounded extension is 0, while 1 is preferred, and 2 is stable, preferred, and semi-stable. For Λ2 there is only one complete extension 3 = {¬a, ¬b, d}, which is grounded, preferred, and semi-stable. The goal b is ) total only for semantics pr and sst (it is not total for st as Λ2 does not have stable extensions) and ) deterministic for semantics gr, st and sst (it is not deterministic for pr as the two preferred extensions, 1 and 2, of Λ1 are such that 1 contains ¬b while 2 contains b). Thus, b is functional for sst only. □
We use TS (resp. DS , FS ), or simply FS (resp. TS, DS) whenever is understood, to denote the problem of deciding whether a literal is total (resp. deterministic, functional).
The next proposition provides conditions under which unattacked arguments are functional. Proposition 1. For any iAF Δ = ⟨, , , ⟩ and unattacked argument ∈ ∪ , it holds that is functional i) under semantics ∈ {gr, co, pr, sst}, and ii) under semantics = st if Δ is odd-cycle free.
ministic. However, this does not hold for general iAFs under stable semantics, as there could be completions prescribing no extensions.
We conclude this section by providing the complexity of the problems of deciding whether a literal is total, deterministic, and functional for the case of general and odd-cycle free iAFs. Theorem 1. For general/odd-cycle free iAFs, the complexity results of Table 1 hold.
The odd-cycle free property guarantees that, except for the grounded and complete semantics, the complexity of checking determinism and functionality decreases by one level of the polynomial hierarchy whereas checking totality becomes trivial.
In this section we show that iAFs can be rewritten into equivalent iAFs where uncertainty is restricted to either attacks or (unattacked) arguments.
Definition 5. An iAF Δ = ⟨, , , ⟩ is said to be argument-incomplete (arg-iAF for short) if = ∅, whereas it is said to be attack-incomplete (att-iAF for short) if = ∅.
gr co st pr sst
TS (General) iAF
DS Π2-c Π2-c Π2-c Π2-c Π2-c Π2-c
FS Π2-c Π2-c Π2-c coNP-c trivial coNP-c coNP-c coNP-c coNP-c coNP-c coNP-c
odd-cycle free iAF TS trivial trivial trivial
DS trivial coNP-c coNP-c coNP-c coNP-c
FS coNP-c coNP-c coNP-c coNP-c coNP-c complexity class , -c means C-complete.
Given an iAF Δ, we denote by (Δ) the arg-iAF derived from Δ by replacing every uncertain attack (, ) with the certain attacks (, ), ( , ), ( , ), where (resp. ) is a fresh certain (resp. uncertain) argument.
Analogously, we denote by (Δ) the att-iAF derived from Δ as follows: for each uncertain argument , make certain and add an uncertain attack (, ), where is a fresh certain argument— it is sufficient to add only one fresh argument . ⟨{b, c, a, }, ∅, {(a, b), (b, a)}, {(b, c), (, a)}⟩ shown in Figure 4 (right).
Example 7. Consider the iAF Δ = ⟨{b, c}, {a}, {(a, b), (b, a)}, {(b, c)}⟩ shown in Figure 4 (left). The arg-iAF derived from Δ is Δ′ = ⟨{b, c, bc}, {a, bc}, {(a, b), (b, a), (b, bc), ( bc, bc), ( bc, c)}, ∅⟩ shown in Figure 4 (center), whereas the att-iAF derived from Δ is Δ′′ =
The transformations described above to eliminate uncertain attacks/arguments are inspired by those to eliminate attacks/arguments with probability less than 1 in probabilistic AF [22].
We now introduce a special class of arg-iAFs.
An arg-iAF Δ = ⟨, , , ∅⟩ is said to be fact-uncertain (farg-iAF) iff ∀(, ) ∈ , Definition 6. ̸∈ . of uncertain arguments.
Given an iAF Δ □ □ Observe that the iAF of Example 1 is an farg-iAF.
Given an arg-iAF Δ, (Δ) denotes the farg-iAF derived from Δ as follows: for each uncertain argument which is attacked in Δ, make certain and add the attacks (, ), (, ), where (resp. ) is a fresh certain (resp. uncertain) argument. With a little abuse of notation, for any iAF Δ we use (Δ) to denote ((Δ)).
Example 8. Considering the iAF Δ of Example 7, the derived farg-iAF (Δ) is shown in ( (Δ)), Δ(Λ′) denotes the AF Λ′′ = ⟨′′, ′′⟩ ∈ (Δ) with: = ⟨, , , ⟩, let
∈ {, , }, for any Λ′ = ⟨′, ′⟩ ∈ • ′′ = ∪ (( ∩ ′) ∖ { | (, ) ∈ ′ ∨ ̸∈ ′}), and • ′′ = (∩(′′ × ′′)) ∪ (( ∩(′′ × ′′))∖{(, ) | ( ̸∈ ′)∨( ∈ ′ ∧ ̸∈ ′)}.
Herein, the set { | (, ) ∈ ′ ∨ ̸∈ ′} is used to avoid considering arguments either () attacked by in ((Δ)) or () always false in ( (Δ)) as ̸∈ ′. Analogously, {(, ) | ( ̸∈ ′) ∨ ( ∈ ′ ∧ ̸∈ ′)} is used to avoid considering uncertain attacks that are chosen to not occur in either () ((Δ)), as ̸∈ ′, or () ( (Δ)) as ( ∈ ′ ∧ ̸∈ ′).
Example 9. Consider the iAF Δ of Example 7 and its farg-iAF (Δ) of Example 8. For Λ = ⟨ ∪ {au}, ∖ {( buc, bcc)}⟩ ∈ ( (Δ)), containing the uncertain argument au but not buc, Δ(Λ) = ⟨{a, b, c}, {(a, b), (b, a)}⟩ ∈ (Δ) that contains the uncertain argument a and does not contain the uncertain attack (b, c). □ Lemma 1. For any iAF Δ and surjective function.
∈ {, , }, Δ : ( (Δ)) → (Δ) is a
The next theorem states the ‘equivalence’ between iAFs and the iAFs derived by applying the previous mappings.
Theorem 2. Let Δ = ⟨, , , ⟩ be an iAF, ∈ {gr, co, st, pr, sst}, and ∈ {, , }. Then, (Δ) = {Δ(Λ) | Λ ∈ ( (Δ))}, and (Λ′) = { ∩ ( ∪ ) | Λ ∈ ( (Δ)) ∧ Λ′ = Δ(Λ) ∧ ∈ (Λ)} ∀Λ′ ∈ (Δ).
Thus, any iAF Δ is equivalent to an arg-iAF (resp. farg-iAF, att-iAF) Δ′ in the sense that there is mapping between the completions of (Δ) and the completions of Δ, and for any pair of AFs for which the mapping holds, the two AFs have the same (modulo arguments added in the rewriting) set of -extensions, for ∈ {gr, co, st, pr, sst}. This result entails that arg-iAFs (resp. farg-iAF, att-iAF) have the same expressivity of general iAFs, though arg-iAFs (resp. fargiAF, att-iAF) have a simpler structure. The results of Theorem 2 with those of Theorem 1 entail that the complexity results for the problems of checking totality, determinism, and functionality for iAFs in Table 1 also hold for att-iAF, arg-iAF and f-arg-iAF.
Finally, as shown next, the restricted forms of iAF allow to establish a tight connection between iAF and Probabilistic AF, and simplify the presentation as it suffices to focus on arg-iAF and an analogous form of restricted Probabilistic AF where only arguments are uncertain.
Probabilistic Argumentation Framework (PrAF) has been investigated in the recent years [18, 23, 24, 25, 26, 27, 28]. Incomplete AF is tightly connected to PrAF, as every completion of an iAF corresponds to a so-called possible world in PrAF. Here we highlight this relationship and relate acceptance problems in iAF, to probabilistic acceptance in PrAF.
W.l.o.g. we focus on PrAF where only arguments are uncertain (and attacks are certain, i.e. their probability is 1), since as shown in [22] a PrAF with probabilities on arguments and attacks can be transformed into an equivalent PrAF where only arguments may have probability lower than 1 (that is, the probability of arguments is greater than 0 and lower than or equal to 1, while that of attacks is 1). Here, an argument ∈ is viewed as a probabilistic event that is independent from events associated with other arguments ∈ (with ̸= ).
Analogously to what is said above, since any iAF is equivalent to an arg-iAF, w.l.o.g. in the following we consider arg-iAFs and denote them by triples ⟨, , ⟩ (i.e. omitting the empty set of uncertain attacks).
Observe that assigning probability equal to 0 to arguments is useless. Basically, the value assigned by to any argument represents the probability that actually occurs. Moreover, every attack (, ) occurs with conditional probability 1, that is, attacks whenever both and occur.
The meaning of a PrAF is given in terms of possible worlds. Given a PrAF ∇ = ⟨, , ⟩, a possible world of ∇ is an AF Λ = ⟨′, ′⟩ such that ′ ⊆ and ′ = ∩ (′ × ′). We use (∇) to denote the set of all possible worlds of ∇. An interpretation for a PrAF ∇ = ⟨, , ⟩ is a probability distribution function (PDF) over the set (∇) of the possible worlds. Each Λ = ⟨′, ′⟩ ∈ (∇) is assigned by probability (Λ), where: (Λ) = ∏︀ () · ∈
∏︀ ∈∖′ (1 − ()).
We now define a PrAF
Δ encoding an iAF Δ.
Definition 8 (Derived PrAF). Given an arg-iAF Δ = ⟨, , ⟩, the PrAF derived from Δ is Δ = ⟨∪, , ⟩, where : ∪ → {1/2, 1} with () = 1 for ∈ and () = 1/2 for ∈ .
It is easy to check that, given an arg-iAF Δ = ⟨, , ⟩, for every Λ ∈ (Δ), (Λ) is equal to either 0 or 2|1| . As stated next, non-zero probability possible worlds of derived PrAF Δ one-to-one correspond to completions of Δ.
Proposition 2. For any arg-iAF Δ, (Δ) = {Λ | Λ ∈ (Δ) ∧ (Λ) > 0}. Example 10. Consider the arg-iAF Δ of Example 6 (see Figure 3). The derived PrAF Δ = ⟨ ∪ , , ⟩, with () = 1 for ∈ {a, b, c} and (d) = 1/2, is shown in Figure 3 (right). There are only two possible worlds with probability greater than 0: Λ1 = ⟨, ∖ {(d, a), (d, b)}⟩ and Λ2 = ⟨ ∪ , ⟩ with (Λ1) = (Λ2) = 1/2. □
Given a PrAF, the probabilistic acceptance provides the probability that a given goal is accepted [28]. Specifically, given a PrAF ∇, a semantics , and a goal literal , the probability that is accepted can be computed by associating to every extension ∈ (Λ), with Λ ∈ (∇), a probability (, Λ, ) so that ∑︀∈ (Λ) (, Λ, ) = 1 (the sum of the probabilities of the -extensions of Λ is equal to 1). More in detail, a PrAF Δ derived from a given iAF Δ is considered, and a PDF over the set (Λ) of the extensions of each possible world Λ ∈ (Δ) is required. This means that the condition (Λ) ̸= ∅ must hold. To ensure this, in the rest of this section, if not specified otherwise, whenever we write semantics and (arg-)iAF Δ we mean that either i) ∈ {gr, co, pr, sst} and Δ is an (arg-)iAF without restrictions or ii) = st and Δ is odd-cycle free; in the latter case, the existence of an extension is guaranteed since st(Λ) = sst(Λ) = pr(Λ) ̸= ∅ for all Λ ∈ (Δ).
Definition 9 (Probabilistic Acceptance). Given an arg-iAF Δ = ⟨, , ⟩ and a literal ∈ * ∪ * , the probability Δ() that is acceptable w.r.t. semantics is: Δ() =
∑︁ Λ ∈ (Δ)∧ ∈ (Λ) ∧ ∈ (Λ) · (, Λ, ) where (· , Λ, ) is a PDF over the set (Λ).
Hereafter, we consider the uniform PDF assigning to every -extension of Λ the same probability (1/ where is the number of -extensions). Our results still hold for other PDFs over (Λ), such as that used in [28].
given semantics ) is denoted by PrA , or simply PrA whenever is understood. We recall that PrA is defined after choosing an arbitrary but fixed PDF over the set of extensions. As stated next, PrA is FP#P-hard, regardless of the chosen PDF and semantics .
Theorem 3. PrA is FP#P-hard, even for acyclic arg-iAF and for any chosen PDF.
We observe that, consistently with our intuition, the complexity of the probabilistic counterpart of the verification problem, that is computing the probability that a set of arguments is a extension for a PrAF [24], is not harder than that of PrA which focuses on acceptance.
The following propositions highlight the relations between iAFs and PrAFs (with uniform PDF over extensions).
Proposition 3. For any goal , we have that: (Δ, ) is false iff Δ () = 0; and (Δ, ) is true iff Δ () = 1.
The connection between iAF and PrAF is also investigated in [16], where the PrAF associated to an iAF assigns a probability in (0, 1) to each uncertain argument. Moreover, PCA, PSA, NCA, and NSA are related to the concept of probabilistic credulous/skeptical acceptance [29], which is different from that of probabilistic acceptance of Definition 9. Indeed, the probability that an argument is credulously (resp. skeptically) accepted is the sum of the probabilities of the possible worlds where is credulously (resp. skeptically) accepted, according to a given semantics . Hence, the probability of a world Λ is added to the summation iff belongs to at least one (resp. every) -extension of Λ. In contrast, with the aim of offering a more granular approach, Definition 9 uses the probabilities assigned to -extensions by the PDF (· , Λ, ). For instance, taking the PrAF Δ of Example 10 (see Figure 3), under the complete semantics the as b belongs to one of three extensions of one of the two worlds (see Example 11 below). probabilistic skeptical (resp. credulous) acceptance of b is 0 (resp. 1/2), while cΔo (b) = 1/6 Although the conditions of Proposition 3 are similar to those identified in [ 16], they refer to different notions of probabilistic acceptance. In fact, while probabilistic skeptical and credulous acceptance define an interval, Definition 9 provides a precise value in that interval.
The next proposition considers acyclic arg-iAFs, a subclass of odd-cycle free iAFs. Proposition 4. Let Δ = ⟨, , ⟩ be an acyclic arg-iAF and a goal. It holds that: ∙ (Δ, ) ≡ (Δ, ) and (Δ, ) ≡ (Δ, ); ∙ (Δ, ) is true iff
Δ () ≥ ∙ (Δ, ) is false iff Δ () ≤ 2|1| ; 1
− 2|1| .
Our last result relates the satisfaction of properties (e.g. totality) to probabilistic acceptance. (Δ), ∑︀ (, Λ, ) = 1, where either: Theorem 4. A goal is total iff Δ() + Δ(¬) = 1; and deterministic iff ∀Λ ∈ () = ∈ (Λ) ∧ ∈ () = ∈ (Λ) ∧ ¬ ∈ () = ∈ (Λ) ∧ ( ̸∈ ∧ ¬ ̸∈ ).
or
or Example 11. Consider again the iAF of Example 6. Assuming a uniform distribution for the probabilities of extensions, the probabilistic acceptance of literals is as reported in the following table, where a grey cell means that the literal of the cell’s column is total, under the semantics of the cell’s row.
gr co st pr sst a 0 0 0 1/6 1/4 ¬a 1/2 2/3 1/2 3/4 1 b 0 1/6 1/2 1/4 1/2 ¬b 1/2 2/3 0 3/4 1/2 c 0 0 0 0 0 ¬c 0 1/6 1/2 1/4 1/2 d 1/2 1/2 0 1/2 1/2 ¬d 1/2 1/2 1/2 1/2 1/2 □
We have presented the totality, determinism and functionality properties for iAFs, and provided
complexity bounds for the problems of checking whether these properties hold under vfie
wellknown argumentation semantics [
As future work we plan to consider other notions of acceptance that, as totality, determinism,
and functionality, require the existence of an extension (e.g. skeptical acceptance under stable
semantics requiring non-emptyness [38]). We envisage that SAT-based approaches for computing
credulous and skeptical acceptance [39] could be used to define algorithms for checking
functionality, totality and determinism since these properties can be defined in terms of credulous and
skeptical acceptance for AFs. More elaborated solutions need to be investigated for iAF.
Considering the connections between iAFs and Control AFs [40, 41, 42, 43], we plan to investigate
totality, determinism, and functionality also in that context. Finally, it would be interesting to
consider the concepts of totality, determinism, and functionality in the presence of some kinds of
preferences, such as those in [
International Conference on Agreement Technologies, 2012, pp. 138–152. [24] B. Fazzinga, S. Flesca, F. Parisi, On the complexity of probabilistic abstract argumentation frameworks, ACM Transactions on Computational Logic 16 (2015) 22:1–22:39. [25] B. Fazzinga, S. Flesca, F. Furfaro, Complexity of fundamental problems in probabilistic abstract argumentation: Beyond independence, Artificial Intelligence 268 (2019) 1–29. [26] B. Fazzinga, S. Flesca, F. Furfaro, Abstract argumentation frameworks with marginal probabilities, in: Proc. of IJCAI, 2022, pp. 2613–2619. [27] B. Fazzinga, S. Flesca, F. Furfaro, Probabilistic bipolar abstract argumentation frameworks: complexity results, in: Proc. of IJCAI, 2018, pp. 1803–1809. [28] G. Alfano, M. Calautti, S. Greco, F. Parisi, I. Trubitsyna, Explainable acceptance in probabilistic abstract argumentation: Complexity and approximation, in: Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR), 2020, pp. 33–43. [29] B. Fazzinga, S. Flesca, F. Furfaro, Credulous and skeptical acceptability in probabilistic abstract argumentation: complexity results, Intelligenza Artificiale 12 (2018) 181–191. [30] W. Dvorák, M. Järvisalo, J. P. Wallner, S. Woltran, Complexity-sensitive decision procedures for abstract argumentation, Artificial Intelligence 206 (2014) 53–78. [31] M. Kröll, R. Pichler, S. Woltran, On the complexity of enumerating the extensions of abstract argumentation frameworks, in: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), 2017, pp. 1145–1152. [32] G. Alfano, S. Greco, F. Parisi, On scaling the enumeration of the preferred extensions of abstract argumentation frameworks, in: Proceedings of ACM/SIGAPP Symposium on Applied Computing (SAC), 2019, pp. 1147–1153. [33] G. Alfano, A. Cohen, S. Gottifredi, S. Greco, F. Parisi, G. R. Simari, Dynamics in abstract argumentation frameworks with recursive attack and support relations, in: Proceedings of the 24th European Conference on Artificial Intelligence (ECAI), 2020, pp. 577–584. [34] G. Alfano, S. Greco, Incremental skeptical preferred acceptance in dynamic argumentation frameworks, IEEE Intelligent Systems 36 (2021) 6–12. [35] G. Alfano, S. Greco, F. Parisi, G. I. Simari, G. R. Simari, Incremental computation of warranted arguments in dynamic defeasible argumentation: the rule addition case, in: Proceedings of the 33rd Annual ACM Symposium on Applied Computing, (SAC), 2018, pp. 911–917. [36] G. Alfano, S. Greco, F. Parisi, Incremental computation in dynamic argumentation frameworks, IEEE Intell. Syst. 36 (2021) 80–86. [37] G. Alfano, S. Greco, F. Parisi, G. I. Simari, G. R. Simari, Incremental computation for structured argumentation over dynamic DeLP knowledge bases, Artificial Intelligence 300 (2021) 103553. [38] P. E. Dunne, M. Wooldridge, Complexity of abstract argumentation, in: Argumentation in
Artificial Intelligence, Springer, 2009, pp. 85–104. [39] M. Järvisalo, SAT for argumentation, in: Proceedings of the International Workshop on
Systems and Algorithms for Formal Argumentation (SAFA), volume 2171, 2018, pp. 1–3. [40] D. Neugebauer, J. Rothe, K. Skiba, Complexity of nonemptiness in control argumentation frameworks, in: Proc. of ECSQARU, 2021, pp. 117–129. [41] F. Gaignier, Y. Dimopoulos, J. Mailly, P. Moraitis, Probabilistic control argumentation frameworks, in: Proc. of AAMAS, 2021, pp. 519–527. [42] Y. Dimopoulos, J. Mailly, P. Moraitis, Control argumentation frameworks, in: Proceedings of the AAAI Conference on Artificial Intelligence, 2018, pp. 4678–4685. [43] A. Niskanen, D. Neugebauer, M. Järvisalo, Controllability of control argumentation frameworks, in: Proc. of IJCAI, 2020, pp. 1855–1861. [44] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)cp-nets:
Pareto and majority voting, Artif. Intell. 272 (2019) 101–142. [45] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)cp-nets: Max and rank voting, Artif. Intell. 303 (2022) 103636.