One of the problems of computational models of
argumentation is to classify the quality of arguments in the context
of the larger discussion. In abstract argumentation, this
is usually achieved by checking whether an argument is
contained in a set of arguments, called extensions, that are
acceptable according to one of several well-established
semantics. While these semantics provides a natural way to
rank arguments based on the larger context of the
argumentation framework, it only allows us to distinguish three
types of arguments: the ones that are skeptically accepted,
i. e. that are contained in every extension; the ones that are
credulously accepted, i. e. that are contained in at least one
extension; and the ones that are not contained in any
extension. For this reason, more fine-grained ways of comparing
arguments have been proposed, the so called
argumentranking semantics [
In this paper, we propose a new way of ranking
arguments which can be seen as a true refinement of the more
common classification in skeptically, credulously and not
accepted arguments. To this end, we combine two strands
of literature that have emerged recently, namely
extensionranking semantics and social ranking functions, in a novel
way. Intuitively, social ranking functions allow us to rank
elements based on the quality of sets they are contained in.
These functions were first introduced in the economics
literature [
Closer to our needs, Skiba et al. [
We show that, by applying the right social ranking
functions to an extension-ranking semantics, we can define
argument-ranking semantics that are a refinement of the
traditional skeptical/credulous acceptance of arguments, both
in spirit and in a strict technical sense. More precisely, we
show that by applying the lexicographic excellence operator
introduced by Bernardi et al. [
In this section, we introduce the basics of abstract argumentation literature that are necessary for our work. We will start with the standard model of abstract argumentation, before introducing argument-ranking and extension-ranking semantics. free if ∀, ∈ , (, ) ̸∈ ; admissible if it is conflict-free, is: conflict
For an AF we use ( ) and ( ) to denote the sets
of conflict-free and admissible sets, respectively. In order
to define the remaining semantics proposed by Dung [
⊆ defined via:
For an AF = (, ) and a set of arguments the characteristic function ℱ () : 2 → 2 is ℱ () = { ∈ | defends } An admissible set ⊆ = ℱ (); a preferred extension () if it is a ⊆ -maximal complete extension; the unique grounded extension () if is the least fixed point of extension, where ∪ + is ⊆ -maximal. + = ∖ ; a semi-stable extension () if it is a complete ℱ ; a stable extension () if is a complete extension () if
The sets of extensions of an AF for these five semantics are denoted as (respectively) ( ), ( ), ( ), ( ) and ( ). Based on these semantics, we can define the status of any argument, namely skeptically accepted (belonging to each -extension), credulously accepted (belonging to some -extension) and rejected (belonging to no -extension). Given an AF and an extension-based semantics , we use (respectively) ( ), ( ) and ( ) to denote these sets of arguments.
Example 1. Consider the AF 1 = (, ) depicted as a directed graph in Figure 1, with the nodes corresponding to arguments = {, , , }, and the edges corresponding to attacks = {(, ), (, ), (, ), (, )}. We see that 1 has three complete extensions {}, {, } and {, } only the last two are preferred in addition. Also, we see that, ∈ (1), , ∈ (1), and ∈ (1).
An isomorphism between two AFs = (, ) and (, ) ∈ if ( (), ()) ∈ ′ for all , ∈ . ′ = (′, ′) is a bijective function : → ′ such that
Instead of reasoning
based on the acceptance of sets of arguments,
argumentranking semantics (also know as ranking-based semantics) [
Intuitively ⪰ means that is at least as strong as in . We define the usual abbreviations as follows; ≻ . Moreover, ≃ denotes equally strong, i. e. ⪰ and ⪰ . ◁▷ denotes incomparability so neither ⪰ nor
Traditionally the development of argument-ranking
semantics is guided by a principle-based approach [
An argument-ranking semantics satisfies the respective principle if for all AFs = (, ) and any , ∈ : Abstraction ( Abs). Names of arguments should not be relhave ⪰ if () ⪰ ′ ().
evant. For a pair of AFs = (, ) and ′ = (′, ′) and every isomorphism : → ′, we Independence ( In). Unconnected arguments should not inlfuence a ranking. For every and for all , ∈ ′: ⪰ if ⪰ ′ .
′ = (′, ′) ∈ ( ) Void Precedence ( VP). Unattacked arguments should be − ̸= ∅ then ≻ .
ranked better then attacked ones. If − = ∅ and Self-Contradiction ( SC). Self-attacking arguments (, ) ∈/ and (, ) ∈ then ≻ .
should be ranked worse than any other argument. If Cardinality Precedence ( CP). Two arguments are com|− | then ≻ .
pared based on the number of attackers. If |− | < Quality Precedence ( QP). Two arguments are compared ≻ . based on the strength of their attackers. If there is ∈ − s.t. for all ∈ − it holds that ≻ then Counter-Transitivity ( CT ). Two arguments are compared for all ∈ − then ⪰ .
based on the number and quality of their attackers. If some injective : − → − exists s.t. () ⪰ 1A preorder is a (binary) relation that is reflexive and transitive. Strict Counter-Transitivity ( SCT ). Strict version of CT.
If some injecitve : − → − exists s.t. () ⪰ some ∈ − with () ≻ , then ≻ .
for all ∈ − and either |− | < |− | or there exists Defense Precedence ( DP). For two arguments with the ≻ . same number of attackers, a defended argument is ranked better than a non-defended argument. If |− | = |− |, (− )− ̸= ∅ and (− )− = ∅, then Distributed Defense precedence ( DDP). The best de ≻ . fender attacks exactly one attacker. If |− | = |− | and |(− )− | = |(− )− |, and if defense of is simple - every direct defender of directly attacks exactly one direct attacker of - and distributed - every direct attacker of is attacked by at most one argument and defense of is simple but not distributed, then Non-attacked Equivalence ( NaE) Two unattacked arguthen ≃ .
ments should be equally ranked. If − = − = ∅ Attack vs. Full Defense ( AvsFD). Arguments withthen ≻ . out any unattacked indirect attackers should be ranked better than arguments only attacked by one unattacked argument. If acyclic and every path (, ) in from unattacked to has = 0 mod 2 and there exists unattacked ∈ − , -Compatibility ( -C). Credulously accepted arguments should be ranked better than rejected arguments. For ( ) and ∈ ( ), then ≻ .
an extension-based semantics it holds that if ∈ weak -Support ( w -S). If an argument is an unavoid -supports , then ⪰ . able side-efect of accepting another argument , then should be at least as acceptable as . If weakly strong -Support ( s -S). If an argument is a prerequisite for accepting another argument and is irrelevant for accepting , then should be ranked better then . If strongly -supports , then ≻ .
Note that these principles are not always compatible with
each other, especially SC and CP are not compatible [
Extension-ranking
semantics defined in Skiba et al. [
Let = (, ) be an AF. An extension ranking on is a preorder over the powerset of arguments 2. An extension-ranking semantics is a function that maps each to an extension ranking ⊒ on .
For an AF = (, ), an extension-ranking semantics and two sets , ′ ⊆ to be accepted as ′ with respect to in if ⊒ ′. We define the usual abbreviations as follows: is strictly more plausible to be accepted than ′ (denoted as ⊐ ′) if
⊒ ′ and not ′ ⊒ ; and ′ are equally as plau sible to be accepted (denoted as ≡ ′) if ⊒ ′ and we say is at least as plausible if neither ⊒ ′ nor ′ ⊒ . ′ ⊒ ; and ′ are incomparable (denoted ≍ ′)
Skiba et al. [
⊒ ′ if () ⊆ (′)
By combining these base relations, we denote the extension-ranking semantics.
′). ⊒ via ⊒ via ′ ⊆ ⊆ via ⊒
We define: via
Let = (, ) be an AF and , ′ ⊆ Admissible extension-ranking semantics - . ⊒ - ′ if ⊐ ′ or ( ≡ ′ and ′). Complete extension-ranking semantics - ⊒ - ′ if ⊐- ′ or ( ≡ - ′ and ′). Preferred extension-ranking semantics - ⊒ - ′ if ⊐- ′ or ( ≡ - ′ and ).
Grounded extension-ranking semantics - via ⊒ - ′ if ⊐- ′ or ( ≡ - ′ and ′). Semi-stable extension-ranking semantics - ⊒ - ′ if ⊐- ′ or ( ≡ - ′ and
In words, one set is at least as plausible to be accepted as ′ with respect to the admissible extension-ranking semantics, if has less conflicts than ′ or if they have the same conflicts, then we look at the undefended arguments. Example 2. Continuing Example 1. Consider for instance the sets 1 = {}, 2 = {, } and 3 = {}. For the complete extension-ranking semantics, we first of all have that all three sets contain no conflicts. However, both 1 and 2 contain the argument which they do not defend against . It follows that 3 ⊐1 - 1 and 3 ⊐1
- 2. Furthermore, both 1 and 2 defend from , but is not contained in 1. Thus,
The relevant excerpt of the extension-ranking for - can we have that 2 ⊐1
- 1. be found in Figure 2.
Extension-ranking semantics also follow a
principlebased approach. Before we recall the principles defined
in Skiba et al. [
Definition 8 (Most plausible sets). Let = (, ) be an AF, , ′ ⊆
two sets of arguments and an extensionranking semantics. We denote by ( ) the maximal (or ( ) = { ⊆ | ∄′ ⊆ with ′ ⊐ }. most plausible) elements of the extension ranking ⊒ , i. e. ... {}
... {} {, } ∅
{} {, } {} {, }
The principle -generalisation states, that the most plausible sets should coincide with the -extensions. Definition 9 ( -Gen). Let be an extension-based semantics and an extension-ranking semantics. satisifes -soundness if for all : ( ) ⊆ ( ). -completeness if for all : ( ) ⊇ ( ). -generalisation if satisfies both -soundness and completeness.
Additional principles can be found in Skiba et al. [
Let us now introduce the final piece of our puzzle, social
rankings. Let be a set of arbitrary objects like players of a
sports team, employees of a company or arguments in an
AF and () its powerset. A social ranking function , as
introduced by Moretti and Öztürk [
Definition 10. Let ⊆ be a subset of and ⊒ a preorder on (). Moreover, let 1, 2, . . . , be the longest sequence such that 1 ⊐ 2 ⊐ · · · ⊐ ⊐ . Then, we define the rank of , as rank⊒() := + 1.
Moreover, for an element ∈ , we define
,⊒ := |{ ∈ () | rank⊒() = , ∈ }|, as the number of rank subsets that contain .
As we will see later, a rank-based approach to social ranking provides many desirable properties, at least in our context of ranking arguments. With the definition of a rank at hand, we can now define our rank-based version of the lex-cel social ranking function.
Definition 11. Let , ∈ be two elements of . The lexcel ranking ⪰ -c is defined by ≻ ⊒- if there exists a such that ,⊒ = ,⊒ for all < and ,⊒ > ,⊒ - if ,⊒ = ,⊒ for all . and ∼ ⊒
Intuitively, an object is ranked better than by the lexicographic excellence operator if is contained in more highly ranked sets than .
Example 3. We continue Example 2 with the complete extension-ranking as depicted in Figure 2. Then, we have three sets with rank 1, namely the complete extensions. The argument is contained in all three sets with rank 1, while and are only contained in one such set each. Consequently ⪰ lex-cel and ⪰ lex-cel . Now, the final admissible sets ∅ and {} are dominated by all three complete extensions under the complete extension-ranking semantics, but dominate all non-admissible sets. Therefore, they are the only sets with rank 2. It follows that ⪰ lex-cel as both are contained in the same number of sets with rank 1, but is contained in more sets with rank 2.
Similarly to argument- and extension-ranking semantics,
social rankings have been studied axiomatically. Let us first
introduce an axiom that has been part of a characterization
of the lex-cel function under the assumption that the ranking
over sets is a total preorder [
Definition 12 (Independence from the worst set). Let ⊒ be a preorder on , let = max(rank⊒())
∈ and assume that ⊒* is another preorder on for which it holds • rank⊒* () ≥
rank⊒() = . • rank⊒() = rank⊒* () for all ∈ such that rank⊒() < .
for all ∈ such that ≻ ⊒* .
Then for any social ranking function that satisfies Independence from the worst set, we must have that ≻ ⊒ implies
Intuitively, this axiom states that if one element is already
strictly worse than another, and we further subdivide the
worst sets, this strict preference remains. As we will see
later, this axiom will be crucial for satisfying our desired
refinement property. Next, we introduce a new, very weak
axiom inspired by the classical Pareto-eficiency concept
[
Definition 13 (Pareto-eficiency) . Let ⊒ be a preorder on and let , be elements such that • rank⊒( ∪ {}) ≤ rank⊒( ∪ {}) for all ∈ with , ∈/ ; • rank⊒( ∪ {}) < rank⊒( ∪ {}) for at least one ∈ with , ∈/ .
A social ranking function satisfies Pareto-eficiency , if ≻ ⊒ .
Furthermore, we establish the novel Dominating set axiom which captures the intuition that if there exists a set containing the object that is ranked better than every set that contains some other object , then must be ranked better than by the social ranking function. satisfies
Dominating set if ≻ ⊒ .
Definition 14 (Dominating set). Let ⊒ be a preorder on and let , be elements such that ∃ ⊆ with ∈ such that ∀ with ∈ then ⊐ . A social ranking function
Crucially, Independence from the Worst Set and Paretoeficiency together imply Dominating set.
Theorem 1. Any social ranking function that satisfies Independence from the worst set and Pareto-eficiency also satisfies Dominating set. claim that Proof. Let ⊒ be a preorder on and let , be elements such that ∃ ⊆
with ∈ such that ∀′ with ∈ ′ then ⊐ ′. Furthermore, let := rank⊒() + 1. We consider the preorder ⊒* that is defined as follows: For any two sets , ∈ we have ⊒ ⊒ and either rank⊒() < or rank⊒( ) < . We * if and only if ∈ max(rank⊒* ()) = .
First, to see that max∈ (rank⊒* ()) ≤ we assume for the sake of a contradiction that there is a set with rank⊒* () = * sequence 1 ⊒
> . Then, by definition, there is a * 2 ⊒ * · · · ⊒ * * ⊒ * . As every preference in ⊒* is also valid in ⊒, the same sequence exists means rank⊒(* ) ≥ for ⊒, i. e. 1 ⊒ 2 ⊒ · · · ⊒ * − * ⊒ . However, this and rank⊒() ≥ * > , which contradicts * ⊒ * . serve that as rank⊒() = −
To see that max∈ (rank⊒* ()) ≥ we first ob1 there is a sequence rank⊒() < , we also have 1 ⊒ 2 maximal, rank⊒ ⊒ · · · ⊒ () < for all elements of the se
− 1 ⊒ . As this sequence is as is a dominating set, we know quence. Hence the same sequence exists in ⊒* . Finally, ⊒ {} and as ⊒ * {}. Therefore,
* {} witnesses for all social rank1 ⊒ * 2 ⊒
* · · · ⊒ that rank⊒* ({}) ≥ .
Next, we claim that ≻ ⊒* * − 1 ⊒ * ⊒ the worst set of ⊒* . ing functions that satisfy Pareto-eficiency: By definition, rank⊒* (( (rank⊒* () = −
∖ {}) ∪ {} ⊒* rank⊒* () < rank⊒* (( ∖ {}) ∪ {}) > − ( ∖ {}) ∪ {}, and thus
1. This shows that ∖ {}) ∪ {}). On the other 1. Furthermore, we have =
Finally, if ⪰ hand, there can be no such that rank⊒* ( ∪ {}) < rank⊒* ( ∪{}): As ∪{} is dominated by , we know rank⊒( ∪ {}) ≥
and thus rank*⊒( ∪ {}) ≥ the claim follows directly from max∈ (rank⊒* ()) = . Thus, also satisfies Independence from the worst set, if follows that also ≻ ⊒ , as ⊒ is just a refinement of
The idea of combining extension-ranking semantics with
argument-ranking semantics was briefly discussed by Skiba
et al. [
ifned via ⪰ if {} ⊒ {}.
Let = (, ) be an AF and any extension-ranking semantics. For any two arguments , ∈ , the singleton argument-ranking semantics is de
Bernardi et al. [
Example 4. Consider the AF 1 from Example 1. We use as the underlying extension-ranking semantics, then since {} and {} are conflict-free and not defended, so {} and {} are admissible we have =1 - and both =1 - ≻ 1 - =1 -
The example shows that - has a limited expressiveness, since - has at most three ranks. The first rank contains arguments for which the singleton set is admissible and the lowest rank are all self-attacking arguments, in between are the non-admissible sets, but conflict-free singleton sets. Observe also that this approach does not refine the classical skeptical/credulous acceptance classification, as in Example 4 the credulously accepted argument is ranked the same as the rejected argument . 4.2. Generalised Social Ranking
Argument-ranking Semantics
In the literature, a number of diferent social ranking
functions that are more complex than the singleton approach
can be found [
Let = (, ) be an AF and a social ranking function with respect to extension ranking . For any , ∈ we call the Social ranking argument-ranking ⪰ if ⪰ ranking ⊒
In words, an argument is at least as strong as argument if the social ranking function applied to the extension returns that is at least as strong as .
Example 5. In Example 3 the social ranking argument ranking lex-celr-co was applied to the AF 1 from Example 1 where lex-cel is used and the underlying extension-ranking semantics is r-co. Thus, the resulting argument ranking is: lex-celr-co ≻ 1 lex-celr-co ≻ 1 lex-celr-co
Any social ranking function can be used to rank
arguments. Skiba et al. [
⊒ ′.
Definition 17 ([
- . Since {, }, {, } ∈ (1) for {, , , } the ranking is the same for any - . Only ∈ - for - the induced ranking difers:
Proof. Let = (, ) be an AF, , ∈ and an extenlex-cel , then there is an s.t for to be an ′ ⊆ ′ ≡ , so ⪰ .
If , ̸= 0 for 1 ≤ ≤ , then there is one ⊆ with ( ) = and ∈ . W.l.o.g. let be the smallest ∈ , therefore ⪰ . Since, , ≤ number s.t. , ̸= 0. Then ⊒ for all ⊆ , , there has with with (′) = and ∈ ′ s.t.
If ,
= 0 for all ∈ {1, . . . , } and , > 0, then there is at least one ⊆ with ∈ and () = with ∈ , and therefore ≻ .
s.t. ⊐ for all ⊆
In particular, lex-celr-co allows us to distinguish among skeptically and credulously accepted arguments ( is ranked before and ). To capture this, we define a skeptical variation of -Compatibility. Skeptical accepted arguments are part of every -extension, therefore they should be ranked better than any other argument.
Let = (, ) be an AF, , ∈ , and let and ∈/ ( ) then ≻ . be a extension-based semantics. Argument-ranking semantics satisfies -skeptical-Compatibility ( -sk-C) if ∈ ( )
Crucially, a well-behaved argument ranking semantics should be able to rank skeptically accepted arguments before all credulously accepted ones, which should be, in turn, ranked before all non-accepted arguments. This translated to the following refinement property.
Definition 19 ( -Refinement) . Argument-ranking semantics satisfies -Refinement if satisfies -C and -sk-C for extension-based semantics for all AFs .
Next, we investigate principles for social ranking based argument-ranking semantics from a general point of view. In particular, we are interested in understanding which combinations of axioms for extension-ranking semantics and social ranking functions represent necessary and suficient conditions for the corresponding social ranking argumentranking semantics to satisfy fundamental principles of argument rankings, chiefly among them our desired refinement property. This translates to the following research questions: RQ1 What properties of and are adequate to ensure that satisfies a specific principle for argumentranking semantics? RQ2 What properties of are adequate to ensure that satisfies a specific principle for social ranking functions when combined with a certain extensionranking semantics ? Next, we address RQ1 and RQ2 for a selected number of principles for argument ranking semantics.
We start by considering -Compatibility. For this we show that Independence from the worst set together with the quite weak condition Pareto-eficiency , is suficient for satisfying -C.
Theorem 2. Let = (, ) be an argumentation framework, an extension-ranking semantics, satisfying - generalisation for extension semantics and a social ranking function that satisfies Independence from the worst set and Pareto-eficiency . Then satisfies -C. we claim that ≻ Proof. Consider first the extension ranking
⊒ if and only if ∈ ( ) and ̸∈ ( ). Furthermore, let ∈ ( ) and ∈ ( ). Then, ⊒
defined by ⊒
for any social ranking function that satisfies Pareto-eficiency: As is credulously accepted, there exists a
∈ ( ) with ∈ and as is rejected, we have ̸∈ ( ) for all ∈ . It follows that rank⊒ ( ∖ {}) ∪ {}) = 1 < rank⊒ (( ∖ {}) ∪ {}). On the other hand, there can be no such that rank⊒ ( ∪ {}) < rank⊒ ( ∪ {}) as, due to the fact that = max⊆ (rank⊒ ()) = 2, this would imply rank⊒ ( ∪ {}) = 1 and therefore ∪ {} ∈ ( ).
Furthermore, as satisfies -generalisation, we know that rank⊒ () = 1 if and only if rank⊒ () = 1. Therefore, it follows from Independence from the worst set that ≻
⊒ implies ≻ . Consequently, we know that satisfies -C.
Next, we show that Independence from the worst set and Pareto-eficiency together also imply that every skeptically accepted argument is ranked before any argument that is not skeptically accepted.
Theorem 3. Let = (, ) be an AF, an extension-ranking semantics satisfying -generalisation for an extension-based semantics , then if social ranking function satisfies
Pareto-eficiency and Independence from the worst set then satisfies -sk-C. cannot exist.
Proof. Let = (, ) be an AF, an extension-ranking semantics satisfying -generalisation for an extension-based semantics , and a social ranking function satisfying Pareto-eficiency and Independence from the worst set.
⊒ Since -generalisation is satisfied by we can view as a refinement of the extension-ranking semantics ′ defined by ⊒′ if ∈ ( ) and ∈/ ( ) for , ⊆ .
Now consider two arguments, , ∈ , such that ∈ ( ) and ∈/ ( ). Assume there exists a ⊆ ∖ {, } s.t. rank ′ ( ∪ {}) < rank ′ ( ∪ {}). Since ′ only has two levels, this implies ∪ {} ∈ ′ ( ) and thus ∪ {} ∈ ( ). As ∈ ( ), we must have ∈ ∪ {}. However, as ∈/ we know that also ∈/ ∪ {}. This is a contradiction and hence such a ⊒
Since ∈/ ( ) we know there has to exists ¯ ⊆ ¯ ∈ ′ ( ) and ∈/ ¯ . Then because ∈ ( ) we know that (¯ ∖ {}) ∪ {} ∈/ ′ ( ). Consequently, s.t.
Pareto-eficiency implies
≻
′ .
′ holds for ′, and is a refinement of ′ such As ≻
that ′ ( ) = ( ) it follows from Independence for the worst set that the same holds for , i. e. ≻ .
Additionally, observe that Independence from the worst set means that we might have to ignore most of the information that is available to us. The following result shows that, at least for the rank information, this is essentially unavoidable if we want to satisfy -C. Let us first introduce an axiom that encodes the idea that we cannot ignore overwhelming, rank based evidence.
Definition 20 (Rank -super majority). Let ∈ N be a natural number. Then we say a social ranking function satisfies rank -super majority if for all and such that |{ ∈ | , ̸∈ ∧rank(∪{}) < rank(∪{})}| > ·|{ ∈ | , ̸∈ ∧rank(∪{}) < rank(∪{})}|. we have ⪰ .
In words, if there are -times as many sets such that the rank of ∪ {} is strictly better than the rank of ∪ {}, than the other way round, then must be (weakly) preferred to .
Proposition 2. Any social ranking function - satisfies -C and violates rank -super majority for every . observe that Proof. Let be an arbitrary natural number, ℓ a natural number such that ℓ ≥
and ℓ ≥ sider an argumentation framework with the arguments , , 1, . . . ℓ and the attacks (, ) and (, ) for all ≤ ℓ. Then, ∈ ( ), as witnessed by the conflict free set {}, but ∈ ( ), as it is self-attacking. It follows from the fact that ≻ , because ⪯ satisfies -C. However, 3. Furthermore con{ ∈ | , ̸∈ ∧ rank-cf( ∪ {})}
< rank-cf( ∪ {}) = {∅} while { ∈ | , ̸∈ ∧ rank-cf( ∪ {}) < rank-cf( ∪ {})} = { ∈ | , ̸∈ ∧ || ≥ 2}.
However, then, by our choice of ℓ we know
|{ ∈ | , ̸∈ ∧ || ≥ 2}| > = · |{∅}| . It follows that rank -super majority is violated.
Next, consider the axiom SC. Here, we can find a property of social ranking functions that guarantees that satisifes SC under the assumption that satisfies the following principle: , ′ ⊆ Definition 21 (Respects Conflicts) . For AF = (, ) and extension-ranking semantics satisfies respects conflicts if ∈ ( ) and ′ ∈/ ( ), then ⊐ ′.
To show that satisfies SC we also need the Dominating set property from Definition 14. With these two properties we can then show when SC is satisfied.
Theorem 4. For AF = (, ) if extension-ranking semantics satisfies respects conflicts and social ranking function satisfies Dominating set, then satisfies SC. we have ≻ .
Proof. For AF = (, ), let , ∈ , (, ) ∈ and (, ) ∈/ , then {} ∈ ( ) and for all ′ with ∈ ′ it holds that ′ ∈/ ( ). Because of respects conflicts we have {} ⊐ ′ and therefore because of Dominating set
Let us try to go the other way, that is finding necessary
conditions for the social ranking functions to satisfy desirable
properties. First observe it is not possible to formulate any
necessary conditions that also hold for any ranking that
cannot be realised by any AF, i. e., we cannot find an AF that
induces this ranking. This is because any property of the
argument-ranking only restricts the social ranking function
on realisable rankings. Therefore, we need to define the
following concept in a similar vain to Dunne et al. [
Let be a set and let ⊒ be a preorder on (). Then, we say that ⊒ is -realisable for a extensionranking semantics if there is an AF with = such that ⊒ =⊒. ({, }, {(, )}).
For example, for a set {, } any preorder containing must be a strict super-set of the conflicts in {, } ⊒ {} is not - -realisable. The conflicts in {}. On the {, } other hand, the preorder containing exactly the relations {} ⊒
{, } and {} ⊒ {, } is realised by the AF Theorem 5. Let be a social ranking function such that - satisfies -. Then, satisfies Dominating set for all - -realisable preorders ⊒. ⊐ for all such that ∈ .
Proof. Let ⊒ be a -realisable preorder and let be an that realises it. Assume further that there are , ∈ such that there exists a with ∈ for which we have
As contains , its set of conflicts must be a strict superset of the conflicts in
{}. It follows that {} ⊒ ⊐ and hence by transitivity also {} ⊐ for all such that ∈ . In particular, it follows that {} ⊐ {}. By definition, this means ({}) ⊂ ({}), which can only hold if is self-attacking and is not. However, then is credulously accepted in the under conflict-free semantics while is not. Consequently, it follows from - that ≻ . Hence, dominating set is satisfied.
It follows that dominating set is a necessary and suficient condition for a social ranking function to satisfy - when combined with - .
A similar result can be found for admissible semantics. Theorem 6. Let be a social ranking s.t. - satisfies -. Then satisfies Dominating set for all --realisable preorders ⊒.
Proof. Let ⊒ be a --realisable preorder and AF = (, ) induces ⊒. Assume , ∈ such that there exists ⊆ with ∈ for which we have ⊐ for all such that ∈ .
Assume that the set is not admissible. That means one of the following two cases must apply (1) () ̸= ∅ or, (2) () ̸= ∅ to (1): Then, there is some attack (, ) ∈ () for , ∈ . From ⊐ it follows that () ⊆ ( ) and thus (, ) ∈ ( ). Now, if = or = it follows that ∈ which directly contradicts our assumption because of ≡ ′ for ′ = with ∈ ′. However, if ̸= and ̸= we can construct ′ = ∖ {, }. Clearly, that means we either have ( ′) = ∅ which means ⊐ or we have ( ′) ̸= ∅ which implies ≍ ′. Because of ∈ ′ both cases contradict the initial assumption, hence we must have that () = ∅, i. e. the set is conflict-free.
to (2): Then, there exists an argument ∈ () which is not defended by . Consider now the set ′ = {} for which we either have that ( ′) = ∅ or ( ′) = {}. If ( ′) = ∅, it follows directly that ′ ⊐ , contradicting our initial assumption. On the other hand, for ( ′) = {} we distinguish between two cases: (2.1) = , (2.2) ̸= Clearly, if = we contradict our initial assumption because ≡ ′′ for ′′ = . Consider now the case ̸= . That means, we have that () ≍ ( ′) and thus ≍ ′. Therefore, it follows that we must have () = ∅, i. e. defends all its elements.
That means is admissible and thus it follows directly that ∈ ( ).
From () = ∅ and ⊐ for all it follows that ( ) ̸= ∅. Since ⊒ satisfies ad-generalisation it follows that ∈/ ( ) for all and thus also ∈ ( ). Consequently, it follows from - that ≻ . Hence, Dominating set is satisfied.
lex-cel In the previous section, we looked at social ranking solutions from a general perspective and were able to characterise -C and present suficient conditions for and -sk-C, however a number of principles are still to be investigated. In this section, we take a closer look at lex-cel and analyse which principles it satisfies.
As the results from the previous section suggest we should start with checking if lex-cel satisfies Pareto-eficiency . Theorem 7. lex-cel satisfies Pareto-eficiency .
Proof. First, consider sets 1, . . . , ∈ for which condition (2) of Pareto-eficiency holds. Among these, take those 1, . . . , (with ≤ ) for which rank⊒( ∪ {}) = (with 1 ≤ ≤ ) is minimal. At this level in the ranking, we have that rank⊒( ∪ {}) = rank⊒( ∪ {}) for each ̸= . Hence, for every ∪ {} there is exactly one corresponding set ∪ {}, except for each ∪ {} (because rank⊒( ∪ {}) > ). Thus, for each ∈ with , ∈/ : |{ ∪ {} ∈ | rank⊒( ∪ {}) = }| >
|{ ∪ {} ∈ | rank⊒( ∪ {}) = }|.
At level , there are more sets containing than those containing , i. e. ,⊒ > ,⊒ by Definition 10. To prove ≻ l⊒ex-cel it remains to show that ,⊒ = ,⊒ for all < . By construction, for all < and ∈ ∖ {, }, we know that rank⊒( ∪ {}) = rank⊒( ∪ {}). Hence, for each set containing there is exactly one set containing . By Definition 10, we obtain ,⊒ = ,⊒, as desired.
Bernardi et al. [
The following result summarises the compliance of lexcel with the argument-ranking principles.
Theorem 8. lex-cel satisfies the respective principles as stated in Table 1 for ∈ {-, -, -, -, -}.
We want to discuss the following counterexample showing that VP is violated by lex-cel in particular.
Example 7. We examine the following AF = ({, , , , }, {(, ), (, ), (, ), (, )}). Consider, for instance, the - extension-ranking for : 0 : {, }, {}, {}, ∅ 1 : {, } The lex-cel- argument-ranking is then:
≻ lex-cel- ≻ lex-cel- ≻ lex-cel- However, is unattacked, while is attacked and therefore VP is violated. Since all other sets that contain are not conflictfree, that means that {, } is always ranked better than these sets. Therefore is ranked better than wrt. lex-cel for all other ∈ {-, -, -, -}
At first glance it might seem unintuitive that VP is violated. Both arguments and are skeptically accepted wrt. complete semantics, so there is no reason to reject either argument. However, argument is involved in more conflicts than and thus is compatible with more arguments than . Therefore we reason that should be ranked better than . In general, if we think back to the motivation of social ranking functions then employees who can work together |{ ∈ ( ∖ {, })| ∪ {} ⊐ ∪ {}}| ✓ ✓ ✓
SCT X ✓ X DDP
NaE
AvsFD w -S s -S ✓ X ad -C ✓ X ad -sk-C ✓ X X with more employees are considered better, so this ranking of and is in line with the idea behind social ranking functions.
The remaining proofs and counterexamples can be found in the supplementary material2.
A number of social ranking functions are discussed in the literature. In the following, let be an arbitrary set of objects and ⊒ is a preorder on the powerset ().
A prominent social ranking function is the Ceteris Paribus
Majority Solution (CP), which was defined by Haret et al. [
Definition 23. For the preorder ⊒ and for any , ∈ , we have that ⪰ ⊒ if and only if |{ ∈ ( ∖ {, })| ∪ {} ⊐ ∪ {}}| ≥
Another relevant social ranking function is the Ordinal
Banzhaf Index Solution (BI) of Khani et al. [
First, we define the notion of ordinal marginal contribution as follows.
Definition 24. Let ⊒ be a preorder on (). The ordinal marginal contribution (⊒) of element wrt. the set with ∈/ , for the preorder ⊒ is defined as: (⊒) = ⎧ ⎨ ⎩
Definition 25. For the preorder ⊒ and for any , ∈ , we define that ⪰ ⊒ if and only if
⊒ ≥ ⊒
However, the corresponding Social ranking argumentranking semantics and do not generalise credulous acceptance, because these two argument-ranking semantics do not satisfy the principle SC, as shown by the following examples.
X X ad
✓ X ✓ Example 8. The argument ranking ⪰ CP violates SC for ∈ {-, -, -, -, -}. Consider the AF 2 in CP , which contradicts SC.
Figure 3. Then we have that ⪰ 2 Example 9. The argument ranking ⪰ BI violates SC for ∈ {-, -, -, -, -}. Consider the AF 3 in Figure 4. Then we have that ⪰ BI3 , which contradicts SC.
So, self-contradicting arguments are not necessarily the worst ranked arguments. Thus, these two social ranking functions are not suitable to rank arguments in the context of abstract argumentation and therefore we do not discuss them further.
A number of other argument-ranking semantics were
introduced in the literature (for an overview see Bonzon et al.
[
Example 10. Let 4 be the AF as depicted in Figure 5. Then argument ∈ (4). So, according to -sk-C it should hold that ≻ 4 , however this is not the case for , i. e. ≻ 4 . Thus -sk-C is violated.
Similarly, we have that the categorizer ranking semantics (Cat) violates -sk-C.
Example 11. Let 5 be the AF as depicted in Figure 6. We have that (5) = {, }. However, we have for . Thus, -sk-C is violated by for instance ≃5 ∈ {, , , , }.
So lex-cel is the only known argument-ranking
semantics that satisfies -C and -sk-C and thus satisfies
Refinement for extension-based semantics . Thus,
lexcel is part of none of the equivalence classes of
argumentranking semantics defined by Amgoud and Beuselinck [
In this paper we have combined well-known approaches from abstract argumentation and social ranking functions to define a new family of argument-ranking semantics. The resulting semantics are generalisations of the acceptance classifications for abstract argumentation. Thus, the skeptically accepted arguments are ranked before credulously accepted arguments and those are ranked before rejected arguments, and within each of these groupings the arguments are also ranked. While the extension ranking methods used are of the shelf approaches and already discussed in the literature, we needed to slightly generalise the existing social ranking functions in order for them to work with partial rankings. Here, our rank-based approach proved to be well suited for our specific setting. Whether this approach to social ranking also is appealing more generally is a very natural and intriguing question, that, unfortunately, is out of the scope of this paper and has to be left to future work.
The converse problem to social ranking functions are
lifting operators, i. e. given a ranking over objects, we want to
construct a ranking over sets of objects. These operators
have been discussed for argumentation in the past by Yun
et al. [
Acknowledgements. The research reported here was supported by the Deutsche Forschungsgemeinschaft under grants 375588274 and 506604007, by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 101034440) and by the Austrian Science Fund (FWF) under grant J4581.