Diversity of Extensions in Abstract Argumentation

# Diversity of Extensions in Abstract Argumentation
Source: [https://arxiv.org/html/2605.13332](https://arxiv.org/html/2605.13332)
Department of Computer and Information Science \(IDA\), Linköping University, Swedenjohannes\.fichte@liu\.sehttps://orcid\.org/0000\-0002\-8681\-7470 University of Potsdam, Germany & University of Artois, CNRS, UMR8188 \(CRIL\), France hecher@cril\.frhttps://orcid\.org/0000\-0003\-0131\-6771 Data Science Group, Heinz Nixdorf Institute, Paderborn University, Germanyyasir\.mahmood@uni\-paderborn\.dehttps://orcid\.org/0000\-0002\-5651\-5391 Data Science Group, Heinz Nixdorf Institute, Paderborn University, Germanyzwang@mail\.uni\-paderborn\.de\\CopyrightYasir Mahmood, Markus Hecher, Johannes K\. Fichte and Zhengjun Wang\\ccsdesc\[100\]Computing methodologies Knowledge representation and reasoning\\hideLIPIcs

###### 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 largestkkfor which an AF admitskk\-diverse extensions\. We outline a prototype and provide an evaluation for computing diversity levels\.

###### keywords:

Abstract Argumentation, Diversity, Computational Complexity

## 1Introduction

Abstract argumentation\[Dung95a,Rahwan07a,BaroniCaminadaGiacomin11\]is a well\-known concept in AI for modeling, relating, and grouping arguments\[AmgoudPrade09a,RagoCocarascuToni18a\]\. 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\[BernreiterMalyNardi24\], deciding between multiple extensions\[DauphinCramerVan\-der\-Torre18\], exploring large solution spaces\[DachseltGagglKrotzsch22\], deciding the significance of individual arguments\[MahmoodEtAl25\], conditional probability of one or multiple arguments occurring in an extension\[FichteH0M23\], counting extensions\[FichteHecherMeier24\], and incorporating preordering over arguments \(extension\-ranking semantics\)\[SkibaRienstraThimm21\]

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​△​BA\\triangle Bof two setsAAandBBtakes the elements that are in exactly one of them, but not in both, i\.e\.,A△B:=\(A∪B\)∖\(A∩B\)A\\triangle B\\,\\mathrel\{\\mathop\{:\}\}=\(A\\cup B\)\\setminus\(A\\cap B\)\. Example[1\.1](https://arxiv.org/html/2605.13332#S1.Thmtheorem1)illustrates a situation where we are interested in understanding the diversity of extensions\.

![Refer to caption](https://arxiv.org/html/2605.13332v1/x1.png)Figure 1:An Example AF modeling the medical decision making\.###### Example 1\.1\.

Take an AFF=\(A,R\)F=\(A,R\)modeling a medical decision under time pressure, as depicted in Figure[1](https://arxiv.org/html/2605.13332#S1.F1)\. The arguments ofFFhave 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,FFadmits exactly three extensions\. Precisely,EX=\{s​x,b​x,e​y\},EY=\{s​y,l​r​y,r​x\}E\_\{X\}=\\\{sx,bx,ey\\\},E\_\{Y\}=\\\{sy,lry,rx\\\}, andEW=\{w,r​x,e​y\}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 ares​x,s​ysx,syandwwwhich 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 \(EWE\_\{W\}\)\. Precisely,EX​△​EY=\{s​x,b​x,e​y,s​y,l​r​y,r​x\}E\_\{X\}\\triangle E\_\{Y\}=\\\{sx,bx,ey,sy,lry,rx\\\}meaning we consider options “StartX” and “StartY” to be66\-diverse\. However, we haveEX​△​EW=\{s​x,b​x,r​x,w\}E\_\{X\}\\triangle E\_\{W\}=\\\{sx,bx,rx,w\\\}, andEY​△​EW=\{s​y,l​r​y,e​y,w\}E\_\{Y\}\\triangle E\_\{W\}=\\\{sy,lry,ey,w\\\}\. Consequently, we observe that the options “StartX” \(“StartY”\) and “Wait” are only44\-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. 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. 2\.We study the computational complexity of central problems \(above, below, exactlykk\-diverse, max diversity\) and provide a thorough picture of the complexity landscape, which are listed in Table[1](https://arxiv.org/html/2605.13332#S1.T1)\.
3. 3\.We provide a prototypical implementation and an initial experimental evaluation, where we compute the range of diversity via logic programming \(ASP\)\.

Table 1:Overview of our complexity results for the semanticsσ1∈\{𝖼𝗈𝗇𝖿,𝗇𝖺𝗂𝗏\}\\sigma\_\{1\}\\in\\\{\\mathsf\{conf\},\\mathsf\{naiv\}\\\},σ2∈\{𝖺𝖽𝗆,𝗌𝗍𝖺𝖻,𝖼𝗈𝗆𝗉\}\\sigma\_\{2\}\\in\\\{\\mathsf\{adm\},\\mathsf\{stab\},\\mathsf\{comp\}\\\}, andσ3∈\{𝗌𝖾𝗆𝗂𝖲𝗍,\\sigma\_\{3\}\\in\\\{\\mathsf\{semiSt\},𝗌𝗍𝖺𝗀\}\\mathsf\{stag\}\\\}\. The problem “Arg” asks if two arguments arekk\-diverse and “Ext” asks if an AF has twokk\-diverseσ\\sigmaextensions\. 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 Repository111[https://github\.com/Yahahasir/argu\_diversity/](https://github.com/Yahahasir/argu_diversity/)\.

##### Related Work\.

\[CyrasRagoAlbini21\]survey argumentation\-based explanation under the perspective of XAI\.\[LiaoTorre20\]introduce and study explanation semantics, which associates with each accepted argument a set of such explanation arguments\.\[NiskanenJarvisalo20a\]and\[SaribaturWallnerWoltran20\]study the opposite case where arguments are rejected and analyze reasons for the rejection\. Although counting complexity for argumentation has been studied\[FichteHecherMeier24\], the results do not apply here, as our focus is on the distances between elements in the extension space\. There are various practical solvers for decision and reasoning tasks\[EglyGagglWoltran08,NiskanenJarvisalo20,ThimmCeruttiVallati21,Alviano18,Alviano21\]that compete in the biannual ICCMA competition\[ThimmEtAl24\]\.

\[MahmoodEtAl25\]propose facets to abstract argumentation, which enable quantifying significance of decisions and study the computational complexity\. Facets do not capture information on extensions containing them, whereas diversity measures the \(dis\)similarity of accepted argument sets in an AF\.\[bohl2023representative\]consider diversity and representative sets in answer\-set programming\.\[UlbrichtWallner21\]consider strong explanation, which ensure that a target set of arguments is acceptable in each sub\-framework containing the explaining set\.\[BesnardDoutreDuchatelle22\]investigate concepts of contrastive and non\-contrastive questions with respect to explanations\. Finding similar and diverse solutions has been considered for constraint programming\[HebrardHnichOSullivan05\]and answer\-set programming\[EiterErdemErdogan13\]\.\[Rodrigues19\]compare different alternative representations of extensions for systematic enumeration\.\[Coste\-MarquisKoniecznyMailly15\]employed Hamming distance to define enforcement operators as previously also done in the context of minimal change\[Baumann12\]\.\[DachseltGagglKrotzsch22\]developed a tool to navigate argumentation frameworks using ASP\-facets and more fine\-grained reasoning modes have also been studied in ASP\[FichteHecherNadeem22\]\. Note that ASP\-navigation is based on forbidding or enforcing atoms in programs via integrity constraints\.

## 2Preliminaries

We assume familiarity with computational complexity\[DBLP:books/daglib/0092426\], graph theory\[DBLP:books/sp/BondyM08\], and Boolean logic\[DBLP:series/faia/336\]\.

##### Complexity Classes\.

We use standard notation for basic complexity classes and for example writeP\(NP\) for the class of decision problems solvable in \(non\-deterministic\) polynomial time\. Additionally, we letcoNPbe the class of decision problems whose complement is inNP, and letDPbe the class of decision problems representable as the intersection of a problem inNPand a problem incoNP\. On top, we use more classes from the polynomial hierarchy\[StockmeyerMeyer73,Stockmeyer76,Wrathall76\],𝚫0P:=𝚷0P:=𝚺0P:=P\\bm\{\\Delta\}^\{\{\\textbf\{P\}\}\}\_\{0\}\\mathrel\{\\mathop\{:\}\}=\\bm\{\\mathrm\{\\Pi\}\}^\{\{\\textbf\{P\}\}\}\_\{0\}\\mathrel\{\\mathop\{:\}\}=\\bm\{\\mathrm\{\\Sigma\}\}^\{\{\\textbf\{P\}\}\}\_\{0\}\\mathrel\{\\mathop\{:\}\}=\{\\textbf\{P\}\}and𝚫iP:=P𝚺i−1P\\bm\{\\Delta\}^\{\{\\textbf\{P\}\}\}\_\{i\}\\mathrel\{\\mathop\{:\}\}=\{\\textbf\{P\}\}^\{\\bm\{\\mathrm\{\\Sigma\}\}^\{\{\\textbf\{P\}\}\}\_\{i\-1\}\},𝚺iP:=NP𝚺i−1P\\bm\{\\mathrm\{\\Sigma\}\}^\{\{\\textbf\{P\}\}\}\_\{i\}\\mathrel\{\\mathop\{:\}\}=\\textbf\{NP\}^\{\\bm\{\\mathrm\{\\Sigma\}\}^\{\{\\textbf\{P\}\}\}\_\{i\-1\}\}, and𝚷iP:=coNP𝚺i−1P\\bm\{\\mathrm\{\\Pi\}\}^\{\{\\textbf\{P\}\}\}\_\{i\}\\mathrel\{\\mathop\{:\}\}=\\text\{co\}\\textbf\{NP\}^\{\\bm\{\\mathrm\{\\Sigma\}\}^\{\{\\textbf\{P\}\}\}\_\{i\-1\}\}fori\>0i\>0whereCDC^\{D\}is the classCCof decision problems augmented by an oracle for some complete problem in classDD\. The complexity classDPk\\textbf\{DP\}\_\{k\}is defined asDPk:=\{L1∩L2∣L1∈𝚺kP,L2∈𝚷kP\}\\textbf\{DP\}\_\{k\}\\mathrel\{\\mathop\{:\}\}=\\\{L\_\{1\}\\cap L\_\{2\}\\mid L\_\{1\}\\in\\bm\{\\mathrm\{\\Sigma\}\}^\{\{\\textbf\{P\}\}\}\_\{k\},L\_\{2\}\\in\\bm\{\\mathrm\{\\Pi\}\}^\{\{\\textbf\{P\}\}\}\_\{k\}\\\},DP=DP1\\textbf\{DP\}\{=\}\\textbf\{DP\}\_\{1\}\[LohreyRosowski23\]\.

The Booleansatisfiabilityproblem \(SAT\) for formulas inconjunctive normal form\(CNF\), asks: givenφ=⋀i=1mCi\\varphi=\\bigwedge\_\{i=1\}^\{m\}C\_\{i\}where eachCiC\_\{i\}is a clause, decide whetherφ\\varphiadmits at least one satisfying assignment\. SAT is the one of the most famousNP\-complete problems, whereas its complementary problem to checkunsatisfiability, iscoNP\-complete\. Moreover, the problem to check whetherφ\\varphiis satisfiable andψ\\psiunsatisfiable for a given pair of formulas\(φ,ψ\)\(\\varphi,\\psi\)\(the SAT\-UNSAT problem\) isDP\-complete\. For𝚷2P\\bm\{\\mathrm\{\\Pi\}\}^\{\{\\textbf\{P\}\}\}\_\{2\}one usually considers the evaluation problem for aquantified Boolean formulaof the form∀X​∃Y\.φ\\forall X\\exists Y\.\\varphiwhereXXandYYare two disjoint sets of variables andφ\\varphia formula in CNF overXXandYY\. Finally, for𝚺2P\\bm\{\\Sigma\}^\{\{\\textbf\{P\}\}\}\_\{2\}the problem is to check whether∀X​∃Y\.φ\\forall X\\exists Y\.\\varphiis false\.

##### Abstract Argumentation\.

We use Dung’s argumentation framework \(\[Dung95a\]\) and consider only non\-empty and finite sets of argumentsAA\. An*\(argumentation\) framework \(AF\)*is a directed graphF=\(A,R\)F=\(A,R\), whereAAis a set of arguments andR⊆A×AR\\subseteq A\\times A, consisting of pairs of arguments representing direct attacks between them\. LetE⊆AE\\subseteq Aanda∈Aa\\in Abe an argument\. Then we say thataais*defended byEEinFF*if for every\(a′,a\)∈R\(a^\{\\prime\},a\)\\in R, there existsa′′∈Ea^\{\\prime\\prime\}\\in Esuch that\(a′′,a′\)∈R\(a^\{\\prime\\prime\},a^\{\\prime\}\)\\in R\. The familydefF⁡\(E\)\\operatorname\{def\}\_\{F\}\(E\)is defined bydefF\(E\):=\{a∣a∈A,ais defended byEinF\}\\operatorname\{def\}\_\{F\}\(E\)\\,\\mathrel\{\\mathop\{:\}\}=\\\{\\;a\\mid a\\in A,a\\text\{ is defended by $E$ in $F$\}\\;\\\}\. In abstract argumentation, one aims at computing so\-called*extensions*, which are subsetsE⊆AE\\subseteq Aof the arguments that have certain properties\. The setEEof arguments is called*conflict\-free inEE*if\(E×E\)∩R=∅\(E\\times E\)\\cap R=\\emptyset;EEis*admissible inFF*if \(1\)EEis*conflict\-free inFF*, and \(2\) everya∈Ea\\in Eis*defended byEEinFF*\. LetER\+:=E∪\{a∣\(b,a\)∈R,b∈E\}E^\{\+\}\_\{R\}\\,\\mathrel\{\\mathop\{:\}\}=E\\cup\\\{\\,a\\mid\(b,a\)\\in R,b\\in E\\,\\\}andEEbe conflict\-free\. Then,EEis \(1\)*naive*inFFif noE′⊃EE^\{\\prime\}\\supset Eexists that is conflict\-free inFF, and \(2\)*stage inFF*if there is no conflict\-free setE′⊆AE^\{\\prime\}\\subseteq AinFFwithER\+⊊\(E′\)R\+E^\{\+\}\_\{R\}\\subsetneq\(E^\{\\prime\}\)^\{\+\}\_\{R\}\. An admissible setEEis \(1\)*complete inFF*ifdefF⁡\(E\)=E\\operatorname\{def\}\_\{F\}\(E\)=E; \(2\)*preferred inFF*, if noE′⊃EE^\{\\prime\}\\supset Eexists that is*admissible inFF*; \(3\)*semi\-stable inFF*if no admissible setE′⊆AE^\{\\prime\}\\subseteq AinFFwithER\+⊊\(E′\)R\+E^\{\+\}\_\{R\}\\subsetneq\(E^\{\\prime\}\)^\{\+\}\_\{R\}exists; and \(4\)*stable inFF*if everya∈A∖Ea\\in A\\setminus Eis*attacked*by somea′∈Ea^\{\\prime\}\\in E\. For a semanticsσ∈\{𝖼𝗈𝗇𝖿,𝗇𝖺𝗂𝗏,𝖺𝖽𝗆,𝖼𝗈𝗆𝗉,𝗌𝗍𝖺𝖻,𝗉𝗋𝖾𝖿,𝗌𝖾𝗆𝗂𝖲𝗍,𝗌𝗍𝖺𝗀\}\\sigma\\in\\\{\\mathsf\{conf\},\\mathsf\{naiv\},\\mathsf\{adm\},\\mathsf\{comp\},\\mathsf\{stab\},\\mathsf\{pref\},\\mathsf\{semiSt\},\\mathsf\{stag\}\\\}, we writeσ​\(F\)\\sigma\(F\)for the set of*all extensions*of semanticsσ\\sigmainFF\. LetF=\(A,R\)F=\(A,R\)be an AF\. Then, the problemExistσ\\textsc\{Exist\}\_\{\\sigma\}asks ifσ​\(F\)≠∅\\sigma\(F\)\\neq\\allowbreak\\emptyset\. The problemscσ\{c\}\_\{\\sigma\}andsσ\{s\}\_\{\\sigma\}question fora∈Aa\{\\,\\in\\,\}A, whetheraais in someE∈σ​\(F\)E\\in\\sigma\(F\)\(“*credulously*accepted”\) or everyE∈σ​\(F\)E\\in\\sigma\(F\)\(“*skeptically*accepted”\), respectively\. We let𝖢σ\\mathsf\{C\}\_\{\\sigma\}\(resp\.,𝖲σ\\mathsf\{S\}\_\{\\sigma\}\) denote the set of all credulously \(skeptically\) accepted arguments under semanticsσ\\sigma\. The complexity of AF reasoning is well\-known, e\.g\.,\[flap/DvorakD17\]\.

## 3Diversity in Abstract Argumentation

In this section, we introduce a quantitative notion of*diversity of extensions*based on the symmetric\-difference\.

###### Definition 3\.1\.

LetF=\(A,R\)F=\(A,R\)be an AF,σ\\sigmabe a semantics andk≥0k\\geq 0be an integer\. For two setsS⊆AS\\subseteq AandT⊆AT\\subseteq Aof arguments, we define byd​\(S,T\)d\(S,T\)the*distance*betweenSSandTT\. Formally, we let

d​\(S,T\)\\displaystyle d\(S,T\):=\|S△T\|=\|\(S∪T\)∖\(S∩T\)\|\\displaystyle\\mathrel\{\\mathop\{:\}\}=\|S\\triangle T\|=\|\(S\\cup T\)\\setminus\(S\\cap T\)\|We say that two extensionsS,T∈σ​\(F\)S,T\\in\\sigma\(F\)are*kk\-diverse ifd​\(S,T\)=kd\(S,T\)=k*\. Moreover, for an extensionS∈σ​\(F\)S\\in\\sigma\(F\)and a setXX, we say thatSS*covers*XXifX⊆SX\\subseteq S\.

We continue our example from above\.

###### Example 3\.2\.

Consider the AF from Example[1\.1](https://arxiv.org/html/2605.13332#S1.Thmtheorem1), its extensions, and their symmetric difference\. We can see that one extension supports treatmentXXwhile another supportsYYunder stable semantics\. These extensions are not only*different*, but are very*diverse*due to their large symmetric difference\.

The arguments “StartX” and “StartY” are both credulously accepted under the stable semantics\. However, asking whether both arguments arekk\-diverse for somek∈ℕk\\in\\mathbb\{N\}reveals how incompatible these acceptable choices actually are, or how radically different two justified medical decisions in this setting can be\. In this context, smaller values ofkkhighlight that the two treatments differ only marginally, i\.e\., same medical reasoning, but different preference\. In contrast, larger values ofkkdepict two entirely different diagnostic strategies\. Thus, in decision\-making, higher diversity indicates deeper disagreement between choices\.⊲\\triangleleft

This consideration leads us to the following problem\.

𝗄​\-​𝖣𝗂𝗏​\-​𝖠𝗋𝗀σ​\(F,K,a,b\)\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Arg\}\_\{\\sigma\}\(F,K,a,b\)

Note that we can extend𝗄​\-​𝖣𝗂𝗏​\-​𝖠𝗋𝗀σ\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Arg\}\_\{\\sigma\}from individual arguments to the sets of arguments, which further allows us to compute the diversity when “absence” \(or even complements\) of arguments are considered\. Since obtained complexity results are identical, we did not explicitly mention these results\.

We can also ask the diversity\-related question at the level of an AF\. That is, does an AF have twokk\-diverseσ\\sigma\-extensions for a given semanticsσ\\sigma\. Here, diversity measures how deep the disagreement encoded in the AF is, beyond mere multiplicity of extensions\. Our notion of diversity applies to the extension space \(all acceptable sets of arguments\) under some semantics\. Therefore, disagreement is interpreted in terms of extensions \(or accepted viewpoints\)\. High diversity implies that the given AF supports radically different and internally coherent positions, thus indicating higher level of disagreement and low robustness of conclusions\. On the other hand, low diversity implies that extensions differ only marginally with most reasons being shared\. Consequently, they indicate near\-consensus and robust conclusions with shallower disagreements\.

𝗄​\-​𝖣𝗂𝗏​\-​𝖤𝗑𝗍σ​\(F,K\)\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Ext\}\_\{\\sigma\}\(F,K\)

The𝗄​\-​𝖣𝗂𝗏​\-​𝖤𝗑𝗍σ​\(F,K\)\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Ext\}\_\{\\sigma\}\(F,K\)problems immediately give rise to whether there areσ\\sigma\-extension that are at least/mostkk\-diverse, which we abbreviate by𝗄≥​\-​𝖣𝗂𝗏​\-​𝖤𝗑𝗍\\,\{\}^\{\\geq\}\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Ext\}and𝗄≤​\-​𝖣𝗂𝗏​\-​𝖤𝗑𝗍\\,\{\}^\{\\leq\}\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Ext\}, respectively\. Similarly,𝗄​\-​𝖣𝗂𝗏​\-​𝖠𝗋𝗀σ​\(F,K,a,b\)\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Arg\}\_\{\\sigma\}\(F,K,a,b\)gives rise to𝗄≥​\-​𝖣𝗂𝗏​\-​𝖠𝗋𝗀\\,\{\}^\{\\geq\}\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Arg\}and𝗄≤​\-​𝖣𝗂𝗏​\-​𝖠𝗋𝗀\\,\{\}^\{\\leq\}\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Arg\}, respectively\.

Finally, we define the problem to obtain the maximumkk\.

𝗆𝖺𝗑​\-​𝗄​\-​𝖣𝗂𝗏​\-​𝖤𝗑𝗍σ​\(F,A,B\)\\mathsf\{max\\text\{\-\}k\\text\{\-\}Div\\text\{\-\}Ext\}\_\{\\sigma\}\(F,A,B\)

Similarly, we can define the corresponding minimization task𝗆𝗂𝗇​\-​𝗄​\-​𝖣𝗂𝗏​\-​𝖤𝗑𝗍σ​\(F,A,B\)\\mathsf\{min\\text\{\-\}k\\text\{\-\}Div\\text\{\-\}Ext\}\_\{\\sigma\}\(F,A,B\)\.

##### Levels of Diversity\.

It could be that some arguments arekk\-diverse andk′k^\{\\prime\}\-diverse for somek′<k∈ℕk^\{\\prime\}<k\\in\\mathbb\{N\}without beingℓ\\ell\-diverse for anyk′≤ℓ≤kk^\{\\prime\}\\leq\\ell\\leq k\. We illustrate how an AF might have different*levels*of diversity among its extensions\.

![Refer to caption](https://arxiv.org/html/2605.13332v1/x2.png)\(a\)Stable44and66\-diversity and admissible11–33and55\-diversity\.
![Refer to caption](https://arxiv.org/html/2605.13332v1/x3.png)\(b\)Neither33\-diverse nor55\-diverse adm\-extensions\.

Figure 2:Example AFs showing different levels of diversity\.###### Example 3\.3\.

Consider the AFF1=\(A,R\)F\_\{1\}=\(A,R\)as depicted in Figure[2\(a\)](https://arxiv.org/html/2605.13332#S3.F2.sf1)\.F1F\_\{1\}admits the following stable setsE1=\{a,e,f\},E2=\{b,e,g\},E3=\{a,d,g\}E\_\{1\}=\\\{a,e,f\\\},E\_\{2\}=\\\{b,e,g\\\},E\_\{3\}=\\\{a,d,g\\\}, andE4=\{c,d,f\}E\_\{4\}=\\\{c,d,f\\\}\. The pair\-wise symmetric difference of these sets yield diversity values in\{4,6\}\\\{4,6\\\}\. In particularF1F\_\{1\}does not admitkk\-diverse stable extensions for anyk∈\{1,2,3,5\}k\\in\\\{1,2,3,5\\\}\. When considering admissible semantics,F1F\_\{1\}additionally admits the following singleton\{e\}\\\{e\\\},\{d\}\\\{d\\\},\{g\}\\\{g\\\},\{f\}\\\{f\\\}, and two\-element extensions\{e,g\}\\\{e,g\\\},\{e,f\}\\\{e,f\\\},\{d,g\}\\\{d,g\\\}, and\{d,f\}\\\{d,f\\\}\. Here, it can be seen that under admissible semantics,F1F\_\{1\}also admits diversity values of11\(due to extensions\{e\}\\\{e\\\},\{e,f\}\\\{e,f\\\}\),22\(due to\{e\},\{d\}\\\{e\\\},\\\{d\\\}\), and33\(due to\{e\}\\\{e\\\},\{d,f\}\\\{d,f\\\}\)\. Finally, by considering sets\{a,e,f\}\\\{a,e,f\\\}and\{d,g\}\\\{d,g\\\}, we also obtain two55\-diverse𝖺𝖽𝗆\\mathsf\{adm\}\-extension\.

Next, consider the AFF2=\(A,R\)F\_\{2\}=\(A,R\)as depicted in Figure[2\(b\)](https://arxiv.org/html/2605.13332#S3.F2.sf2)\. The AFF2F\_\{2\}admits the admissible setsE1=\{a,c\}E\_\{1\}=\\\{a,c\\\},E2=\{e,g\}E\_\{2\}=\\\{e,g\\\},E3=\{f,h\}E\_\{3\}=\\\{f,h\\\},E4=\{a,c,f,h\}E\_\{4\}=\\\{a,c,f,h\\\}, andE5=\{a,c,e,g\}E\_\{5\}=\\\{a,c,e,g\\\}\. The pair\-wise symmetric difference of these sets yield diversity values in\{2,4,6\}\\\{2,4,6\\\}\. Notable, there are neither33\-diverse nor55\-diverse𝖺𝖽𝗆\\mathsf\{adm\}\-extensions\.⊲\\triangleleft

## 4Complexity of Reasoning about Diversity

We first consider the complexity of deciding whether an AF admits twokk\-diverse extensions \(𝗄​\-​𝖣𝗂𝗏​\-​𝖤𝗑𝗍σ\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Ext\}\_\{\\sigma\}\) for a semanticsσ\\sigma, or whether additionally contains two arguments in the question \(𝗄​\-​𝖣𝗂𝗏​\-​𝖠𝗋𝗀σ\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Arg\}\_\{\\sigma\}\)\. Moreover, we also consider the complexity of deciding whether an AF admits some diversity level above, or belowkk, i\.e\.,𝗄≥​\-​𝖣𝗂𝗏​\-​𝖠𝗋𝗀σ\\,\{\}^\{\\geq\}\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Arg\}\_\{\\sigma\}and𝗄≤​\-​𝖣𝗂𝗏​\-​𝖠𝗋𝗀σ\\,\{\}^\{\\leq\}\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Arg\}\_\{\\sigma\}, respectively\. Finally, we consider analogous problems \(𝗄≥​\-​𝖣𝗂𝗏​\-​𝖤𝗑𝗍σ\\,\{\}^\{\\geq\}\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Ext\}\_\{\\sigma\}and𝗄≤​\-​𝖣𝗂𝗏​\-​𝖤𝗑𝗍σ\\,\{\}^\{\\leq\}\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Ext\}\_\{\\sigma\}\) for extensions\.

We find it convenient to present our hardness reductions on top of the*standard translation*of SAT/QBF instances to AFs\. The following reduction is relevant for some hardness results\.

###### Definition 4\.1\(\[flap/DvorakD17\]\)\.

Letφ:=⋀i=1mCi\\varphi\\mathrel\{\\mathop\{:\}\}=\\bigwedge\_\{i=1\}^\{m\}C\_\{i\}, be a CNF\-formula where eachCiC\_\{i\}is a clause\. Consider the AFFφ=\(A,R\)F\_\{\\varphi\}=\(A,R\)constructed as follows:

A:=\\displaystyle A\\mathrel\{\\mathop\{:\}\}=\{φ,C1,…,Cm\}∪\{x,x¯∣x∈𝗏𝖺𝗋⁡\(φ\)\}\\displaystyle\\\{\\varphi,C\_\{1\},\\dots,C\_\{m\}\\\}\\cup\\\{\\,x,\\bar\{x\}\\mid x\\in\\operatorname\{\\mathsf\{var\}\}\(\\varphi\)\\\}R:=\\displaystyle R\\mathrel\{\\mathop\{:\}\}=\{\(Ci,φ\)∣i≤m\}∪\{\(x,x¯\),\(x¯,x\)∣x∈𝗏𝖺𝗋⁡\(φ\)\}\\displaystyle\\\{\\,\(C\_\{i\},\\varphi\)\\mid i\\leq m\\,\\\}\\cup\\\{\\,\(x,\\bar\{x\}\),\(\\bar\{x\},x\)\\mid x\\in\\operatorname\{\\mathsf\{var\}\}\(\\varphi\)\\,\\\}∪\{\(x,Ci\)∣x∈Ci\}∪\{\(x¯,Ci\)∣x¯∈Ci\}\.\\displaystyle\\cup\\\{\\,\(x,C\_\{i\}\)\\mid x\\in C\_\{i\}\\,\\\}\\cup\\\{\\,\(\\bar\{x\},C\_\{i\}\)\\mid\\bar\{x\}\\in C\_\{i\}\\,\\\}\.We callFφF\_\{\\varphi\}the argumentation framework ofφ\\varphigenerated via the*standard translation*for admissible semantics\.

Then,φ\\varphiis satisfiable iff the argumentφ\\varphiis credulously accepted inFφF\_\{\\varphi\}under semanticsσ∈\{𝖺𝖽𝗆,𝖼𝗈𝗆𝗉,𝗌𝗍𝖺𝖻\}\\sigma\\in\\\{\\mathsf\{adm\},\\mathsf\{comp\},\\mathsf\{stab\}\\\}\.

#### 4\.0\.1Above, Below, and ExactkkDiversity

The problem𝗄​\-​𝖣𝗂𝗏​\-​𝖠𝗋𝗀σ​\(F,k,a,b\)\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Arg\}\_\{\\sigma\}\(F,k,a,b\)asks: given two argumentsaaandbbin an AFF=\(A,R\)F=\(A,R\)and a numberk∈ℕk\\in\\mathbb\{N\}, are there twoσ\\sigma\-extensionsS1,S2S\_\{1\},S\_\{2\}witha∈S1,b∈S2a\\in S\_\{1\},b\\in S\_\{2\}, andd​\(S1,S2\)=kd\(S\_\{1\},S\_\{2\}\)=k? We prove that this problem \(i\) shows higher complexity than credulous reasoning for conflict\-free, naive, and preferred semantics, whereas \(ii\) is of same complexity as credulous reasoning under all other considered semantics\.

We also consider the problem𝗄​\-​𝖣𝗂𝗏​\-​𝖤𝗑𝗍σ​\(F,k,a,b\)\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Ext\}\_\{\\sigma\}\(F,k,a,b\)asking: given an AFF=\(A,R\)F=\(A,R\)and a numberk∈ℕk\\in\\mathbb\{N\}, are there twoσ\\sigma\-extensionsS1,S2S\_\{1\},S\_\{2\}withd​\(S1,S2\)=kd\(S\_\{1\},S\_\{2\}\)=k?

### 4\.1Conflict\-free and Naive Semantics

We first consider the*lightest*semantics\. Surprisingly, here we get hardness already for the conflict\-free semantics\. This case is interesting as almost all other reasoning problems \(extension existence, credulous and skeptical acceptance, etc\.\) are decidable in polynomial time under conflict\-free semantics\. Nevertheless, the hardness is more involved in some cases \(e\.g\., for belowkkdiversity\) and in fact both semantics incur different complexity in those cases \(under reasonable complexity assumptions\)\.

###### Theorem 4\.2\(⋆\\star\)\.

The problems𝗄​\-​𝖣𝗂𝗏​\-​𝖠𝗋𝗀σ\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Arg\}\_\{\\sigma\}and𝗄≥​\-​𝖣𝗂𝗏​\-​𝖠𝗋𝗀σ\\,\{\}^\{\\geq\}\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Arg\}\_\{\\sigma\}areNP\-complete forσ∈\{𝖼𝗈𝗇𝖿,𝗇𝖺𝗂𝗏\}\\sigma\\in\\\{\\mathsf\{conf\},\\mathsf\{naiv\}\\\}\.

###### Proof 4\.3\.

For membership, one guesses two witness setsSa,Sb⊆AS\_\{a\},S\_\{b\}\\subseteq Asuch that \(i\)SaS\_\{a\}andSbS\_\{b\}areσ\\sigma\-extension, \(ii\)a∈Saa\\in S\_\{a\},b∈Sbb\\in S\_\{b\}, and \(iii\)d​\(Sa,Sb\)=kd\(S\_\{a\},S\_\{b\}\)=k\. The verification requires polynomial time for eachσ∈\{𝖼𝗈𝗇𝖿,𝗇𝖺𝗂𝗏\}\\sigma\\in\\\{\\mathsf\{conf\},\\mathsf\{naiv\}\\\}\. For naive, one checks conflict\-freeness and additionally that adding any argument not in the set breaks the conflict\-freeness\. For𝗄≥​\-​𝖣𝗂𝗏​\-​𝖠𝗋𝗀σ\\,\{\}^\{\\geq\}\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Arg\}\_\{\\sigma\}, we substitute \(iii\) byd​\(Sa,Sb\)≥kd\(S\_\{a\},S\_\{b\}\)\\geq k\.

For hardness, we reduce from the canonicalNP\-complete problem3​SAT3\\textsc\{SAT\}\. Here, the reduction in Definition[4\.1](https://arxiv.org/html/2605.13332#S4.Thmtheorem1)can not be directly used as it is based on the notion of admissibility, which both semanticsσ∈\{𝖼𝗈𝗇𝖿,𝗇𝖺𝗂𝗏\}\\sigma\\in\\\{\\mathsf\{conf\},\\mathsf\{naiv\}\\\}lack\. Our reduction builds on the idea of the standard reduction for proving the hardness of independent sets existence \(IS\) problem implicitly\. However, one can not directly reduce from IS as we do not have control over the size of solution sets\.

Letφ=⋀i≤mCi\\varphi=\\bigwedge\_\{i\\leq m\}C\_\{i\}where eachCi=\(ℓi​1∨ℓi​2∨ℓi​3\)C\_\{i\}=\(\\ell\_\{i1\}\\lor\\ell\_\{i2\}\\lor\\ell\_\{i3\}\)is a clause with three literals over the setXXof variables\. In our AF, we only require symmetric edges\. Hence we find it convenient to write\{u,v\}\\\{u,v\\\}for two attacks\(u,v\)\(u,v\)and\(v,u\)\(v,u\)\. We construct an AFF=\(A,R\)F=\(A,R\)where:

A:=\\displaystyle A\\mathrel\{\\mathop\{:\}\}=\{ℓi​j∣1≤i≤m,1≤j≤3\}∪\{a,b\},\\displaystyle\\\{\\ell\_\{ij\}\\mid 1\\leq i\\leq m,1\\leq j\\leq 3\\\}\\cup\\\{a,b\\\},R:=\\displaystyle R\\mathrel\{\\mathop\{:\}\}=\{\{ℓi​1,ℓi​2\},\{ℓi​2,ℓi​3\},\{ℓi​3,ℓi​1\}∣1≤i≤m\}\\displaystyle\\\{\\\{\\ell\_\{i1\},\\ell\_\{i2\}\\\},\\\{\\ell\_\{i2\},\\ell\_\{i3\}\\\},\\\{\\ell\_\{i3\},\\ell\_\{i1\}\\\}\\mid 1\\leq i\\leq m\\\}∪\{\{ℓ,ℓ′\}∣ℓ=x,ℓ′=x¯​for some​x∈X\}\\displaystyle\\cup\\\{\\\{\\ell,\\ell^\{\\prime\}\\\}\\mid\\ell=x,\\ell^\{\\prime\}=\\bar\{x\}\\text\{ for some \}x\\in X\\\}∪\{\{a,b\}\}∪\{\{b,x\}∣x∈A∖\{b\}\},\\displaystyle\\cup\\\{\\\{a,b\\\}\\\}\\cup\\\{\\\{b,x\\\}\\mid x\\in A\\setminus\\\{b\\\}\\\},for fresh argumentsa,b∉Xa,b\\not\\in X\. Moreover, we letk=m\+2k=m\+2\. Here, we observe that\{b\}\\\{b\\\}is a naive and hence also a conflict\-free set inFF\. Intuitively, we let each position of a literal in a clause as an argument thus resulting in three arguments for each clause ofφ\\varphi\. For attacks, we add a “triangle” of symmetric attacks between all three arguments for a clause, and further attacks between two literals of opposite parity\. For correctness, we prove the following claim\.

###### Claim 1\(⋆\\star\)\.

Argumentsaaandbbare\(m\+2\)\(m\+2\)\-diverse inFFiff formulaφ\\varphiis satisfiable\.

We conclude by observing that the presented reduction also applies to the problem that asks abovekkdiverse extensions coveringaaandbb, that is, to𝗄≥​\-​𝖣𝗂𝗏​\-​𝖠𝗋𝗀σ\\,\{\}^\{\\geq\}\\mathsf\{k\\text\{\-\}Div\\text\{\-\}Arg\}\_\{\\sigma\}\.