In value-based argumentation, an audience's ordering of values decides which attacks succeed as defeats. In many settings the deciding factor is not the audience but the circumstances: the same attack may succeed at one procedural stage, or under one regulation, and fail at another. Context-dependent argumentation frameworks (CDAFs), a model we recently introduced, capture this directly: one attack relation and a defeat function that switches each attack on or off per context, so every context induces an ordinary Dung framework. This raises a reduction question: can one value assignment with per-context orderings reproduce the defeat function, collapsing the CDAF into a VAF? We present a polynomial-time decision procedure for this question and map the harder neighbouring problems, with upper bounds from NP to Σ3p. We also present a validated reference implementation and a measurement: representability is rare and falls fast with the number of contexts.
Figures & tables
Figure 1: The worked instance. Left: the attack relation R ; the dashed attack (x,y) is the only attack suppressed in some context. Right: the defeat function δ .
Problem
Semantics
Bound
Status
Cross-context acceptance (all classes)
grounded
in P
closed
Universal acceptance
preferred
Π2p -complete
closed
Indefensibility
preferred
coNP-complete
closed
Audience inducibility of R′⊆R
(defeat relation)
O(n+m)
closed
VAF-representability
(defeat function)
O(n2k+nmk)
closed
Single-context realisability
grounded
in NP
lower bound open
Table 1: Decision problems for a CDAF with n arguments, m attacks, and k contexts. Cross-context bounds follow from single-framework classifications Dvořák and Dunne (2018) with a factor k for iterating over contexts; the corresponding audience-dependent questions for VAFs are classified by Bench-Capon et al. (2007) .
k=1
k=2
k=3
k=4
n=3
54.9
10.5
1.51
0.18
n=4
20.3
0.52
0.009
<0.002
n=5
4.1
0.003
<0.002
<0.002
Table 2: Percentage of VAF-representable CDAFs among labeled instances without self-attacks, by arguments n and contexts k . The cells with n=3 , k≤3 are exact (exhaustive enumeration); the others are estimates from 2×105 uniform samples per cell, all 95% confidence intervals below 0.2 percentage points. Cells with no representable sample are bounded above by 0.002 percent.
The same arguments often need to be evaluated under different external regimes. An agent with influence over the regime has a strategic lever that standard formalisms do not directly capture. We introduce context-dependent argumentation frameworks (CDAFs), an extension of Dung's theory in which a defeat function determines, per context, which attacks succeed. A perspective-labeled specialisation derives the defeat function from a relevance set ρ and a priority π. The relevance set is the agent's action space. In a small worked example, the agent's target argument is rejected under every full-relevance injective priority, yet accepted under partial activations, one of which no VAF audience can mirror. We define the corresponding decision problem, ACTIVATION-MANIPULATION, and record baseline complexity bounds. Tight bounds and multi-agent variants are left open.
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 Π2P-complete, while deciding tenability and strong tenability is PSPACE-complete.
Uri Andrews, Luca San Mauro, John Spoerl
Department of Mathematics, University of Wisconsin–Madison · Dipartimento di Ricerca e Innovazione Umanistica, University of Bari, Italy
Preference-based argumentation frameworks (PAFs) extend Dung's approach to abstract argumentation (AAFs) by encoding preferences over arguments. Such preferences control the transformation of attacks into defeats, and different approaches to doing so result in different reductions from a PAF to an AAF. In this paper we consider a PAF inverse problem which takes an argumentation graph, a labelling and a semantics as an input, and outputs a yes" or no" as to whether there is a preference relation between the arguments which can yield the desired labelling. This inverse problem has applications in areas including preference elicitation and explainability. We consider this problem in the context of the four most widely-used preference based reductions under the complete semantics. We show that in most cases, the problem can be answered in polynomial time.
Alessio Zaninotto, Bruno Yun, Nir Oren +1
1CRIL - Université d’Artois, CNRS · 2Universite Claude Bernard Lyon 1, CNRS, Ecole Centrale de Lyon, INSA Lyon, Université Lumière Lyon 2, LIRIS, UMR5205, 69622 Villeurbanne, France · University of Aberdeen