Source-linked AI summary
AFRA: Argumentation framework with recursive attacks
Pietro Baroni, Federico Cerutti, Massimiliano Giacomin, Giovanni Guida
TL;DR
Argumentation frameworks traditionally represent attacks between arguments, but many contexts require reasoning about attacks themselves. The paper introduces AFRA, a simple formalism for unlimited recursive attacks, and develops its semantics with compatibility to Dung’s framework. AFRA also provides correspondences with ordinary AFs while offering a general modelling tool for defeasible attacks.
Problem
Dung’s framework does not directly represent attacks as defeasible entities, although recursive attacks are useful for preferences and other reasoning contexts.
Method
AFRA defines a framework ⟨A, R⟩ whose attacks may target arguments or other attacks, and develops compatible argumentation semantics.
Results
AFRA encompasses unlimited recursive attacks while retaining a simpler formalism and direct correspondences with Dung’s AF at several levels.
Takeaways & Limitations
AFRA provides a general modelling tool for reasoning about defeasible attacks, including applications such as meta-argumentation and articulated decision processes.
Takeaways & Limitations
Recursive attacks are a modelling choice rather than a technically necessary expressive extension, since AFRA can be translated into traditional argumentation frameworks.
Abstract
from arXiv · showhide
The issue of representing attacks to attacks in argumentation is receiving an increasing attention as a useful conceptual modelling tool in several contexts. In this paper we present AFRA, a formalism encompassing unlimited recursive attacks within argumentation frameworks. AFRA satisfies the basic requirements of definition simplicity and rigorous compatibility with Dung's theory of argumentation. This paper provides a complete development of the AFRA formalism complemented by illustrative examples and a detailed comparison with other recursive attack formalizations.
1. Introduction
The paper situates AFRA within extensions and generalizations of Dung’s abstract argumentation framework, focusing on recursive attacks as a further modelling capability.
- Dung’s argumentation framework abstracts arguments and a binary attack relation, supporting theoretical analysis across several reasoning domains.
- Existing extensions add concepts such as preferences, values, support relations, or weighted attacks to model specific reasoning situations.
- The paper introduces AFRA to extend Dung’s framework with recursive attacks while preserving simple definitions and compatibility with Dung’s semantics.
- The paper develops AFRA through formal definitions, examples, semantic notions, and comparisons with other recursive-attack formalisms.
2. Background notions
This section recalls Dung’s framework, its semantics, and the fundamental properties that later guide AFRA’s compatible generalization.
- Dung’s framework is a pair ⟨A, →⟩ consisting of arguments A and a binary attack relation → over those arguments.
- Conflict-free, acceptable, admissible, and complete sets provide the core constructions underlying Dung’s extension semantics.
- Argumentation semantics identify collectively acceptable sets of arguments, supporting skeptical and credulous justification across extensions.
- Grounded, preferred, stable, semi-stable, and ideal semantics characterize extensions using fixed points, maximality, coverage, or relations among admissible sets.
- These properties support the existence of preferred extensions and the existence and uniqueness of the grounded extension, including in the infinite case.
- The characteristic function is conflict-free-preserving and monotonic, while admissible sets form a complete partial order and satisfy Dung’s fundamental lemma.
3. Motivations and requirements
The paper motivates AFRA as a simple extension of Dung’s framework that permits unrestricted recursive attacks while preserving compatibility with Dung’s concepts and properties.
- Motivations and requirements: Recursive attacks are useful for representing preferences, coalitions, and other reasoning patterns in which attacks themselves may be defeasible.
- Motivations and requirements: AFRA pursues unrestricted recursive attacks, simplicity, inclusion of Dung’s AF as a special case, and semantic compatibility with Dung’s AF.
- Motivations and requirements: Unlike earlier approaches allowing only one recursive level, AFRA is designed to accommodate further levels for varied representation and reasoning needs.
- Motivations and requirements: Bob’s holiday example uses attacks on attacks to represent how preferences and new information alter the status of competing travel choices.
- Motivations and requirements: Recursive attacks are a modelling choice rather than a technically necessary increase in expressive power, because such frameworks can be translated into traditional AFs.
- Motivations and requirements: An AFRA is a pair ⟨A, R⟩ where A is a set of arguments and attacks in R may target either arguments or other attacks.
- Motivations and requirements: When an AFRA contains no attacks targeting attacks, it is also an ordinary AF, supporting a direct correspondence between the formalisms.
4. Basic semantic notions for AF RA
AFRA generalizes argumentation semantics to sets containing both arguments and attacks, using direct and indirect defeat to handle recursive attacks. Its characteristic function preserves key properties needed to recover Dung-style admissibility structure.
- Defeat: AFRA distinguishes direct defeat of a target from indirect defeat of an attack through its source.An attack directly defeats its target, while it indirectly defeats another attack when it directly defeats that attack’s source.
- Conflict-freeness: Conflict-free sets contain no defeating pair among their arguments and attacks, including recursively related attacks.AFRA therefore permits argument-only sets to be conflict-free while attack-containing sets can conflict through direct or indirect defeat.
- Acceptability: An element is acceptable when every attack defeating it is itself defeated by an element of the candidate set.Only attacks in the defending set are effective for acceptability, even when the set also contains arguments.
- Acceptability: Acceptability of an attack implies acceptability of its source argument.This links the treatment of attacks to the requirement that attacks remain rooted in their source arguments.
- Characteristic function: The AFRA characteristic function preserves conflict-freeness and is monotonic with respect to set inclusion.These properties support the subsequent fixed-point and extension constructions.
- Admissibility: Admissible sets are conflict-free sets whose elements are all acceptable, and they form a complete partial order under set inclusion.The empty set is the least element, and every chain has a least upper bound.
- Admissibility: AFRA’s fundamental lemma allows an acceptable element to be added to an admissible set while preserving admissibility and acceptability.This establishes the extension-building property used in the semantic development.
5. Semantics for AF RA
AFRA extends Dung-style extension semantics to frameworks containing both arguments and recursive attacks. The resulting grounded, preferred, stable, semi-stable, and ideal semantics preserve the principal inclusion and existence relationships, while examples distinguish their extensions.
- Complete semantics: Complete extensions are admissible sets containing every element acceptable with respect to themselves.Equivalently, they are conflict-free fixed points of the characteristic function.
- Grounded semantics: The grounded extension is the unique least fixed point and equivalently the least complete extension.This parallels Dung’s grounded semantics in AFRA.
- Preferred semantics: Preferred extensions are maximal admissible sets, and every admissible set is contained in at least one preferred extension.Every preferred extension is complete, although some complete extensions are not preferred.
- Stable semantics: Stable extensions are preferred extensions that attack every element outside the extension, but preferred extensions need not be stable.Some AFRAs have no stable extension; in Example 2, neither preferred extension is stable.
- Semi-stable semantics: Semi-stable extensions are complete extensions with maximal range, and they coincide with stable extensions whenever stable extensions exist.Every semi-stable extension is preferred, but the converse does not always hold.
- Ideal semantics: The ideal extension is the unique maximal admissible set contained in every preferred extension and is also complete.Its uniqueness follows because the union of two ideal sets would remain admissible and contained in all preferred extensions.
6. Compatibility with AF
For AFRA instances that are also traditional Dung AFs, the paper establishes a bijective correspondence between AFRA extensions and Dung extensions through the →AFRA operator, across the principal semantics considered.
- Proof strategy: The compatibility proof relies on showing that AFRA notions reduce to Dung notions when attacks target arguments rather than other attacks.The proof section explicitly restricts R to A × A and establishes the required correspondence in that setting.
- Proof strategy: The operator’s correspondence results are supported by lemmas concerning attack sources, acceptability, set inclusion, unions, and ranges.These properties are used to prove conflict-freeness, admissibility, completeness, and related semantic correspondences.
- Compatibility mapping: The →AFRA operator extends an argument set U with every attack whose source belongs to U.This mapping is used to relate traditional AF extensions to AFRA extensions.
- Corresponding semantics: Complete, preferred, grounded, stable, semi-stable, and ideal extensions correspond bijectively under the →AFRA operator.The paper states this correspondence through Propositions 6–11 and summarizes it as a reduction to Dung’s semantics.
- Complete semantics: In the AF case, each complete extension is exactly the operator-completion of a D-complete extension, and conversely.The example lists D-complete extensions ∅, {D}, {A,D}, and {B,D}, with corresponding AFRA extensions obtained by adding arising attacks.
7. Expressing AF RA as an AF
The paper translates an AFRA into a traditional AF by turning both arguments and attacks into arguments and encoding AFRA defeats as attacks, yielding bijective correspondences between the relevant notions.
- Translation: The corresponding AF ΓAF represents both original arguments and attacks as arguments.Its relation contains pairs corresponding to direct and indirect defeats in the original AFRA.
- Implication: The resulting relationships between the relevant notions in AFRA and its corresponding AF are bijections.This provides a basis for reusing theoretical results from Dung’s framework in AFRA.
- Preserved notions: The translation preserves conflict-freeness, acceptability, admissibility, preferred, stable, complete, and grounded extensions.Proposition 12 states these equivalences between AFRA notions and Dung notions in ΓAF.
8. Comparison with related works
AFRA is compared with EAF and HOAF, emphasizing broader recursive-attack coverage, compatibility with Dung-style semantics, and simpler representation. The comparison also identifies EAF restrictions and semantic divergences that AFRA avoids or resolves.
- Extended Argumentation Framework: EAF limits attacks on attacks to attacks targeting arguments, whereas AFRA permits general recursive attacks.EAF+ extends EAF toward recursive attacks, and AFRA can also cover EAF+.
- Extended Argumentation Framework: AFRA directly encompasses an EAF situation forbidden by EAF’s constraints, with {A, B, C, C′, γ, δ} conflict-free.The EAF restriction is justified for preference modelling but may limit other applications.
- Extended Argumentation Framework: AFRA retains monotonicity of its characteristic function, unlike general EAF, where monotonicity holds only for HEAF and psEAF subclasses.This preserves desirable semantic properties beyond the restricted EAF cases.
- Extended Argumentation Framework: EAF’s grounded semantics need not correspond to its preferred semantics: only C belongs to all preferred extensions in the cited example, while A belongs to the grounded extension.Thus the grounded extension is not guaranteed to be included in every preferred extension.
- Higher Order Argumentation Framework: AFRA and HOAF have the same expressiveness through translations, but AFRA represents recursive attacks directly without HOAF’s additional “not” arguments.AFRA also introduces semantics directly and analyzes their properties, whereas HOAF relies on an indirectly represented AF.
9. Conclusion and future works
AFRA provides a simple, general formalism for unlimited recursive attacks while preserving relationships with Dung’s framework. Its simplicity supports implementation, and future work includes formalizing reasoning contexts and comparing AFRA with value-based argumentation.
- Contribution: AFRA treats attacks as defeasible entities, enabling reasoning about attacks within argumentation frameworks.The paper identifies meta-argumentation as a promising area where this capability may be useful.
- Future work: A full formalization of reasoning contexts requiring recursive attacks remains an important future research task.The paper highlights meta-argumentation and notes that reasoning about preferences had previously been analyzed only for one recursion level.
- Contribution: AFRA achieves greater simplicity than other approaches to recursive attacks, including some that are less expressive.The paper notes that competing formalisms often use more complicated structures and lack fully analyzed semantic properties.
- Implementation: AFRA has been incorporated into ASPARTIX, whose fixed logic-program architecture supports computing extensions and rapid prototyping.The system is described as easily extensible because frameworks are supplied as input to a fixed program.
- Future work: Analyzing relationships between AFRA and Value-Based Argumentation Frameworks is identified as a significant direction for future work.This direction is motivated by articulated decision processes involving reasoning with values.