In the context of probabilistic AAFs, we introduce AAFs with marginal probabilities (mAAFs) requiring only marginal probabilities of arguments/attacks to be specified and not relying on the independence assumption. Differently from the literature, reasoning over mAAFs 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 maximum and minimum probabilities of extensions over mAAFs under Dungeon semantics and characterize their complexity.
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 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 on the left, reporting the marginal probabilities of arguments and attacks. 0.6 a 1 0.4 c 1 0.6 b The numbers besides nodes and edges are the marginal probabilities returned by a function (· ) possible world 1 = ⟨∅, ∅⟩ 2 = ⟨{}, ∅⟩ 3 = ⟨{}, ∅⟩ 4 = ⟨{}, ∅⟩ 5 = ⟨{, }, ∅⟩ 6 = ⟨{, }, {(, )}⟩ 7 = ⟨{, }, {(, )}⟩ 8 = ⟨{, , }, {(, ), (, )}⟩
1 0.096 0.144 0.144 0.064 0.216 0.096 0.096 0.144 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 above. 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 the product of the marginal probabilities (resp., complements of marginal probabilities) of the arguments/attacks in (resp., not in ). As for 3, it corresponds to the case where , are positively correlated and are in mutual exclusion with (so that the only possible scenarios for the argumentation are 4 and 5), while 2 to the case where either , , coexist, or at most one between or 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 (), (), 1 − ()).
Let = {, }. The only where 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 () that is admissible is the probability of 5. Therefore, from what said above on the minimum and maximum probability of 5, we conclude that () is in the range [ 2(5).. 3(5)] = [0..0.6].
Now, suppose that the analyst is a lawyer, and that , are arguments possibly claimed by the counterpart’s witnesses. If the lawyer trusted the analysis under independence, they would conclude that {,} is not a robust set of arguments, since () = 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 () can be rather high, as () may be up to 3(5) = 0.6, thus they can make more cautious decisions regarding the trial strategy.
Contributions. We formally define mAAFs and introduce the problems of maximizing and minimizing the probability that a set is an extension over an mAAF. We then focus on MAXP-VER and MINP-VER, the decision counterparts of the maximization and minimization problems, and provide a thorough complexity analysis under the Dungean semantics for extensions. 2. mAAFs: abstract argumentation frameworks with marginal probabilities We assume that the reader is familiar with the fundamental notions regarding abstract argumentation frameworks (AAFs). We will denote an AAF as a pair = ⟨, ⟩, where is the set of arguments and the attack relation, and use the following shorthands for the Dungean semantics: cf for conflict-free, ad for admissible, st for stable, co for complete, gr for grounded, and pr for preferred. The set of extensions of an AAF under a semantics is denoted as Ext(, ).
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 is 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. This yields the definition below.
Definition 1 (mAAF). An AAF with marginal probabilities (mAAF) is a tuple ⟨, , ⟩, where
⟨, ⟩ is an AAF and : ( ∪ ) → [
Formally, given an mAAF = ⟨, , ⟩, a possible world of is any AAF = ⟨′, ′⟩
with ′ ⊆ , ′ ⊆ (′ × ′) ∩ . We denote as ( ) the set of the possible worlds
of . Given two possible worlds = ⟨, ⟩, ′ = ⟨′, ′⟩, we say that ′ expands if
( ∪ ) ⊂ (′ ∪ ′). Differently from the probabilistic extensions of AAFs in the literature
(in particular, for the constellations approaches [
Given a pdf over ( ) and a set of possible worlds ′ ⊆ ( ), ( ′) = ∑︀∈ ′ () denotes the overall probability assigned by to the possible worlds in ′. Then, we say that is consistent with the marginal probability of argument (resp., attack ∑︀)∈,writ(te)n| a∈s (|=)/ (∑︀)(∈resp(.,)||=∈∧(∈)()if)).I(n)tu=rn∑, ︀i∈scon(si)s|te∈nt w(ith) (re(sp|=., () ifi)t =is consistent with the marginal probabilities of ’s arguments/attacks. We denote as Π( ) the set of pdfs over ( ) consistent with .
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 ( ) may be consistent with ), naturally call for revisiting the traditional way of considering extensions. In this spirit, given a pdf in Π( ) and a semantics , we define the probability that is a -extension of according to as: (, , ) = ∑︀|∈Ext(, ) (), that is the sum of the probabilities assigned by to the possible worlds where 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: min(, , ) = min ∈Π( ) (, , ) and max(, , ) = max ∈Π( ) (, , ), i.e. the minimum and maximum probabilities that is a -extension.
Reasoning over min(, , ) and max(, , ) is obviously relevant for an analyst looking into an argumentation modeled via an mAAF , since this gives insights on the extent to which can be considered “robust". Thus, we address the decision problems MAXP-VER and MINP-VER, that are the decision counterparts of finding max(, , ) and min(, , ): Problem statement: MAXP-VER and MINP-VER: “Let be an mAAF , a semantics, a set of arguments, and * a probability value. MAXP-VER(, , , * ) (resp., MINP-VER(, , , * )) asks if there is a pdf in Π( ) such that (, , ) ≥ * (resp., (, , ) ≤ * )".
The main contribution of this paper is summarized by the following theorem: Theorem 1. Given an mAAF = ⟨, , ⟩ and ⊆ , MAXP-VER(, , , * ) is: 1) in under ∈ {cf, st, ad}; 2) -complete under ∈ {co, gr}; 3) Σ 2-complete under = pr. MINP-VER(, , , * ) is: 1)in under = cf, 2) -complete under = pr; 3)in under ∈ {ad, st, co, gr}.
It is interesting to analyze Theorem 1 in the light of the results in the literature regarding IND
(i.e. probabilistic AAFs under the independence assumption, mentioned in the introduction) and
iAAFs [
Independently from inspiring a comparison with IND and iAAFs, Theorem 1 states that,
analogously to several other computational approaches in formal argumentation, the problems
defined over mAAFs generally suffer from a high computational complexity [