=Paper=
{{Paper
|id=Vol-3236/paper6
|storemode=property
|title=Realisability of Rankings-based Semantics
|pdfUrl=https://ceur-ws.org/Vol-3236/paper6.pdf
|volume=Vol-3236
|authors=Kenneth Skiba,Matthias Thimm,Tjitze Rienstra,Jesse Heyninck,Gabriele Kern-Isberner
|dblpUrl=https://dblp.org/rec/conf/comma/SkibaTRHK22
}}
==Realisability of Rankings-based Semantics==
https://ceur-ws.org/Vol-3236/paper6.pdf
Realisability of Ranking-based Semantics
Kenneth Skiba1 , Matthias Thimm1 , Tjitze Rienstra2 , Jesse Heyninck3 and
Gabriele Kern-Isberner4
1 Artificial Intelligence Group, University of Hagen, Germany
2 Maastricht University, Maastricht, The Netherlands
3 Open Universiteit, Heerlen, The Netherlands
4 TU Dortmund, Dortmund, Germany
Abstract
In this work, we discuss the realisability problem for ranking-based semantics in the area of abstract
argumentation. So, for a given ranking and ranking-based semantics, we want to find an AF s.t. the
selected ranking-based semantics induces our ranking when applied to the AF. We show that this question
can be answered trivially with yes for a number of ranking-based semantics, i.e. for every ranking we can
find such an AF. In addition to the discussion about the realisability problem, we also introduce a new
equivalence notion for argumentation frameworks. We call two AFs ranking equivalent if they have the
same ranking for a ranking-based semantics.
Keywords
Abstract Argumentation, Ranking-based Semantics, Realisability, Equivalence
1. Introduction
In recent years, abstract argumentation frameworks (AF) [1] have gathered research interest as a
model for argumentative reasoning. They are a model for rational decision-making in presence of
conflicting information. Arguments and attacks are represented as nodes and edges, respectively,
of a directed graph, i.e. an argument a attacking argument b is represented as a directed edge from
a to b. In a scenario of strategic argumentation, an agent wants to persuade an opponent. One
way to find a persuasion strategy is by considering the strength of each argument, since stronger
arguments have a higher chance to persuade the opponent. Hence, ranking-based semantics
were introduced (see [2, 3] for an overview). These semantics define a preorder based on the
acceptability degree of each argument s.t. we can state that an argument a is “stronger” than an
argument b. With these preorders we can establish an acceptance value for each argument, which
is more than a binary classification of accepted or not accepted.
Consider a scenario where an agent was invited to a public discussion about the topic of
banning cars from the city-center. To prepare for this discussion, our agent observes prior
discussions about the same topic. Based on this observation, she prepares arguments and a
strength assessment of each argument. For example, she estimates that the argument “Banning
cars from the city-center would yield better air in the city-center” is her strongest argument.
SAFA’22: Fourth International Workshop on Systems and Algorithms for Formal Argumentation 2022, September 13,
2022, Cardiff, Wales, United Kingdom
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
73
Kenneth Skiba et al. CEUR Workshop Proceedings 73–85
However, she only has a set of arguments and a strength assessment of each argument and no
presentation strategy. An abstract argumentation framework can represent one such a strategy.
So, our agent has to establish an AF based on her observed arguments and strength assessment.
In this work, we discuss a more fundamental question of whether there exists an AF with the
observed strength assessment. So, for a given ranking-based semantics ρ and a preorder r can
we find an AF, which exactly has r as its ranking when applying ρ? This problem is known as
realisability and was already investigated for extension semantics, which specify when a set of
arguments is considered jointly acceptable. Dunne et al. [4] have shown that there are sets of
extensions for which we cannot find an AF s.t. this AF has exactly these extensions. For example,
for a set of extensions to be the set of the stable extensions of an AF, each set has to be pairwise
incomparable with respect to set inclusion, and for every argument a not in a set E there has to be
a conflict between a and E.
A discussion about the realisability of rankings can be motivated as a discussion about the
expressivity of ranking-based semantics. We can ask about the limitations of any semantics, so
what can we express with this formalism and what is impossible to express. This discussion will
also show us the limitations of any solver for ranking-based semantics. With knowledge about the
realisability of rankings, we can reduce the search room for solvers for ranking-based semantics.
Since when a ranking is not realisable we do not need to test if this ranking is a solution of our
problem.
In this paper, we show that for a number of ranking-based semantics it holds that any ranking
is realisable. So, for every ranking, we can find an AF where that ranking is the corresponding
ranking induced by the ranking-based semantics. Hence, the realisability problem for these
ranking-based semantics is trivial (the answer is always yes). We show this with a simple
construction, where we can construct an acyclic AF for any ranking. Based on these results, we
discuss a new notion of equivalence, where two AFs are considered ranking equivalent if they
have the same corresponding rankings.
This paper is structured as follows: First, we recall all necessary background information about
abstract argumentation and ranking-based semantics in Section 2. In Section 3 we discuss the
realisability problem for ranking-based semantics. Our new notion of ranking equivalence is
introduced in Section 4. In Section 5 we talk about related work, and Section 6 concludes this
paper.
2. Preliminaries
Argumentation frameworks introduced by Dung [1] are a formalism that allows the representation
of conflicts between pieces of information, and the deduction of which pieces of information
are acceptable (i.e. which ones can be considered as true). Formally, an abstract argumentation
framework (AF) is a directed graph AF = (A, R) where A is a finite set of arguments and R ⊆ A×A
is an attack relation. An argument a is said to attack an argument b if (a, b) ∈ R. We say that
an argument a is defended by a set E ⊆ A if every argument b ∈ A that attacks a is attacked by
some c ∈ E. For a ∈ A define a− = {b | (b, a) ∈ R} and a+ = {b | (a, b) ∈ R}, so the sets of
attackers of a and the set of arguments attacked by a. For a set of arguments E ⊆ A we extend
these definitions to E − and E + via E − = a∈E a− and E + = a∈E a+ , respectively.
⋃︁ ⋃︁
74
Kenneth Skiba et al. CEUR Workshop Proceedings 73–85
a b c d
Figure 1: Abstract argumentation framework AF from Example 1.
Example 1. Consider the argumentation framework AF = (A, R) depicted as a directed graph in
Figure 1, with the nodes corresponding to arguments A = {a, b, c, d}, and the edges corresponding
to attacks R = {(a, b), (b, c), (c, d), (d, c)}.
A number of approaches to reason in the area of argumentation were proposed, like the
extension-based or the labelling-based approaches (for an overview, see the book chapter [5]).
Both these approaches are handling sets of arguments, which can be considered jointly acceptable.
The extension-based semantics are relying on two basic concepts: conflict-freeness and defence.
Definition 1 (Conflict-free, Admissible). Given AF = (A, R), a set E ⊆ A is
• conflict-free iff ∀a, b ∈ E, (a, b) ̸∈ R;
• admissible iff it is conflict-free, and it defends its elements.
We use cf(AF) and ad(AF) for denoting the sets of conflict-free and admissible sets of an
argumentation framework AF, respectively. The intuition behind these principles is that a set
of arguments may be accepted only if it is internally consistent (conflict-freeness) and able to
defend itself against potential threats (admissibility). The semantics proposed by Dung are then
defined as follows.
Definition 2 (Extension-based Semantics). Given AF = (A, R), an admissible set E ⊆ A is
• a complete extension (co) iff it contains every argument that it defends;
• a preferred extension (pr) iff it is a ⊆-maximal complete extension;
• the unique grounded extension (gr) iff it is the ⊆-minimal complete extension;
• a stable extension (st) iff E + = A \ E.
The sets of extensions of an argumentation framework AF, for these four semantics, are denoted
(respectively) co(AF), pr(AF), gr(AF) and st(AF).
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 argumentation framework AF
and an extension-based semantics σ , we use (respectively) skσ (AF), crσ (AF) and rejσ (AF) to
denote these sets of arguments.
Instead of only reasoning based on the acceptance of sets of arguments, ranking-based seman-
tics focus on the acceptance of a single argument with respect to the other arguments. Another
difference is that any argument can have more than two levels of relative acceptability. So, instead
of saying an argument is acceptable or not, we can say whether an argument is more acceptable
than another argument. Ranking-based semantics rank a set of arguments in an argumentation
framework from the most acceptable to the weakest one(s). This family of semantics compares
pairs of arguments using criteria like the number of attackers or defenders, or the quality of the
attackers. Note that the order returned by a ranking-based semantics is not necessarily total,
especially not every argument is comparable.
75
Kenneth Skiba et al. CEUR Workshop Proceedings 73–85
Definition 3. A ranking-based semantics ρ is a function, which maps an argumentation framework
ρ
AF = (A, R) to a preorder1 ⪰AF on A.
ρ
Intuitively a ⪰AF b means, that a is at least as acceptable as b in AF. We define the usual
ρ ρ ρ
abbreviations as follows; a ≻AF b denotes strictly more acceptable, i.e. a ⪰AF b and b ̸⪰AF a.
ρ ρ ρ
a ≃AF b denotes equally acceptable, i.e. a ⪰AF b and b ⪰AF a.
One example for ranking-based semantics is the h-categoriser ranking-based semantics [6].
This ranking considers the direct attackers of an argument to calculate its acceptability value.
Definition 4 ([6]). Let AF = (A, R). The h-categoriser function Cat : A → (0, 1] is defined as
Cat(a) = 1+∑ 1− Cat(b) .
b∈a
The h-categoriser ranking-based semantics defines a ranking ⪰Cat
AF on A s.t. for a, b ∈ A,
a ⪰Cat
AF b iff Cat(a) ≥ Cat(b).
Pu et al. [7] have shown, that the h-categoriser ranking-based semantics is well defined, i.e. a
h-categoriser function exists and is unique for every AF. Hence, the possibility of cycles is no
problem.
Example 2. Given the AF from Example 1. We can calculate for each argument a value using
the h-categoriser function. Argument a is unattacked, hence, Cat(a) = 1. Based on the value of
a we can calculate the remaining values: Cat(b) = 0.5; Cat(c) = 0.46; Cat(d) = 0.69. These
values will result in the following ranking:
a ≻Cat Cat Cat
AF d ≻AF b ≻AF c.
So, argument a is ranked highest, then d, b, and finally the least ranked argument is c.
Since there are a number of different approaches to rank arguments (see [2] for an overview), a
number of properties were defined to compare these approaches. We want to recall only a few of
them namely Abstraction, Argument Equivalence, and (Strict) Counter-Transitivity.
Abstraction [3] states that any isomorphism on the argumentation framework should not
influence the resulting ranking. So, the names of any argument are not important and should not
influence the acceptance of any argument.
Definition 5 (Isomorphism). An isomorphism γ between two argumentation frameworks AF =
(A, R) and AF′ = (A′ , R′ ) is a bijective function γ : A → A′ such that for all a, b ∈ A, (a, b) ∈ R
iff (γ(a), γ(b)) ∈ R′ .
Definition 6 (Abs). A ranking-based semantics ρ satisfies Abstraction if for every pair of AFs
AF = (A, R), AF′ = (A′ , R′ ) and every isomorphism γ : A → A′ , for all a, b ∈ A, we have a ⪰AF b
ρ
ρ
iff γ(a) ⪰AF′ γ(b).
Argument Equivalence [8] states that if two arguments have the same ancestors, then they are
equally acceptable. So, if two arguments have the same attackers, they also should be equally
acceptable.
1A preorder is a (binary) relation that is reflexive and transitive.
76
Kenneth Skiba et al. CEUR Workshop Proceedings 73–85
Definition 7 (AE). A ranking-based semantics ρ satisfies Argument Equivalence if for every
AF = (A, R) and every pair of argument a, b ∈ A it holds that if a− = b− then a ≃AF b.
ρ
We want to recall the property (Strict) Counter-Transitivity [3], which states that if an argument
b has at least as many number of attackers as argument a and every attacker is at least as acceptable
as those of a, then a is at least as acceptable as b. However, before we define these properties, we
need a different definition allowing us to compare two sets of arguments based on their number
of elements and acceptability.
Definition 8 ((Strict) group comparison [3]). Let ρ be a ranking-based semantics and AF = (A, R)
ρ
an AF. For any two sets E1 , E2 ⊆ A, E1 ≥S E2 iff there exists an injective mapping f from E2
ρ ρ ρ
to E1 s.t. that for all a ∈ E2 , f (a) ⪰AF a, and E1 >AF E2 iff E1 ≥AF E2 and (|E2 | < |E1 | or
ρ
∃a ∈ E2 , f (a) ≻AF a).
Definition 9 (CT). A ranking-based semantics ρ satisfies Counter-Transitivity iff for any AF =
(A, R) and ∀a, b ∈ A, if b− ≥S a− then a ⪰AF b.
ρ ρ
Amgoud and Ben-Naim [3] have introduced a strict version of Counter-Transitivity to ensure,
that if an argument b has strictly more attackers or the attackers of b are more acceptable, then a
should be more acceptable, than b.
Definition 10 (SCT). A ranking-based semantics ρ satisfies Strict Counter-Transitivity iff for
any AF = (A, R) and ∀a, b ∈ A, if b− >S a− then a ≻AF b.
ρ ρ
3. Realisability of Ranking-based Semantics
Realisability problems are not focusing on analysing given AFs, but rather on finding an AF with
given properties. These problems are fundamental to establish the limitations of a formalism.
Hence, we can use them to define the expressivity of this formalism.
3.1. Formal Definition
For extensions-based semantics σ , Dunne et al. [4] have defined the realisability problem. So,
given a set of σ -extensions E the question is: does an AF exist with exactly these σ -extensions
E? They have shown, when this question can be answered positively and when it is impossible to
construct such an AF. Since ranking-based semantics can be used to reason on AFs, a similar
realisability question can be asked. For a given ranking, does there exist an AF with exactly this
ranking induced by a ranking-based semantics?
Definition 11. A ranking r is ρ-realisable by a ranking-based semantics ρ if there is an AF s.t.
ρ(AF) = r.
Example 3. Consider the ranking-based semantics h-categoriser and the ranking r1 = a ≻Cat
d ≻Cat b ≻Cat c, then the AF depicted in Figure 1 has r1 as the corresponding ranking calculated
by the h-categoriser semantics.
77
Kenneth Skiba et al. CEUR Workshop Proceedings 73–85
a d b c
Figure 2: AFr1 constructed in Example 4.
So, the realisability problem depends on the ranking-based semantics used. There are rankings
for which we can find an AF s.t. the categoriser functions returns this ranking, but for a different
ranking-based semantics we may not find such an AF.
In the remainder of this section, we want to discuss, when a ranking based on a ranking-based
semantics can be realised. Later we will see that for a number of ranking-based semantics the
question whether there exists an AF with a given ranking is trivial, because every ranking is
realisable.
Definition 12. A ranking-based semantics ρ is called universally realisable if every ranking r is
ρ-realisable.
Next, we want to discuss one construction for an AF based on a given ranking.
Definition 13. Given a ranking r, we construct an AF AFr = (Ar , Rr ) in the following way:
• Every argument a appearing in r is part of Ar .
• (a, b) ∈ Rr iff a ≻ b in r.
So, every argument appearing in r is part of the AF and if an argument a is strictly more
plausible than b, then a attacks b. Otherwise, there is no attack. So, the highest ranked arguments
have no attackers and if two arguments are equally ranked, then they have the same attackers and
do not attack each other.
Example 4. Consider again r1 = a ≻ d ≻ b ≻ c. Using Definition 13 we construct the following
AFr1 = {{a, b, c, d}, {(a, b), (a, c), (a, d), (d, b), (d, c), (b, c)}} depicted in Figure 2.
With this construction, we can find an AF for a given ranking. Next, we will show that an
AF constructed in this way can already realise any ranking induced by a number of ranking-
based semantics. More specific, any ranking-based semantics which satisfies Abstraction, Strict
Counter-Transitivity, and Argument Equivalence are universally realisable.
Theorem 1. If a ranking-based semantics ρ satisfies Abstraction, Strict Counter-Transitivity, and
Argument Equivalence, then ρ is universally realisable.
Proof. To prove that ρ is universally realisable we have to show that every ranking is ρ-realisable.
Let r be any ranking and AFr = (Ar , Rr ) the corresponding AF constructed with Definition 13.
Assume ρ satisfies Abstraction, Strict Counter Transitivity, and Argument Equivalence. Let
a, b ∈ Ar with a ≻ b in r. Then because of the transitivity of r, we know that, a− ⊂ b− . Hence,
a has less attackers than b and every attacker of a is also an attacker of b. So there can not
78
Kenneth Skiba et al. CEUR Workshop Proceedings 73–85
be any attacker of a, which is strictly more acceptable any every attacker of b therefore Strict
ρ
Counter-Transitivity ensures that a ≻AFr b. Abstraction ensures, that the name of any argument is
not relevant for the ranking.
Let a, b ∈ Ar with a ≃ b in r. Then, it holds that a− = b− , since a and b have the same attackers
ρ
and ρ satisfies Argument Equivalence, we know a ≃AFr b.
This result shows that a good number of ranking-based semantics are universally realisable.
So, if we recall our agent example from the beginning, then we know that the agent has an easy
job establishing one underlying AF with her strength assessment.
Looking at the h-categoriser semantics, we know that it satisfies Abstraction, Strict Counter-
Transitivity, and Argument Equivalence, so any ranking is Cat-realisable (see [6, 7]).
Corollary 2. h-categoriser ranking-based semantics is universally realisable.
3.2. Realisability wrt. Discussion-based and Burden-based semantics
Next, we will discuss the realisability problem for a few ranking-based semantics from the
literature. We will start with Discussion-based (Dbs) and Burden-based (Bbs) semantics defined
in [3].
Discussion-based semantics compares two arguments with respect to the number of attackers
or defenders they have. First two arguments a and b are compared based on their number of
attackers. Argument a is more acceptable than b if a has fewer attackers. If both arguments have
the same number of attackers, the number of defenders are compared.
Definition 14 ([3]). Let AF = (A, R) be an AF. The discussion count of argument a ∈ A is denoted
as Dis(a) = (Dis1 (a), Dis2 (a), ...), whereby the function Disi for i ∈ {0, ..., n} are mapping
arguments to a value as follows:
−|a∗i | if i is odd
{︃
Disi : A → Z, Disi (a) :=
|a∗i | if i is even
Where a∗i denotes the arguments with a path to a with a length of i. So there is sequence
s = (a0 , ..., an ) of arguments s.t. for all b ∈ a∗i with a0 = b, an = a and for all i < n, (ai , ai+1 ) ∈ R.
The discussion-based semantics (Dbs) defines a ranking ⪰Dbs AF on A s.t. for a, b ∈ A, a ⪰AF b
Dbs
iff Disi (b) ⪰lex Disi (a), where ⪰lex denotes the lexicographical order.
The Burden-based semantics calculates the burden number of an argument at each step and
compares this value lexicographically for each pair of arguments to establish a ranking over
arguments. The burden number considers only the attackers of an argument.
Definition 15 ([3]). Let AF = (A, R) be an AF. The burden number is the value Bur(a) =
(Bur1 (a), Bur2 (a), ...) whereby the functions Buri for i ∈ N are mapping arguments a ∈ A to
values as follows:
{︄
1 if i = 0
Buri : A → Z, Buri (a) := 1
1 + ∑b∈a− Buri−1 (b) otherwise
The burden-based semantics (Bbs) defines a ranking ⪰Bbs Bbs
AF on A s.t. for a, b ∈ A, a ⪰AF b iff
Buri (b) ⪰lex Buri (a), where ⪰lex denotes the lexicographical order.
79
Kenneth Skiba et al. CEUR Workshop Proceedings 73–85
Amgoud and Ben-Naim [3] have shown that both Discussion-based and Burden-based seman-
tics satisfying Abstraction, Strict Counter-Transitivity, and Argument Equivalence. Meaning that
any ranking r is Dbs-realisable and Bbs-realisable.
Corollary 3. Discussion-based and Burden-based semantics are universally realisable.
3.3. Realisability wrt. Social Abstract Argumentation Framework
Since the abstract nature of AFs limit the expressivity of this framework a number of extensions
were introduced. Leite and Martins [9] have introduced social abstract argumentation frameworks
(SAF) which adds an assignment of votes to each argument. Later, Bonzon et al. [2] are using these
SAF as well as the simple product semantics by Leite and Martins [9] to denote a ranking-based
semantics ⪰SAF .
Definition 16 ([9, 2]). Let AF = (A, R) be an AF and SPε = ([0, 1], τε , ⋏, ⋎, ¬) be the simple
1
product semantics proposed in [9], where τε = 1+ε (with ε > 0), x1 ⋏ x2 = x1 × x2 (Product
T-Norm), x1 ⋎ x2 = x1 + x2 − x1 × x2 (Probabilistic Sum T-CoNorm) and ¬x1 = 1 − x1 . The total
mapping MS : A ← [0, 1] is a social model of AF under SPε s.t. for all a ∈ A:
MS = (a) = τε (a) ⋏ ¬ ⋎ {M(ai ) : ai ∈ a− }
The ranking-based semantics ⪰SAF defines a ranking ⪰SAF SAF
AF on A s.t. for a, b ∈ A, a ⪰AF b iff
MS (a) ≥ MS (b).
Bonzon et al. have shown that the resulting ranking-based semantics satisfies Abstraction
and Strict Counter-Transitivity. When looking at the definitions it is easy to see that Argument
Equivalence is also satisfied and therefore ⪰SAF is universally realisable.
Corollary 4. ⪰SAF is universally realisable.
3.4. Realisability wrt. Probabilistic Graded Semantics
Social abstract argumentation frameworks are not the only extension used to define a ranking-
based semantics. Thimm et al. [10] are using probabilistic argumentation frameworks (PAF)
[11], which are an extension of AFs s.t. every argument a receives a probability P(a) of being
present in an AF.
Definition 17. A probabilistic argumentation framework PAF is a triple PAF = (A, R, P) where
(A, R) is an AF and P is a function P : A → [0, 1].
By assuming probabilistic independence between the presence of different arguments, the
probability of acceptance of a can be defined. For PAF = (A, R, P), a ∈ A, σ ∈ {co, pr, gr} be
a semantics and ◦σ (AF) ∈ {skσ (AF), crσ (AF)} is the set of skeptically or credulously accepted
arguments, we denote PPAF
σ ,◦σ (AF) (a) as:
PσPAF
,◦σ (AF) (a) = ∑ ∏ P(a) ∏ (1 − P(a))
a∈X⊆A,a∈◦σ (AF|X ) a∈X a∈X
/
80
Kenneth Skiba et al. CEUR Workshop Proceedings 73–85
a b c d a d b c
Figure 3: [Left] AF from Example 1. [Right] AFr1 constructed in Example 4.
where AF|X is the induced subgraph of AF wrt. X i.e. AF|X = (X, R ∩ (X × X)). In order to define
a ranking-based semantics, Thimm et al. proposed that every argument in an AF receives the the
same uniform probability. Then the probability of acceptance of an argument can be interpreted
as a value of acceptance.
Definition 18. Let AF = (A, R) be an AF, p ∈ [0, 1] and PAF = (A, R, P) with P(a) = p for all
a ∈ A the corresponding PAF. For σ ∈ {co, pr, gr}, and ◦σ (AF) the probabilistic graded semantics
Gσ ,◦σ (AF),p is defined as: Gσ ,◦σ (AF),p = PPAF
σ ,◦σ (AF) for every a ∈ A. The corresponding ranking-
σ ,◦σ (AF),p σ ,◦σ (AF),p
based semantics Gσ ,◦σ (AF),p defines a ranking ⪰G
AF on A s.t. for a, b ∈ A, a ⪰G
AF b iff
Gσ ,◦σ (AF),p (a) ≥ Gσ ,◦σ (AF),p (b).
Thimm et al. have shown that the probabilistic graded semantics does not satisfy SCT [10],
however we can still show that this semantics is universally realisable.
Theorem 5. Gσ ,◦σ (AF),p is universally realisable for σ ∈ {co, pr, gr} and ◦σ (AF) ∈
{skσ (AF), crσ (AF)}.
Proof. Let r be any ranking and AFr the corresponding AF constructed with Definition 13.
Since AFr is acyclic, all semantics and reasoning modes coincide with credulous/skeptical
reasoning with grounded semantics, so there will be no need to distinguish those. We show
that Gσ ,◦σ (AFr ),p (AFr ) = r. Every unattacked argument in AFr will be ranked highest in the
induced ranking of Gσ ,◦σ (AF),p and these arguments are also ranked highest in r. Let a, b ∈ Ar
with a ≻ b in r, then we know that a− ⊂ b− . So every attacker of a is also an attacker of b.
Hence, if b is accepted in a subgraph, then a has to be accepted as well. Since a attacks b we
have the subgraph induced by X = {a, b} in which a is accepted and b is not accepted. Therefore
Gσ ,◦σ (AF),p b.
Gσ ,◦σ (AF),p (a) > Gσ ,◦σ (AF),p (b) and therefore a ≻AF
Since Gσ ,◦σ (AFr ),p satisfies AE we can use the same proof as for Theorem 1 to prove the case
a = b. So Gσ ,◦σ (AFr ),p is universally realisable.
This result shows that satisfying Abs, AE and SCT is not a necessary condition for a ranking-
based semantics to be universally realisable.
4. Ranking Equivalence
When we recall the AFs from Example 2 and Example 4 (both depicted again in Figure 3) we
see that they have a different structure. Indeed, these two AFs have different extensions. For
example, in AF the set {a, d} is stable, while in AFr1 the set {a} is the only non-empty complete
extension, meaning that this is also the only stable extension. In general, every AF constructed
81
Kenneth Skiba et al. CEUR Workshop Proceedings 73–85
with Definition 13 has only one complete extension. However, for both AFs the h-categoriser
semantics returns the same ranking: a ≻Cat Cat Cat
AF,AFr1 d ≻AF,AFr1 b ≻AF,AFr1 c, like shown in Example
2 and Example 4, respectively. So, even this easy construction defined in Definition 13 already
presents an interesting result: Two AFs have the same ranking but not the same extensions. Based
on this observation, we can define an equivalence notion.
Definition 19 (ρ-Ranking Equivalence). Two AFs AF1 = (A, R1 ), AF2 = (A, R2 ) are ρ-ranking
equivalence iff ρ(AF1 ) = ρ(AF2 ).
Two AFs are ρ-ranking equivalent if they have the same ranking. Like discussed previously,
this equivalence notion does not coincide with the standard notion of equivalence of AFs, where
two AFs are considered equivalent if they have the same extensions. A full study of the ranking
equivalence notion will be done in future work.
5. Related Work
Beside the work from Dunne et al. [4] there are more works discussing the realisability problem
in the area of abstract argumentation. Like the works from Pührer and colleagues [12, 13, 14].
They discuss the realisability problem for abstract dialectical frameworks (ADFs), which is
a generalisation of AFs. In this framework, each argument has a logic formula as acceptance
condition. So, only if this condition is true, an argument can be considered acceptable. In contrast
to our work, ADFs are focusing on sets of arguments similar to extension-based semantics for
AFs and not on the strength of a single argument.
The recent works from Oren and colleagues [15, 16] are talking about the inverse problem of
gradual semantics which at first glance is the realisability problem for gradual semantics. Gradual
semantics are functions which calculate for every argument in an AF a numerical acceptance
value. For example, the h-categoriser semantics is a gradual semantics. Note that every gradual
semantics is a ranking-based semantics, but there are ranking-based semantics, which are not
based on gradual semantics like the semantics based on iterated graded defence by Grossi and
Modgil [17]. However, they analyse a different problem. Given an AF, gradual semantics ρ, and
a desired ranking r they want to find initial weights for each argument such that they obtain r.
Hence, they extend argumentation framework with initial weight which results in an extension of
AF named weighted argumentation frameworks (WAFs) introduced by [18, 19]. So, they try to
find WAFs based on a given AF.
Another extension of AFs are the value-based argumentation frameworks. In addition to a set
of arguments and attacks a value-based AF also has a preference order over the set of arguments.
An attack between two arguments a, b is only valid if the attacker a is at least as preferred as b.
The realisibility problem for value-based AFs were investigated by Airiau and colleagues [20].
Their problem takes a set of AFs and ask whether there exists an attack-relation and a preference
order s.t. a value-based AF can be constructed. So, similar to the work of Oren and colleagues
[15, 16] the problem based on a given set of AFs, while our work focuses on finding an AF.
82
Kenneth Skiba et al. CEUR Workshop Proceedings 73–85
6. Conclusion
In this work, we continue the discussion of realisability problems in the area of abstract argu-
mentation. We focus on ranking-based semantics and ask the question for a ranking whether
there exists an argumentation framework for which a ranking-based semantics ρ induces the
ranking. It turns out, that this problem is trivial for a number of ranking-based semantics, because
if a ranking-based semantics satisfies Abstraction, Strict Counter-Transitivity, and Argument
Equivalence, then for any ranking r we can find an AF with r as its corresponding ranking. We
showed this by presenting a simple construction specification for an AF based on a ranking. Based
on our observation, we defined a new notion of equivalence of two argumentation frameworks.
Named ρ-ranking equivalence, which states that two AFs are equivalent if they have the same
ranking. If we recall our motivating example, we see that our agent can construct an AF quite
easily if she uses any universally realisable ranking-based semantics. However, we can question
the usefulness of the resulting AF. Since real world discussion have different structures. Normally
there is no argument, which attacks everything else. Especially if we consider that the resulting
strategy means that every stronger argument attacks every weaker argument, regardless of whether
they are in conflict or not. Nevertheless, the agent only needs to find an AF, which is ranking
equivalent to the constructed AF, which is an easier problem.
Beside fully analysing ρ-ranking equivalence, another future work approach would be to look
at a strong version of this ranking equivalence notion like in the work of Oikarinen and Woltran
[21]. Here, for two AFs with the same extensions to be considered strongly equivalent it has to
hold that if we add the same arguments and attacks to these AFs, then the extensions also have to
be the same after the addition.
Many ranking-based semantics can be used to establish starting weight for every argument of
an AF. Baroni et al. [22] have investigated properties of argumentation frameworks with initial
weights. The results of our paper can be used to investigate AFs with initial weights even further,
especially with respect to the realisability problem.
The realisability notion can be extended to a two-dimesional one, similar to the work of Dunne
et.al [23]. So, given two ranking r1 , r2 and two ranking-based semantics ρ1 , ρ2 does there exist an
AF such that ρ1 (AF) = r1 and ρ2 (AF) = r2 . This discussion can present more insights to which
extend two ranking-based semantics deviate.
Acknowledgements. The research reported here was supported by the Deutsche Forschungsge-
meinschaft under grant 423456621.
References
[1] P. M. Dung, On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic
Reasoning, Logic Programming and n-Person Games, Artificial Intelligence (1995).
[2] E. Bonzon, J. Delobelle, S. Konieczny, N. Maudet, A comparative study of ranking-based
semantics for abstract argumentation, in: Proc. of AAAI’16, 2016.
[3] L. Amgoud, J. Ben-Naim, Ranking-based semantics for argumentation frameworks, in:
Proc. SUM’13), 2013.
83
Kenneth Skiba et al. CEUR Workshop Proceedings 73–85
[4] P. E. Dunne, W. Dvořák, T. Linsbichler, S. Woltran, Characteristics of multiple viewpoints
in abstract argumentation, Artificial Intelligence 228 (2015) 153–178.
[5] P. Baroni, M. Caminada, M. Giacomin, Abstract argumentation frameworks and their
semantics, in: P. Baroni, D. Gabbay, M. Giacomin, L. van der Torre (Eds.), Handbook of
Formal Argumentation, College Publications, 2018, pp. 159–236.
[6] P. Besnard, A. Hunter, A logic-based theory of deductive arguments, Artif. Intell. (2001).
[7] F. Pu, J. Luo, Y. Zhang, G. Luo, Argument ranking with categoriser function, in: R. Buch-
mann, C. V. Kifor, J. Yu (Eds.), Knowledge Science, Engineering and Management - 7th
International Conference, KSEM 2014, Sibiu, Romania, October 16-18, 2014. Proceedings,
volume 8793 of Lecture Notes in Computer Science, Springer, 2014, pp. 290–301.
[8] J. Delobelle, Ranking-based semantics for abstract argumentation (sémantique à base de
classement pour l’argumentation abstraite), 2017. Artois University, Arras, France.
[9] J. Leite, J. G. Martins, Social abstract argumentation, in: T. Walsh (Ed.), IJCAI 2011,
Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona,
Catalonia, Spain, July 16-22, 2011, IJCAI/AAAI, 2011, pp. 2287–2292.
[10] M. Thimm, F. Cerutti, T. Rienstra, Probabilistic graded semantics, in: S. Modgil, K. Budzyn-
ska, J. Lawrence (Eds.), Computational Models of Argument - Proceedings of COMMA
2018, Warsaw, Poland, 12-14 September 2018, volume 305 of Frontiers in Artificial Intelli-
gence and Applications, IOS Press, 2018, pp. 369–380.
[11] H. Li, N. Oren, T. J. Norman, Probabilistic argumentation frameworks, in: S. Modgil,
N. Oren, F. Toni (Eds.), Theorie and Applications of Formal Argumentation - First Interna-
tional Workshop, TAFA 2011. Barcelona, Spain, July 16-17, 2011, Revised Selected Papers,
volume 7132 of Lecture Notes in Computer Science, Springer, 2011, pp. 1–16.
[12] T. Linsbichler, J. Pührer, H. Strass, A uniform account of realizability in abstract argumen-
tation, in: G. A. Kaminka, M. Fox, P. Bouquet, E. Hüllermeier, V. Dignum, F. Dignum,
F. van Harmelen (Eds.), ECAI 2016 - 22nd European Conference on Artificial Intelligence,
29 August-2 September 2016, The Hague, The Netherlands - Including Prestigious Applica-
tions of Artificial Intelligence (PAIS 2016), volume 285 of Frontiers in Artificial Intelligence
and Applications, IOS Press, 2016, pp. 252–260.
[13] J. Pührer, Realizability of three-valued semantics for abstract dialectical frameworks, Artif.
Intell. 278 (2020).
[14] T. Linsbichler, J. Pührer, H. Strass, Characterizing realizability in abstract argumentation,
CoRR abs/1603.09545 (2016).
[15] N. Oren, B. Yun, A. Libman, M. S. Baptista, Analytical solutions for the inverse problem
within gradual semantics, arXiv preprint arXiv:2203.01201 (2022).
[16] N. Oren, B. Yun, S. Vesic, M. S. Baptista, The inverse problem for argumentation gradual
semantics, CoRR abs/2202.00294 (2022).
[17] D. Grossi, S. Modgil, On the graded acceptability of arguments in abstract and instantiated
argumentation, Artificial Intelligence (2019).
[18] P. E. Dunne, A. Hunter, P. McBurney, S. Parsons, M. J. Wooldridge, Weighted argument
systems: Basic definitions, algorithms, and complexity results, Artif. Intell. 175 (2011)
457–486.
[19] L. Amgoud, J. Ben-Naim, D. Doder, S. Vesic, Acceptability semantics for weighted argu-
mentation frameworks, in: C. Sierra (Ed.), Proceedings of the Twenty-Sixth International
84
Kenneth Skiba et al. CEUR Workshop Proceedings 73–85
Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August
19-25, 2017, ijcai.org, 2017, pp. 56–62.
[20] S. Airiau, E. Bonzon, U. Endriss, N. Maudet, J. Rossit, Rationalisation of profiles of abstract
argumentation frameworks: Characterisation and complexity, J. Artif. Intell. Res. 60 (2017)
149–177.
[21] E. Oikarinen, S. Woltran, Characterizing strong equivalence for argumentation frameworks,
Artif. Intell. 175 (2011) 1985–2009.
[22] P. Baroni, A. Rago, F. Toni, From fine-grained properties to broad principles for gradual
argumentation: A principled spectrum, Int. J. Approx. Reason. 105 (2019) 252–286.
[23] P. E. Dunne, C. Spanring, T. Linsbichler, S. Woltran, Investigating the relationship between
argumentation semantics via signatures, in: S. Kambhampati (Ed.), Proceedings of the
Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New
York, NY, USA, 9-15 July 2016, IJCAI/AAAI Press, 2016, pp. 1051–1057.
85