Source-linked AI summary
From Contexts to Values: Context-Dependent Defeat in Abstract Argumentation
Albert Sadowski, Jarosław A. Chudziak
TL;DR
The paper asks whether context-dependent defeat can be reduced to one value assignment with per-context orderings. It develops a polynomial-time decision procedure and finds that representability is rare and decreases with each added context.
Problem
The central question is whether context-dependent defeat can be reproduced by one value assignment with per-context orderings.
Method
The paper develops a structural partition-refinement criterion and polynomial-time decision procedure, maps neighbouring complexity bounds, and validates an implementation.
Results
Representability is rare and decreases with every added context; the implementation was validated against definitions on over half a million small instances.
Takeaways & Limitations
Cross-context reasoning cannot in general be delegated to value-based argumentation machinery under uniform sampling.
Takeaways & Limitations
Family-level realisability has no known criterion or upper bound better than brute force, leaving the shared-value-assignment problem open.
Abstract
from arXiv · showhide
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 set of arguments, 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: is context genuinely new, or 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 $Σ^p_3$. We also present a validated reference implementation and a measurement: representability is rare and falls fast with the number of contexts.
1 Introduction
The paper asks whether context-dependent defeat is genuinely new or can be reproduced by value orderings, and answers the exact reduction question with a structural criterion and polynomial-time procedure. It also maps harder extension-based problems and reports a validated implementation showing that representability is rare and declines as contexts increase.
- Motivation: CDAFs keep arguments and attacks fixed while contexts switch individual attacks on or off, making circumstances—not evaluators—the source of variation.Contexts may represent procedural stages, regulatory regimes, or available evidence.
- Research questions: The central reduction asks whether one value assignment with one ordering per context can reproduce a CDAF’s defeat function exactly.The introduction also distinguishes reproducing defeat from reproducing the extensions of every induced framework.
- Contributions: The exact reduction question has a structural criterion and a decision procedure running in O(n3k+nmk) time for n arguments, m attacks, and k contexts.Section 3 presents the procedure as pseudocode and traces it on a small instance exercising every phase.
- Contributions: The extension-reproduction problem has known upper bounds of NP for grounded and Σp_3 for preferred semantics, without matching lower bounds.Section 4 maps these complexity results in a table.
- Contributions: The reference implementation is cross-validated against definitional brute force, while measurements show representability is rare and declines with each added context.Section 5 presents the implementation and measurement; Section 6 lists open problems.
2 Preliminaries
This section defines ordinary, value-based, and context-dependent argumentation frameworks, together with their induced defeat relations and standard semantics. It also introduces cross-context acceptance classes for comparing arguments across contexts.
- Argumentation frameworks: An argumentation framework is a finite argument set A paired with an attack relation R, and a semantics assigns it a set of extensions.The paper uses grounded, complete, preferred, and stable semantics, with n = |A| and m = |R|.
- Value-based frameworks: A value-based framework adds values, an argument-to-value assignment, and audiences represented by strict total orders over values.For audience p, an attack (a, b) succeeds exactly when val(b) is not strictly preferred to val(a).
- Context-dependent frameworks: A context-dependent framework is a tuple ⟨A, R, C, δ⟩ with a non-empty finite context set and a binary defeat function over contexts and attacks.The defeat function is δ: C × R → {0, 1}.
- Context-dependent frameworks: Each context activates a defeat relation from the latent attack relation and thereby induces an ordinary Dung framework AF_c = ⟨A, R_c⟩.The number of contexts is denoted k = |C|.
- Cross-context acceptance: Cross-context acceptance classifies arguments as universally accepted, indefensible, or context-contingent according to their membership across all extensions and contexts.These classes are defined relative to a chosen semantics σ.
3 Representability and Its Algorithm
VAF-representability asks whether one value assignment and context-specific strict value orders reproduce every defeat entry of a CDAF. A value-consistent partition characterizes representability and enables a polynomial-time decision algorithm.
- Representability criterion: VAF-representability requires a finite value set, one argument-to-value assignment, and context-specific strict total orders that reproduce every defeat entry exactly.Matching only extensions is the weaker realisability problem of Section 4.
- Representability criterion: A CDAF is VAF-representable iff its arguments admit a value-consistent partition satisfying intra-class unanimity, cross-class uniformity, complementarity, and acyclicity.These conditions capture how equal values and ordered value classes constrain defeats across contexts.
- Decision algorithm: The algorithm starts with singleton classes, performs forced co-equality merges, checks intra-class defeats, merges per-context cycles, and then verifies the surviving partition.Its correctness follows because current partitions refine every value-consistent partition, while any partition surviving the final check is value-consistent.
- Decision algorithm: O(n^3k + nmk) time is sufficient to decide VAF-representability for a CDAF with n arguments, m attacks, and k contexts.Each round costs O(mk + n^2k), and at most n − 1 rounds occur because every round removes at least one class.
- Worked example: A cycle activated in one context can force arguments into one value class, while a suppressed attack in another context can then violate intra-class unanimity and cause rejection.The worked instance is individually representable in each context but not jointly representable because one value assignment must serve both contexts.
4 The Complexity Landscape
The complexity landscape ranges from linear-time single-audience inducibility to unresolved family-level realisability, with cross-context queries inheriting single-framework complexity. Grounded and preferred realisability differ, while strategic perspective selection is NP-complete under preferred and stable semantics.
- Cross-context acceptance: Cross-context acceptance is polynomial under grounded semantics, while preferred-semantics universal acceptance is Πp_2-complete and indefensibility is coNP-complete.Iterating over contexts adds a factor k, but the family structure contributes bookkeeping rather than additional hardness.
- Single-audience inducibility: Single-audience inducibility is decidable in linear time by checking whether a mixed constraint graph has a directed cycle through a strict edge.Weak edges encode attacks that succeed, strict edges encode attacks that fail, and satisfiability corresponds to the absence of such a cycle.
- Single-context realisability: Single-context realisability lies in NP under grounded semantics and in Πp_3 under preferred semantics, although neither upper bound is known to be tight.The procedure guesses an audience, computes the relevant extensions, and compares them; preferred semantics requires comparing extension sets.
- Single-context realisability: Grounded realisability is not characterized by acyclicity alone: the smallest counterexamples have three arguments and four attacks, and grounded and preferred realisability can diverge.The counterexamples were found by exhaustive enumeration up to four arguments.
- Family realisability: Family realisability is decidable by brute force, but no better upper bound or Theorem 1-style criterion is known because contexts must share one value assignment.This shared-assignment coupling is identified as the first open problem of Section 6.
- Strategic variant: The strategic variant is NP-complete under preferred and stable semantics when an agent chooses active perspectives to make a target argument credulously accepted.Choosing perspectives selects which attacks succeed during evaluation.
5 A Reference Implementation and a Measurement
The section presents a validated Python implementation of the CDAF inducibility procedure and measures how often small context-dependent frameworks are VAF-representable. Representability declines sharply as contexts and arguments increase, while optimized code handles substantially larger constructed instances.
- Implementation: A Python script implements Algorithm 1 and the mixed-graph inducibility test, extending apx files with contexts and suppressed attacks.Plain apx files represent one-context CDAFs, and cross-context queries require only orchestration over k solver calls.
- Validation: The implementation agrees with brute-force oracles on 547,795 three-argument instances with up to three contexts and 180,000 sampled four- and five-argument instances.It also agrees on all 532,180 inducibility pairs with up to four arguments, while checking value-consistent finest partitions and the worked trace.
- Scalability: 103 arguments, 105 attacks, and 20 contexts are handled in five seconds on VAF-generated instances; a mask-based variant handles 104 arguments and 2 × 10^6 attacks in under three minutes.These instances are representable by construction and must be accepted.
- Measurement: 55 percent of three-argument instances are representable with one context, but only 1.5 percent with three contexts.Table 2 reports labeled instances without self-attacks, with exact values for n = 3 and k ≤3.
- Measurement: Fewer than one instance in ten thousand is representable at five arguments and two contexts, and measurements stop at n = 5 because larger cases fall below uniform-sampling detection.Further instances would add empty bounds rather than measurements.
6 Open Problems
Open problems center on structural characterisations of realisability, especially criteria coupling all contexts and tighter complexity bounds. Further challenges include exploiting perspective-labeled structure and avoiding per-context framework materialisation in cross-context queries.
- Structural characterisations: A family-level realisability criterion coupling all contexts, or any upper bound better than brute force, remains open.The paper identifies this as the main structural question.
- Structural characterisations: For grounded single-context realisability, acyclicity of latent attacks inside the target extension is necessary but not sufficient; a characterisation could lower the NP upper bound.The missing characterisation would determine whether the existing NP upper bound can be improved.
- Complexity and algorithms: The NP and Σp_3 upper bounds for realisability lack matching lower bounds.The passage states that both upper bounds remain without corresponding lower bounds.
- Complexity and algorithms: Whether perspective-labeled structure from Sadowski and Chudziak [2026] enables faster algorithms remains unexplored.That fragment derives δ from perspective activation and priorities.
- Complexity and algorithms: Cross-context queries currently materialise k frameworks and run a solver per context; declarative encodings working directly on δ could avoid this materialisation.The proposed direction follows the spirit of ASPIC+ encodings by Lehtonen et al. [2024].
7 Conclusion
The conclusion frames CDAF analysis around a polynomial-time test for VAF-representability, broader complexity upper bounds, and validation on over half a million instances. Measurements show representability is rare and decreases with each added context, motivating further work on realisability criteria and encodings.
- Conclusion: VAF-representability is decidable by a polynomial-time partition-refinement algorithm, while neighbouring realisability problems have upper bounds from NP to Σp_3.The algorithm is presented as pseudocode and traced on a fresh instance; no matching lower bounds are established.
- Conclusion: The reference implementation was validated against the definitions on over half a million small instances.This validation supports the algorithmic treatment of the decision problems.
- Conclusion: Under uniform sampling, representability is thin and decreases with every added context, limiting the general use of VAF machinery for cross-context reasoning.The released code and data provide a starting point for addressing the open problems, especially family-level realisability.