×

Complexity of fundamental problems in probabilistic abstract argumentation: beyond independence. (English) Zbl 1478.68352

Summary: The complexity of the probabilistic counterparts of the classical verification and acceptance problems is investigated over Probabilistic Abstract Argumentation Frameworks (prAAFs), in a setting more general than that considered in the current literature, where the complexity has been characterized only under the assumption of independence between arguments/defeats. The complexity of the problems is shown to range from FP to \(\mathrm{FP}^\mathrm{\#P}\)-complete, with \(\mathrm{FP}^{\|\mathrm{NP}}\)-complete cases, depending on the semantics of the extensions, the representation paradigm used for encoding the prAAF, and the imposed correlations between arguments/defeats, thus providing a thorough analysis of the sensitivity to several aspects. In this regard, in order to allow the study of the impact of different forms of correlations between arguments/defeats on the complexity, a new form of prAAF is introduced, called gen. It is based on the well-known paradigm of world-set descriptors and world-set sets for representing probabilities, and it allows the correlations to be easily and explicitly expressed. Interestingly, the introduction of gen is shown to be also a standalone contribution as a powerful representation paradigm for prAAFs, owing to its high expressiveness, compactness, and the possibility to support user-friendly mechanisms for defining correlations.

MSC:

68T27 Logic in artificial intelligence
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
68T30 Knowledge representation

Software:

Dungine; ASPARTIX
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Bench-Capon, T. J.M.; Dunne, P. E., Argumentation in artificial intelligence, Artif. Intell., 171, 10-15, 619-641, (2007) · Zbl 1168.68560
[2] Besnard, P.; Hunter, A., Elements of Argumentation, (2008), MIT Press
[3] (Simari, G. R.; Rahwan, I., Argumentation in Artificial Intelligence, (2009), Springer)
[4] Dung, P. M., On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artif. Intell., 77, 2, 321-358, (1995) · Zbl 1013.68556
[5] Hunter, A., Probabilistic qualification of attack in abstract argumentation, Int. J. Approx. Reason., 55, 2, 607-638, (2014) · Zbl 1316.68153
[6] Dung, P. M.; Mancarella, P.; Toni, F., Computing ideal sceptical argumentation, Artif. Intell., 171, 10-15, 642-674, (2007) · Zbl 1168.68564
[7] Baroni, P.; Giacomin, M., Semantics of abstract argument systems, (Argumentation in Artificial Intelligence, (2009)), 25-44
[8] Caminada, M., Semi-stable semantics, (Proceedings of Computational Models of Argument: COMMA. Proceedings of Computational Models of Argument: COMMA, Liverpool, UK, September 11-12, (2006)), 121-130
[9] Dung, P. M.; Thang, P. M., Towards (probabilistic) argumentation for jury-based dispute resolution, (Proceedings of Computational Models of Argument: COMMA. Proceedings of Computational Models of Argument: COMMA, Desenzano del Garda, Italy, September 8-10, (2010)), 171-182
[10] Rienstra, T., Towards a probabilistic Dung-style argumentation system, (Proceedings of the First International Conference on Agreement Technologies, AT 2012. Proceedings of the First International Conference on Agreement Technologies, AT 2012, Dubrovnik, Croatia, October 15-16, (2012)), 138-152
[11] Doder, D.; Woltran, S., Probabilistic argumentation frameworks - a logical approach, (Proceedings of 8th International Conference on Scalable Uncertainty Management: SUM. Proceedings of 8th International Conference on Scalable Uncertainty Management: SUM, Oxford, UK, September 15-17, (2014)), 134-147
[12] Dondio, P., Toward a computational analysis of probabilistic argumentation frameworks, Cybern. Syst., 45, 3, 254-278, (2014) · Zbl 1331.68221
[13] Hunter, A., Some foundations for probabilistic abstract argumentation, (Proceedings of Computational Models of Argument: COMMA. Proceedings of Computational Models of Argument: COMMA, Vienna, Austria, September 10-12, 2012, (2012)), 117-128
[14] Li, H.; Oren, N.; Norman, T. J., Probabilistic argumentation frameworks, (Proceedings of First International Workshop on Theory and Applications of Formal Argumentation: TAFA. Proceedings of First International Workshop on Theory and Applications of Formal Argumentation: TAFA, Barcelona, Spain, July 16-17, (2011)), 1-16
[15] Fazzinga, B.; Flesca, S.; Parisi, F., On the complexity of probabilistic abstract argumentation, (Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI). Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI), Beijing, China, August 3-9, (2013)), 898-904
[16] Fazzinga, B.; Flesca, S.; Parisi, F., On the complexity of probabilistic abstract argumentation frameworks, ACM Trans. Comput. Log., 16, 3, 22:1-22:39, (2015) · Zbl 1354.68253
[17] Fazzinga, B.; Flesca, S.; Furfaro, F., Credulous acceptability in probabilistic abstract argumentation: complexity results, (Proceedings of the 1st Workshop on Advances in Argumentation in Artificial Intelligence Co-located with XVI International Conference of the Italian Association for Artificial Intelligence (AI*IA). Proceedings of the 1st Workshop on Advances in Argumentation in Artificial Intelligence Co-located with XVI International Conference of the Italian Association for Artificial Intelligence (AI*IA), Bari, Italy, November 16-17, 2017, (2017)), 43-57
[18] Antova, L.; Jansen, T.; Koch, C.; Olteanu, D., Fast and simple relational processing of uncertain data, (Proceedings of the 24th International Conference on Data Engineering: ICDE. Proceedings of the 24th International Conference on Data Engineering: ICDE, Cancún, Mexico, April 7-12, (2008)), 983-992
[19] Koch, C.; Olteanu, D., Conditioning probabilistic databases, PVLDB, 1, 1, 313-325, (2008)
[20] Fazzinga, B.; Flesca, S.; Parisi, F., On efficiently estimating the probability of extensions in abstract argumentation frameworks, Int. J. Approx. Reason., 69, 106-132, (2016) · Zbl 1344.68221
[21] Valiant, L. G., The complexity of computing the permanent, Theor. Comput. Sci., 8, 189-201, (1979) · Zbl 0415.68008
[22] Toda, S.; Watanabe, O., Polynomial time 1-Turing reductions from #ph to #p, Theor. Comput. Sci., 100, 1, 205-221, (1992) · Zbl 0779.68037
[23] Dunne, P. E.; Caminada, M., Computational complexity of semi-stable semantics in abstract argumentation frameworks, (Proceedings of 11th European Conference on Logics in Artificial Intelligence: JELIA. Proceedings of 11th European Conference on Logics in Artificial Intelligence: JELIA, Dresden, Germany, September 28-October 1, (2008)), 153-165 · Zbl 1178.68557
[24] Dunne, P. E.; Wooldridge, M., Complexity of abstract argumentation, (Argumentation in Artificial Intelligence, (2009)), 85-104
[25] Dunne, P. E., The computational complexity of ideal semantics, Artif. Intell., 173, 18, 1559-1591, (2009) · Zbl 1185.68666
[26] Dvorák, W.; Woltran, S., Complexity of semi-stable and stage semantics in argumentation frameworks, Inf. Process. Lett., 110, 11, 425-430, (2010) · Zbl 1229.68041
[27] Gaggl, S. A.; Woltran, S., The cf2 argumentation semantics revisited, J. Log. Comput., 23, 5, 925-949, (2013) · Zbl 1275.68138
[28] Booth, R.; Caminada, M.; Dunne, P. E.; Podlaszewski, M.; Rahwan, I., Complexity properties of critical sets of arguments, (Proceedings of Computational Models of Argument: COMMA, Atholl Palace Hotel. Proceedings of Computational Models of Argument: COMMA, Atholl Palace Hotel, Scottish Highlands, UK, September 9-12, (2014)), 173-184
[29] Olteanu, D.; Koch, C.; Antova, L., World-set decompositions: expressiveness and efficient algorithms, Theor. Comput. Sci., 403, 2-3, 265-284, (2008) · Zbl 1203.68042
[30] Benjelloun, O.; Sarma, A. D.; Halevy, A. Y.; Widom, J., ULDBs: Databases with uncertainty and lineage, (Proceedings of the 32nd International Conference on Very Large Data Bases. Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea, September 12-15, (2006)), 953-964
[31] Besnard, P.; Doutre, S., Checking the acceptability of a set of arguments, (Proceedings of the 10th International Workshop on Non-Monotonic Reasoning (NMR). Proceedings of the 10th International Workshop on Non-Monotonic Reasoning (NMR), Whistler, Canada, June 6-8, (2004)), 59-64
[32] Thimm, M., A probabilistic semantics for abstract argumentation, (Proceedings of the 20th European Conference on Artificial Intelligence (ECAI). Including Prestigious Applications of Artificial Intelligence (PAIS) System Demonstrations Track. Proceedings of the 20th European Conference on Artificial Intelligence (ECAI). Including Prestigious Applications of Artificial Intelligence (PAIS) System Demonstrations Track, Montpellier, France, August 27-31, (2012)), 750-755 · Zbl 1327.68290
[33] Hunter, A.; Thimm, M., Probabilistic argumentation with incomplete information, (Proceedings of the 21st European Conference on Artificial Intelligence (ECAI), 18-22 August, Prague, Czech Republic. Including Prestigious Applications of Intelligent Systems (PAIS), (2014)), 1033-1034
[34] Hunter, A.; Thimm, M., Probabilistic argumentation with epistemic extensions, (Proceedings of the International Workshop on Defeasible and Ampliative Reasoning, DARe@ECAI, Co-located with the 21st European Conference on Artificial Intelligence (ECAI). Proceedings of the International Workshop on Defeasible and Ampliative Reasoning, DARe@ECAI, Co-located with the 21st European Conference on Artificial Intelligence (ECAI), Prague, Czech Republic, August 19, (2014))
[35] Hunter, A., A probabilistic approach to modelling uncertain logical arguments, Int. J. Approx. Reason., 54, 1, 47-81, (2013) · Zbl 1266.68176
[36] Prakken, H., An abstract framework for argumentation with structured arguments, Argum. Comput., 1, 2, 93-124, (2010)
[37] Dondio, P., Computing the grounded semantics in all the subgraphs of an argumentation framework: an empirical evaluation, (Proceedings of 14th International Workshop on Computational Logic in Multi-Agent Systems: CLIMA. Proceedings of 14th International Workshop on Computational Logic in Multi-Agent Systems: CLIMA, Corunna, Spain, September 16-18, (2013)), 119-137 · Zbl 1401.68303
[38] Liao, B.; Xu, K.; Huang, H., Formulating semantics of probabilistic argumentation by characterizing subgraphs: theory and empirical results, J. Log. Comput., 28, 2, 305-335, (2018) · Zbl 1444.68184
[39] Fazzinga, B.; Flesca, S.; Parisi, F., Efficiently estimating the probability of extensions in abstract argumentation, (Proceedings of 7th International Conference on Scalable Uncertainty Management: SUM. Proceedings of 7th International Conference on Scalable Uncertainty Management: SUM, Washington, DC, USA, September 16-18, (2013)), 106-119
[40] Bench-Capon, T. J.M., Persuasion in practical argument using value-based argumentation frameworks, J. Log. Comput., 13, 3, 429-448, (2003) · Zbl 1043.03026
[41] Amgoud, L.; Vesic, S., A new approach for preference-based argumentation frameworks, Ann. Math. Artif. Intell., 63, 2, 149-183, (2011) · Zbl 1234.68371
[42] Amgoud, L.; Cayrol, C., A reasoning model based on the production of acceptable arguments, Ann. Math. Artif. Intell., 34, 1-3, 197-215, (2002) · Zbl 1002.68172
[43] Modgil, S., Reasoning about preferences in argumentation frameworks, Artif. Intell., 173, 9-10, 901-934, (2009) · Zbl 1192.68663
[44] Dunne, P. E.; Hunter, A.; McBurney, P.; Parsons, S.; Wooldridge, M., Weighted argument systems: basic definitions, algorithms, and complexity results, Artif. Intell., 175, 2, 457-486, (2011) · Zbl 1216.68261
[45] Coste-Marquis, S.; Konieczny, S.; Marquis, P.; Ouali, M. A., Weighted attacks in argumentation frameworks, (Proceedings of Principles of Knowledge Representation and Reasoning: KR. Proceedings of Principles of Knowledge Representation and Reasoning: KR, Rome, Italy, June 10-14, (2012))
[46] Brewka, G.; Polberg, S.; Woltran, S., Generalizations of dung frameworks and their role in formal argumentation, IEEE Intell. Syst., 29, 1, 30-38, (2014)
[47] Amgoud, L.; Prade, H., Reaching agreement through argumentation: a possibilistic approach, (Proceedings of Principles of Knowledge Representation and Reasoning: KR. Proceedings of Principles of Knowledge Representation and Reasoning: KR, Whistler, Canada, June 2-5, (2004)), 175-182
[48] Alsinet, T.; Chesñevar, C. I.; Godo, L.; Sandri, S. A.; Simari, G. R., Formalizing argumentative reasoning in a possibilistic logic programming setting with fuzzy unification, Int. J. Approx. Reason., 48, 3, 711-729, (2008) · Zbl 1184.68497
[49] Alsinet, T.; Chesñevar, C. I.; Godo, L.; Simari, G. R., A logic programming framework for possibilistic argumentation: formalization and logical properties, Fuzzy Sets Syst., 159, 10, 1208-1228, (2008) · Zbl 1187.68601
[50] Baroni, P.; Caminada, M.; Giacomin, M., An introduction to argumentation semantics, Knowl. Eng. Rev., 26, 4, 365-410, (2011)
[51] Dimopoulos, Y.; Torres, A., Graph theoretical structures in logic programs and default theories, Theor. Comput. Sci., 170, 1-2, 209-244, (1996) · Zbl 0874.68190
[52] Dunne, P. E.; Bench-Capon, T. J.M., Coherence in finite argument systems, Artif. Intell., 141, 1/2, 187-203, (2002) · Zbl 1043.68098
[53] Coste-Marquis, S.; Devred, C.; Marquis, P., Symmetric argumentation frameworks, (Proceedings of 8th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty: ECSQARU. Proceedings of 8th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty: ECSQARU, Barcelona, Spain, July 6-8, (July 2005)), 317-328 · Zbl 1122.68642
[54] Kim, E. J.; Ordyniak, S.; Szeider, S., Algorithms and complexity results for persuasive argumentation, Artif. Intell., 175, 9-10, 1722-1736, (2011) · Zbl 1230.68189
[55] South, M.; Vreeswijk, G.; Fox, J., Dungine: a java dung reasoner, (Proceedings of Computational Models of Argument: COMMA. Proceedings of Computational Models of Argument: COMMA, Toulouse, France, May 28-30, (2008)), 360-368
[56] Egly, U.; Gaggl, S. A.; Woltran, S., ASPARTIX: implementing argumentation frameworks using answer-set programming, (Proceedings of 24th International Conference on Logic Programming: ICLP. Proceedings of 24th International Conference on Logic Programming: ICLP, Udine, Italy, December 9-13, (2008)), 734-738
[57] Snaith, M.; Reed, C., TOAST: online aspic^{+} implementation, (Proceedings of Computational Models of Argument: COMMA. Proceedings of Computational Models of Argument: COMMA, Vienna, Austria, September 10-12, (2012)), 509-510
[58] Alsinet, T.; Béjar, R.; Godo, L.; Guitart, F., Using answer set programming for an scalable implementation of defeasible argumentation, (Proceedings of IEEE 24th International Conference on Tools with Artificial Intelligence: ICTAI. Proceedings of IEEE 24th International Conference on Tools with Artificial Intelligence: ICTAI, Athens, Greece, November 7-9, (2012)), 1016-1021
[59] Fazzinga, B.; Flesca, S.; Parisi, F.; Pietramala, A., PARTY: a mobile system for efficiently assessing the probability of extensions in a debate, (Proceedings of 26th International Conference on Database and Expert Systems Applications: DEXA. Proceedings of 26th International Conference on Database and Expert Systems Applications: DEXA, Valencia, Spain, September 1-4, (2015)), 220-235
[60] Charwat, G.; Dvorák, W.; Gaggl, S. A.; Wallner, J. P.; Woltran, S., Methods for solving reasoning problems in abstract argumentation - a survey, Artif. Intell., 220, 28-63, (2015) · Zbl 1328.68212
[61] Caminada, M., An algorithm for stage semantics, (Proceedings of Computational Models of Argument: COMMA. Proceedings of Computational Models of Argument: COMMA, Desenzano del Garda, Italy, September 8-10, (2010)), 147-158
[62] Dunne, P. E.; Dvorák, W.; Woltran, S., Parametric properties of ideal semantics, Artif. Intell., 202, 1-28, (2013) · Zbl 1329.68244
[63] Fazzinga, B.; Flesca, S.; Furfaro, F., Computing extensions’ probabilities in probabilistic abstract argumentation: Beyond independence, (Proceedings of ECAI - 22nd European Conference on Artificial Intelligence, 29 August-2 September, The Hague, The Netherlands - Including Prestigious Applications of Artificial Intelligence (PAIS), (2016)), 1588-1589
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.