=Paper=
{{Paper
|id=Vol-3354/short1
|storemode=property
|title=Probabilistic AAFs with Marginal Probabilities
|pdfUrl=https://ceur-ws.org/Vol-3354/short1.pdf
|volume=Vol-3354
|authors=Bettina Fazzinga,Sergio Flesca,Filippo Furfaro
|dblpUrl=https://dblp.org/rec/conf/aiia/FazzingaFF22
}}
==Probabilistic AAFs with Marginal Probabilities==
<pdf width="1500px">https://ceur-ws.org/Vol-3354/short1.pdf</pdf>
<pre>
Probabilistic AAFs with marginal probabilities
Bettina Fazzinga1 , Sergio Flesca2 and Filippo Furfaro2
1
    DICES - University of Calabria, Italy
2
    DIMES - University of Calabria, Italy


                                         Abstract
                                         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.




1. Introduction
Several frameworks based on the probability theory have extended Dung’s Abstract Argumentation
Framework (AAF [2]) to take into account the uncertainty possibly affecting the occurrence
of arguments and attacks in the argumentation. In particular, in the constellations approach
[3, 4, 5, 6, 7, 8, 9, 10] 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

6th Workshop on Advances in Argumentation in Artificial Intelligence (AI3 2022)
This is an extended abstract of [1]
" bettina.fazzinga@unical.it (B. Fazzinga); flesca@dimes.unical.it (S. Flesca); furfaro@dimes.unical.it (F. Furfaro)
 0000-0001-8611-2377 (B. Fazzinga); 0000-0002-4164-940X (S. Flesca); 0000-0001-5145-1301 (F. Furfaro)
                                       © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073       CEUR Workshop Proceedings (CEUR-WS.org)
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 proba-
bilities of arguments and attacks.
                                    possible world                       𝜋1     𝜋2 𝜋3
                                    𝜔1 = ⟨∅, ∅⟩                        0.096 0.2      0
  0.6           0.4           0.6   𝜔2 = ⟨{𝑎}, ∅⟩                      0.144 0.2      0
   a             c             b    𝜔3 = ⟨{𝑏}, ∅⟩                      0.144 0.2      0
          1             1           𝜔4 = ⟨{𝑐}, ∅⟩                      0.064    0    0.4
The numbers besides nodes and       𝜔5 = ⟨{𝑎, 𝑏}, ∅⟩                   0.216    0    0.6
edges are the marginal probabili-
ties returned by a function 𝑃 (·)
                                    𝜔 6 = ⟨{𝑎, 𝑐}, {(𝑐, 𝑎)}⟩           0.096    0     0
                                    𝜔7 = ⟨{𝑏, 𝑐}, {(𝑐, 𝑏)}⟩            0.096    0     0
                                    𝜔8 = ⟨{𝑎, 𝑏, 𝑐}, {(𝑐, 𝑎), (𝑐, 𝑏)}⟩ 0.144 0.4      0
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 MAX P-V ER
and MIN P-V ER, 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 argumenta-
tion 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 𝑃 : (𝐴 ∪ 𝐷) → [0, 1] associates arguments and attacks with probabilities.
Arguments and attacks are said to be certain if they have probability 1, uncertain otherwise.

   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 [3, 4, 5, 6, 7, 8, 9, 11], mAAFs do not rely on
a unique probability distribution function (pdf) over the possible worlds: different pdfs may be
consistent with the marginal probabilities, 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 𝑎): no consistent pdf can assign
to 𝜔2 a value higher than any of 𝑃 (𝑎), 1 − 𝑃 (𝑏), 1 − 𝑃 (𝑐).
                                                                  ′                    ′
∑︀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
𝛿𝑎𝑏 ), written as 𝜋 |= 𝑃 (𝑎)
∑︀                       ∑︀ (resp., 𝜋 |= 𝑃 (𝛿𝑎𝑏 )) if 𝑃 (𝑎) = 𝜔∈𝑃 𝑊 (𝐹 )|𝑎∈𝜔 𝜋(𝜔) (resp., 𝑃 (𝛿𝑎𝑏 ) =
   𝜔∈𝑃 𝑊 (𝐹 )|𝛿∈𝜔 𝜋(𝜔)/    𝜔∈𝑃 𝑊 (𝐹 )|𝑎∈𝜔∧𝑏∈𝜔 𝜋(𝜔)). In turn, 𝜋 is consistent with 𝑃 (𝜋 |= 𝑃 ) if it 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 MAX P-V ER and MIN P-V ER,
that are the decision counterparts of finding 𝑃max (𝐹, 𝑆, 𝜎) and 𝑃min (𝐹, 𝑆, 𝜎):
Problem statement: MAX P-V ER and MIN P-V ER: “Let 𝐹 be an mAAF 𝐹 , 𝜎 a semantics, 𝑆 a set
of arguments, and 𝑝* a probability value. MAX P-V ER(𝐹, 𝑆, 𝜎, 𝑝* ) (resp., MIN P-V ER(𝐹, 𝑆, 𝜎, 𝑝* ))
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 𝑆 ⊆ 𝐴, MAX P-V ER(𝐹, 𝑆, 𝜎, 𝑝* ) is: 1) in 𝑃
under 𝜎 ∈ {cf, st, ad}; 2) 𝑁𝑃 -complete under 𝜎 ∈ {co, gr}; 3) Σ𝑝2 -complete under 𝜎 = pr.
MIN P-V ER (𝐹, 𝑆, 𝜎, 𝑝* ) is: 1)in 𝑃 under 𝜎 = cf, 2) 𝑁𝑃 -complete under 𝜎 = pr; 3)in 𝑁𝑃 under
𝜎 ∈ {ad, st, co, gr}.


3. Discussions and conclusions
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 [12] (i.e. incomplete AAFs, which are AAFs where some arguments and attacks are
marked as uncertain, without specifying any probability). If we focus on MAX P-V ER, 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 𝑃 and Σ𝑝2 -complete, respectively, while, under 𝜎 ∈
{co, gr}, reasoning over iAAFs is strictly simpler than over mAAFs (as INC V ER is in 𝑃 [12]
while MAX P-V ER is 𝑁𝑃 -complete). Overall, for both MAX P-V ER and MIN P-V ER, mAAFs are
between iAAFs and IND (where the computation of the probabilities of extensions is generally
FP#𝑃 -complete): 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).
   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 [13, 14, 15, 16, 17,
18, 19]. In future work, we plan to investigate islands of tractability, and to extend mAAFs with
the specification of correlations among arguments/attacks, as done for iAAFs [20, 21]. This would
exclude pdfs assigning non-zero probability to unrealistic possible worlds from the reasoning.


References
 [1] B. Fazzinga, S. Flesca, F. Furfaro, Abstract argumentation frameworks with marginal
     probabilities, in: Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI), 2022, pp. 2613–
     2619.
 [2] P. M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic
     reasoning, logic programming and n-person games, Artif. Intell. 77 (1995) 321–358.
 [3] A. Hunter, Some foundations for probabilistic abstract argumentation, in: Proc. Computa-
     tional Models of Argument (COMMA), 2012, pp. 117–128.
 [4] A. Hunter, Probabilistic qualification of attack in abstract argumentation, Int. J. Approx.
     Reasoning 55 (2014) 607–638.
 [5] P. Dondio, Toward a computational analysis of probabilistic argumentation frameworks,
     Cybernetics and Systems 45 (2014) 254–278.
 [6] D. Doder, S. Woltran, Probabilistic argumentation frameworks - A logical approach, in:
     Proc. Conf. Scalable Uncertainty Management (SUM), 2014, pp. 134–147.
 [7] T. Rienstra, Towards a probabilistic dung-style argumentation system, in: Proc. Int. Conf.
     on Agreement Technologies (AT), 2012, pp. 138–152.
 [8] P. M. Dung, P. M. Thang, Towards (probabilistic) argumentation for jury-based dispute
     resolution, in: Proc. Computational Models of Argument (COMMA), 2010, pp. 171–182.
 [9] H. Li, N. Oren, T. J. Norman, Probabilistic argumentation frameworks, in: Proc. Int.
     Workshop on Theory and Applications of Formal Argumentation (TAFA), 2011, pp. 1–16.
[10] B. Fazzinga, S. Flesca, F. Furfaro, Complexity of fundamental problems in probabilistic
     abstract argumentation: Beyond independence, Artif. Intell. 268 (2019) 1–29.
[11] B. Fazzinga, S. Flesca, F. Parisi, On the complexity of probabilistic abstract argumentation
     frameworks, ACM Trans. Comput. Log. 16 (2015) 22:1–22:39.
[12] B. Fazzinga, S. Flesca, F. Furfaro, Revisiting the notion of extension over incomplete
     abstract argumentation frameworks, in: Proc. Joint Conf. on Artificial Intelligence (IJCAI),
     2020, pp. 1712–1718.
[13] P. E. Dunne, M. Wooldridge, Complexity of abstract argumentation, in: Argumentation in
     Artificial Intelligence, 2009, pp. 85–104.
[14] W. Dvorák, S. Woltran, Complexity of semi-stable and stage semantics in argumentation
     frameworks, Inf. Process. Lett. 110 (2010) 425–430.
[15] 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.
[16] G. Alfano, A. Cohen, S. Gottifredi, S. Greco, F. Parisi, G. Simari, Dynamics in abstract
     argumentation frameworks with recursive attack and support relations, in: Proceedings of
     European Conference on Artificial Intelligence (ECAI), 2020, pp. 577–584.
[17] G. Alfano, S. Greco, F. Parisi, G. I. Simari, G. R. Simari, Incremental computation for
     structured argumentation over dynamic delp knowledge bases, Artif. Intell. 300 (2021)
     103553.
[18] G. Alfano, S. Greco, Incremental skeptical preferred acceptance in dynamic argumentation
     frameworks, IEEE Intell. Syst. 36 (2021) 6–12.
[19] G. Alfano, S. Greco, F. Parisi, Incremental computation in dynamic argumentation frame-
     works, IEEE Intell. Syst. 36 (2021) 80–86.
[20] B. Fazzinga, S. Flesca, F. Furfaro, Reasoning over argument-incomplete aafs in the presence
     of correlations, in: Proc. Joint Conf. on Artificial Intelligence (IJCAI), 2021.
[21] J. Mailly, Constrained incomplete argumentation frameworks, in: Proc. of European Conf.
     on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU,
     2021, pp. 103–116.

</pre>