argumentation frameworks. In particular, we investigate approaches to transform these two semantics into each other, i.e. going from a ranking over arguments to a ranking over sets of arguments (lifting) and from a ranking over sets of arguments to a ranking over arguments (social ranking). Additionally, we analyse the principles and properties the resulting semantics do satisfy.
Using these functions we can state whether a set of arguments is “better” than another set.
Formal argumentation [1] has gained attention as a ration Both ranking-based semantics and extension-ranking decision-making model with a focus on the representa- semantics in a sense are focusing on ranking argution of arguments and their relationships. The well-know ments. Both these approaches return preorders, rankingapproach of abstract argumentation frameworks (AF) [2] based semantics ranks single arguments, while extensionuses directed graphs to reason, where arguments are the ranking semantics return rankings over sets of argunodes and the edges are representing attacks between ments. Like already shown by Skiba et al. [6] these two arguments s.t. the source of the edge is attacking approaches are related and can be combined. We can the target. One way to reason with these frameworks project extension-ranking semantics into ranking-based are the so called extension-based semantics, which are semantics and the other way around. Similar projection functions allowing us to state that a set of arguments tasks between rankings of objects and rankings of sets is jointly accepted. So, these semantics can be used as of objects were already discussed as part of the area of a binary classifier for sets of arguments based on their computational social choice and in particular voting the“acceptability”, a set is either acceptable based on some ory (for an overview see [7]), where the best committee account of acceptability or not. should be constructed based on the preferences of each
In recent years, this binary classification has been crit- voter. So, we take a set of preferences or preorders over icised as being too limiting in real world scenarios like candidates and lift them to a preorder over potential comonline debates [3]. For any argument, we can only say if mittee setups (sets of candidates). These lifting questions it is part of an acceptable set or not. The extension-based were already discussed in the context of argumentation semantics do not give us any insight into the inherent by Maly and Wallner [8], however they focus on a strucstrength of each argument. For that purpose the so called tured approach, where the preferences are part of the ranking-based semantics [4, 5] were proposed. These func- input. In the AF setting, we do not have such prefertions allow us to rank arguments based on their strength ence data, hence we need to generate our preferences alone. in another way. One possibility are the ranking-based
While we can use ranking-based semantics to rank semantics, which we can lift to extension-ranking searguments base on their strength, these functions do not mantics. The work by Maly and Wallner [8] represents allow us to state that a set is jointly acceptable. Further, a starting point for a discussion about lifting in formal two arguments with high strength degrees may not be argumentation and can be extended. Besides structured allowed to be jointly acceptable, since they are in con- approaches the problem of lifting was also discussed for lfict with each other. To refine the reasoning based on Preference-based AFs (PAFs) [9, 10, 11, 12], which are extensions, extension-ranking semantics were defined [ 6]. extensions of argumentation framework with a preferences order over the set of arguments as part of the input. 9th Workshop on Formal and Cognitive Reasoning, Again, preference data is part of the input and needs to September 26, 2023, Berlin, Germany be generated separately. $ kenneth.skiba@fernuni-hagen.de (K. Skiba) The other direction (going from a ranking over sets of © 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License objects to a ranking over objects) is equally interesting. CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) The social ranking problem has received considerable in- terest in the area of computation social choice in recent years. Here individual persons, like researchers, are evaluated based on their performances and their impact in Figure 1: Abstract argumentation framework from Example diferent teams. A number of social ranking solutions can 1. be found in the literature [13, 14, 15, 16], however a discussion in the context of argumentation is missing. Using the idea of a social ranking solution we want to project a ranking over sets of arguments down to a ranking over freWeaenudseadm (issi)balensdetso(fa)ntoAdFen o.tTehteheinsteutistioofncboenhflicint-d arguments, allowing us to reason on the argument level. these concepts is that a set of arguments may be accepted
In this work, we look at the relationship between only if it is internally consistent (conflict-freeness) and ranking-based semantics and extension-ranking seman- able to defend itself against potential threats (admissibiltics in detail and want to establish connections between ity). In order to define the remaining semantics proposed these two reasoning formalisms in abstract argumentation. These connections allow us to bring the ranking- by [2] we use the characteristic function. based semantics closer to an extension-based approach. Definition 2. For an AF = (, ) the characteristic We look at the social ranking and the lifting problems function for a set of arguments ⊆ , ℱ () : 2 → between these two approaches, hence we transform 2 is defined via: ranking-based semantics into extension-ranking semantics and the other way around. For the social ranking ℱ () = { ∈ | defends } problem it turns out, that the resulting rankings are generalisations of the credulous acceptance problems. Ad- In words, the characteristic functions returns for evditionally, we investigate the properties of the resulting ery set of arguments all arguments defended by that set. semantics based on principles from the literature. Using this function we introduce all the remaining se
In Section 2, we recall preliminaries about argumenta- mantics defined by [ 2] and in addition the semi-stable
tion frameworks, ranking-based semantics and extension- semantics [
An abstract argumentation framework is a directed graph = (, ) where is a finite set of arguments and ⊆ × is an attack relation [2]. An argument is said to attack an argument if (, ) ∈ . We say that an argument is defended by a set ⊆ if every argument ∈ that attacks is attacked by some ∈ . For ∈ we define − = { | (, ) ∈ } and + = { | (, ) ∈ }, so the sets of attackers of and the set of arguments attacked by in . For a set of arguments ⊆ we extend these definitions to − and + via − = ⋃︀∈ − and + = ⋃︀∈ + , respectively. If the AF is clear in the context, we will omit the index.
Most semantics [
Given = (, ), a set ⊆ is • conflict-free if ∀, ∈ , (, ) ̸∈ ; • admissible if it is conflict-free, and every element of is defended by . • a complete extension () if = ℱ (); • a preferred extension () if it is a ⊆ -maximal admissible extension; • the unique grounded extension () if is the least fixed point of ℱ ; • a stable extension () if + = ∖ ; • a semi-stable extension () if it is a complete extension, where ∪ + is ⊆ -maximal.
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 (set of) argument(s), 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 = (, ) depicted as a directed graph in Figure 1, with the nodes corresponding to arguments = {, , , }, and the edges corresponding to attacks = {(, ), (, ), (, ), (, )}. We see that has three complete extensions {}, {, } and {, } only the last two are preferred in addition. Also, we see that, is skeptically accepted w.r.t. complete semantics, and are credulously accepted w.r.t. complete semantics and is rejected w.r.t complete semantics.
An isomorphism between two AFs = (, ) and ′ = (′, ′) is a bijective function : → ′ such that (, ) ∈ if ( (), ()) ∈ ′ for all , ∈ .
Instead of only reasoning based on the acceptance of sets of arguments, ranking-based semantics [4] were introduced to focus on the strength of a single argument with respect to the other arguments. Note that the order returned by a ranking-based semantics is not necessarily total, i. e. not every pair of arguments is comparable.
A ranking-based semantics is a function,
which maps an AF = (, ) to a preorder1 ⪰ on .
Intuitively, ⪰ means, that is at least as strong as in . We define the usual abbreviations as follows;
̸⪰ ; ⪰ ; nor ⪰ . • ≻ denotes strictly stronger, i. e. ⪰ and • ≃ denotes equally strong, i. e. ⪰ and • ◁▷ denotes incomparability so neither ⪰ categoriser ranking-based semantics [19]. This ranking considers the direct attackers of an argument to calculate its strength value.
Definition 5 ([19]). Let = (, ). The h-categoriser function : → (0, 1] is defined as: () = ⎧ ⎨1 ⎩ 1+∑︀∈− 1 () if − = ∅ otherwise ().
The h-categoriser ranking-based semantics defines a ranking ⪰ on s.t. for , ∈ , ⪰
if () ≥
Pu et al. [20] have shown, that the h-categoriser ranking-based semantics is well defined, i. e., an hcategoriser function exists and is unique for every AF.
Example 2. Given the AF from Example 1. We can calculate for each argument a strength value using the h-categoriser function. Argument is unattacked, hence, () = 1. Based on the value of , we can calculate the remaining values: 1A preorder is a (binary) relation that is reflexive and transitive.
One example for ranking-based semantics is the h- -supports if ∈ ( ) and for all ∈ ( ), with These values will result in the following ranking: (, ) = (, 1, ..., − 1, ) with (, +1) ∈ for all with 0
= and = . The strongly connected components ( ) of an AF are the maximal subgraphs ′ = (′, ′), where for every pair of arguments , ∈ ′ there exists an undirected path (, ) = ( = 0, 1, ..., +1, = ) s.t. for every there is either (, +1) ∈ or (+1, ) ∈ . For an AF = (, ) and an extension-based semantics , an argument weakly -supports if ∈ ( ) and for all ∈ ( ), with ∈ then ∈ and strongly ∈ then there is ′ ∈ ( ) with ′ ⊆ , ∈ ′
A ranking-based semantics satisfies the respective principle if for all AFs = (, ) and any and ∈/ ′.
, ∈ : () = 0.46; relevant. ⪰ if () ⪰ ′ ().
For a pair of AFs = (, ) and ′ = (′, ′) and every isomorphism : → ′, we have Independence ( In). Unconnected arguments should not influence a ranking.
, ∈ ′: ⪰ if ⪰ ′ .
For every ′ = (′, ′) ∈ ( ) and for all Void Precedence ( VP). Unattacked arguments should be ranked better then attacked ones.
If − = ∅ and − ̸= ∅ then ≻ .
Self-Contradicition ( SC). Self-attacking
arguments should be ranked worse than any other argument.
If (, ) ∈/ and (, ) ∈ then ≻ . compared based on the number of attackers.
If |− | < |− | then ≻ .
Quality Precedence ( QP). Two arguments are compared based on the strength of their attackers. ≻ then ≻ .
If there is ∈ − s.t. for all ∈ − it holds that Counter-Transitivity ( CT ). Two arguments are compared based on the number and quality of their attackers. for all ∈ − then ⪰ .
If some injecitve : − → − exists s.t. () ⪰
Strict Counter-Transitivity ( SCT ). Strict version of .
If some injecitve : − → − exists s.t. () ⪰ for all ∈ − and either |− | < |− | or there exists some ∈ − with () ≻ , then ≻
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). Every defender should attack 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 arguments should be equally ranked.
If − = − = ∅ then ≃ . any unattacked indirect attackers should be ranked better than arguments only attacked by one unattacked argument.
Attack vs. Full Defense ( AvsFD). Arguments without fine such extension-ranking semantics. Their semantics exists unattacked ∈ − , then ≻ .
If acyclic and every path (, ) in from
argued that the characteristic function does not behave unattacked to has = 0 mod 2 and there intuitive if applied to conflicting sets. Therefore a variaCardinality Precedence ( CP). Two arguments are weak -Support ( w -S). If an argument is an un -Compatibility ( -C). Credulously accepted argu
ments should be ranked better than rejected ar- . guments.
For an extension-based semantics it holds that if ∈ ( ) and ∈ ( ), then ≻ . avoidable side-efect of accepting another argument , then should be at least as acceptable as .
If weakly -supports , then ⪰ . 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 [4]. h-categoriser satisfies
Abs, In, VP, CT, SCT, DP, and NaE, every other principle from Definition 6 is violated
Extension-ranking semantics defined in [ 6] are a generalisation of extension-based semantics. These semantics are used to state that a set of arguments is not only jointly acceptable or not, but also whether a set is more plausible than another set ′.
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 , ′ ⊆ define the usual abbreviations as follows:
plausible as ′ with respect to in if ⊒ ′. We
we say is at least as • is strictly more plausible than ′ (denoted as ⊐ ′) if ⊒ ′ and not ′ ⊒ ;
• and ′ are equally as plausible (denoted as if neither ⊒ ′ nor ′ ⊒ . ≡ ′) if ⊒ ′ and ′ ⊒ ;
• and ′ are incomparable (denoted ≍ ′)
Skiba et al. [6] defined a family of approaches to deare generalisations of the classical extension-based semantics. Using these semantics we can state that a set is “closer” to be admissible, than another set. Skiba et al. [6] tion of the characteristic function ℱ
* was introduced.
The function ℱ * : 2 ℱ * () = ⋃︀∞ =1 ℱ*, () with
→ Let = (, ) be an AF and ⊆
2 is defined as ℱ 1*, () = ; ℱ*, () = ℱ*− 1, () ∪ ℱ (ℱ*− 1, ()) ∖ − . Before we define the semantics, we recall the base funcExtension-ranking semantics also follows a principletions, each of them generalises one aspect of extension- based approach. Before we recall the principles defined • Complete extension-ranking semantics - via ence the ranking. based reasoning. be an AF and ⊆ {, , , } via Definition 9 (Base Functions [6]). Let = (, ) . Define the base functions
∈ (, ) = {(, ) ∈ |, ∈ }; (, ) = ∖ ℱ (); (, ) = ℱ * () ∖ ; (, ) = { ∈ ∖ |¬∃ ∈ : (, ) ∈ }; , ′ ∈ via: and the corresponding base extension ranking ⊒ for
⊒ ′ if (, ) ⊆ (′, )
By lexicographically combining these base functions, we denote the extension-ranking semantics.
We define: Definition 10. Let = (, ) be an AF and , ′ ⊆ .
• Admissible extension-ranking semantics - via ⊒ - ′ if ⊐ ′ or ( ≡
′ and ⊒
′). ⊒ ⊒ ⊒ ′ ⊆ ⊒ ⊆ ). ′). ′). - ′ if ⊐ - ′ or ( ≡
- ′ and • Preferred extension-ranking semantics - via - ′ if ⊐ - ′ or ( ≡
- ′ and • Grounded extension-ranking semantics - via - ′ if ⊐ - ′ or ( ≡
- ′ and via ⊒ and ⊒
′). • Semi-stable extension-ranking semantics - - ′ if ⊐ - ′ or ( ≡
- ′
In words, one set is at least as plausible as ′ with respect to the admissible ranking, if has fewer conflicts than ′ or if and ′ have the same conflicts, then we compare the undefended arguments. For complete we first look at the admissible ranking and in case of equality we look at the ranking. Note that since AFs without a stable extension exists it is impossible to define a generalisation of the stable semantics, hence we define a generalisation of the semi-stable semantics instead.
Example 3. Continuing Example 1. Comparing sets 1 = {, } and 2 = {, , } with the admissible ranking, we see and ′ have the same conflicts (, ) and (, ), however 2 defends argument from , therefore 2 ⊐ 1, so 2 is closer to be admissible, then 1. in [6], we need to introduce the notion of most plausible sets i.e. sets for which we can not find any other sets ranked strictly better.
Definition 11 (Most plausible sets). Let = (, ) be an AF, , ′ ⊆
two sets of arguments and an extension-ranking semantics. We denote by ( ) the minimal (or most plausible) elements of the extension ranking ⊒ , i.e., ( ) = { ⊆ | ∄′ ⊆ with ′ ⊐ }.
The principle -generalisation states, that most plausible sets should coincide with the -extensions.
Definition 12 ( -Gen). Let be an extension-based semantics and an extension-ranking semantics. satisfies • -soundness if for all
• -completeness if for all
( ) ⊆ ( ) ⊇ ( ).
( ).
and -completeness. • -generalisation if satisfies both -soundness = = (, ): (, ):
The next two properties (composition and decomposition) state that unconnected arguments should not influDefinition 13 ((De)Comp). Let
be an extensionranking semantics. satisfies
composition if for every if s.t. = 1 ∪ 2
︂{ 1 ∩ 2 = ∅ and , ′ ⊆ ∩ 1 ⊒1 ′ ∩ 1 }︂ ∩ 2 ⊒2 ′ ∩ 2 = (1, 1) ∪ (2, 2) with 1 ∪ 2 it holds that then ⊒ ′.
decomposition if for every s.t. = 2 1 ∪ 2 = =
(1, 1) ∪ (2, 2) with 1 ∩ ∅ and , ′ ⊆
1 ∪ 2 it holds that if ⊒ ′ then ︂{ ∩ 1 ⊒1 ′ ∩ 1 }︂ ∩ 2 ⊒2 ′ ∩ 2
.
The reinstatement principles are used to establish that the addition of defended arguments, which do not create new conflicts, is preferred.
Definition 14 (RI ). Let be an extension-ranking se ∈/ (− ∪ + ) implies ∪ {} ⊒ . mantics. satisfies (, ) with ⊆ weak reinstatement if for all = holds ∈ ℱ (), ∈/ and
strong reinstatement if for all = (, ) + ) implies ∪ {} ⊐ .
with ⊆
holds ∈ ℱ (), ∈/ and ∈/ (− ∪
Names of arguments should not influence the ranking Definition 15 (SI ). An extension-ranking semantics however these two semantics disagree on the strength satisfies syntax independence if for every pair of AFs = of argument quite strongly. In the ranking induced (, ), ′ = (′, ′) and for every isomorphism : by -, is the weakest argument, while in the rankLike shown by Skiba et al. [6] extension-ranking se- that ⪰ mantics and ranking-based semantics are related to each other. We use extension-ranking semantics and their re for these principles. sulting preorders to construct a ranking over arguments, is not influenced by the names of the arguments if the where arguments are ranked based on the strength of the corresponding sets. underlying extension-ranking semantics is also not influenced by the names.
Definition 16 ([6]). Let = (, ) be an AF, , ∈ , Proposition 1. If extension-ranking semantics satisfies In words, an argument is at least as plausible as if we have ⊐ ′ it also hold that () ⊐ ( ) (′). → ′, for all , ′ ⊆
The extension-ranking semantics based on semantics responding -Gen,
Comp,
DeComp, SI and
wRI.
{, , , , } do satisfy their cor{-, -, -, -} also satisfies sRI [6]. 3. Social Ranking Problem
⊒ ′. and be an extension-ranking semantics. We define an
ranking-based semantics ⪰ via ⪰ if there is a set with ∈ s.t. for all sets ′ with ∈ ′ we have is contained in a set , which is ranking better than any set ′ containing .
Example 4. Continuing with Example 1. Using - as the underlying extension-ranking semantics, we see that {, } and {, } are admissible sets. Since - satisfies -Gen, we know that there can not be any set ranked better than these two sets and especially no set containing is ranked better. This observation result in the ranking: ≃ - ≃ - ≻
- .
Since {, } and {, } are also complete, preferred and semi-stable sets, we see that -, -, and - do induce the same ranking. Only for - the induced ranking difers: ing based on h-categoriser, is the weakest argument.
Hence, the discussion about counter-intuitive behaviour of ranking-based semantics from Blümel and Thimm [21] can be recalled. Blümel and Thimm argued that credulously accepted arguments with respect to an extensionbased semantics should be ranked better, than rejected arguments. Hence, should be ranked better than .
Next, we investigate the principles the ranking induced by an extension-ranking semantics does satisfy. Skiba et al. [6] have discussed Abs, In and SC and have stated
∈ {-, -, -, -, -} satisfies
Starting with Abs, we see that the induced ranking SI, then ⪰ any extension-based semantics. Similar for the extensionranking semantics the first step is to compare two sets of arguments based on their conflicts. A conflict-free set is always ranked better than a conflicting set. Since the addition of a self-attacking argument into a set always coincides with a conflicting set, we see that any selfattacking argument will be ranked worse, than any non self-attacking argument.
Proposition 3. If extension-ranking semantics satisfies -soundness, then ⪰
satisfies SC. ⪰ . ′ for any ′ with ∈ ′, since ({}, ) = ∅ and (′, ) ̸= ∅. So, the induced ranking will be lates CP, CT and SCT [4].
Based on the satisfaction of SC, we know that ⪰ vio -soundness, then ⪰
violates CP, CT and SCT.
Since two credulously accepted arguments are always ranked equally in the induced ranking, we can not identify whether one argument is attacked or not. Hence, VP is violated.
Example 5. Let
= ({, , }, {(, ), (, )} extension and therefore we have be an AF and any extension-ranking semantics satisfying -soundness. We know that {, } is an admissible
≃ ≻ . satisfies the weak version.
However, − = ∅ and − = {} and this violates VP.
Thimm and Kern-Isberner [
Similar to the example for showing the violation of VP, we can show that two arguments are ranked equally despite their attackers not being equally strong, which violates QP.
Example 6. Let = ({, , , , }, {(, ), (, ), (, ), (, ), (, )}) tics satisfying -soundness, then since is self-attacking,
we know that ≻ . So, the attacker of is stronger a contradiction to QP.
However, , ∈ ( ) and therefore ≃ . This is 32–43 Proposition 4. If extension-ranking semantics satisfies depicted in Figure 2 and any extension-ranking seman- that these defenders are simple or distributed. Hence, than the attacker of , therefore QP would imply ≻ . Example 8. Let be the AF depicted in Figure 4 and Two arguments, which are rejected and not selfattacking, can be ranked equally. This fact entails the violation of DP. Even-though one argument has a defender while the other one has none, both these arguments can be rejected.
depicted in Figure 3 and = ({, , , , , }, {(, ), (, ), (, ), (, )}
∈ {-, -, -, -, -, -}. induced ranking entails ≃ the remaining semantics.
Then |− | = |− | = 1, while has one defender and
has no defender. DP would entail ≻ , however the
- respectively ◁▷ for
The idea of DDP is that every attacker should be defeated by exactly one defender. This behaviour can not be depicted, while using extension-ranking semantics, since the number of defenders is not relevant for the acceptance of an argument. An argument is credulous accepted w.r.t. admissible semantics if we find at least one set of defenders for this argument, it is not important
∈ {-, -, -, -, -, -}. which violates DDP.
For , it holds that the number of attackers and defenders are the same. However, the defense of is distributed and simple, while the defense of is only simple. So, if DDP is that both {} and {} are conflict-free, hence both these sets are most plausible sets and therefore we have ≃ ,
satisfied it has to hold that ⪰ . For
= - , we have ≃ .
Let = -, we know that
= {1, 3, 4, 1, 2, 4} and its subsets are the admissible extensions and therefore also the most plausible sets. In particular, , ∈ ( ). For set {} we have ({}, ) = ∅ and ({}, ) = {} and for {} we have ({}, ) = ∅ and ({}, ) = {}, so there can not be a set ̸⊆ with ≻ and () ⊂ {}, otherwise this entails () = ∅ ({}), which means () = ∅
.
However, Skiba et al. [6] have shown that this entails ∈ ( ) meaning ⊆ for {}. Hence, {} and {} are on the second level, but these two sets are incomparable, which entails ◁▷ and
. Similar can be reason with ∈ such that for every ′ ⊆ with ∈ ′ we have ⊐ ′, this implies ≻ .
For an ranking-based semantics to satisfy NaE, two unattacked argument should be handled equally. To recap, unattacked arguments are always admissible credulously accepted, and therefore this principle is satisfied by ranking-based semantics defined based on Definition 16.
Proposition 6. If extension-ranking semantics satisfies -soundness, then ⪰ Proof. Let = (, ) be an AF and an extension- found in the literature like in [13, 14, 15, 16]. A detailed unattacked, we know that they are admissible credulous accepted and there are sets ∈ ( ) and ′ ∈ ( ) with ∈ and ∈ ′, this implies was to generalise the extension-based reasoning. The goal was to keep -extensions intact and compare the remaining sets. For every credulously accepted argument, we can find one -extension containing that argument.
Hence, ⪰ satisfies -C.
Proposition 7. If extension-ranking semantics satisfies -Gen, then ⪰
satisfies -C. and therefore ≻ .
Proof. Let = (, ) be an AF and an extensionranking semantics. Assume satisfies -generalisation, then for any argument ∈ that is credulously accepted, there is a set ∈ ( ) with ∈ and for every rejected argument there is no set ′ s.t. ′ ∈ ( ) and ∈ ′. This implies that ⊐ ′
If the acceptance of an argument is the unavoidable ∈ side efect of accepting another argument, then both these arguments are credulously accepted and ranked equally.
Hence, w -S is satisfied.
Proposition 8. If extension-ranking semantics satisfies -Gen, then ⪰ if is credulously accepted wrt. and for all ∈ ( ) with ∈ we have ∈ , then has to be credulously accepted as well. This implies that there exists a set ∈ ( ) with , ∈ and therefore we can
As shown in the proof for Proposition 8 we know that two credulously accepted arguments are ranked equally
and therefore s -S is violated. strong with respect to ⪰
Since a number of principles are violated a discussion about Definition 16 is evident. One obvious change of this definition is to change the quantifiers used. So, for an AF = (, ), a extension-ranking semantics and , ⊆
instead of searching for one set with ∈ it has to hold for all sets with ∈ that there is a
set ′ with ∈ ′ such that ⊐ ′. The problem with this definition is that the resulting ranking is flat, i.e. it has only one level, since the set ′ = is always ranked at least as bad as any other set. Hence, this change results in an even worse ranking. Besides Definition 16 a number of diferent social ranking approaches can be analysis of the resulting ranking-based semantics will be done in future work. Another interesting observation is that the induced The example shows a few shortcomings.
Since ranking based on an extension-ranking semantics are in a sense a generalisation of credulous acceptance. Every olated. If we focus on extensions alone, then conflictcredulously accepted argument is ranked best, however freeness is the most basic propriety for the acceptance of we can say even more. If we look at the ranking induced by the grounded extension-ranking semantics in Example 4, we see that argument ∈ ( ), while , , ∈/ ( ). However, we can still compare and with and can state that and are stronger arguments than . a set. In addition to the violation of -soundness, we see that the set containing all arguments is ranked highly, despite being the most conflicting set. If we follow the justification of Skiba et al. [ 6], we argue that this is a disadvantage of this approach. However, the goal of the Such a statement is not possible with classical credulously work of Skiba et al. was to generalise the extension-based {, } ⊐- {}, we know that -soundness is vito structured argumentation [8] or preference-based ar- since the names of the arguments are not important. We
In a sense, the elitist operator focuses on the best ar- ranked element, hence this best ranked argument domiacceptance.
A number of approaches to lift a ranking over objects into a ranking over sets of objects were already discussed in the area of computation social choice [23] and applied gumentation frameworks [9, 10, 11, 12]. For both these frameworks, the preference data is part of the input and not based on the structure of the argumentation framework. The goal of this section is to discuss an approach satisfies to define lifting operators without the need of additional information like preference data. ⊆ Definition 17 (Lifting Operator). For an AF = (, ) an lifting operator takes as input a set of arguments and a ranking-based semantics on and outputs
an extension-ranking semantics ⊒ on the powerset of .
Lifting operators were already discussed in the context of structured argumentation and in particular for the ASPIC+ framework [24]. Maly and Wallner [8] have shown that the elitist lifting operator satisfies a number of interesting principles in the structured case. The elitist lifting operator states that for a set to be preferred over another set ′, there has to be an argument in which is ranked better than any argument in ′ wrt. a ranking-based semantics .
Let = (, ) be an AF, and rankingranking semantics ⊒ based semantics and , ′ ⊆ - by: ⊒ . We define an extension
- ′ if there is an argument ∈ s.t. for all arguments ∈ ′ we have ⪰ . gument of each set.
Example 9. Let us continue with Example 1. The hcategoriser function returns {, } ⊐- {}, since ≻
. for . Looking at the sets {} and {, }, we see that that ⊒ reasoning. reasoning process. Blümel and Thimm [21] have discussed the counter-intuitive behaviour of ranking-based semantics from the viewpoint of extension-based reasoning. The majority of the ranking-based semantics used in the literature do not satisfy -C, hence it is not surprising,
- is not a generalisation of extension-based For SI we see easily, that ⊒
Next, we discuss the principles ⊒ - satisfies this principle,
- does satisfy. show a more general statement.
Proposition 9. If the underlying ranking-based semantics
Abs, then ⊒
- satisfies SI.
Proof. Let = (, ) be an AF, a ranking-based semantics, which satisfies abstraction, and two arguments , ∈ , then for any isomorphism ( ) it holds that
if ⪰ , then () ⪰ ( ) (). Hence, for two sets , ′ ⊆
we have if exists in ( ) therefore () ⊒ ( )
- (′).
argument ∈ s.t. ⪰ and this argument also ⊒
- ′, then there is an In Example 9, we have seen that ⊒ satisfies -soundness and therefore this semantics can not satisfy -Gen for
∈ {, , , , }. In order to show that one set of arguments is ranked better than another one, we only have to find one argument in the ifrst set which is better than any argument in the second set. This observation yield to conflicting sets being ranked highly, if these sets contain one highly ranked argument, especially the set containing all arguments will be ranked as a most plausible set. This shows that for no ranking-based semantics the induced extensionranking semantics ⊒
For every set , ⊒ - satisfies -soundness.
- focuses only on the best nates the whole set. This domination of one argument also holds in disjoint AFs. Hence, we can show that
Comp. We can show an even stronger ⊒ proposition.
- satisfies tics satisfies In, then ⊒ - satisfies
Comp.
Proposition 10. If the underlying ranking-based semanProof. Let be an AF s.t. = 1 ∪ 2 = (1, 1) ∪ Proposition 11. If satisfies VP and NaE, then ⊒ every argument in ′ and therefore ̸⊒1 is a contradiction to our assumption and proofing that
- ′, which , assume ′ ⊐
- , composition is satisfied. ing Comp, this behaviour violates DeComp.
While one dominating argument is helpful for satisfy- satisfied, since every set is ranked better then ∅ . EsExample 10. Let = ({, , , }, {(, ), (, )}) and which satisfies
VP like h-categoriser is: the resulting ranking for every ranking-based semantics , know that − = ∅ otherwise ∈/ ℱ (). If satisfies ≃ ≻ ≃ .
Let us look at the two sets = {, } and ′ = {, }, then these two sets are equally ranked in wrt. ⊒ However, if we split this AF into its connected components
-. then we see that ⊐1 fore DeComp is violated. 1 = ({, }, {(, )} ) and 2
= ({, }, {(, )}), is violated.
- ′ and ′ ⊐-2 and there
Before we discuss the reinstatement principles, we have to discuss the empty set. The elitist lifting operator is not applicable for the empty set. Hence, the empty set has to be handled diferently. Modgil and Prakken [ 24] argued that the empty set should not be ranked better than any non-empty set and any non-empty set should be ranked better than the empty set. In the context of extension-based reasoning we can argue that this should not be the case, since the empty set is always an admissible extension and if -Gen should be satisfied, then the empty set should be among the best ranked sets. However, in Example 9 we have seen that ⊒ satisfies -soundness and therefore will not satisfy any
- does not version of -Gen. Investigating ⊒ that for every non-empty set every superset of is at least as plausible as . Following this observation, then we should agree with Modgil and Prakken and rank the empty set as the least preferred set. In the remainder of this section, we will discuss both approaches to handle
- further, we see the empty set.
Using the fact that for every non-empty set their supersets are ranked at least as good as , we see that adding any argument into the ranking of will not get worse and this implies that wRI is satisfied. satisfies
wRI.
Proof. Let = (, ) be an AF, any ranking-based semantics and ⊆ ′ of it holds that ′ ⊒ . We know that for every superset
- , since every argument in is also in ′, therefore if an argument from is ranked better any argument inside another set ′′ and we can follow that ⊒ and therefore also ′ ⊒ - ′′, we know that ∈ ′
- ′′. Since ∪ {} for , we know that weak reinstatement is satisfied. ∈ ℱ (), ∈/ and ∈/ (− ∪ + ) is a superset of
Next, we discuss the two variations of handling ∅, the empty set is either among the best ranked sets or the worst ranked set. If = ∅ and ′ ⊐- for every non-empty set ′ ⊆
, then weak reinstatement is ∈/ (− ∪ + ). If = ∅ and ⊒ pecially the set {}, with ∈ ℱ (), ∈/ and
- ′ for every ′, then for ∈ ℱ (), ∈/ and ∈/ (− ∪ + ), we reinstatement is satisfied. void-precedence and non-attack equivalence, then there
is no ∈ s.t. ≻ this implies that for every set ′ containing , we know that ′ ⊒ ′′ ⊆ and especially ′′ = ∅. This implies that weak
- ′′ for any set While ⊒
- satisfies wRI, we can easily see that sRI attack . Hence, sRI is violated.
Example 11. Let = ({, , }, {(, ), (, )} be an AF and the resulting ranking based on h-categoriser is despite the fact that is defended by {} and does not
Looking back at the proofs, we see that there is no diference between ranking the empty set as the best or the worst set w.r.t. the satisfied principles. Hence, the position of the empty set should be based on the application. If admissible sets should be ranked highly, then the empty set should be ranked highly.
In this work, we discussed the connection between ranking-based semantics and extension-ranking semantics. We proposed approaches to transform extensionranking semantics into ranking-based semantics (social ranking) and the other way around, from ranking-based semantics to extension-ranking semantics (liftings). Additionally, we analysed the properties of the resulting semantics based on principles out of literature for rankingbased and extension-ranking semantics.
Combining ranking-based semantics and extensionbased reasoning was already discussed in [25]. One of receive the rankings as a fixed input. This ranking is not based on the behaviour of the arguments or the structure of the underlying AFs. Additionally, PAFs are only focused on -extensions, while our work focuses on the
powerset of arguments. The semantics proposed in this work have some undesirable behaviour. For the social ranking case, we receive a generalisation of credulous acceptance, however a numFigure 5: AF for Example 12, where arguments and are ber of desirable principles are violated. For the lifting added later. case, the most conflicting set is ranked among the best sets. Additionally, applying these two semantics one after another result in a flat ranking, i.e. every argument resp. the goals of the authors was to refine the extension-based set of arguments are ranked equally. These behaviours reasoning process with the help of ranking-based seman- can be used as a motivation to define new social ranktics. The strength of a set is the aggregated strength of ing solutions and lifting operators specifically tailored to each argument contained inside that set. One way to es- abstract argumentation. tablish the strength of each argument are ranking-based semantics and the resulting rankings over arguments. Acknowledgements. The research reported here was Based on the number of arguments ranked better than an supported by the Deutsche Forschungsgemeinschaft unargument, the strength of that argument is established. der grant 506604007.
= ({, , }, {(, ), (, ), (, ), (, ), (, ), (, )}) [1] K. Atkinson, P. Baroni, M. Giacomin, A. Hunter, as depicted in Figure 5 be an AF. The corresponding ranking H. Prakken, C. Reed, G. R. Simari, M. Thimm, S. Vilbased on h-categoriser is ≻ ≻ . Argument lata, Towards artificial argumentation, AI Mag. receives a score of 0, a score of 1 and a score of 2. If (2017). we sum up the strength values of each argument inside set [2] P. M. Dung, On the Acceptability of Arguments and we can establish the strength of each set. For example, set its Fundamental Role in Nonmonotonic Reasoning, = {, } has the value of 1 while set ′ = {} has the Logic Programming and n-Person Games, Artificial value of 2, meaning should be ranked better than ′. If Intelligence (1995). we add two arguments , , which are independent from [3] J. Leite, J. G. Martins, Social abstract argumentation, any other argument i.e. they do not attack , or nor are in: IJCAI’11, 2011, pp. 2287–2292. attacked by these arguments, the resulting ranking is: [4] L. Amgoud, J. Ben-Naim, Ranking-based semantics for argumentation frameworks, in: SUM’13, 2013, ≃ ≻ ≻ ≻ . pp. 134–147.
[5] E. Bonzon, J. Delobelle, S. Konieczny, N. Maudet, However, for the two sets and ′ we see that has the A comparative study of ranking-based semantics aggregate strength value of 2 + 3 = 5 and for ′ the for abstract argumentation, in: AAAI’16, 2016, pp. score is 4, meaning that ′ should be ranked better than 914–920. . Hence, this ranking is influenced by unconnected and [6] K. Skiba, T. Rienstra, M. Thimm, J. Heyninck, independent elements, which can be seen as a big disadvan- G. Kern-Isberner, Ranking extensions in abstract tage. This example shows that aggregation of the strength argumentation, in: IJCAI’21, 2021, pp. 2047–2053. values of each argument inside a set is possible, however [7] F. Brandt, V. Conitzer, U. Endriss, J. Lang, A. D. Prothe resulting ranking has undesired properties. Hence, a caccia, Handbook of computational social choice, discussion about the used ranking-based semantics and Cambridge University Press, 2016. aggregation functions is needed. [8] J. Maly, J. P. Wallner, Ranking sets of defeasible
Finding the “best” extensions is one of the focal points elements in preferential approaches to structured for discussing preference-based argumentation frame- argumentation: Postulates, relations, and characworks (short PAF ) [26], which are extensions of AFs, terizations, in: AAAI’21, 2021, pp. 6435–6443. where in addition to sets of arguments and attacks, a [9] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On preorder ≥ over the set of arguments is given. Using preferences and priority rules in abstract argumenthese preorders the “best” extensions can be found with tation, in: IJCAI’22, 2022. the help of operators similar to Definition 18 [ 9, 10, 11, 12]. [10] L. Amgoud, S. Vesic, Rich preference-based arThe diference between PAFs and our work is that PAF