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.