pith. sign in

arxiv: 2605.02024 · v1 · submitted 2026-05-03 · 💻 cs.AI

Tenability and Weak Semantics: Modeling Non-uniform Defense -- Extended Version

Uri Andrews , Luca San Mauro , John Spoerl This is my paper

Pith reviewed 2026-05-08 19:17 UTC · model grok-4.3

classification 💻 cs.AI
keywords abstract argumentationtenabilityweak semanticsdialogue gamesnon-uniform defenseadmissibilitycomputational complexityconflict-free sets
0
0 comments X

The pith

Tenability semantics let a proponent maintain an argument by adapting replies to each specific conflict-free attack rather than defending uniformly against all reasonable ones.

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

Standard weak semantics in abstract argumentation relax admissibility by ignoring incoherent attacks, yet still insist on a single defense set that works against every remaining attack at once. This paper argues that defensibility is often strategic, so the right reply can depend on which attack the opponent actually chooses. It therefore defines tenability through monotone commitment games in which the proponent and opponent alternate finite conflict-free moves, with the proponent winning if the designated argument survives every possible opponent line. Three graded variants—static tenability, tenability, and strong tenability—differ only in the obligations they place on each player. The resulting semantics separate from all previously studied weak semantics on the benchmark patterns of self-defeating attacks, floating assignments, and disjunctive reinstatement, and they yield precise complexity results: static tenability is Π₂ᵖ-complete while the other two are PSPACE-complete.

Core claim

Tenability formalizes the maintenance of a designated argument (or set) in a dialogue game where the opponent may present any conflict-free set of attacks and the proponent must respond without committing in advance to a uniform defense; the three variants differ in the monotonicity and commitment rules imposed on the players, and they provably handle self-defeating attacks, floating assignments, and disjunctive reinstatement differently from earlier weak semantics.

What carries the argument

Monotone commitment games over finite conflict-free moves, with graded obligations on the disputants that allow adaptive rather than uniform defense.

If this is right

  • An argument can remain tenable even when no single defense set defeats every possible reasonable attack.
  • The three variants produce distinct acceptance sets on the same framework when strategic adaptation is required.
  • Deciding static tenability lies in Π₂ᵖ while deciding tenability and strong tenability lies in PSPACE.
  • Tenability separates from all prior weak semantics precisely on self-defeating attacks, floating assignments, and disjunctive reinstatement.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Dialogue-game models of this kind could be used to simulate adaptive legal or policy debates where each side chooses its next move after seeing the opponent's concrete challenge.
  • The complexity jump from Π₂ᵖ to PSPACE suggests that practical implementations will need heuristics or approximations once frameworks exceed modest size.
  • Extending the games to allow probabilistic or weighted moves would test whether the non-uniformity insight survives when attacks carry degrees of strength.

Load-bearing premise

Defensibility is inherently strategic, so the appropriate reply depends on the opponent's specific line of attack and uniform defense against all reasonable arguments is too demanding.

What would settle it

A finite argumentation framework with a self-defeating attack or floating assignment in which the proponent wins the monotone commitment game by adapting replies yet is rejected by every defined tenability variant, or vice versa.

Figures

Figures reproduced from arXiv: 2605.02024 by John Spoerl, Luca San Mauro, Uri Andrews.

Figure 1
Figure 1. Figure 1: S: Self-Defeating Attack F: Floating Assignment U: Disjunctive Reinstatement arXiv:2605.02024v1 [cs.AI] 3 May 2026 view at source ↗
Figure 2
Figure 2. Figure 2: An argumentation framework E in which {a} is statically tenable, but not strongly tenable. example the argumentation framework E ( view at source ↗
Figure 3
Figure 3. Figure 3: An argumentation framework in which {a} is statically tenable, but not tenable. Proposition 4.1. Strong tenability implies ten￾ability; tenability implies static tenability. More￾over, each implication is strict. The strictness of these implications are given by the framework in view at source ↗
Figure 4
Figure 4. Figure 4: An AF demonstrating the need to play sets of arguments simultaneously. We end this portion of the investigation by clas￾sifying the complexity of each semantics. Theorem 4.6. For finite F: a. The problem of determining if A ⊆ F is stati￾cally tenable is ΠP 2 -complete. b. The problem of determining if A ⊆ F is tenable is P SP ACE-complete. c. The problem of determining if A ⊆ F is strongly tenable is P SP … view at source ↗
Figure 5
Figure 5. Figure 5: An argumentation framework with a set A, consisting of a along with all unattacked arguments, which is not statically tenable, yet every finite subset is statically tenable. 5 Comparison to other semantics Tenability departs radically from labeling-based, extension-based, and recursion-based semantics. There is no way to label arguments in, out, undec that coincides with our intuitions about tenability. Th… view at source ↗
Figure 6
Figure 6. Figure 6: The relations among weak semantics in finite argumentation frameworks. We remark that some of the refinements among semantics presented in Theorem 5.5 need not per￾sist in infinite argumentation frameworks. In fact, semantics such as weak admissibility fail to be well￾defined for arbitrary argumentation frameworks.2 We leave the project of mapping out the relations among weak semantics in the arbitrary set… view at source ↗
Figure 7
Figure 7. Figure 7: {a} is statically tenable, but a ∈ G+. Proof. Suppose A is strongly tenable. We show that A is 1-strongly tenable by giving a strategy for P ro in the 1-strong tenability game. Through￾out the strategy, at each stage, we will consider a position in the strong tenability game for A. We call this the simulated game. To avoid confusion between the choices of moves in the (simulated) strong tenability game for… view at source ↗
Figure 8
Figure 8. Figure 8: An Example H which encodes the QBF ∀x1∀x2∃x3[(x1 ∨ ¬x3) ∧ (¬x2 ∨ x3) ∧ x2] view at source ↗
Figure 9
Figure 9. Figure 9: Consecutive quantifiers of the same kind view at source ↗
Figure 10
Figure 10. Figure 10: Alternating quantifiers are joined directly. Further, we now argue that if ρ is false, then a is not tenable in H. The strategy is essentially as above, except in the tenability game we may not assume that P ro plays only single element exten￾sions. At turn s, P ro plays xi or ¬xi if • Qi = ∀; • For each j < i with Qj = ∃, P ro has already played xj or ¬xj ; • For each bj with j ≤ i and Qj = ∀, P ro has a… view at source ↗
read the original abstract

In Dung-style abstract argumentation, various semantics capture notions of acceptability of arguments. The admissibility semantics capture the notion that an argument can be consistently defended from any potential counterargument. Weak semantics often relax the demands of admissibility by restricting which counterarguments must be taken seriously (e.g., discounting self-defeating or otherwise incoherent attacks). Many prominent proposals for weak semantics remain extension-based in a stronger sense. While these semantics discount attacks from arguments which are considered unreasonable, they still require a uniform defense against all reasonable arguments, even if they are collectively inconsistent. This uniformity can be too demanding when defensibility is inherently strategic, and thus the appropriate reply depends on the opponent's line of attack. We introduce tenability, a family of dialogue-based semantics that formalize when a designated argument (or a set of arguments) can be maintained in debate by a proponent against any conflict-free attack which the opponent may present. The approach is motivated by three natural benchmark patterns: self-defeating attack, floating assignment, and disjunctive reinstatement, on which tenability behaves differently from all weak semantics previously considered in the literature. We define three variants -- static tenability, tenability, and strong tenability -- via monotone commitment games over finite conflict-free moves, differing in the obligations imposed on the disputants. We establish the relative strength of these notions, prove implications and separations with previously studied weak semantics, and we analyze computational complexity on finite frameworks: deciding static tenability is $\Pi^P_2$-complete, while deciding tenability and strong tenability is PSPACE-complete.

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

0 major / 3 minor

Summary. The manuscript introduces tenability, a family of dialogue-based semantics for Dung-style abstract argumentation frameworks. Tenability formalizes when a designated argument or set can be maintained by a proponent against any conflict-free sequence of attacks from an opponent, using monotone commitment games over finite moves. Three variants are defined—static tenability, tenability, and strong tenability—differing in the obligations placed on the disputants. The paper establishes that these variants are strictly ordered by strength, provides explicit counterexamples separating them from prior weak semantics on the benchmark patterns of self-defeating attack, floating assignment, and disjunctive reinstatement, and proves complexity results: static tenability is Π₂ᵖ-complete while tenability and strong tenability are PSPACE-complete.

Significance. If the formal development holds, the contribution is significant for providing a principled, game-theoretic model of non-uniform and strategic defense in argumentation. This directly addresses the limitation of uniform defense requirements in existing weak semantics when replies must adapt to the opponent's specific attack line. Credit is due for the explicit benchmark separations via counterexamples, the clean formalization via monotone commitment games that avoids hidden uniformity assumptions, and the complexity characterizations obtained through standard reductions, all of which support potential applications in computational argumentation systems.

minor comments (3)
  1. The abstract and introduction would benefit from a brief, self-contained example of one benchmark pattern (e.g., disjunctive reinstatement) immediately after stating the uniformity limitation, to make the motivation concrete before the formal definitions.
  2. In the sections presenting the three variants, the notation for commitment games and winning conditions could be accompanied by a small running example showing a single play sequence, to clarify how monotonicity and conflict-freeness interact in practice.
  3. The complexity section states the results via 'standard game reductions' but does not include a high-level sketch of the reduction for PSPACE-completeness; adding one sentence outlining the source problem and how conflict-free moves are preserved would improve readability without lengthening the paper.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their detailed summary of the manuscript and for the positive assessment of its contribution to modeling non-uniform defense in abstract argumentation. The recommendation for minor revision is appreciated. However, the major comments section of the report contains no specific points requiring response or clarification. Accordingly, we have identified no changes to incorporate at this stage.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper introduces tenability as a new family of dialogue-based semantics defined directly via monotone commitment games over finite conflict-free moves, with three variants (static, standard, strong) distinguished by explicit obligations on disputants. Properties such as relative ordering, separations from prior weak semantics (via counterexamples on the three benchmark patterns), and complexity results (Π₂ᵖ-complete and PSPACE-complete via standard game reductions) are established through direct formal proofs and constructions rather than any reduction to fitted parameters, self-citations, or prior results by the same authors. The development is self-contained: new definitions are motivated by benchmark patterns and shown to differ from existing work without any load-bearing step that collapses by construction to its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on standard domain assumptions of Dung-style argumentation frameworks and the novel definitions of tenability via commitment games; no free parameters or invented entities with independent evidence are apparent from the abstract.

axioms (1)
  • domain assumption Argumentation frameworks are finite sets of arguments with a binary attack relation.
    This is the standard setup for Dung-style abstract argumentation assumed throughout.
invented entities (1)
  • Tenability (and its static/strong variants) no independent evidence
    purpose: To capture non-uniform defense through dialogue-based commitment games.
    Newly defined concept introduced to address limitations of uniform defense.

pith-pipeline@v0.9.0 · 5583 in / 1184 out tokens · 53925 ms · 2026-05-08T19:17:25.511833+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

54 extracted references · 54 canonical work pages

  1. [1]

    Structure and Interpretation of Computer Programs

    Harold Abelson and Gerald Jay Sussman and Julie Sussman. Structure and Interpretation of Computer Programs. 1985

    work page 1985

  2. [2]

    Visual Information Extraction with Lixto

    Robert Baumgartner and Georg Gottlob and Sergio Flesca. Visual Information Extraction with Lixto. Proceedings of the 27th International Conference on Very Large Databases. 2001

    work page 2001

  3. [3]

    Brachman and James G

    Ronald J. Brachman and James G. Schmolze. An overview of the KL-ONE knowledge representation system. Cognitive Science. 1985

    work page 1985

  4. [4]

    Complexity results for nonmonotonic logics

    Georg Gottlob. Complexity results for nonmonotonic logics. Journal of Logic and Computation. 1992

    work page 1992

  5. [5]

    Hypertree Decompositions and Tractable Queries

    Georg Gottlob and Nicola Leone and Francesco Scarcello. Hypertree Decompositions and Tractable Queries. Journal of Computer and System Sciences. 2002

    work page 2002

  6. [6]

    Levesque

    Hector J. Levesque. Foundations of a functional approach to knowledge representation. Artificial Intelligence. 1984

    work page 1984

  7. [7]

    Levesque

    Hector J. Levesque. A logic of implicit and explicit belief. Proceedings of the Fourth National Conference on Artificial Intelligence. 1984

    work page 1984

  8. [8]

    On the compilability and expressive power of propositional planning formalisms

    Bernhard Nebel. On the compilability and expressive power of propositional planning formalisms. Journal of Artificial Intelligence Research. 2000

    work page 2000

  9. [9]

    Artificial Intelligence 77(2), pp

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

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

  10. [10]

    Chandra and Dexter C

    Chandra, Ashok K. and Kozen, Dexter C. and Stockmeyer, Larry J. , title =. 1981 , issue_date =. doi:10.1145/322234.322243 , journal =

    work page doi:10.1145/322234.322243 1981

  11. [11]

    Proceedings of the 20th Conference on Theoretical Aspects of Rationality and Knowledge (

    Uri Andrews and Luca San Mauro , title =. Proceedings of the 20th Conference on Theoretical Aspects of Rationality and Knowledge (. 2025 , doi =

    work page 2025

  12. [12]

    Artificial Intelligence , volume =

    Dung, Phan Minh , title =. Artificial Intelligence , volume =. 1995 , doi =

    work page 1995

  13. [13]

    Bench-Capon, Trevor J. M. and Dunne, Paul E. , title =. Artificial Intelligence , volume =. 2007 , doi =

    work page 2007

  14. [14]

    2009 , doi =

    Argumentation in Artificial Intelligence , publisher =. 2009 , doi =

    work page 2009

  15. [15]

    The Knowledge Engineering Review , volume =

    Baroni, Pietro and Caminada, Martin and Giacomin, Massimiliano , title =. The Knowledge Engineering Review , volume =. 2011 , doi =

    work page 2011

  16. [16]

    Artificial Intelligence , volume =

    Baroni, Pietro and Giacomin, Massimiliano , title =. Artificial Intelligence , volume =. 2007 , doi =

    work page 2007

  17. [17]

    Argumentation in Artificial Intelligence , editor =

    Baroni, Pietro and Giacomin, Massimiliano , title =. Argumentation in Artificial Intelligence , editor =. 2009 , doi =

    work page 2009

  18. [18]

    Handbook of Formal Argumentation , publisher =

    work page

  19. [19]

    IfCoLog Journal of Logics and Their Applications , volume =

    van der Torre, Leendert and Vesic, Srdjan , title =. IfCoLog Journal of Logics and Their Applications , volume =

    work page

  20. [20]

    and Tohm

    Bodanza, Gustavo A. and Tohm. Two Approaches to the Problems of Self-Attacking Arguments and General Odd-Length Cycles of Attack , journal =. 2009 , doi =

    work page 2009

  21. [21]

    and Tohm

    Bodanza, Gustavo A. and Tohm. Beyond Admissibility: Accepting Cycles in Argumentation with Game Protocols for Cogency Criteria , journal =. 2016 , doi =

    work page 2016

  22. [22]

    Proceedings of the

    Baumann, Ringo and Brewka, Gerhard and Ulbricht, Markus , title =. Proceedings of the

    work page

  23. [23]

    On the Complexity of Semantics Based on Weak Admissibility , journal =

    Dvo. On the Complexity of Semantics Based on Weak Admissibility , journal =. 2022 , doi =

    work page 2022

  24. [24]

    2021 , note=

    Weakly Complete Semantics Based on Undecidedness Blocking , author=. 2021 , note=

    work page 2021

  25. [25]

    and Giacomin, Massimiliano , title =

    Baroni, Pietro and Dunne, Paul E. and Giacomin, Massimiliano , title =. Artificial Intelligence , volume =. 2011 , doi =

    work page 2011

  26. [26]

    Proceedings of NAIC , pages =

    Verheij, Bart , title =. Proceedings of NAIC , pages =

    work page

  27. [27]

    Caminada, Martin W. A. and Carnielli, Walter A. and Dunne, Paul E. , title =. Journal of Logic and Computation , volume =. 2012 , doi =

    work page 2012

  28. [28]

    Vreeswijk, Gerard A. W. and Prakken, Henry , title =. Proceedings of JELIA , pages =. 2000 , publisher =

    work page 2000

  29. [29]

    Journal of Logic and Computation , volume =

    Prakken, Henry , title =. Journal of Logic and Computation , volume =. 2005 , doi =

    work page 2005

  30. [30]

    Logic Journal of the IGPL , volume =

    Caminada, Martin and Wu, Yining , title =. Logic Journal of the IGPL , volume =

    work page

  31. [31]

    Argumentation in Artificial Intelligence , editor =

    McBurney, Peter and Parsons, Simon , title =. Argumentation in Artificial Intelligence , editor =. 2009 , doi =

    work page 2009

  32. [32]

    , title =

    Horty, John F. , title =. Artificial Intelligence and Law , year =

    work page

  33. [33]

    New Weak Admissibility Semantics for Abstract Argumentation , booktitle =

    J. New Weak Admissibility Semantics for Abstract Argumentation , booktitle =

    work page

  34. [34]

    Katie Atkinson and Trevor J. M. Bench. Argumentation and Standards of Proof , booktitle =

    work page

  35. [35]

    Proceedings of the 11th International Conference on Artificial Intelligence and Law (ICAIL 2007) , pages =

    Henry Prakken and Giovanni Sartor , title =. Proceedings of the 11th International Conference on Artificial Intelligence and Law (ICAIL 2007) , pages =

    work page 2007

  36. [36]

    Gordon and Henry Prakken and Douglas Walton , title =

    Thomas F. Gordon and Henry Prakken and Douglas Walton , title =. Artificial Intelligence , volume =. 2007 , doi =

    work page 2007

  37. [37]

    Walton and Erik C

    Douglas N. Walton and Erik C. W. Krabbe , title =. 1995 , isbn =

    work page 1995

  38. [38]

    2014 , isbn =

    Douglas Walton , title =. 2014 , isbn =

    work page 2014

  39. [39]

    1997 , series =

    Henry Prakken , title =. 1997 , series =

    work page 1997

  40. [40]

    Legal Knowledge and Information Systems

    Henry Prakken and Giovanni Sartor , title =. Legal Knowledge and Information Systems. JURIX 2006: The Nineteenth Annual Conference , editor =. 2006 , isbn =

    work page 2006

  41. [41]

    Legal Evidence and Proof: Statistics, Stories, Logic , editor =

    Henry Prakken , title =. Legal Evidence and Proof: Statistics, Stories, Logic , editor =

    work page

  42. [42]

    Bex and Peter J

    Floris J. Bex and Peter J. van Koppen and Henry Prakken and Bart Verheij , title =. Artificial Intelligence and Law , volume =. 2010 , doi =

    work page 2010

  43. [43]

    Henry Prakken and Gerard A. W. Vreeswijk , title =. Handbook of Philosophical Logic , editor =. 2002 , doi =

    work page 2002

  44. [44]

    Argument & Computation , volume =

    Sanjay Modgil and Henry Prakken , title =. Argument & Computation , volume =. 2014 , doi =

    work page 2014

  45. [45]

    2022 , month =

    Blümel, Lydia and Ulbricht, Markus , booktitle =. 2022 , month =. doi:10.24963/kr.2022/7 , url =

    work page doi:10.24963/kr.2022/7 2022

  46. [46]

    2025 , eprint =

    Gustavo Bodanza , title =. 2025 , eprint =. doi:10.48550/arXiv.2511.09600 , url =

    work page doi:10.48550/arxiv.2511.09600 2025

  47. [47]

    International Journal of Intelligent Systems , volume=

    On bipolarity in argumentation frameworks , author=. International Journal of Intelligent Systems , volume=. 2008 , publisher=

    work page 2008

  48. [48]

    Dunne and Trevor J

    Paul E. Dunne and Trevor J. M. Bench. Coherence in finite argument systems , journal =. 2002 , url =. doi:10.1016/S0004-3702(02)00261-8 , timestamp =

    work page doi:10.1016/s0004-3702(02)00261-8 2002

  49. [49]

    Jech, Thomas , biburl =

    work page

  50. [50]

    Proceedings of

    Uri Andrews and Luca San Mauro , title =. Proceedings of. 2025 , publisher =

    work page 2025

  51. [51]

    A Principle-Based Analysis of Weakly Admissible Semantics , booktitle =

    J. A Principle-Based Analysis of Weakly Admissible Semantics , booktitle =. 2020 , doi =

    work page 2020

  52. [52]

    and Shelah, Saharon , title =

    Larson, Paul B. and Shelah, Saharon , title =. Mathematical Logic Quarterly , volume =. doi:https://doi.org/10.1002/malq.200610054 , abstract =

    work page doi:10.1002/malq.200610054

  53. [53]

    Bodanza, Gustavo and Tohmé, Fernando and Simari, Guillermo , year =

    work page

  54. [54]

    2017 , url=

    Argumentation semantics as formal discussion , author=. 2017 , url=

    work page 2017