Probabilistic abstract argumentation combines Dung’s abstract argumentation framework with probability theory in order to model uncertainty in argumentation. In this setting, we address the fundamental problem of computing the probability that an argument is credulously or skeptically acceptable according to a given semantics. Specifically, we focus on the most popular semantics (i.e., admissible, stable, semi-stable, complete, grounded, preferred, ideal, ideal-set), and show that computing the probability that an argument is credulously or skeptically accepted is FP# P-complete independently from the adopted semantics, in the cases when computing it is not trivial (i.e., when skeptical acceptance is assumed under the admissible and ideal-set semantics).
BaroniP., CaminadaM. and GiacominM., An introduction to argumentation semantics, Knowledge Eng Review26(4) (2011), 365–410.
2.
BaroniP. and GiacominM., Semantics of abstract argument systems, In pp, Argumentation in Artificial Intelligence (2009), 25–44.
3.
BoothR., CaminadaM., DunneP.E., PodlaszewskiM. and RahwanI., Complexity properties of critical sets of arguments, In Proc of Computational Models of Argument (COMMA), 2014, pp. 173–184.
4.
CaminadaM., Semi-stable semantics, In Proc Int Conf Computational Models of Argument (COMMA), 2006, pp. 121–130.
5.
CookS.A., The complexity of theorem-proving procedures, In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, Shaker Heights, Ohio, USA, 1971, pp. 151–158.
6.
Coste-MarquisS., DevredC. and MarquisP., Symmetric argumentation frameworks, In Proc of Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU) (2005), 317–328.
7.
DimopoulosY. and TorresA., Graph theoretical structures in logic programs and default theories, Theor Comput Sci170(1-2) (1996), 209–244.
8.
DoderD. and WoltranS., Probabilistic argumentation frameworks - A logical approach, In Proc Int Conf on Scalable Uncertainty Management (SUM), 2014, pp. 134–147.
9.
DondioP., Computing the grounded semantics in all the subgraphs of an argumentation framework: An empirical evaluation, In Proc Int Workshop Computational Logic in Multi-Agent Systems (CLIMA), 2013, pp. 119–137.
10.
DondioP., Toward a computational analysis of probabilistic argumentation frameworks, Cybernetics and Systems45(3) (2014), 254–278.
11.
MinhD.P., On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artif Intell77(2) (1995), 321–358.
DungP.M. and ThangP.M., Towards (probabilistic) argumentation for jury-based dispute resolution, In Proc Int Conf Computational Models of Argument (COMMA), 2010, pp. 171–182.
14.
DunneP.E., The computational complexity of ideal semantics, Artif Intell173(18) (2009).
15.
DunneP.E. and Bench-CaponT.J.M., Coherence in finite argument systems, Artif Intell141(1/2) (2002), 187–203.
16.
DunneP.E. and CaminadaM., Computational complexity of semi-stable semantics in abstract argumentation frameworks, In Proc European Conf on Logics in Artificial Intelligence (JELIA), 2008, pp. 153–165.
17.
DunneP.E. and WooldridgeM., Complexity of abstract argumentation, In Argumentation in Artificial Intelligence, 2009, pp. 85–104.
18.
DvorákW. and WoltranS., Complexity of semistable and stage semantics in argumentation frameworks, Inf Process Lett110(11) (2010), 425–430.
19.
FazzingaB., FlescaS. and ParisiF., On the complexity of probabilistic abstract argumentation frameworks, ACM Trans Comput Log (TOCL)16(3) (2015), 22.
20.
FazzingaB., FlescaS. and ParisiF., On efficiently estimating the probability of extensions in abstract argumentation frameworks, Int J Approx Reasoning69 (2016), 106–132.
21.
FazzingaB., FlescaS., ParisiF. and PietramalaA., PARTY: A mobile system for efficiently assessing the probability of extensions in a debate, In Proc Int Conf on Database and Expert Systems Applications (DEXA), 2015, pp. 220–235.
22.
FazzingaB., FlescaS., ParisiF. and PietramalaA., Computing or estimating extension’s probabilities over structured probabilistic argumentation frameworks, Special Issue on Probabilistic and other Quantitative Approaches to Computational Argumentation of the IfCoLog Journal of Logics and their Applications3(2) (2016), 177–200.
23.
GagglS.A. and WoltranS., The cf2 argumentation semantics revisited, J Log Comput23(5) (2013), 925–949.
24.
HunterA., Some foundations for probabilistic abstract argumentation, In Proc Int Conf Computational Models of Argument (COMMA), 2012, pp. 117–128.
25.
HunterA., A probabilistic approach to modelling uncertain logical arguments, Int J Approx Reasoning54(1) (2013), 47–81.
26.
HunterA., Probabilistic qualification of attack in abstract argumentation, Int J Approx Reasoning55(2) (2014), 607–638.
27.
HunterA. and ThimmM., Probabilistic argumentation with epistemic extensions, In Proc Int Workshop on Defeasible and Ampliative Reasoning (DARe@ECAI), 2014.
28.
HunterA. and ThimmM., Probabilistic argumentation with incomplete information, In Proc European Conf. on Artificial Intelligence (ECAI), 2014, pp. 1033–1034.
29.
LiH., OrenN. and NormanT.J., Probabilistic argumentation frameworks, In Proc Int Workshop on Theorie and Applications of Formal Argumentation (TAFA), 2011.
30.
PrakkenH., An abstract framework for argumentation with structured arguments, Argument & Computation1(2) (2010), 93–124.
31.
RienstraT., Towards a probabilistic dung-style argumentation system, In AT, 2012, pp. 138–152.
32.
ThimmM., A probabilistic semantics for abstract argumentation, In Proc European Conf on Artificial Intelligence (ECAI), 2012, pp. 750–755.
33.
ValiantL.G., The complexity of computing the permanent, Theor Comput Sci (TCS)8 (1979), 189–201.
