Realisability of Ranking-based Semantics

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 ifnd 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

• eol>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. 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.

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 semantics 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. 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+∑b∈a1− Cat(b) .

The h-categoriser ranking-based semantics defines a ranking ⪰ CAaFt on A s.t. for a, b ∈ A, a ⪰ CAaFt 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 ≻ CAaFt d ≻ CAaFt b ≻ CAaFt 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. 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, Eρ1 ≥ 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.

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 rankingbased 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 and ρ satisfies Argument Equivalence, we know not relevant for the ranking.

ρ 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 Let a, b ∈ Ar with a ≃ b in r. Then, it holds that a− = b− , since a and b have the same attackers ρ 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 CounterTransitivity, 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. arguments to a value as follows: 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 Disi : A → Z, Disi(a) := ︃{ |a∗i | |− a∗i | if i is odd if i is even iff Disi(b) ⪰ lex Disi(a), where ⪰ lex denotes the lexicographical order.

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 ⪰ ADFbs on A s.t. for a, b ∈ A, a ⪰ ADFbs b 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. values as follows: 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 Buri : A → Z, Buri(a) :=

1 1 + ∑b∈a− Buri− 1(b) if i = 0 otherwise Buri(b) ⪰ lex Buri(a), where ⪰ lex denotes the lexicographical order.

The burden-based semantics (Bbs) defines a ranking ⪰ BAbFs on A s.t. for a, b ∈ A, a ⪰ BAbFs b iff {︄ 1

Amgoud and Ben-Naim [ 3 ] have shown that both Discussion-based and Burden-based semantics 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 ⪰ SAAFF on A s.t. for a, b ∈ A, a ⪰ SAAFF 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 rankingbased 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 PσPA,◦ Fσ (AF)(a) as:

PσPA,◦Fσ (AF)(a) =

∑ ∏ P(a) ∏ (1 − P(a)) a∈X⊆ A,a∈◦ σ (AF|X ) a∈X a∈/X a b c d a d b 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 = PσPA,◦ Fσ (AF) for every a ∈ A. The corresponding rankingbased semantics Gσ,◦ σ (AF),p defines a ranking ⪰ AF Gσ,◦ σ (AF),p b iff

Gσ,◦ σ (AF),p on A s.t. for a, b ∈ A, a ⪰ AF 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 rankingbased 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 with Definition 13 has only one complete extension. However, for both AFs the h-categoriser semantics returns the same ranking: a ≻ CAaFt,AFr1 d ≻ CAaFt,AFr1 b ≻ CAaFt,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 ifnd 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.

6. Conclusion

In this work, we continue the discussion of realisability problems in the area of abstract argumentation. 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 Forschungsgemeinschaft 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 .

[4] P. E. Dunne , W. Dvorˇá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. Buchmann , 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. Budzynska , J. Lawrence (Eds.), Computational Models of Argument - Proceedings of COMMA 2018 , Warsaw, Poland, 12 -14 September 2018 , volume 305 of Frontiers in Artificial Intelligence 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 International 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 argumentation , 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 Applications 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 argumentation frameworks , in: C. Sierra (Ed.), Proceedings of the Twenty-Sixth International 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 .