Source-linked AI summary
A Comparative Study of Ranking-based Semantics for Abstract Argumentation
Elise Bonzon, Jérôme Delobelle, Sébastien Konieczny, Nicolas Maudet
TL;DR
Ranking-based semantics had been proposed with different properties but lacked a broad comparison. This paper compares existing unique-ranking semantics against those properties and shows that they differ in behavior, with the analysis also identifying shared, discriminatory, incompatible, and dependent properties. The study is limited by some methods producing multiple rankings or requiring acyclic graphs.
Problem
Existing ranking-based semantics had different behaviors and logical properties, but had not been compared broadly.
Method
The paper studies existing ranking-based semantics and compares them against properties proposed in the literature.
Results
The analysis finds properties shared by all ranking semantics, properties that classify semantics into different groups, and incompatibilities and dependencies among axioms.
Takeaways & Limitations
The comparison provides a common lens for inspecting existing and new ranking-based semantics and clarifies the differences among their design choices.
Takeaways & Limitations
The tuple-based approach is considered only for acyclic graphs because cycles can produce infinite tuples requiring a highly involved calculation.
Abstract
from arXiv · showhide
Argumentation is a process of evaluating and comparing a set of arguments. A way to compare them consists in using a ranking-based semantics which rank-order arguments from the most to the least acceptable ones. Recently, a number of such semantics have been proposed independently, often associated with some desirable properties. However, there is no comparative study which takes a broader perspective. This is what we propose in this work. We provide a general comparison of all these semantics with respect to the proposed properties. That allows to underline the differences of behavior between the existing semantics.
Introduction
Classical abstract argumentation uses binary attack graphs and accepted/rejected extensions, but ranking-based semantics introduce multiple acceptability levels. This paper compares existing unique-ranking semantics against proposed properties to clarify their behavioral differences.
- Dung’s frameworks represent arguments as graph nodes and attacks as graph edges.
- Classical semantics select mutually compatible sets of arguments rather than ranking individual arguments across many acceptability levels.
- Recent ranking-based semantics differ in behavior and logical properties, but had not previously been compared systematically.
- The paper studies existing ranking-based semantics that return unique rankings and evaluates them against proposed properties.
- The comparison highlights differences in behavior and clarifies the choices associated with alternative ranking-based semantics.
Preliminaries
The preliminaries define abstract argumentation frameworks, their attack paths and connected components, and ranking-based semantics as preorders over arguments. They also introduce lexicographical comparison for ranking vectors.
- An argumentation framework is a pair F = ⟨A, R⟩, with arguments A and a binary attack relation R.
- A set attacks an argument when one member has an attack relation to it, and connected components group arguments linked by undirected paths.
- A path identifies defenders and attackers by parity: even-length paths indicate defenders, while odd-length paths indicate attackers.
- Ranking-based semantics assign each framework a preorder over its arguments, where a ⪰σ b means a is at least as acceptable as b.
- Lexicographical order compares real-valued vectors using the first position at which their values differ.
Properties
The paper formalizes proposed ranking properties, including attack, defense, structural, independence, and change conditions. It also identifies incompatibilities and dependencies among these properties.
- The properties are defined for every ranking-based semantics, argumentation framework, and pair of arguments unless stated otherwise.
- Abstraction requires rankings to depend only on attacks, while Independence excludes influence from disconnected arguments.
- Void Precedence ranks non-attacked arguments above attacked ones, and Self-Contradiction ranks non-self-attacking arguments above self-attacking ones.
- Cardinality and Quality Precedence make arguments less acceptable when their direct attackers are more numerous or more acceptable.
- Defense properties distinguish defended arguments by the number, arrangement, and distribution of defenders relative to direct attackers.
- Change properties formalize how adding or lengthening defense and attack branches should improve or degrade an argument’s ranking.
- Total requires every argument pair to be comparable, while Non-attacked Equivalence gives all non-attacked arguments the same rank.
- Several properties are incompatible: CP conflicts with QP, AvsFD, and +DB, while VP conflicts with ⊕DB.
Existing Ranking-based Semantics
The paper compares ranking-based semantics by how they evaluate attack and defense structures and which formal properties they satisfy. The semantics differ in whether they prioritize attacker strength, attacker count, branch structure, or broader behavioral criteria.
- Categoriser: Categoriser computes argument strength from the values of direct attackers and can rank an argument attacked twice above one attacked once by a stronger attacker.In the example, e is ranked higher than c because its attackers are weaker despite their greater number.
- Categoriser: The Categoriser semantics satisfies Abs, In, VP, DP, CT, SCT, ↑AB, ↑DB, +AB, Tot, and NaE, but not the remaining properties.
- Social Abstract Argumentation Framework: SAF also makes attacker strength more important than attacker count, but defense branches have weaker impact than under Categoriser.Its example ranks b ≻SAF e ≻SAF d ≻SAF c ≻SAF a.
- Social Abstract Argumentation Framework: The SAF semantics satisfies Abs, In, VP, DP, CT, SCT, ↑AB, ↑DB, +AB, Tot, and NaE, while failing the other properties.
- Discussion-based semantics: Discussion-based semantics compares recursively expanded path counts lexicographically, making attacker number more important than attacker strength in the example.It ranks b ≻Dbs d ≻Dbs c ≻Dbs e ≻Dbs a, so c outranks e.
- Burden-based semantics: Burden-based semantics lexicographically compares recursively assigned burden numbers and often agrees with Discussion-based semantics, while additionally satisfying DDP.Its example returns the same ranking as Dbs, but structures covered by DDP can distinguish the two semantics.
- Valuation with tuples: Tuples* compares the lengths and contents of attack and defense branches, applies only to acyclic graphs, and can return partial rankings when arguments are incomparable.Cycles can produce infinite tuples, and arguments with more attack and defense branches than another may remain incomparable.
- Valuation with tuples: The studied semantics differ in their formal property profiles, with Tuples* satisfying Abs, In, VP, +DB, ↑AB, ↑DB, +AB, NaE, and AvsFD.
Discussion
The comparison shows that ranking semantics produce distinct argument orders and differ in which axioms they satisfy. Several properties are widely shared, while others discriminate among semantics or expose unresolved disagreement about the worst arguments.
- Comparative behavior: The studied ranking semantics produce different orders on the running example, motivating an axiomatic comparison.The resulting orders are summarized in Table 1.
- Property comparison: The study checks proposed properties across existing ranking semantics and summarizes the results in Table 2.The same analysis can also inspect newly proposed semantics, while grounded semantics is evaluated as a two-level comparison point.
- Shared properties: Abs, In, and VP are satisfied by all ranking semantics, while NaE is also shared by all semantics.These properties concern abstraction, independence, non-attacked arguments, and equivalence among non-attacked arguments.
- Compatibility and graduality: Abs, In, NaE, and Tot are compatible with grounded semantics, whereas VP and +AB introduce graduality absent from its accepted/rejected evaluation.Together, the discussion identifies six properties expected of ranking semantics: Abs, In, VP, NaE, Tot, and +AB.
- Discriminating properties: Some local axioms make choices based only on direct attackers or defenders, whereas change-related properties are described as appealing and systematically generalized.The discussion contrasts local behavior with properties concerning changes in attack and defense branches.
- Best and worst arguments: All semantics agree axiomatically on the best arguments, but none satisfy SC's treatment of self-contradicting arguments, leaving no consensus about the worst arguments.SC regards a self-contradicting argument as intrinsically flawed without requiring other arguments to defeat it.
Conclusion
The study finds that existing ranking-based semantics behave differently and satisfy different properties, while identifying further work on expanding and characterizing the field.
- Existing ranking-based semantics exhibit quite different behaviors and satisfy different properties.
- The study adopts Abs, In, VP, NaE, Tot, and +AB as basic properties for ranking-based semantics.
- AvsFD is proposed to discriminate two subclasses of ranking-based semantics.
- Further work includes proposing other semantics, finding additional logical properties, and characterizing semantic classes by those properties.
- An ambitious research direction is identifying when controversial axioms are justified.