Constrained incomplete argumentation frameworks: Expressiveness, complexity and enforcement
Abstract
Operations like belief change or merging have been adapted to the context of abstract argumentation. However, these operations may require to express some uncertainty or some disjunction in the result, which is not representable in classical AFs. For this reason, some of these earlier works require a set of AFs or a set of extensions as the outcome of the operation, somehow to represent a “disjunction” of AFs or extensions. In parallel, the notion of Incomplete AFs (IAFs) has been developed recently. It corresponds to AFs where the existence of some arguments or attacks may be uncertain. Each IAF can be associated with a set of classical AFs called completions, that correspond to different ways of resolving the uncertainty. While these IAFs could be good candidates for a compact representation of a disjunction of AFs, we prove that this model is not expressive enough. Then we introduce Constrained IAFs, that include a propositional formula allowing to select the set of completions used for reasoning. We prove that this model is expressive enough for representing any set of AFs, or any set of extensions. Moreover, we study the complexity of various decision problems related to the verification of extensions and the acceptability of arguments. While some of them are one level higher in the polynomial hierarchy (compared to their counterpart with standard IAFs), most of them have the same complexity than in the case of IAFs. Finally, we show that CIAFs can be used to model a new form of extension enforcement, where the possible evolutions of an AF are taken into account and modeled by the completions of the CIAF.
Get full access to this article
View all access and purchase options for this article.
References
1. C.E. Alchourrón, P. Gärdenfors and D. Makinson, On the logic of theory change: Partial meet contraction and revision functions, J. Symb. Log.50(2) (1985), 510–530.
2. P. Balbiani, A. Herzig and N. Troquard, Dynamic logic of propositional assignments: A well-behaved variant of PDL, in: 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25–28, 2013, IEEE Computer Society, 2013, pp. 143–152.
3. P. Baroni, M. Caminada and M. Giacomin, Abstract argumentation frameworks and their semantics, in: Handbook of Formal Argumentation, P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre, eds, College Publications, 2018, pp. 159–236.
4. R. Baumann and G. Brewka, Expanding argumentation frameworks: Enforcing and monotonicity results, in: Proc. of COMMA’10, Vol. 216, 2010, pp. 75–86.
5. R. Baumann, S. Doutre, J.-G. Mailly and J.P. Wallner, Enforcement in formal argumentation, Journal of Applied Logics – IfCoLog Journal of Logics and their Applications8(6) (2021), 1623–1677.
6. R. Baumann, S. Doutre, J.-G. Mailly and J.P. Wallner, Enforcement in formal argumentation, in: Handbook of Formal Argumentation, D. Gabbay, M. Giacomin, G.R. Simari and M. Thimm, eds, Vol. 2, College Publications, 2021, Chapter 8.
7. R. Baumann, W. Dvorák, T. Linsbichler, H. Strass and S. Woltran, Compact argumentation frameworks, in: Proc. of ECAI’14, Vol. 263, 2014, pp. 69–74.
8. D. Baumeister, M. Järvisalo, D. Neugebauer, A. Niskanen and J. Rothe, Acceptance in incomplete argumentation frameworks, Artif. Intell.295 (2021), 103470.
9. D. Baumeister, D. Neugebauer and J. Rothe, Verification in attack-incomplete argumentation frameworks, in: Proc. of ADT’15, 2015, pp. 341–358.
10. D. Baumeister, D. Neugebauer and J. Rothe, Credulous and skeptical acceptance in incomplete argumentation frameworks, in: Proc. of COMMA’18, 2018, pp. 181–192.
11. D. Baumeister, D. Neugebauer, J. Rothe and H. Schadrack, Verification in incomplete argumentation frameworks, Artif. Intell.264 (2018), 1–26.
12. D. Baumeister, J. Rothe and H. Schadrack, Verification in argument-incomplete argumentation frameworks, in: Proc. of ADT’15, 2015, pp. 359–376.
13. E. Bonzon, J. Delobelle, S. Konieczny and N. Maudet, A parametrized ranking-based semantics for persuasion, in: Proc. of SUM’17, 2017, pp. 237–251.
14. G. Brewka, H. Strass, S. Ellmauthaler, J.P. Wallner and S. Woltran, Abstract dialectical frameworks revisited, in: Proc. of IJCAI’13, F. Rossi, ed., 2013, pp. 803–809.
15. S. Cook, The complexity of theorem-proving procedures, in: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971, pp. 151–158.
16. S. Coste-Marquis, C. Devred, S. Konieczny, M. Lagasquie-Schiex and P. Marquis, On the merging of Dung’s argumentation systems, Artif. Intell.171(10–15) (2007), 730–753.
17. S. Coste-Marquis, C. Devred and P. Marquis, Constrained argumentation frameworks, in: Proc. of KR’06, 2006, pp. 112–122.
18. S. Coste-Marquis, S. Konieczny, J.-G. Mailly and P. Marquis, On the revision of argumentation systems: Minimal change of arguments statuses, in: Proc. of KR’14, 2014.
19. S. Coste-Marquis, S. Konieczny, J.-G. Mailly and P. Marquis, A translation-based approach for revision of argumentation frameworks, in: Proc. of JELIA’14, 2014, pp. 77–85.
20. S. Coste-Marquis, S. Konieczny, J.-G. Mailly and P. Marquis, Extension enforcement in abstract argumentation as an optimization problem, in: Proc. of IJCAI’15, 2015, pp. 2876–2882.
21. A. Darwiche and P. Marquis, A knowledge compilation map, J. Artif. Intell. Res.17 (2002), 229–264.
22. J. Delobelle, A. Haret, S. Konieczny, J.-G. Mailly, J. Rossit and S. Woltran, Merging of abstract argumentation frameworks, in: Proc. of KR’16, 2016, pp. 33–42.
23. M. Diller, A. Haret, T. Linsbichler, S. Rümmele and S. Woltran, An extension-based approach to belief revision in abstract argumentation, Int. J. Approx. Reason.93 (2018), 395–423.
24. Y. Dimopoulos, J.-G. Mailly and P. Moraitis, Control argumentation frameworks, in: Proc. of AAAI’18, 2018, pp. 4678–4685.
25. Y. Dimopoulos, J.-G. Mailly and P. Moraitis, Argumentation-based negotiation with incomplete opponent profiles, in: Proc. of AAMAS’19, 2019, pp. 1252–1260.
26. S. Doutre and J.-G. Mailly, Constraints and changes: A survey of abstract argumentation dynamics, Argument Comput.9(3) (2018), 223–248.
27. P.M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Art. Intel.77 (1995), 321–357.
28. P.E. Dunne, W. Dvorák, T. Linsbichler and S. Woltran, Characteristics of multiple viewpoints in abstract argumentation, Artif. Intell.228 (2015), 153–178.
29. W. Dvorák and P.E. Dunne, Computational problems in formal argumentation and their complexity, in: Handbook of Formal Argumentation, P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre, eds, College Publications, 2018, pp. 631–688.
30. B. Fazzinga, S. Flesca and F. Furfaro, Revisiting the notion of extension over incomplete abstract argumentation frameworks, in: Proc. of IJCAI’20, 2020, pp. 1712–1718.
31. B. Fazzinga, S. Flesca and F. Furfaro, Reasoning over argument-incomplete AAFs in the presence of correlations, in: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event, Montreal, Canada, 19–27 August 2021, Z. Zhou, ed., ijcai.org, 2021, pp. 189–195.
32. B. Fazzinga, S. Flesca and F. Furfaro, Reasoning over attack-incomplete AAFs in the presence of correlations, in: Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, Online Event, 2021, November 3–12, M. Bienvenu, G. Lakemeyer and E. Erdem, eds, 2021, pp. 301–311.
33. A. Herzig and A. Yuste-Ginel, Abstract argumentation with qualitative uncertainty: An analysis in dynamic logic, in: Logic and Argumentation – 4th International Conference, CLAR 2021, Proceedings, Hangzhou, China, October 20–22, 2021, P. Baroni, C. Benzmüller and Y.N. Wáng, eds, Lecture Notes in Computer Science, Vol. 13040, Springer, 2021, pp. 190–208.
34. H. Katsuno and A.O. Mendelzon, On the difference between updating a knowledge base and revising it, in: Proc. of KR’91, 1991, pp. 387–394.
35. H. Katsuno and A.O. Mendelzon, Propositional knowledge base revision and minimal change, Artif. Intell.52(3) (1992), 263–294.
36. S. Konieczny and R.P. Pérez, Merging information under constraints: A logical framework, J. Log. Comput.12(5) (2002), 773–808.
37. J.-G. Mailly, A Note on Rich Incomplete Argumentation Frameworks, 2020, CoRR,.
38. J.-G. Mailly, Possible controllability of control argumentation frameworks, in: Proc. of COMMA’20, Vol. 326, 2020, pp. 283–294.
39. J.-G. Mailly, Constrained incomplete argumentation frameworks, in: Symbolic and Quantitative Approaches to Reasoning with Uncertainty – 16th European Conference, ECSQARU 2021, Proceedings, Prague, Czech Republic, September 21–24, 2021, J. Vejnarová and N. Wilson, eds, Lecture Notes in Computer Science, Vol. 12897, Springer, 2021, pp. 103–116.
40. J.-G. Mailly, Constrained incomplete argumentation frameworks, in: 15èmes Journées d’Intelligence Artificielle Fondamentale, Z. Bouraoui and S. Doutre, eds, 2021, pp. 6–14.
41. J.-G. Mailly, Yes, no, maybe, I don’t know: Complexity and application of abstract argumentation with incomplete knowledge, Argument Comput.13(3) (2022), 291–324.
42. J.-G. Mailly, A logical encoding for k-m-realization of extensions in abstract argumentation, in: Logic and Argumentation – 5th International Conference, CLAR 2023, Proceedings, Hangzhou, China, September 10-12, 2023, A. Herzig, J. Luo and P. Pardo, eds, Lecture Notes in Computer Science, Vol. 14156, Springer, 2023, pp. 84–100.
43. A. Niskanen, D. Neugebauer and M. Järvisalo, Controllability of control argumentation frameworks, in: Proc. of IJCAI’20, 2020, pp. 1855–1861.
44. A. Niskanen, D. Neugebauer, M. Järvisalo and J. Rothe, Deciding acceptance in incomplete argumentation frameworks, in: Proc. of AAAI’20, 2020, pp. 2942–2949.
45. H. Prakken, Formalising an aspect of argument strength: Degrees of attackability, in: Computational Models of Argument – Proceedings of COMMA 2022, Cardiff, Wales, UK, 14–16 September 2022, F. Toni, S. Polberg, R. Booth, M. Caminada and H. Kido, eds, Frontiers in Artificial Intelligence and Applications, Vol. 353, IOS Press, 2022, pp. 296–307.
46. F. Toni, A tutorial on assumption-based argumentation, Argument Comput.5(1) (2014), 89–117.
47. J.P. Wallner, Structural constraints for dynamic operators in abstract argumentation, Argument Comput.11(1–2) (2020), 151–190.
48. J.P. Wallner, A. Niskanen and M. Järvisalo, Complexity results and algorithms for extension enforcement in abstract argumentation, J. Artif. Intell. Res.60 (2017), 1–40.
49. A. Yuste-Ginel and A. Herzig, Qualitative uncertainty and dynamics of argumentation through dynamic logic, J. Log. Comput.33(2) (2023), 370–405.
Cite
Cite
Cite
OR
Download to reference manager
If you have citation software installed, you can download citation data to the citation manager of your choice
Information, rights and permissions
Information
Published In
Article first published online: November 16, 2023
Issue published: June 19, 2024
Keywords
Authors
Metrics and citations
Metrics
Journals metrics
This article was published in The European Journal on Artificial Intelligence.
View All Journal MetricsPublication usage*
Total views and downloads: 15
*Publication usage tracking started in December 2016
Publications citing this one
Receive email alerts when this publication is cited
Web of Science: 2 view articles Opens in new tab
Crossref: 1
- Proceedings of the 40th ACM/SIGAPP Symposium on Applied Computing
Figures and tables
Figures & Media
Tables
View Options
Access options
If you have access to journal content via a personal subscription, university, library, employer or society, select from the options below:
I am signed in as:
View my profileSign out
I can access personal subscriptions, purchases, paired institutional access and free tools such as favourite journals, email alerts and saved searches.
loading institutional access options
Alternatively, view purchase options below:
Purchase 24 hour online access to view and download content.
Access journal content via a DeepDyve subscription or find out more about this option.
