Bettina Fazzinga
Skip Abstract Section
Abstract
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 a set of arguments is an extension according to a given semantics. We focus on the most popular semantics (i.e., admissible, stable, complete, grounded, preferred, ideal-set, ideal, stage, and semistable) and show the following dichotomy result: computing the probability that a set of arguments is an extension is either FP or FP#P-complete depending on the semantics adopted. Our polynomial-time results are particularly interesting, as they hold for some semantics for which no polynomial-time technique was known so far.
- Teresa Alsinet, Carlos Iván Chesñevar, Lluis Godo, Sandra Sandri, and Guillermo Ricardo Simari. 2008a. Formalizing argumentative reasoning in a possibilistic logic programming setting with fuzzy unification. Int. J. Approx. Reasoning 48, 3 (2008), 711--729. Google Scholar
Digital Library
- Teresa Alsinet, Carlos Iván Chesñevar, Lluis Godo, and Guillermo Ricardo Simari. 2008b. A logic programming framework for possibilistic argumentation: Formalization and logical properties. Fuzzy Sets Syst. 159, 10 (2008), 1208--1228. Google ScholarDigital Library
- Leila Amgoud and Claudette Cayrol. 2002. A reasoning model based on the production of acceptable arguments. Ann. Math. Artif. Intell. 34, 1--3 (2002), 197--215. Google ScholarDigital Library
- Leila Amgoud and Henri Prade. 2004. Reaching agreement through argumentation: A possibilistic approach. In Principles of Knowledge Representation and Reasoning (KR). 175--182.Google Scholar
- Leila Amgoud and Srdjan Vesic. 2011. A new approach for preference-based argumentation frameworks. Ann. Math. Artif. Intell. 63, 2 (2011), 149--183. Google ScholarDigital Library
- Pietro Baroni, Martin Caminada, and Massimiliano Giacomin. 2011. An introduction to argumentation semantics. Knowl. Eng. Rev. 26, 4 (2011), 365--410. Google ScholarDigital Library
- Pietro Baroni and Massimiliano Giacomin. 2009. Semantics of abstract argument systems. In Argumentation in Artificial Intelligence. 25--44.Google Scholar
- Pietro Baroni, Massimiliano Giacomin, and Giovanni Guida. 2005. SCC-recursiveness: A general schema for argumentation semantics. Artif. Intell. 168, 1--2 (2005), 162--210. Google ScholarDigital Library
- Trevor J. M. Bench-Capon. 2003. Persuasion in practical argument using value-based argumentation frameworks. J. Log. Comput. 13, 3 (2003), 429--448.Google ScholarCross Ref
- Trevor J. M. Bench-Capon and Paul E. Dunne. 2007. Argumentation in artificial intelligence. Artif. Intell. 171, 10--15 (2007), 619--641. Google ScholarDigital Library
- Philippe Besnard and Anthony Hunter (Eds.). 2008. Elements of Argumentation. MIT Press. Google ScholarDigital Library
- Martin Caminada. 2006. Semi-stable semantics. In Computational Models of Argument (COMMA). 121--130. Google ScholarDigital Library
- Martin W. A. Caminada, Walter Alexandre Carnielli, and Paul E. Dunne. 2012. Semi-stable semantics. J. Log. Comput. 22, 5 (2012), 1207--1254. Google ScholarDigital Library
- Sylvie Coste-Marquis, Caroline Devred, and Pierre Marquis. 2005. Prudent semantics for argumentation frameworks. In International Conference on Tools with Artificial Intelligence (ICTAI). 568--572. Google ScholarDigital Library
- Sylvie Coste-Marquis, Sébastien Konieczny, Pierre Marquis, and Mohand Akli Ouali. 2012. Weighted attacks in argumentation frameworks. In Principles of Knowledge Representation and Reasoning (KR). 593--597.Google Scholar
- P. M. Dung, R. A. Kowalski, and F. Toni. 2009. Assumption-based argumentation. In Argumentation in Artificial Intelligence. 199--218.Google Scholar
- Phan Minh Dung. 1995. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell. 77, 2 (1995), 321--358. Google ScholarDigital Library
- Phan Minh Dung, Paolo Mancarella, and Francesca Toni. 2007. Computing ideal sceptical argumentation. Artif. Intell. 171, 10--15 (2007), 642--674. Google ScholarDigital Library
- Phan Minh Dung and Phan Minh Thang. 2010. Towards (probabilistic) argumentation for jury-based dispute resolution. In Computational Models of Argument (COMMA). 171--182. Google ScholarDigital Library
- Paul E. Dunne. 2009. The computational complexity of ideal semantics. Artif. Intell. 173, 18 (2009), 1559--1591. Google ScholarDigital Library
- Paul E. Dunne, Anthony Hunter, Peter McBurney, Simon Parsons, and Michael Wooldridge. 2011. Weighted argument systems: Basic definitions, algorithms, and complexity results. Artif. Intell. 175, 2 (2011), 457--486. Google ScholarDigital Library
- Paul E. Dunne and Michael Wooldridge. 2009. Complexity of abstract argumentation. In Argumentation in Artificial Intelligence. 85--104.Google Scholar
- Wolfgang Dvorák. 2012. Computational Aspects of Abstract Argumentation. Ph.D. Dissertation. Technische Universität Wien.Google Scholar
- Wolfgang Dvorák, Matti Järvisalo, Johannes Peter Wallner, and Stefan Woltran. 2014. Complexity-sensitive decision procedures for abstract argumentation. Artif. Intell. 206 (2014), 53--78. Google ScholarDigital Library
- Wolfgang Dvorák and Stefan Woltran. 2010. Complexity of semi-stable and stage semantics in argumentation frameworks. Inf. Process. Lett. 110, 11 (2010), 425--430. Google ScholarDigital Library
- Thomas Eiter and Georg Gottlob. 1997. The complexity class Θp2 : Recent results and applications in AI and modal logic. In Fundamentals of Computation Theory, Bogdan S. Chlebus and Ludwik Czaja (Eds.). Lecture Notes in Computer Science, Vol. 1279. Springer, Berlin, 1--18. Google ScholarDigital Library
- Bettina Fazzinga, Sergio Flesca, and Francesco Parisi. 2013a. Efficiently estimating the probability of extensions in abstract argumentation. In International Conference on Scalable Uncertainty Management (SUM). 106--119.Google ScholarCross Ref
- Bettina Fazzinga, Sergio Flesca, and Francesco Parisi. 2013b. On the complexity of probabilistic abstract argumentation. In International Joint Conference on Artificial Intelligence (IJCAI). 898--904. Google ScholarDigital Library
- A. Ferrara, G. Pan, and M. Y. Vardi. 2005. Treewidth in verification: Local vs. global. In International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR). 489--503. Google ScholarDigital Library
- Sergio Flesca, Filippo Furfaro, and Francesco Parisi. 2014. Consistency checking and querying in probabilistic databases under integrity constraints. J. Comput. Syst. Sci. 80, 7 (2014), 1448--1489.Google ScholarCross Ref
- Sarah Alice Gaggl and Stefan Woltran. 2013. The cf2 argumentation semantics revisited. J. Log. Comput. 23, 5 (2013), 925--949.Google ScholarCross Ref
- Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. Google ScholarDigital Library
- Davide Grossi and Wiebe van der Hoek. 2013. Audience-based uncertainty in abstract argument games. In International Joint Conference on Artificial Intelligence (IJCAI). 143--149. Google ScholarDigital Library
- R. Haenni, B. Anrig, J. Kohlas, and N. Lehmann. 2001. A survey on probabilistic argumentation. In ECSQARU Workshop: Adventures in Argumentation. 19--25.Google Scholar
- R. Haenni, J. Kohlas, and N. Lehmann. 2000. Probabilistic argumentation systems. In Handbook of Defeasible Reasoning and Uncertainty Management Systems, Volume 5: Algorithms for Uncertainty and Defeasible Reasoning. Kluwer, 221--288.Google Scholar
- Anthony Hunter. 2012. Some foundations for probabilistic abstract argumentation. In Computational Models of Argument (COMMA). 117--128.Google Scholar
- Anthony Hunter. 2013a. Modelling uncertainty in persuasion. In International Conference on the Scalable Uncertainty Management (SUM). 57--70.Google ScholarCross Ref
- Anthony Hunter. 2013b. A probabilistic approach to modelling uncertain logical arguments. Int. J. Approx. Reasoning 54, 1 (2013), 47--81. Google ScholarDigital Library
- Anthony Hunter. 2014. Probabilistic qualification of attack in abstract argumentation. Int. J. Approx. Reasoning 55, 2 (2014), 607--638. Google ScholarDigital Library
- Abhay Kumar Jha and Dan Suciu. 2013. Knowledge compilation meets database theory: Compiling queries to decision diagrams. Theory Comput. Syst. 52, 3 (2013), 403--440. Google ScholarDigital Library
- Eun Jung Kim, Sebastian Ordyniak, and Stefan Szeider. 2011. Algorithms and complexity results for persuasive argumentation. Artif. Intell. 175, 9--10 (2011), 1722--1736. Google ScholarDigital Library
- Hengfei Li, Nir Oren, and Timothy J. Norman. 2011. Probabilistic argumentation frameworks. In Theorie and Applications of Formal Argumentation (TAFA). 1--16. Google ScholarDigital Library
- Hengfei Li, Nir Oren, and Timothy J. Norman. 2013. Relaxing independence assumptions in probabilistic argumentation. In Workshop on Argumentation in Multi-Agent Systems (ArgMAS).Google Scholar
- T. Lukasiewicz. 1999. Probabilistic deduction with conditional constraints over basic events. J. Artif. Intell. Res. (JAIR) 10 (1999), 199--241. Google ScholarDigital Library
- T. Lukasiewicz. 2001. Probabilistic logic programming with conditional constraints. ACM Trans. Comput. Logic 2, 3 (2001), 289--339. Google ScholarDigital Library
- Thomas Lukasiewicz. 2007. Probabilistic description logic programs. Int. J. Approx. Reasoning 45, 2 (2007), 288--307. Google ScholarDigital Library
- Diego C. Martínez, Alejandro Javier García, and Guillermo Ricardo Simari. 2008. An abstract argumentation framework with varied-strength attacks. In Principles of Knowledge Representation and Reasoning (KR). 135--144.Google Scholar
- C. Meinel and T. Theobald. 1998. Algorithms and Data Structures in VLSI Design. Springer-Verlag. Google ScholarDigital Library
- Sanjay Modgil. 2009. Reasoning about preferences in argumentation frameworks. Artif. Intell. 173, 9--10 (2009), 901--934. Google ScholarDigital Library
- R. T. Ng and V. S. Subrahmanian. 1992. Probabilistic logic programming. Inf. Comput. 101, 2 (1992), 150--201. Google ScholarDigital Library
- Juan Carlos Nieves and Roberto Confalonieri. 2011. A possibilistic argumentation decision making framework with default reasoning. Fundam. Inform. 113, 1 (2011), 41--61. Google ScholarDigital Library
- Nir Oren and Timothy J. Norman. 2008. Semantics for evidence-based argumentation. In Computational Models of Argument (COMMA). 276--284. Google ScholarDigital Library
- Mauricio Osorio and Juan Carlos Nieves. 2009. Possibilistic well-founded semantics. In Advances in Artificial Intelligence, International Conference on Artificial Intelligence (MICAI). 15--26. Google ScholarDigital Library
- C. M. Papadimitriou. 1994. Computational Complexity. Addison-Wesley.Google Scholar
- David Poole. 1997. The independent choice logic for modelling multiple agents under uncertainty. Artif. Intell. 94, 1--2 (1997), 7--56. Google ScholarDigital Library
- Henry Prakken. 2010. An abstract framework for argumentation with structured arguments. Argument Comput 1, 2 (2010), 93--124.Google ScholarCross Ref
- Iyad Rahwan and Guillermo R. Simari (Eds.). 2009. Argumentation in Artificial Intelligence. Springer. Google ScholarDigital Library
- Tjitze Rienstra. 2012. Towards a probabilistic dung-style argumentation system. In International Conference on Agreement Technologies (AT). 138--152.Google Scholar
- Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch. 2011. Probabilistic Databases. Morgan & Claypool. Google ScholarDigital Library
- Matthias Thimm. 2012. A probabilistic semantics for abstract argumentation. In European Conference on Artificial Intelligence (ECAI). 750--755.Google Scholar
- Seinosuke Toda and Osamu Watanabe. 1992. Polynomial time 1-turing reductions from #PH to #P. Theor. Comput. Sci. 100, 1 (1992), 205--221. Google ScholarDigital Library
- Leslie G. Valiant. 1979. The complexity of computing the permanent. Theor. Comput. Sci. 8 (1979), 189--201.Google ScholarCross Ref
- Bart Verheij. 1996. Two approaches to dialectical argumentation: Admissible sets and argumentation stages. In International Conference on Formal and Applied Practical Reasoning Workshop (FAPR). 357--368.Google Scholar
Index Terms
- On the Complexity of Probabilistic Abstract Argumentation Frameworks
Recommendations
Probabilistic reasoning with abstract argumentation frameworks
Abstract argumentation offers an appealing way of representing and evaluating arguments and counterarguments. This approach can be enhanced by considering probability assignments on arguments, allowing for a quantitative treatment of formal ...
Probabilistic argumentation frameworks
TAFA'11: Proceedings of the First international conference on Theory and Applications of Formal ArgumentationIn this paper, we extend Dung's seminal argument framework to form a probabilistic argument framework by associating probabilities with arguments and defeats. We then compute the likelihood of some set of arguments appearing within an arbitrary argument ...
Explainable acceptance in probabilistic and incomplete abstract argumentation frameworks
AbstractDung's Argumentation Framework (AF) has been extended in several directions, including the possibility of representing uncertainty about the existence of arguments and attacks. In this regard, two main proposals have been introduced in ...
Comments