🤖 AI

Diversity of Extensions in Abstract Argumentation

This paper introduces a quantitative notion of extension diversity in abstract argumentation frameworks based on symmetric difference, provides a systematic complexity classification for related decision and optimization problems, and presents a prototype evaluation for computing diversity levels.

Original authors: Johannes K. Fichte, Markus Hecher, Yasir Mahmood, Zhengjun Wang

Published 2026-05-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Johannes K. Fichte, Markus Hecher, Yasir Mahmood, Zhengjun Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a complex puzzle, like deciding on a medical treatment or choosing a policy for a city. In the world of Artificial Intelligence, this is often modeled using Abstract Argumentation. Think of this as a giant map of ideas (called "arguments") where some ideas attack or contradict others.

Usually, when computers solve these puzzles, they find one or more "solutions" (called extensions). Each solution is a consistent set of ideas that can stand together without fighting each other. If there are multiple solutions, it means there are different valid ways to look at the same situation.

The Problem: "How different are these solutions?"
Until now, if a computer found three different solutions, it could tell you what they were, but it couldn't easily tell you how far apart they were.

Are Solution A and Solution B just slightly different (like choosing a red shirt vs. a blue shirt)?
Or are they completely incompatible (like choosing to eat a burger vs. deciding to starve)?

Existing methods couldn't measure this "distance" effectively.

The New Idea: Measuring "Diversity"
This paper introduces a new way to measure exactly how different these solutions are. The authors use a mathematical concept called Symmetric Difference.

The Creative Analogy: The "Swap" Count
Imagine you have two lists of groceries:

List A: Milk, Eggs, Bread, Apples.
List B: Milk, Eggs, Bread, Bananas.

To find the "diversity" between them, you look at what is in one list but not the other.

List A has Apples (List B doesn't).
List B has Bananas (List A doesn't).
They share Milk, Eggs, and Bread.

The "diversity score" here is 2 (Apples and Bananas). If the lists were identical, the score would be 0. If they shared nothing, the score would be the total number of items.

The authors apply this to their argument maps. They ask: "If we take two different valid viewpoints, how many arguments would we have to swap to turn one into the other?"

Low Diversity: The viewpoints are very similar; they mostly agree, just with minor tweaks.
High Diversity: The viewpoints are fundamentally different; they rely on completely different reasoning.

Why Does This Matter?
The paper uses a medical decision example (Figure 1 in the text).

Option X: Start Treatment X immediately.
Option Y: Start Treatment Y immediately.
Option W: Wait for more data.

The authors found that Option X and Option Y were very diverse (they shared almost no reasoning). However, Option X and Option W were less diverse (they shared some reasoning).
This helps decision-makers see the real trade-offs. If you only look at one solution, you might miss the fact that the other options are radically different. High diversity means deep disagreement; low diversity means near-consensus.

What Did They Actually Do?

Defined the Rules: They created a formal mathematical definition for this "diversity" score based on the symmetric difference.
Checked the Difficulty (Complexity): They analyzed how hard it is for a computer to find these diverse solutions.
- For some types of logic (semantics), finding the most diverse pair is very hard (mathematically speaking, it's "NP-complete" or even harder).
- For others, it's easier.
- They mapped out exactly how difficult these problems are for different scenarios (like "Is there a pair of solutions that are at least 5 steps apart?").
Built a Prototype: They wrote a computer program (using a tool called ASPARTIX) to actually calculate these diversity scores.
Tested It: They ran their program on hundreds of standard test cases (up to 1,000 arguments).
- Result: They found that for many cases, the solutions were actually quite close to each other (low diversity).
- However, for some specific, complex frameworks, the solutions were wildly different (high diversity).
- The program could calculate these scores in a reasonable amount of time (usually under a second or two for the test cases).

What They Did NOT Claim

They did not claim this will immediately cure diseases or solve political crises.
They did not claim this works for every single type of logic problem in the universe (they focused on specific "semantics" like "stable," "admissible," and "complete").
They did not provide a final, perfect algorithm for the hardest cases; they identified where the difficulty lies and left some "open cases" for future research.

In a Nutshell
This paper gives us a new "ruler" to measure how much different valid opinions disagree with each other in a logical system. It shows that while some disagreements are just minor tweaks, others are fundamental clashes, and we can now calculate exactly where the line is. They proved that calculating this is possible but can be computationally heavy, and they built a working tool to demonstrate it.

Technical Summary: Diversity of Extensions in Abstract Argumentation

Problem Definition

Abstract argumentation models reasoning through Argumentation Frameworks (AFs), represented as directed graphs where nodes are arguments and edges represent attacks. The semantics of an AF define "extensions"—sets of arguments that satisfy specific coherence conditions (e.g., conflict-freeness, admissibility, stability). While standard reasoning tasks determine the existence of extensions or the acceptance status of individual arguments (credulous or skeptical), they often fail to quantify the structural distance between these extensions. In scenarios involving negotiation or decision-making, understanding whether alternative viewpoints (extensions) are marginally different or fundamentally incompatible is crucial. Existing concepts, such as selecting representative viewpoints or counting extensions, do not explicitly measure the "diversity" or dissimilarity between entire extensions.

This paper addresses the gap by introducing a quantitative notion of extension diversity based on the symmetric difference ( $A \triangle B = (A \cup B) \setminus (A \cap B)$ ). The core problem is to determine whether an AF admits two extensions that differ by exactly $k$ arguments, at least $k$ arguments, or at most $k$ arguments, and to compute the maximum possible diversity ( $k_{max}$ ) for a given framework.

Methodology

The authors approach the problem through three main pillars: formal definition, computational complexity analysis, and experimental evaluation.

1. Formal Definitions

The diversity between two extensions $S$ and $T$ is defined as $d(S, T) = |S \triangle T|$ . The paper defines several decision and optimization problems:

$k$ -Div-Arg $_\sigma$ : Given arguments $a, b$ , do there exist two $\sigma$ -extensions $S, T$ such that $a \in S, b \in T$ , and $d(S, T) = k$ ?
$k$ -Div-Ext $_\sigma$ : Does the AF admit two $\sigma$ -extensions with distance $k$ ?
Variants: Problems are also defined for diversity $\ge k$ and $\le k$ , as well as optimization problems to find the maximum $k$ ($max$- $k$ -Div).

2. Complexity Analysis

The paper provides a systematic classification of the computational complexity for these problems across various semantics:

Conflict-free and Naive Semantics: The problems are generally NP-complete. Notably, while standard reasoning (e.g., extension existence) is polynomial for conflict-free semantics, determining diversity is NP-hard.
Admissible, Complete, and Stable Semantics: The complexity aligns with credulous acceptance, remaining NP-complete.
Semi-stable, Stage, and Preferred Semantics: These higher-level semantics increase the complexity to $\Sigma_2^P$ -complete for decision problems involving specific arguments and extensions.
Maximal Diversity: Determining the exact maximum diversity threshold is shown to be DP-complete for lower-level semantics and DP $_2$ -complete for semi-stable and stage semantics. This involves checking both the existence of a solution with diversity $k$ and the non-existence of solutions with diversity $> k$ .

The authors utilize reductions from standard complexity problems (3SAT, Dominating Set, SAT-UNSAT, and Quantified Boolean Formulas) to establish these hardness results.

3. Experimental Evaluation

A prototype implementation was developed using Answer Set Programming (ASP) and the solver ASPARTIX. The system computes minimal and maximal diversity values for AFs. Experiments were conducted on 270 instances from the ICCMA 2025 benchmark suite (restricted to frameworks with $\le 1000$ arguments) under admissible, complete, and stable semantics.

Key Contributions

Introduction of Symmetric-Difference Diversity: The paper formalizes a new metric for abstract argumentation that quantifies the disagreement between alternative viewpoints (extensions) rather than just their existence.
Comprehensive Complexity Landscape: The authors provide a thorough classification of the complexity of reasoning about diversity. They demonstrate that for certain semantics (conflict-free, naive), diversity reasoning is strictly harder than standard acceptance reasoning, while for others, it matches the complexity of credulous acceptance.
Prototype and Evaluation: The paper presents a working implementation and initial empirical results, showing that computing diversity levels is feasible for medium-sized frameworks, though runtime varies significantly based on the semantics and the specific diversity target (min vs. max).

Results

Complexity: The study reveals that diversity reasoning is not uniformly easy. For conflict-free semantics, it is NP-complete, contrasting with the polynomial-time solvability of standard extension existence. For semi-stable and stage semantics, the problem jumps to the second level of the polynomial hierarchy ( $\Sigma_2^P$ ).
Experimental Findings: The experiments indicate that diversity values vary substantially across instances. While many frameworks have extensions that are structurally close (low diversity), a subset admits extensions that are fundamentally different (high diversity). The average runtimes for computing maximal diversity were generally under 2 seconds for the tested instances, suggesting practical feasibility for medium-scale problems.
Non-Monotonicity: The authors note that diversity is neither monotonic nor anti-monotonic, meaning that adding arguments to a framework does not predictably increase or decrease the maximum diversity.

Significance and Claims

The paper claims that its primary contribution is making explicit how strongly alternative, internally coherent viewpoints in an AF diverge. By moving beyond simple acceptance or counting, this quantitative measure allows for a finer-grained analysis of argumentative situations.

The authors position this work as a tool for:

Negotiation and Decision Making: Identifying whether disagreements are superficial (low diversity) or fundamental (high diversity).
Robustness Analysis: High diversity implies low robustness of conclusions, as the framework supports radically different positions.
Future Directions: The authors modestly suggest that this notion could be extended to logic-based argumentation and applied to consistent query answering in knowledge bases, but they do not claim these applications are currently realized. They also identify open complexity cases (e.g., minimal diversity) and the potential for parameterized complexity approaches as future work.

The paper concludes that while the computational cost can be high for certain semantics, the ability to quantify the "distance" between viewpoints offers a valuable new dimension for analyzing abstract argumentation frameworks.