pith. sign in

arxiv: 2605.13332 · v1 · pith:UKLSWFULnew · submitted 2026-05-13 · 💻 cs.AI · cs.CC

Diversity of Extensions in Abstract Argumentation

Johannes K. Fichte , Markus Hecher , Yasir Mahmood , Zhengjun Wang This is my paper

Pith reviewed 2026-05-14 19:07 UTC · model grok-4.3

classification 💻 cs.AI cs.CC
keywords abstract argumentationextensionsdiversitysymmetric differencecomputational complexityargumentation frameworksreasoning
0
0 comments X

The pith

Argumentation frameworks can quantify diversity among their extensions using symmetric difference between the sets.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines a quantitative measure of diversity for the extensions of an abstract argumentation framework based on the symmetric difference of the sets. This distinguishes cases where different accepted viewpoints differ only slightly from those where they are fundamentally incompatible. The authors classify the computational complexity of deciding if k-diverse extensions exist, whether such extensions cover specific arguments, and finding the maximum diversity level. Standard reasoning tasks ignore this spread, which matters for applications where the range of possible outcomes affects robustness or choice.

Core claim

We introduce a quantitative notion of diversity of extensions based on the symmetric difference and provide a systematic complexity classification. We study whether an AF admits k-diverse extensions, admits k-diverse extensions covering specific arguments, and computing the largest k for which an AF admits k-diverse extensions. A prototype is outlined with an evaluation for computing diversity levels.

What carries the argument

Diversity measure for extension sets defined via symmetric difference, used to decide existence of k-diverse sets and compute maximum k.

Load-bearing premise

Symmetric difference between sets of arguments meaningfully captures whether extensions represent marginally or fundamentally different viewpoints.

What would settle it

An experiment where two extensions with small symmetric difference are judged by domain experts as representing fundamentally incompatible viewpoints.

read the original abstract

Argumentation is an important topic of AI for modelling 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 for which an AF admits k-diverse extensions. We outline a prototype and provide an evaluation for computing diversity levels.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces a quantitative notion of diversity among extensions in abstract argumentation frameworks (AFs), defined via the symmetric difference of sets of arguments. It claims a systematic complexity classification for three problems: deciding existence of k-diverse extensions, deciding existence of k-diverse extensions that cover specified arguments, and computing the maximum diversity level. The authors also outline a prototype implementation and report on its evaluation.

Significance. If the complexity results hold, the work supplies a concrete, computable metric for distinguishing marginally versus fundamentally different extensions, which is a useful addition to standard qualitative reasoning in abstract argumentation. The classification of the three decision/computation problems provides guidance for algorithm design in applications that require diverse viewpoints (e.g., multi-agent decision support). The prototype and evaluation constitute a modest but positive step toward reproducibility and practical assessment.

major comments (2)
  1. [Definition of diversity (early sections)] The central modeling choice—taking (minimum) symmetric difference as the quantitative proxy for diversity—is load-bearing for all subsequent complexity claims, yet the manuscript provides no justification, comparison to alternatives (e.g., attack-weighted Hamming distance or distance to the grounded extension), or sensitivity analysis. This renders the headline classification specific to the chosen metric rather than to a general intuitive notion of viewpoint diversity.
  2. [Complexity classification sections] The abstract asserts a 'systematic complexity classification,' but the provided text contains no explicit statements of the hardness results, reductions, or proof sketches for the covering variant or the maximization problem. Without these details, it is impossible to verify whether the reductions are tight or whether they correctly inherit from known AF complexity results.
minor comments (2)
  1. [Abstract and evaluation section] The abstract states that a prototype is outlined and an evaluation is provided, but supplies no information on the benchmark AFs (size, density, semantics used), the range of k values tested, or the observed running times; these details are needed to assess practical relevance.
  2. [Notation throughout] Notation for argumentation frameworks, extensions, and the diversity function should be introduced once and used consistently; minor inconsistencies in variable naming appear in the abstract.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive review and positive assessment of the significance of our work on diversity of extensions in abstract argumentation. We address each major comment point by point below, indicating the revisions we will make to strengthen the manuscript.

read point-by-point responses

  1. Referee: [Definition of diversity (early sections)] The central modeling choice—taking (minimum) symmetric difference as the quantitative proxy for diversity—is load-bearing for all subsequent complexity claims, yet the manuscript provides no justification, comparison to alternatives (e.g., attack-weighted Hamming distance or distance to the grounded extension), or sensitivity analysis. This renders the headline classification specific to the chosen metric rather than to a general intuitive notion of viewpoint diversity.

    Authors: We agree that the manuscript would be strengthened by a more explicit justification of the symmetric difference metric. In the revised version, we will add a dedicated paragraph in the introduction explaining why symmetric difference is a natural choice: it directly counts the arguments on which two extensions disagree, respects the set-based semantics of AFs, and forms a metric on the power set. We will also include a brief comparison to alternatives such as attack-weighted Hamming distance and distance to the grounded extension, discussing their relative merits for capturing fundamental versus marginal differences in viewpoints. In addition, we will incorporate a short sensitivity discussion in the evaluation section showing how diversity values respond to small changes in the AF. revision: yes

  2. Referee: [Complexity classification sections] The abstract asserts a 'systematic complexity classification,' but the provided text contains no explicit statements of the hardness results, reductions, or proof sketches for the covering variant or the maximization problem. Without these details, it is impossible to verify whether the reductions are tight or whether they correctly inherit from known AF complexity results.

    Authors: The main theorems stating the complexity results for existence of k-diverse extensions, the covering variant, and the maximization problem appear in Section 4, with full proofs in the appendix. To improve accessibility, we will insert concise proof sketches into the main text of the complexity section. These sketches will explicitly describe the reductions (e.g., from standard extension existence for the covering problem and from known #P-hard problems for maximization) and note how they inherit tightness from established AF complexity results, thereby making the systematic classification fully verifiable without requiring the reader to consult the appendix. revision: yes

Circularity Check

0 steps flagged

No circularity: diversity defined from standard set operation with independent complexity analysis

full rationale

The paper defines its diversity notion directly via the standard symmetric difference on extension sets, a fixed mathematical operation with no dependence on fitted parameters, self-referential equations, or prior author results. Complexity results for k-diverse extensions, covering problems, and maximum diversity are then derived as standard analyses of the resulting decision/optimization problems. No load-bearing step reduces by construction to the inputs; the modeling choice is explicit and external to any derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Relies on standard definitions of argumentation frameworks and extensions from prior literature; no free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Standard definition of argumentation frameworks as directed graphs and extensions satisfying conflict-free and acceptability conditions
    Invoked implicitly when defining diversity over extensions

pith-pipeline@v0.9.0 · 5445 in / 976 out tokens · 22987 ms · 2026-05-14T19:07:06.448110+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

54 extracted references · 54 canonical work pages

  1. [1]

    and Hecher, Markus and Nadeem, Mohamed A

    Fichte, Johannes K. and Hecher, Markus and Nadeem, Mohamed A. , booktitle =. Plausibility Reasoning via Projected Answer Set Counting - A Hybrid Approach , year =. doi:10.24963/ijcai.2022/363 , editor_off =

    work page doi:10.24963/ijcai.2022/363 2022

  2. [2]

    Answer-set programming encodings for argumentation frameworks , url =

    Uwe Egly and Sarah Alice Gaggl and Stefan Woltran , bibsource =. Answer-set programming encodings for argumentation frameworks , url =. 2010 , bdsk-url-1 =. doi:10.1080/19462166.2010.486479 , journal =

    work page doi:10.1080/19462166.2010.486479 2010

  3. [3]

    CoRR , title =

    Wolfgang Dvor. CoRR , title =. 2021 , bdsk-url-1 =. 2109.03166 , eprinttype =

    work page arXiv 2021

  4. [4]

    2018 , bdsk-url-1 =

    Alviano, Mario , booktitle =. 2018 , bdsk-url-1 =. doi:10.4230/OASIcs.ICLP.2017.2 , editor_off =

    work page doi:10.4230/oasics.iclp.2017.2 2018

  5. [5]

    Representing and comparing large sets of extensions of abstract argumentation frameworks , year =

    Rodrigues, Odinaldo , booktitle =. Representing and comparing large sets of extensions of abstract argumentation frameworks , year =. doi:10.1145/3297280.3297394 , isbn =

    work page doi:10.1145/3297280.3297394

  6. [6]

    Ranking Extensions in Abstract Argumentation , year =

    Kenneth Skiba and Tjitze Rienstra and Matthias Thimm and Jesse Heyninck and Gabriele Kern-Isberner , booktitle =. Ranking Extensions in Abstract Argumentation , year =. doi:10.24963/ijcai.2021/282 , editor =

    work page doi:10.24963/ijcai.2021/282 2021

  7. [7]

    On the computation of top-k extensions in abstract argumentation frameworks , year =

    Jabbour, Said and Raddaoui, Badran and Sais, Lakhdar and Salhi, Yakoub , booktitle =. On the computation of top-k extensions in abstract argumentation frameworks , year =

    work page

  8. [8]

    An introduction to argumentation semantics , volume =

    Baroni, Pietro and Caminada, Martin and Giacomin, Massimiliano , date-added =. An introduction to argumentation semantics , volume =. 2011 , bdsk-url-1 =. doi:10.1017/S0269888911000166 , journal =

    work page doi:10.1017/s0269888911000166 2011

  9. [9]

    Dunne and Wolfgang Dvo

    Paul E. Dunne and Wolfgang Dvo. Characteristics of multiple viewpoints in abstract argumentation , volume =. Artificial Intelligence , keywords =. 2015 , bdsk-url-1 =. doi:10.1016/j.artint.2015.07.006 , issn =

    work page doi:10.1016/j.artint.2015.07.006 2015

  10. [10]

    Abstract and Concrete Decision Graphs for Choosing Extensions of Argumentation Frameworks , year =

    Dauphin, J. Abstract and Concrete Decision Graphs for Choosing Extensions of Argumentation Frameworks , year =. COMMA , date-added =. doi:10.3233/978-1-61499-906-5-437 , pages =

    work page doi:10.3233/978-1-61499-906-5-437

  11. [11]

    NEXAS: A Visual Tool for Navigating and Exploring Argumentation Solution Spaces , volume_off =

    Raimund Dachselt and Sarah Alice Gaggl and Markus Kr. NEXAS: A Visual Tool for Navigating and Exploring Argumentation Solution Spaces , volume_off =. COMMA , date-added =. 2022 , bdsk-url-1 =. doi:10.3233/FAIA220146 , editor_off =

    work page doi:10.3233/faia220146 2022

  12. [12]

    Maximum Satisfiability , volume =

    Fahiem Bacchus and Matti J. Maximum Satisfiability , volume =. Handbook of Satisfiability , chapter =. 2021 , bdsk-url-1 =. doi:10.3233/FAIA201008 , editor =

    work page doi:10.3233/faia201008 2021

  13. [13]

    Structure-Guided Cube-and-Conquer for MaxSAT , year =

    Bannach, Max and Hecher, Markus , booktitle =. Structure-Guided Cube-and-Conquer for MaxSAT , year =

    work page

  14. [14]

    MaxSAT Evaluation 2024: Solver and Benchmark Descriptions , year =

    work page 2024

  15. [15]

    What does it take to enforce an argument? minimal change in abstract argumentation , year =

    Baumann, Ringo , booktitle =. What does it take to enforce an argument? minimal change in abstract argumentation , year =

    work page

  16. [16]

    Extension enforcement in abstract argumentation as an optimization problem , year =

    Coste-Marquis, Sylvie and Konieczny, S\'. Extension enforcement in abstract argumentation as an optimization problem , year =. IJCAI , date-added =

    work page

  17. [17]

    Finding similar/diverse solutions in answer set programming , volume =

    Thomas Eiter and Esra Erdem and Halit Erdogan and Michael Fink , date-added =. Finding similar/diverse solutions in answer set programming , volume =. 2013 , bdsk-url-1 =. doi:10.1017/S1471068411000548 , journal = tplp, number =

    work page doi:10.1017/s1471068411000548 2013

  18. [18]

    Finding diverse and similar solutions in constraint programming , year =

    Hebrard, Emmanuel and Hnich, Brahim and O'Sullivan, Barry and Walsh, Toby , booktitle =. Finding diverse and similar solutions in constraint programming , year =

    work page

  19. [19]

    , date-added =

    Ulbricht, Markus and Wallner, Johannes P. , date-added =. Strong Explanations in Abstract Argumentation , url =. 2021 , bdsk-url-1 =. doi:10.1609/aaai.v35i7.16805 , journal =

    work page doi:10.1609/aaai.v35i7.16805 2021

  20. [20]

    Explaining Semantics and Extension Membership in Abstract Argumentation , url =

    Philippe Besnard and Sylvie Doutre and Th. Explaining Semantics and Extension Membership in Abstract Argumentation , url =. Intelligent Systems with Applications , keywords =. 2022 , bdsk-url-1 =. doi:https://doi.org/10.1016/j.iswa.2022.200118 , issn =

    work page doi:10.1016/j.iswa.2022.200118 2022

  21. [21]

    Combining Voting and Abstract Argumentation to Understand Online Discussions , year =

    Bernreiter, Michael and Maly, Jan and Nardi, Oliviero and Woltran, Stefan , booktitle =. Combining Voting and Abstract Argumentation to Understand Online Discussions , year =

    work page

  22. [22]

    Explanation Semantics for Abstract Argumentation , volume_off =

    Beishui Liao and Leendert van der Torre , booktitle =. Explanation Semantics for Abstract Argumentation , volume_off =. 2020 , bdsk-url-1 =. doi:10.3233/FAIA200511 , editor_off =

    work page doi:10.3233/faia200511 2020

  23. [23]

    Saribatur and Johannes P

    Zeynep G. Saribatur and Johannes P. Wallner and Stefan Woltran , booktitle =. Explaining Non-Acceptability in Abstract Argumentation , year =. doi:10.3233/FAIA200179 , editor_off =

    work page doi:10.3233/faia200179

  24. [24]

    KR , date-added =

    Niskanen, Andreas and J. KR , date-added =. 2020 , bdsk-url-1 =. doi:10.24963/kr.2020/67 , month =

    work page doi:10.24963/kr.2020/67 2020

  25. [25]

    IJCAI , date-added =

    Argumentative. IJCAI , date-added =. 2021 , bdsk-url-1 =. doi:10.24963/ijcai.2021/600 , editor_off =

    work page doi:10.24963/ijcai.2021/600 2021

  26. [26]

    Argumentation in Artificial Intelligence , volume =

    Rahwan, Iyad , date-added =. Argumentation in Artificial Intelligence , volume =. 2007 , bdsk-url-1 =. doi:10.1016/j.artint.2007.05.001 , issn =

    work page doi:10.1016/j.artint.2007.05.001 2007

  27. [27]

    Egly, Uwe and Gaggl, Sarah Alice and Woltran, Stefan , booktitle =

    work page

  28. [28]

    Matthias Thimm and Federico Cerutti and Mauro Vallati , bibsource =. Fudge:. CoRR , timestamp =. 2021 , bdsk-url-1 =. 2109.03106 , eprinttype =

    work page arXiv 2021

  29. [29]

    The pyglaf argumentation reasoner

    Mario Alviano , bibsource =. The pyglaf argumentation reasoner. CoRR , timestamp =. 2021 , bdsk-url-1 =. 2109.03162 , eprinttype =

    work page arXiv 2021

  30. [30]

    Wallner , date-added =

    Matthias Thimm and Jean-Guy Mailly and Johannes P. Wallner , date-added =. International Competitions on Computational Models of Argumentation , year =

    work page

  31. [31]

    KR , booktitle_long =

    Niskanen, Andreas and J. KR , booktitle_long =. 2020 , bdsk-url-1 =. doi:10.24963/kr.2020/82 , month_off =

    work page doi:10.24963/kr.2020/82 2020

  32. [32]

    Quantitative Reasoning and Structural Complexity for Claim-Centric Argumentation , url =

    Johannes Klaus Fichte and Markus Hecher and Yasir Mahmood and Arne Meier , booktitle =. Quantitative Reasoning and Structural Complexity for Claim-Centric Argumentation , url =. 2023 , bdsk-url-1 =. doi:10.24963/IJCAI.2023/358 , pages =

    work page doi:10.24963/ijcai.2023/358 2023

  33. [33]

    Quantitative Claim-Centric Reasoning in Logic-Based Argumentation , url =

    Markus Hecher and Yasir Mahmood and Arne Meier and Johannes Schmidt , booktitle =. Quantitative Claim-Centric Reasoning in Logic-Based Argumentation , url =. 2024 , bdsk-url-1 =

    work page 2024

  34. [34]

    Dung's Argumentation Framework: Unveiling the Expressive Power with Inconsistent Databases , url =

    Yasir Mahmood and Markus Hecher and Axel. Dung's Argumentation Framework: Unveiling the Expressive Power with Inconsistent Databases , url =. AAAI , booktitle_long =. 2025 , bdsk-url-1 =. doi:10.1609/AAAI.V39I14.33651 , pages =

    work page doi:10.1609/aaai.v39i14.33651 2025

  35. [35]

    Computing Repairs Under Functional and Inclusion Dependencies via Argumentation , url =

    Yasir Mahmood and Jonni Virtema and Timon Barlag and Axel. Computing Repairs Under Functional and Inclusion Dependencies via Argumentation , url =. FoIKS , booktitle_long =. 2024 , bdsk-url-1 =. doi:10.1007/978-3-031-56940-1\_2 , pages =

    work page doi:10.1007/978-3-031-56940-1 2024

  36. [36]

    Decomposition-Guided Reductions for Argumentation and Treewidth , url =

    Johannes Klaus Fichte and Markus Hecher and Yasir Mahmood and Arne Meier , booktitle =. Decomposition-Guided Reductions for Argumentation and Treewidth , url =. 2021 , bdsk-url-1 =. doi:10.24963/IJCAI.2021/259 , editor =

    work page doi:10.24963/ijcai.2021/259 2021

  37. [37]

    Structure-Aware Encodings of Argumentation Properties for Clique-width , url =

    Yasir Mahmood and Markus Hecher and Johanna Groven and Johannes Klaus Fichte , booktitle =. Structure-Aware Encodings of Argumentation Properties for Clique-width , url =. 2026 , bdsk-url-1 =. doi:10.1609/AAAI.V40I23.39005 , pages =

    work page doi:10.1609/aaai.v40i23.39005 2026

  38. [38]

    Parameterized Complexity of Logic-based Argumentation in Schaefer's Framework , url =

    Yasir Mahmood and Arne Meier and Johannes Schmidt , doi =. Parameterized Complexity of Logic-based Argumentation in Schaefer's Framework , url =. 2023 , bdsk-url-1 =

    work page 2023

  39. [39]

    Fichte, Johannes K. and Fr. Facets in Argumentation: A Formal Approach to Argument Significance , year =. IJCAI , booktitle_long =. doi:10.24963/ijcai.2025/500 , editor_off =

    work page doi:10.24963/ijcai.2025/500 2025

  40. [40]

    Fichte and Markus Hecher and Arne Meier , date-added =

    Johannes K. Fichte and Markus Hecher and Arne Meier , date-added =. 2024 , bdsk-url-1 =. doi:10.1613/jair.1.16210 , journal = jair, title =

    work page doi:10.1613/jair.1.16210 2024

  41. [41]

    Argumentation-Based Recommendations: Fantastic Explanations and How to Find Them , year =

    Rago, Antonio and Cocarascu, Oana and Toni, Francesca , booktitle =. Argumentation-Based Recommendations: Fantastic Explanations and How to Find Them , year =

    work page

  42. [42]

    Using arguments for making and explaining decisions , volume =

    Amgoud, Leila and Prade, Henri , date-added =. Using arguments for making and explaining decisions , volume =. 2009 , bdsk-file-1 =

    work page 2009

  43. [43]

    Stockmeyer

    Stockmeyer, Larry J. , date-added =. The polynomial-time hierarchy , volume =. 1976 , bdsk-file-1 =. doi:10.1016/0304-3975(76)90061-X , issn =

    work page doi:10.1016/0304-3975(76)90061-x 1976

  44. [44]

    and Meyer, Albert R

    Stockmeyer, Larry J. and Meyer, Albert R. , booktitle =. Word problems requiring exponential time , year =. doi:10.1145/800125.804029 , editor_off =

    work page doi:10.1145/800125.804029

  45. [45]

    Complete Sets and the Polynomial-Time Hierarchy , volume =

    Wrathall, Celia , date-added =. Complete Sets and the Polynomial-Time Hierarchy , volume =. 1976 , bdsk-file-1 =. doi:10.1016/0304-3975(76)90062-1 , issn =

    work page doi:10.1016/0304-3975(76)90062-1 1976

  46. [46]

    2023 , bdsk-url-1 =

    Lohrey, Markus and Rosowski, Andreas , booktitle =. 2023 , bdsk-url-1 =. doi:10.4230/LIPIcs.ICALP.2023.134 , editor_off =

    work page doi:10.4230/lipics.icalp.2023.134 2023

  47. [47]

    Theories of computability , year =

    Nicholas Pippenger , publisher =. Theories of computability , year =

    work page

  48. [48]

    Adrian Bondy and Uppaluri S

    J. Adrian Bondy and Uppaluri S. R. Murty , publisher =. Graph Theory , year =

    work page

  49. [49]

    Handbook of Satisfiability - Second Edition , volume =

    work page

  50. [50]

    Artificial Intelligence 77(2), 321–357 (Sep 1995).https://doi.org/10.1016/0004-3702(94)00041-X , https://www.sciencedirect.com/science/article/pii/000437029400041X

    Dung, Phan Minh , date-added =. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n -person games , volume =. 1995 , bdsk-url-1 =. doi:10.1016/0004-3702(94)00041-X , issn =

    work page doi:10.1016/0004-3702(94)00041-x 1995

  51. [51]

    Combining voting and abstract argumentation to understand online discussions , year =

    Bernreiter, Michael and Maly, Jan and Nardi, Oliviero and Woltran, Stefan , journal =. Combining voting and abstract argumentation to understand online discussions , year =

    work page

  52. [52]

    Representative answer sets: Collecting something of everything , year =

    B. Representative answer sets: Collecting something of everything , year =. ECAI , pages =

    work page

  53. [53]

    Computational Problems in Formal Argumentation and their Complexity , url =

    Wolfgang Dvor. Computational Problems in Formal Argumentation and their Complexity , url =. J. Logics and their Applications , number =. 2017 , bdsk-url-1 =

    work page 2017

  54. [54]

    Complexity of semi-stable and stage semantics in argumentation frameworks , url =

    Wolfgang Dvo. Complexity of semi-stable and stage semantics in argumentation frameworks , url =. Information Processing Letters , number =. 2010 , bdsk-url-1 =. doi:https://doi.org/10.1016/j.ipl.2010.04.005 , issn =

    work page doi:10.1016/j.ipl.2010.04.005 2010