Diversity of Extensions in Abstract Argumentation
Johannes K. Fichte, Markus Hecher, Yasir Mahmood, Zhengjun Wang · 2026
Read Diversity of Extensions in Abstract Argumentation by Johannes K. Fichte, Markus Hecher, Yasir Mahmood, Zhengjun Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13332.txt.
Introduction
Johannes Fichte and three colleagues introduce a measure of diversity for extensions in abstract argumentation. In this field, arguments and their conflicts form a graph with arrows. An extension is a set of arguments that jointly meet certain rules. Standard reasoning rarely shows how far apart two accepted viewpoints sit. They measure diversity through symmetric difference, which counts arguments in exactly one of the two sets. They classify how hard it is to decide if diverse extensions exist and to find the largest level.
Catalog record
| CREATOR | Johannes K. Fichte, Markus Hecher, Yasir Mahmood, Zhengjun Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 138500 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.13332
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Diversity of Extensions in Abstract Argumentation Johannes K. Fichte, Markus Hecher, Yasir Mahmood, Zhengjun Wang Abstract Argumentation is an important topic of AI for modeling and reasoning about arguments. In abstract argumentation, we consider directed graphs, so-called argumentation frameworks (AF) , that express conflicts between arguments. The semantics is defined by the notion of extensions , which are sets of arguments that satisfy particular relationship conditions in the AF. Usually, standard reasoning in argumentation do not reveal how far apart extensions are. We introduce a quantitative notion of diversity of extensions based on the symmetric-difference and provide a systematic complexity classification. Intuitively, diversity captures whether extensions of a framework (accepted viewpoints) differ only marginally or represent fundamentally incompatible sets of arguments. We study whether an AF admits k-diverse extensions, admits k-diverse extensions covering specific arguments, and to compute the largest k k for which an AF admits k k -diverse extensions. We outline a prototype and provide an evaluation for computing diversity levels. Department of Computer and Information Science (IDA), Linköping University, [email protected]://orcid.org/0000-0002-8681-7470 University of Potsdam, Germany & University of Artois, CNRS, UMR8188 (CRIL), France [email protected]://orcid.org/0000-0003-0131-6771 Data Science Group, Heinz Nixdorf Institute, Paderborn University, [email protected]://orcid.org/0000-0002-5651-5391 Data Science Group, Heinz Nixdorf Institute, Paderborn University, [email protected] ccs Computing methodologies Knowledge representation and reasoning keywords Abstract Argumentation, Diversity, Computational Complexity † † runningtitle: Diversity of Extensions in Abstract Argumentation † † runningauthor: J.K. Fichte, M. Hecher, Y. Mahmood, and Z. Wang † † copyright: Yasir Mahmood, Markus Hecher, Johannes K. Fichte and Zhengjun Wang 1 Introduction Abstract argumentation [ 15 , 39 , 4 ] is a well-known concept in AI for modeling, relating, and grouping arguments [ 3 , 38 ] . To express opposing positions, arguments are related to each other in form of a directed graph, so-called argumentation framework (AF) . Sets of arguments ( extensions ), which satisfy certain conditions regarding the relationship among them (semantics), build the solutions to an AF. Usually, an AF admits multiple extensions, in other words, mutually incompatible but internally coherent sets of jointly acceptable arguments, which can be understood as alternative “view-points” on the same argumentative situation. Research in abstract argumentation has introduced concepts to facilitate insights into diverging extensions, for example, explaining and selecting a set of most representative view-points [ 6 ] , deciding between multiple extensions [ 14 ] , exploring large solution spaces [ 13 ] , deciding the significance of individual arguments [ 22 ] , conditional probability of one or multiple arguments occurring in an extension [ 26 ] , counting extensions [ 23 ] , and incorporating preordering over arguments (extension-ranking semantics) [ 42 ] However, existing concepts do not reveal how far apart and diverse entire extensions or how diverse AFs are. This is particularly interesting in environments where we want to negotiate positions. Different view-points may reasonably endorse different extensions. If we consider only one arbitrarily chosen extension, a representative extension, or parts of extensions, we easily hide genuine trade-offs and impede agreement. To this end, we study diverse extensions and introduce a quantitative notion of extension diversity based on the symmetric-difference. The symmetric-difference A\triangle B of two sets A and B takes the elements that are in exactly one of them, but not in both, i.e., A\triangle B\,\mathrel{\mathop{:}}=(A\cup B)\setminus(A\cap B) . Example 1 illustrates a situation where we are interested in understanding the diversity of extensions. Figure 1 : An Example AF modeling the medical decision making. Example 1 . Take an AF F=(A,R) modeling a medical decision under time pressure, as depicted in Figure 1 . The arguments of F have the following intuitive meaning: • sx (StartX): Start Treatment X immediately. • sy (StartY): Start Treatment Y immediately. • rx (RiskX): Given no immediate decision, X’s long-term risks must be carefully evaluated first. • ey (EffectiveY): Given no immediate decision, Y’s effectiveness must be further tested. • bx (BenefitsX): X has strong short-term benefits. • lry (LowRiskY): Y has fewer side effects. • w (Wait): collect more data before deciding. Under stable semantics, which intuitively expresses a self-consistent position that defeats all alternatives, F admits exactly three extensions. Precisely, E_{X}=\{sx,bx,ey\},E_{Y}=\{sy,lry,rx\} , and E_{W}=\{w,rx,ey\} , each highlighting either a type of treatment, or the argument to wait for more data. Here, three most important arguments regarding the final decision are sx,sy and w which either select a type of treatment or argue to wait, respectively. Each of these arguments occur in some extension (credulously accepted). Hence, we cannot tell much about either of the three options. But looking from a global perspective on all the available options (stable extensions), we observe that the extensions for either treatment do not share any argument, whereas they do share at least one argument with the extension that forces us to wait ( E_{W} ). Precisely, E_{X}\triangle E_{Y}=\{sx,bx,ey,sy,lry,rx\} meaning we consider options “StartX” and “StartY” to be 6 -diverse. However, we have E_{X}\triangle E_{W}=\{sx,bx,rx,w\} , and E_{Y}\triangle E_{W}=\{sy,lry,ey,w\} . Consequently, we observe that the options “StartX” (“StartY”) and “Wait” are only 4 -diverse. Intuitively, this means that the justification for either type of treatment uses very “different” line of reasoning, whereas both treatment options share at least some reasoning with the third option to wait before deciding anything. Alternatively, the reasoning for “StartX” is somewhat similar to the reasoning for “Wait” compared to “StartY”. \triangleleft Contributions. Our main contributions are as follows. 1. We introduce the notion of symmetric-difference-based diversity to abstract argumentation and study its properties. We show how diversity differs from existing notions and that it provides a more fine-grained notion where concepts based on credulous and skeptical reasoning fail. 2. We study the computational complexity of central problems (above, below, exactly k -diverse, max diversity) and provide a thorough picture of the complexity landscape, which are listed in Table 1 . 3. We provide a prototypical implementation and an initial experimental evaluation, where we compute the range of diversity via logic programming (ASP). Problems/ \sigma \sigma_{1} \sigma_{2} \sigma_{3} \,{}^{\leq}\mathsf{k\text{-}Div\text{-}Ext}_{\sigma} \in\textbf{NP}/ Trivial R. 13 NP -c Th. 15 \bm{\Sigma}^{{\textbf{P}}}_{2} -c Th. 19 \,{}^{\geq}\mathsf{k\text{-}Div\text{-}Ext}_{\sigma} NP -c Th. 8 NP -c Th. 15 \bm{\Sigma}^{{\textbf{P}}}_{2} -c Th. 19 \,{}^{\leq}\mathsf{k\text{-}Div\text{-}Arg}_{\sigma} NP -c Th. 11 / \in{\textbf{P}}^{\footnotesize{\color[rgb]{0,0,1}\text{ Th.}\ref{rem:conf-atmost-div-arg}}} NP -c Th. 14 \bm{\Sigma}^{{\textbf{P}}}_{2} -c Th. 17 \,{}^{\geq}\mathsf{k\text{-}Div\text{-}Arg}_{\sigma} NP -c Th. 6 NP -c Th. 14 \bm{\Sigma}^{{\textbf{P}}}_{2} -c Th. 17 Max DP -c Th. 22 / Th. 23 DP -c Th. 26 \textbf{DP}_{2} -c Th. 26 Table 1 : Overview of our complexity results for the semantics \sigma_{1}\in\{\mathsf{conf},\mathsf{naiv}\} , \sigma_{2}\in\{\mathsf{adm},\mathsf{stab},\mathsf{comp}\} , and \sigma_{3}\in\{\mathsf{semiSt}, \mathsf{stag}\} . The problem “Arg” asks if two arguments are k -diverse and “Ext” asks if an AF has two k -diverse \sigma extensions. The results for \,{}^{\leq}\mathsf{k\text{-}Div\text{-}Arg}_{\sigma} also apply to \mathsf{k\text{-}Div\text{-}Arg}_{\sigma} for each \sigma . Proofs to our statements can be found in the technical appendix attached at the end of this pdf . The implementation code is available online in our GitHub Repository 1 1 1 https://github.com/Yahahasir/argu_diversity/ . Related Work. [ 12 ] survey argumentation-based explanation under the perspective of XAI. [ 29 ] introduce and study explanation semantics, which associates with each accepted argument a set of such explanation arguments. [ 35 ] and [ 41 ] study the opposite case where arguments are