Diversity of Extensions in Abstract Argumentation

1 Introduction

Abstract argumentation [Dung, 1995; Rahwan, 2007; Baroni et al., 2011] is a well-known concept in AI for modeling, relating, and grouping arguments [Amgoud and Prade, 2009; Rago et al., 2018]. 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 viewpoints [Bernreiter et al., 2024], deciding between multiple extensions [Dauphin et al., 2018], exploring large solution spaces [Dachselt et al., 2022], deciding the significance of individual arguments [Fichte et al., 2025], conditional probability of one or multiple arguments occurring in an extension [Fichte et al., 2023], counting extensions [Fichte et al., 2024], and incorporating preordering over arguments (extension-ranking semantics) [Skiba et al., 2021]

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△B of two sets A and B takes the elements that are in exactly one of them, but not in both, i.e., A△B := (A∪B) \ (A∩B). Example 1 illustrates a situation where we are interested in understanding the diversity of extensions.

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 selfconsistent position that defeats all alternatives, F admits exactly three extensions. Precisely, EX = {sx, bx, ey}, EY = {sy, lry, rx}, and EW = {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 (EW). Precisely, EX△EY = {sx, bx, ey, sy, lry, rx} meaning we consider options "StartX" and "StartY" to be 6-diverse. However, we have EX△EW = {sx, bx, rx,w}, and EY △EW = {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". ◁

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).

Proofs to our statements and details on the code implementation can be found in the technical report [Fichte et al., 2026].

Related Work. ˇCyras et al. [2021] survey argumentationbased explanation under the perspective of XAI. Liao and van der Torre [2020] introduce and study explanation semantics, which associates with each accepted argument a set of such explanation arguments. Niskanen and J¨arvisalo [2020a] and [Saribatur et al., 2020] study the opposite case where arguments are rejected and analyze reasons for the rejection. Although counting complexity for argumentation has been studied [Fichte et al., 2024], 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 [Egly et al., 2008; Niskanen and J¨arvisalo, 2020b; Thimm et al., 2021; Alviano, 2018; Alviano, 2021] that compete in the biannual ICCMA competition [Thimm et al., 2024].

Fichte et al. [2025] 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. B¨ohl et al. [2023] consider diversity and representative sets in answer-set programming. Ulbricht and Wallner [2021] consider strong explanation, which ensure that a target set of arguments is acceptable in each sub-framework containing the explaining set. Besnard et al. [2022] investigate concepts of contrastive and non-contrastive questions with respect to explanations. Finding similar and diverse solutions has been considered for constraint programming [Hebrard et al., 2005] and answer-set programming [Eiter et al., 2013]. Rodrigues [2019] compare different alternative representations of extensions for systematic enumeration. Coste-Marquis et al. [2015] employed Hamming distance to define enforcement operators as previously also done in the context of minimal change [Baumann, 2012]. Dachselt et al. [2022] developed a tool to navigate argumentation frameworks using ASP-facets and more fine-grained reasoning modes have also been studied in ASP [Fichte et al., 2022]. Note that ASP-navigation is based on forbidding or enforcing atoms in programs via integrity constraints.

2 Preliminaries

We assume familiarity with computational complexity [Pippenger, 1997], graph theory [Bondy and Murty, 2008], and Boolean logic [Biere et al., 2021].

Complexity Classes. We use standard notation for basic complexity classes and for example write P (NP) for the class of decision problems solvable in (non-deterministic) polynomial time. Additionally, we let coNP be the class of decision problems whose complement is in NP, and let DP be the class of decision problems representable as the intersection of a problem in NP and a problem in coNP. On top, we use more classes from the polynomial hierarchy [Stockmeyer and Meyer, 1973; Stockmeyer, 1976; Wrathall, 1976], ∆P0 := ΠP0 := ΣP0 := P and ∆Pi := PΣPi-1 , ΣPi := NPΣPi-1 , and ΠPi := coNPΣPi-1 for i > 0 where C D is the class C of decision problems augmented by an oracle for some complete problem in class D. The complexity class DPk is defined as DPk := {L1 ∩ L2 | L1 ∈ ΣPk , L2 ∈ ΠPk }, DP=DP1 [Lohrey and Rosowski, 2023].

The Boolean satisfiability problem (SAT) for formulas in conjunctive normal form (CNF), asks: given φ = ∧mi=1 Ci where each Ci is a clause, decide whether φ admits at least one satisfying assignment. SAT is the one of the most famous NP-complete problems, whereas its complementary problem to check unsatisfiability, is coNP-complete. Moreover, the problem to check whether φ is satisfiable and ψ unsatisfiable for a given pair of formulas (φ, ψ) (the SAT-UNSAT problem) is DP-complete. For ΠP2 one usually considers the evaluation problem for a quantified Boolean formula of the form ∀X∃Y.φ where X and Y are two disjoint sets of variables and φ a formula in CNF over X and Y . Finally, for ΣP 2 the problem is to check whether ∀X∃Y.φ is false.

Abstract Argumentation. We use Dung's argumentation framework (1995) and consider only non-empty and finite sets of arguments A. An (argumentation) framework (AF) is a directed graph F = (A,R), where A is a set of arguments and R ⊆ A × A, consisting of pairs of arguments representing direct attacks between them. Let E ⊆ A and a ∈ A be an argument. Then we say that a is defended by E in F if for every (a′ , a) ∈ R, there exists a′′ ∈ E such that (a′′ , a′ ) ∈ R. The family defF (E) is defined by defF (E) := { a | a ∈ A, a is defended by E in F }. In abstract argumentation, one aims at computing so-called extensions, which are subsets E ⊆ A of the arguments that have certain properties. The set E of arguments is called conflictfree in E if (E × E) ∩ R = ∅; E is admissible in F if (1) E is conflict-free in F, and (2) every a ∈ E is defended by E in F. Let E+ R := E ∪ {a | (b, a) ∈ R, b ∈ E } and E be conflict-free. Then, E is (1) naive in F if no E′ ⊃ E exists that is conflict-free in F, and (2) stage in F if there is no conflict-free set E′ ⊆ A in F with E+ R ⊊ (E′ )+R . An admissible set E is (1) complete in F if defF (E) = E; (2) preferred in F, if no E′ ⊃ E exists that is admissible in F; (3) semi-stable in F if no admissible set E′ ⊆ A in F with E+ R ⊊ (E′ )+R exists; and (4) stable in F if every a ∈ A \ E is attacked by some a′ ∈ E. For a semantics σ ∈ {conf, naiv, adm, comp, stab, pref, semiSt, stag}, we write σ(F) for the set of all extensions of semantics σ in F . Let F = (A, R) be an AF. Then, the problem EXISTσ asks if σ(F) ̸= ∅. The problems cσ and sσ question for a∈A, whether a is in some E ∈ σ(F) ("credulously accepted") or every E ∈ σ(F) ("skeptically accepted"), respectively. We let Cσ (resp., Sσ) denote the set of all credulously (skeptically) accepted arguments under semantics σ. The complexity of AF reasoning is well-known, e.g., [Dvor´ak and Dunne, 2017].

3 Diversity in Abstract Argumentation

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

Definition 2. Let F = (A,R) be an AF, σ be a semantics and k ≥ 0 be an integer. For two sets S ⊆ A and T ⊆ A of arguments, we define by d(S, T) the distance between S and T . Formally, we let

We say that two extensions S, T ∈ σ(F) are k-diverse if d(S, T) = k. Moreover, for an extension S ∈ σ(F) and a set X, we say that S covers X if X ⊆ S.

We continue our example from above.

Example 3. Consider the AF from Example 1, its extensions, and their symmetric difference. We can see that one extension supports treatment X while another supports Y under 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 are k-diverse for some k ∈ 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 of k highlight that the two treatments differ only marginally, i.e., same medical reasoning, but different preference. In contrast, larger values of k depict two entirely different diagnostic strategies. Thus, in decision-making, higher diversity indicates deeper disagreement between choices. ◁

This consideration leads us to the following problem.

k-Div-Argσ(F, K, a, b)

Input:

an AF F , k ∈ N, and arguments a, b.

Question: does F admit two k-diverse σ-extensions

S and T such that a ∈ S, b ∈ T?

Note that we can extend k-Div-Argσ 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 two k-diverse σ-extensions for a given semantics σ. 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.

k-Div-Extσ(F, K)

Input:

an AF F and k ∈ N

Question: does F admit two non-empty k-diverse σ-extensions?

The k-Div-Extσ(F,K) problems immediately give rise to whether there are σ-extension that are at least/most k-diverse, which we abbreviate by ≥k-Div-Ext and ≤k-Div-Ext, respectively. Similarly, k-Div-Argσ(F,K, a, b) gives rise to ≥k-Div-Arg and ≤k-Div-Arg, respectively.

Finally, we define the problem to obtain the maximum k.

max-k-Div-Extσ(F, A, B)

Input: an AF F and sets A,B of arguments

Task: Output the maximum k for which A and

B are covered by k-diverse extensions.

Similarly, we can define the corresponding minimization task min-k-Div-Extσ(F, A, B).

(a) Stable 4 and 6-diversity and admissible 1-3 and 5-diversity.

Figure 2: Example AFs showing different levels of diversity.

Levels of Diversity. It could be that some arguments are k-diverse and k′ -diverse for some k′ < k ∈ N without being ℓ-diverse for any k′ ≤ ℓ ≤ k. We illustrate how an AF might have different levels of diversity among its extensions.

Example 4. Consider the AF F1 = (A,R) as depicted in Figure 2a. F1 admits the following stable sets E1 = {a, e, f}, E2 = {b, e, g}, E3 = {a, d, g}, and E4 = {c, d, f}. The pair-wise symmetric difference of these sets yield diversity values in {4, 6}. In particular F1 does not admit k-diverse stable extensions for any k ∈ {1, 2, 3, 5}. When considering admissible semantics, F1 additionally admits the following singleton {e}, {d}, {g}, {f}, and two-element extensions {e, g}, {e, f}, {d, g}, and {d, f}. Here, it can be seen that under admissible semantics, F1 also admits diversity values of 1 (due to extensions {e}, {e, f}), 2 (due to {e}, {d}), and 3 (due to {e}, {d, f}). Finally, by considering sets {a, e, f} and {d, g}, we also obtain two 5-diverse adm-extension.

Next, consider the AF F2 = (A, R) as depicted in Figure 2b. The AF F2 admits the admissible sets E1 = {a, c}, E2 = {e, g}, E3 = {f, h}, E4 = {a, c, f, h}, and E5 = {a, c, e, g}. The pair-wise symmetric difference of these sets yield diversity values in {2, 4, 6}. Notable, there are neither 3-diverse nor 5-diverse adm-extensions. ◁

4 Complexity of Reasoning about Diversity

We first consider the complexity of deciding whether an AF admits two k-diverse extensions (k-Div-Extσ) for a semantics σ, or whether additionally contains two arguments in the question (k-Div-Argσ). Moreover, we also consider the complexity of deciding whether an AF admits some diversity level above, or below k, i.e., ≥k-Div-Argσ and ≤k-Div-Argσ, respectively. Finally, we consider analogous problems ( ≥k-Div-Extσ and ≤k-Div-Extσ) 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 5 ([Dvor´ak and Dunne, 2017]). Let φ := ∧mi=1 Ci, be a CNF-formula where each Ci is a clause. Consider the AF Fφ = (A, R) constructed as follows:

We call Fφ the argumentation framework of φ generated via the standard translation for admissible semantics.

Then, φ is satisfiable iff the argument φ is credulously accepted in Fφ under semantics σ ∈ {adm, comp, stab}.

Above, Below, and Exact k Diversity

The problem k-Div-Argσ(F, k, a, b) asks: given two arguments a and b in an AF F = (A,R) and a number k ∈ N, are there two σ-extensions S1, S2 with a ∈ S1, b ∈ S2, and d(S1, S2) = 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 k-Div-Extσ(F, k, a, b) asking: given an AF F = (A, R) and a number k ∈ N, are there two σ-extensions S1, S2 with d(S1, S2) = k?

4.1 Conflict-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 below k diversity) and in fact both semantics incur different complexity in those cases (under reasonable complexity assumptions).

Theorem 6 (⋆). The problems k-Div-Argσ and ≥k-Div-Argσ are NP-complete for σ ∈ {conf, naiv}.

Proof. For membership, one guesses two witness sets Sa, Sb ⊆ A such that (i) Sa and Sb are σ-extension, (ii) a ∈ Sa, b ∈ Sb, and (iii) d(Sa, Sb) = k. The verification requires polynomial time for each σ ∈ {conf, naiv}. For naive, one checks conflict-freeness and additionally that adding any argument not in the set breaks the conflict-freeness. For ≥k-Div-Argσ, we substitute (iii) by d(Sa, Sb) ≥ k.

For hardness, we reduce from the canonical NP-complete problem 3SAT. Here, the reduction in Definition 5 can not be directly used as it is based on the notion of admissibility, which both semantics σ ∈ {conf, 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≤m Ci where each Ci = (ℓi1 ∨ ℓi2 ∨ ℓi3) is a clause with three literals over the set X of variables. In our AF, we only require symmetric edges. Hence we find it convenient to write {u, v} for two attacks (u, v) and (v, u). We construct an AF F = (A, R) where:

for fresh arguments a, b ̸∈ X. Moreover, we let k = m+ 2. Here, we observe that {b} is a naive and hence also a conflictfree set in F. Intuitively, we let each position of a literal in a clause as an argument thus resulting in three arguments for each clause of φ. 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 7 (⋆). Arguments a and b are (m+ 2)-diverse in F iff formula φ is satisfiable.

We conclude by observing that the presented reduction also applies to the problem that asks above k diverse extensions covering a and b, that is, to ≥k-Div-Argσ.

Next, we consider the problem of (general) k-diverse extensions in an AF (hence, to determine whether an AF admits two at least k-diverse extensions). The reduction in the proof above does not apply directly as F may have two σ extensions only coming from the arguments in triangles. This has the consequence that φ might not be satisfiable but still F has two k-diverse extensions. Luckily, we can still utilize the ideas and expand our reduction to obtain the following.

Theorem 8. The problems k-Div-Extσ and ≥k-Div-Extσ are NP-complete for σ ∈ {conf, naiv}.

Proof. For membership, guess two witness sets as before.

For hardness, we reuse the reduction from the proof of Theorem 6. The intuition why the same reduction may fail is the following. An AF F might have two small conflictfree/naive sets such that they give jointly a diversity of k. However, we are looking for one satisfying assignment for all the m clause in φ. To overcome this issue, we duplicate each argument in F and ask for a larger diversity value instead.

Let F = (A,R) be the AF constructed in the proof of Theorem 6 for a formula φ with m clauses. Here, we do not need arguments a and b, hence our arguments set A and attacks in R does not include these auxiliary arguments. As before, we only consider symmetric edges in our AF and write {u, v} for attacks. We consider an AF F ′ = (A′ , R′ ) where

Intuitively, each argument s now has a shadow vertex s∗ which participates in all the edges as s. Additionally, s∗ also have edges to the shadow vertices of each neighbor t of s in F . This encodes that whenever a set S ⊆ A is conflict-free in F ′ , then its shadow set S∗ = {s∗ | s ∈ S} is also conflict-free whereas neither S ∪{t∗} nor S∗ ∪{t} is conflict-free for any t ∈ S and its shadow t∗ ∈ S∗, respectively. Moreover, in this case, the set S \{t}∪{t∗} and S∗ \{t∗}∪{t} are both still conflict-free in F ′ . We first prove this claim in the following. For brevity, we denote ℓ∗ = a∗ if ℓ = a and ℓ∗ = a for ℓ = a∗ (intuitively, the shadow of a shadow argument is the argument).

Claim9 (⋆). (I) S is conflict-free (naive) in F ′ iff S∗ is conflictfree (naive) in F ′ for any S ⊆ A. (II) For any conflict-free set L ⊆ A′ and ℓ ∈ L: the sets (L \ {ℓ}) ∪ {ℓ∗} is also conflict-free.

We next prove the correctness via the following claim.

Claim 10 (⋆). φ is satisfiable if and only if F admits two σ-extensions which are 2m-diverse for σ ∈ {conf, naiv}.

We conclude by observing that the reduction also applies to ≥k-Div-Extσ for both semantics σ ∈ {cnf, naiv}.

We next turn to the problem of asking whether two arguments are below k diverse. Here, the hardness holds only for naive semantics as we establish next. Observe that the reduction from before does not apply here as in Claim 3: a "small" naive set in F may yield two above-k-diverse extensions for a and b while the corresponding literals still do not satisfy all the clauses (e.g., when a witness naive set for a has size < m). In fact, this also explains why the hardness does not apply to the conflict-free semantics.

Theorem 11. The problem ≤k-Div-Argnaiv is NP-complete.

Proof. For membership, guess two witness sets as before.

For hardness, we reduce from the dominating set problem. Given a graph G = (V, E) and an integer k ∈ N: the question asks whether there are k vertices S ⊆ V such that for every vertex v ∈ V , either v ∈ S or there exists u ∈ S with {u, v} ∈ E. We consider an AF F = (A, R) with symmetric attacks where, for fresh a, b ̸∈ V : A := V ∪ {a, b},

Then, we prove the following claim:

Claim 12 (⋆). G admits a dominating set of size k iff arguments a, b are below (k + 2)-diverse in F (naive semantics).

The reduction does not work for conflict-free semantics, but turns out to be trivial as any two non-self-attacking arguments are trivially below k-diverse for any 2 ≤ k ∈ N.

Remark 13. Let F = (A,R) be an AF and a, b ∈ A be two arguments such that none of these arguments have a selfattack. Then, considering conflict-free semantics a and b are at least (≥) 2-diverse iff either (a, b) ∈ R or (b, a) ∈ R. Thus, any two arguments in an AF (without self-attacks) are trivially (below) k-diverse for any k ̸= 1. The answer for k = 1 depends on whether two arguments are conflicting. In fact, no two conflicting arguments can be 1-diverse in any AF.

4.2 Admissible, Complete, and Stable Semantics

We now consider semantics σ ∈ {adm, comp, stab} and prove that the complexities are similar to credulous reasoning. That is, reasoning on diverse arguments and extensions does not incur additional complexity compared to argument acceptance.

Theorem 14 (⋆). Problems k-Div-Argσ, ≥k-Div-Argσ, and ≤k-Div-Argσ are NP-complete for σ ∈ {adm, comp, stab}.

Details are given in the appendix, as we mostly adapt standard reductions. We next establish that the problem with diverse extensions admits the same complexity.

Theorem 15 (⋆). Problems k-Div-Extσ, ≥k-Div-Extσ, and ≤k-Div-Extσ are NP-complete for σ ∈ {adm, comp, stab}.

NP-hardness for preferred semantics follows from admissible semantics. However, we do not have membership, as preferred extensions cannot be verified in polynomial time.

4.3 Semi-stable, Stage, and Preferred Semantics

The following lemma is essential for proving claims regarding semi-stable and stage semantics. Let F = (A, R) and a, b ∈ A be two arguments. We say that a and b are R-equivalent in F if they have identical attacks in F, i.e., if (a, c) ∈ R ⇐⇒ (b, c) ∈ R and (c, a) ∈ R ⇐⇒ (c, b) ∈ R for any c ∈ A.

Lemma 16 (⋆). Let F = (A, R) be an AF and a, b ∈ A be two R-equivalent arguments in F ; for any S ⊆ A with a ∈ S:

1. S is conflict-free (admissible) in F iff (S \ {a}) ∪ {b} is conflict-free (admissible) in F.

Theorem 17. The problems k-Div-Argσ, ≥k-Div-Argσ and ≤k-Div-Argσ are ΣP 2 -complete for σ ∈ {semiSt, stag}.

Proof. For membership, observe that one can guess two sets of arguments Sa, Sb ⊆ A and verify that both are σ-extensions, k-diverse, and contain a and b, respectively. The verification for σ-extensions requires an NP oracle to decide rangemaximality. Moreover, the same also applies to extensions with diversity ≤ k and ≥ k.

We next turn to prove hardness. To this aim, we utilize an existing reduction by [Dvoˇr´ak and Woltran, 2010] proving credulous acceptance under both considered semantics. Given a QBF Φ = ∀Y ∃Z.φ where φ := ∧mi=1 Ci is a CNF-formula with clauses Ci over variables X = Y ∪Z. We let Y∗ = {y∗ | y ∈ Y } and ¯ Y∗ = {¯ y∗ | y ∈ Y } as auxiliary sets of arguments and consider the AF FΦ = (A, R) constructed as follows:

It is known that Φ is true iff φ is contained in each semi-stable (stage) extension of FΦ iff ¯ φ is not contained in any semistable (stage) extension of FΦ. To complete the reduction, we construct an AF F ′ = (A′ ,R′ ) by taking a fresh argument ¯ φc ̸∈ A, such that A′ := A∪ {¯ φc},

Intuitively, the argument ¯ φc serves as a copy of ¯ φ. Whereby, it is accepted in some σ-extension iff ¯ φ is accepted in some σ-extension for σ ∈ {semiSt, stag} due to Lemma 16. We prove correctness of our reduction in the following claim.

Claim 18 (⋆). Φ is false iff argument ¯ φ is contained in some σ-extension of FΦ for σ ∈ {semiSt, stag} iff arguments ¯ φ and ¯ φc are 2-diverse in F ′ under σ.

Note that the reduction in the proof above also applies to the case of ≤ k- and ≥ k-diverse arguments for σ ∈ {semiSt, stag}. This holds as one can still take k = 2.

For deciding diverse extensions, the reduction in the proof of Theorem 17 does not directly apply for σ ∈ {semiSt, stag}. This holds due to the following issue: when the CNF φ in Φ is satisfiable, FΦ already admits a σ-extension of size |X| + 1 where X = Y ∪ Z and hence |X| > |Y |. It might happen that Φ admits two satisfying assignments which only differ at one literal. Thus, their corresponding σ-extensions also differ at only one argument and hence are 2-diverse. Nevertheless, we can expand our reduction to consider sufficiently many copies of the argument ¯ φ in F to avoid this case. The proof of the following theorem formalizes this intuition. Interestingly, this trick with multiple copies does not work in the case of ≤k-Div-Extσ. This holds since smaller than k diversity is already achievable via any satisfying assignments for φ.

Theorem19 (⋆). The problems k-Div-Extσ and ≥k-Div-Extσ are ΣP 2 -complete for semantics σ ∈ {semiSt, stag}.

We next turn towards preferred semantics which possesses the same complexity, modulo a different reduction.

Theorem 20 (⋆). The problem k-Div-Argpref and ≤k-Div-Argpref are both ΣP 2 -complete.

However, the precise complexity of ≥k-Div-Argpref is open. The issue why the above reduction does not work for ≥k-Div-Argpref is the following. If φ is satisfiable, one can construct an extension containing ¯b from a satisfying assignment, of size |X| + 2, which together with {b} gives two (|X| + 3)-diverse extensions which is above k anyway.

We also extablish the complexity for k-diverse extensions.

Theorem 21 (⋆). The problem k-Div-Extpref is ΣP 2 -complete.

4.4 Maximal Diversity

Finally, we compute the threshold for maximum diversity. Precisely, we ask whether an AF has k-diverse σ-extensions (for a pair of arguments) but not k′ -diverse for any k′>k.

We reduce SAT-UNSAT (for QBF) to the considered semantics by encoding two formulas into one AF and choosing a diversity threshold K that separates them. The construction ensures that the AF has two k-diverse extensions iff the first formula is satisfiable (true), and no k′ -diverse extensions for k′ > k iff the second formula is unsatisfiable (false).

Theorem 22 (⋆). The problem max-k-Div-Extσ is DPcomplete for each σ ∈ {conf, naiv}.

We next prove that the argument version of the diversity problem is also DP-complete for σ ∈ {conf, naiv}. Our construction works similar as in the proof of Theorem 22.

Theorem 23 (⋆). The problem max-k-Div-Argσ is DPcomplete for each σ ∈ {conf, naiv}.

Next, we consider the connection between extensions.

Lemma 24 (⋆). Let F1 = (A1,R1), F2 = (A2,R2) be two mutually disjoint AFs, and let F = (A1 ∪ A2,R1 ∪ R2). Then, for each semantics σ and sets Si ⊆ Ai: S1 ∪ S2 is a σ-extension in F iff Si is a σ-extension in Fi for i = 1, 2.

By Lemma 24, when considering disjoint AFs, their extensions are sub-extensions in the individual sub-AFs.

We next establish that the argument version of the diversity problem is DP-complete for σ ∈ {adm, comp, stab}.

Theorem 25 (⋆). The problem max-k-Div-Argσ is DPcomplete for each σ ∈ {adm, comp, stab}.

Also the extension-version of the problem is DP and DP2-c.

Theorem 26 (⋆). The problemmax-k-Div-Extσ is

1. DP-complete for each σ ∈ {adm, comp, stab} and
2. DP2-complete for semantics σ ∈ {semiSt, stag}.

A Note On Minimal Diversity. Since diversity is neither monotonic, nor monotonic, the problem of determining the smallest k for which an AF admits two k-diverse σ-extensions is not complementary to its maximum counterpart. Moreover, our hardness-reductions in Section 4.4 does not immediately extend to the case of minimal diversity.

5 Experiments

To investigate practical feasibility of diversity, we implemented our approach and conducted experiments.

Implementation. We base our implementation on an ASPencoding and the argumentation solver ASPARTIX [Egly et al., 2008; Egly et al., 2010; Dvor´ak et al., 2021] for rapid prototyping. Our encoding computes, given an AF F, two extensions that are the minimally or maximally k-diverse in F . The core computational component of our approach is an ASP encoding implementing the proposed diversity computation, which we solve using clingo (5.8.0). We place a simple wrapper to orchestrate the experiments, and collect runtime and optimization statistics. For each instance and semantics, we record the runtime required to solve the corresponding optimization problem, as well as the resulting diversity value k. We consider both the maximal and minimal diversity variants.

Instances and Setup. As benchmark data, we use AFs from the ICCMA 2025 benchmark suite. For each benchmark instance, we evaluate the proposed diversity computation under the admissible, complete, and stable semantics. Each run was subject to a fixed timeout of 300 seconds. Our analysis focuses on instances for which an optimal solution was found within the given timeout. To avoid the influence of a small number of extremely large AFs, we further restrict the evaluation to AFs with at most 1000 arguments, leaving us with 270 instances. We conduct the experiments on a desktop machine equipped with an Intel i9-11900K CPU running Windows 10, which is sufficient as we are primarily interested in obtaining the maximum k and minimum k for the considered frameworks.

Result. In total, we evaluated 270 instances, each under three semantics. Among these, 145 instances reached optimality within the timeout under at least one semantics, while the remaining instances either where unsatisfiable or exceeded the time limit under all semantics. Table 2 provides a summary of the results aggregated over all instances in this range, reporting the average and median diversity values, as well as the average runtime per semantics, for both maximal and minimal variants. To analyze how the minimum and maximum diversity distributes, we provide Figure 3 that plots per instance (X-axis) the min (orange), max (blue), and median (dashed green) k-diversity value (Y-axis).

Discussion. The experimental results reveal characteristic patterns in how diversity values are distributed under the considered semantics. Figure 3 shows that, diversity values vary substantially across instances, indicating that the structure of extensions can differ markedly even within the same AF. In particular, the instance-wise distribution reveals that for a large portion of instances, extensions remain relatively close to each other, while a smaller set of instances admits extensions that are structurally far apart. This suggests that high diversity is not uniformly present, but rather concentrated in specific frameworks that allow for fundamentally different solutions. Distributions for further semantics are in the appendix.

6 Conclusion

We introduce a quantitative notion of extension diversity for abstract argumentation based on symmetric difference, which makes explicit how strongly alternative, internally coherent viewpoints in an AF diverge. We provide a comprehensive complexity classification for reasoning about existence of kdiverse extensions, diversity covering specific arguments, and optimization variants. We implement a k-diversity computation and conduct an initial experimental study, which indicates practical feasibility for medium-sized frameworks.

For future work, we are interested in completing the complexity landscape for open cases (e.g., for minimal k-diversity). To tame the high complexity, one could consider parameterized complexity or structure-aware encoding into Boolean satisfiability [Fichte et al., 2021; Mahmood et al., 2026]. Moreover, we propose diversity as a useful measure to consistent query answering in data- or knowledge-bases, following the natural connections to argumentation [Mahmood et al., 2024; Mahmood et al., 2025]. Finally, extending the diversity notion to logic-based argumentation [Mahmood et al., 2023; Hecher et al., 2024] is another venue for future work. Finally we are interested in applications and use-cases of diversity to check disagreement and robustness of real-world instances.

Acknowledgments

Authors are stated in alphabetical order. This research was funded in whole or in part by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation), grant TRR 318/3 2026 - 438445824 and the Ministry of Culture and Science of North Rhine-Westphalia (MKW NRW) within projects WHALE (LFN 1-04) funded under the Lamarr Fellow Network programme and project SAIL, grant NW21-059D, the Austrian Science Fund (FWF) grant J4656, the French Agence nationale de la recherche (ANR) grant ANR-25-CE23-7647; and Excellence Center at Link¨oping - Lund in Information Technology (ELLIIT) funded by the Swedish government and the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.