Power index-based semantics for ranking arguments in abstract argumentation frameworks

Abstract

Ranking-based semantics for Abstract Argumentation Frameworks represent a well-established concept used for sorting a group of arguments from the most to the least acceptable. This paper describes a ranking-based semantics that makes use of power indexes such as the Shapley Value and the Banzhaf Power Index. This power index-based semantics is parametric to a chosen Dung semantics and inherits the properties of the index that is used for evaluating the arguments. We highlight the characteristics of the rankings obtained through different evaluation functions and we verify which of the properties from the literature are satisfied. Finally, we study the relation between the (skeptical/credulous) acceptability of an argument and its position in the ranking, thus designing new properties.

Keywords

Argumentation semantics ranking cooperative game theory Shapley Value Banzhaf Index

1 Introduction

Argumentation Theory is a field of Artificial Intelligence that provides formalisms for reasoning with conflicting information. Arguments from a knowledge base are modelled by Dung [19] as nodes in a directed graph, that we call Abstract Argumentation Framework (AF in short), where edges represent a binary attack relation. Among the arguments in a framework, it is possible to select the sets of those that are not in conflict with each other. Many semantics (i.e., criteria through which refine this selection) have been defined in order to establish different kinds of acceptability (see [4] for a survey). All these semantics return two disjoint sets of arguments: “accepted” and “not accepted”. An additional level of acceptability is introduced by Caminada in [15] with the reinstatement labelling, a kind of semantics that marks as undecided the arguments that can be neither accepted nor rejected.

Dividing the arguments into just three partitions is still not sufficient when dealing with very large AFs, where one needs to limit the choice on a restricted number of selected arguments. For this reason, a different family of semantics can be used for obtaining a broader range of acceptability levels for the arguments. Such semantics, called ranking-based, have been studied in many works, as [1 , 25], each focusing on a different criterion for identifying the best arguments in an AF. The shared idea is to assign a value to each argument through an evaluation function, in order to obtain a total order over the arguments.

We conducted an investigation on a ranking-based semantics that relies on power indexes, like the Shapley Value [26] and the Banzhaf index [3], and notions of coalition formation from cooperative games [26]. Our semantics is parametric to a chosen power index and allows for obtaining a ranking where the arguments are sorted according to their contribution to the acceptability of the other arguments in the various coalitions.

In this paper we provide a thorough study of the semantics we introduced, following different directions: first of all, we study our power index-based semantics with respect to a set of properties that are used in literature to compare the various existing ranking semantics [14]. This allows us for identifying the advantages of power indexes to rank arguments. To better characterize our semantics, we also discuss the relationship between the acceptability of an argument (in terms of skeptical/credulous acceptability) and the ranking resulting from the evaluation of such argument. Finally, we introduce a property linking the skeptical/credulous acceptability of two arguments with their rank. To complete our study and support the research in this field, we also provide an online tool 1 capable of dealing with argumentation frameworks and reasoning with our ranking-based semantics, besides classical ones.

The paper, that extends and supersedes [7] and [8], is organised as follows: Section 2 provides the background on both argumentation semantics and power indexes, Section 3 describes and gives the main definitions for the power index-based semantics, while in Section 4 we discuss some of the properties proposed in the literature, also introducing new ones. Section 5 reports some examples we use for analysing the different rankings obtained through various indexes and semantics, and in Section 6 we describe a web tool we have endowed with the possibility of handling ranking-based semantics. Section 7 describes some related work and, finally, Section 8 wraps up the paper with final conclusions and ideas for possible future work.

2 Preliminaries

In this section, we introduce the fundamental notions of labelling- and ranking-based semantics in Abstract Argumentation. We put particular attention on the properties defined for ranking-based semantics. Moreover, we provide some background on the power indexes we use for our semantics.

2.1 Argumentation

Argumentation [5] is a discipline that copes with uncertainty and defeasible reasoning. In Abstract Argumentation, arguments have no internal structure and the attack relation is not defined. An Abstract Argumentation Framework (AF in short) [19] consists of a set of arguments and the relations among them. Such relations, which we call “attacks”, are interpreted as conflict conditions that allow for determining the arguments in A that are acceptable together (i.e., collectively).

Definition 1. [AF] An Abstract Argumentation Framework is a pair 〈A, F〉 where A is a set of arguments and R ⊆ A × A is a binary attack relation on A.

An argumentation semantics is a criterion that establishes which are the acceptable arguments by considering the relations among them. The sets of accepted arguments with respect to a semantics are called extensions of that semantics. Two leading characterisations can be found in the literature, namely extension-based [19] and labelling-based [15] semantics. While providing the same outcome in terms of accepted arguments, labelling-based semantics permits to differentiate between three levels of acceptability, by assigning labels to arguments according to the conditions stated in the following definition.

Definition 2. [Reinstatement Labelling] Let F = 〈A, R〉 be an AF and $𝕃 = {in, out, undec}$ . A labelling of F is a total function $L : A \to 𝕃$ . We define in (L) = {a ∈ A ∣ L (a) = in}, out (L) = {a ∈ A ∣ L (a) = out} and undec (L) = {a ∈ A ∣ L (a) = undec}. We say that L is a reinstatement labelling if and only if it satisfies the following conditions:

∀a, b ∈ A, if a ∈ in (L) and (b, a) ∈ R then b ∈ out (L);

∀a ∈ A, if a ∈ out (L) then ∃b ∈ A such that b ∈ in (L) and (b, a) ∈ R.

The labelling obtained through the function in Definition 2 can be then analysed in terms of Dung semantics [19]: by checking specific properties in a labelling, it is possible to establish its correspondence with an extension of a certain semantics.

Definition 3. [Labelling-based semantics] A labelling-based semantics σ associates with an AF F = 〈A, R〉 a subset of all the possible labellings for F, denoted as L_σ (F). Let L be a labelling of F, then L is

conflict-free if and only if for each a ∈ A it holds that if a is labelled in then it does not have an attacker that is labelled in, and if a is labelled out then it has at least one attacker that is labelled in;

admissible if and only if the attackers of each in argument are labelled out, and each out argument has at least one attacker that is in;

complete if and only if for each a ∈ A, a is labelled in if and only if all its attackers are labelled out, and a is out if and only if it has at least one attacker that is labelled in;

preferred/grounded if L is a complete labelling where the set of arguments labelled in is maximal/minimal (with respect to set inclusion) among all complete labellings;

stable if and only if it is a complete labelling and undec (L) =∅.

The accepted arguments of F, with respect to a certain semantics σ, are those labelled in by σ. We refer to sets of arguments that are labelled in, out or undec in at least one labelling of L_σ (F) with in (L_σ), out (L_σ) and undec (L_σ), respectively 2 . Given an argument a ∈ F, we say that a is credulously accepted with respect to a semantics σ if it is labelled in in at least one extension of σ. We say that a is sceptically accepted if it is labelled in in all extensions of σ. In order to further discriminate among arguments, ranking-based semantics [14] can be used for sorting the arguments from the most to the least preferred.

Definition 4. [Ranking-based semantics] A ranking-based semantics associates with any F = 〈A, R〉 a ranking ≽_F on A, where ≽_F is a pre-order (a reflexive and transitive relation) on A. a ≽ _Fb means that a is at least as acceptable as b (a ≃ b is a shortcut for a ≽ _Fb and b ≽ _Fa, and a ≻ _Fb is a shortcut for a ≽ _Fb and b_{notsucccurlyeqF}b).

A ranking-based semantics can be characterised by some specific properties that take into account how couples of arguments in an AF are evaluated for establishing their position in the ranking. We provide a list of the properties suggested in [1] and that we use in Section 5 to discuss an example of how our tool can be used for both research and applicative purposes.

Definition 5. [Isomorphism] An isomorphism ι between two AFs F = 〈A, R〉 and F′ = 〈A′, R′〉 is a bijective function ι : A → A′ such that ∀a, b ∈ A, (a, b) ∈ R if and only if (ι (a) , ι (b)) ∈ R′.

We can characterise the role of an argument with respect to another one according to the length of the path between them: an odd path represents an attack, while an even path is considered as a defence.

Definition 6. [Attackers and defenders [1]] Let F = 〈A, R〉 be an AF and a, b ∈ A and denote with P (b, a) a path from b to a. The multi-sets of defenders and attackers of a are $R_{n}^{+} (a) = {b | \exists P (b, a)$ with length $n \in 2 ℕ}$ and $R_{n}^{-} (a) = {b | \exists P (b, a)$ with length $n \in 2 ℕ + 1}$ , respectively. $R_{1}^{-} (a) = R^{-} (a)$ is the set of direct attackers of a.

Besides arguments alone, also sets of arguments can be compared. Two rules apply: the greater the number of arguments, the more preferred the group; in case of two groups with the same size, the more preferred the arguments in a group, the more preferred the group itself.

Definition 7. [Group comparison [1]] Let ≥_S be a ranking on a set of arguments A. For any S₁, S₂ ⊆ A, S₁ ≥ _SS₂ is a group comparison if and only if there exists an injective mapping f : S₂ → S₁ such that ∀a ∈ S₂, f (a) ≽ a. Moreover, S₁ > _SS₂ is a strict group comparison if and only if S₁ ≥ _SS₂ and (|S₂| < |S₁|) or ∃ a ∈ S₂, f (a) ≻ a.

For example, consider the sets of arguments S₁ = {a, b, c}, S₂ = {c, e} and S₃ = {d, f}, and the ordering a ≻ b ≻ c ≻ d ≻ e ≻ f. By Definition 7, we have that S₁ > _SS₂ since |S₂| < |S₁|, and S₂ > _SS₃ since c ≻ d and e ≻ f.

In the following, we list the properties proposed in [1], all defined for a ranking-based semantics σ, for any AF F = 〈A, R〉 and for all pairs of arguments a, b ∈ F.

The ranking on A is defined only on the basis of the attacks between arguments, that is it is preserved over isomorphisms of the framework.

(Abs) For any isomorphism γ such that F′ = γ (F), $a ≽_{F}^{σ} b$ if and only if $γ (a) ≽_{F^{'}}^{σ} γ (b)$

The ranking between two arguments a and b should be independent of any argument that is neither connected to a nor to b.

(Ind) ∀F′ = 〈A′, R′〉 ∈ cc (F) , ∀a, b ∈ A′, then $a ≽_{F^{'}}^{σ} b \Rightarrow a ≽_{F}^{σ} b$ , where cc (F) denotes the set of connected components in F

A non-attacked argument is ranked strictly higher than any attacked argument.

(VP) $R_{1}^{-} (a) = \emptyset$ and $R_{1}^{-} (b) \neq \emptyset \Rightarrow a ≻^{σ} b$

A self-attacking argument is ranked lower than any non self-attacking argument.

(SC) (a, a) ∉ R and (b, b) ∈ R ⇒ a ≻ ^σb

The greater the number of direct attackers for an argument, the weaker the rank of this argument.

(CP) $| R_{1}^{-} (a) | < | R_{1}^{-} (b) | \Rightarrow a ≻^{σ} b$

An argument a should be ranked higher than an argument b, if at least one attacker of b is ranked higher than any attacker of a.

(QP) $\exists c \in R_{1}^{-} (b)$ such that $\forall d \in R_{1}^{-} (a), c ≻^{σ} d \Rightarrow a ≻^{σ} b$

If the direct attackers of b are at least as numerous and acceptable as those of a, then a is at least as acceptable as b.

(CT) $R_{1}^{-} (b) \geq_{S} R_{1}^{-} (a) \Rightarrow a ≽^{σ} b$

If CT holds and either the direct attackers of b are strictly more numerous or acceptable than those of a, then a is strictly more acceptable than b.

(SCT) $R_{1}^{-} (b) >_{S} R_{1}^{-} (a) \Rightarrow a ≻^{σ} b$

For two arguments with the same number of direct attackers, a defended argument is ranked higher than a non-defended argument.

(DP) $| R_{1}^{-} (a) |$ = $| R_{1}^{-} (b) |$ , $R_{2}^{+} (a)$ ≠ ∅ and $R_{2}^{+} (b)$ = ∅ ⇒ a ≻^σb

All the non-attacked arguments have the same rank.

(NaE)R^- (a) =∅ and R^- (b) = ∅ ⇒ a ≃ ^σb

All pairs of arguments can be compared.

(ToT)a ≽ ^σb or b ≽ ^σa.

In [1] and [14] implications between the above properties are studied. In particular, we take into account the following considerations.

Proposition 1. For every ranking-based semantics,

CP and QP are not compatible

SCT implies VP

CT and SCT imply DP

SCT implies CT

CT implies NaE

Before continuing, we remark that all these properties are not mandatory for obtaining a well-defined ranking, but they are just meant to provide a form of characterization for a ranking-based semantics. In fact, some properties are incompatible, and one might or might not find convenient to have a particular property for a certain application. In building our ranking-based semantics, we rely on power indexes for establishing a total order between the arguments of a framework.

2.2 Power indexes

In game theory, cooperative games are a class of games where groups of players (or agents) are competing to maximise their goal, through one or more specific rules. Voting games are a particular category of cooperative games in which the profit of coalitions is determined by the contribution of each individual player. In order to identify the “value” brought from a single player to a coalition, power indexes are used to define a preference relation between different agents, computed on all the possible coalitions. In our work, we use two among the most commonly used power indexes, namely the Shapley Value [26, 28] and the Banzhaf Index [3] 3 .

Every power index relies on a characteristic function $v : 2^{N} \to ℝ$ that, given the set N of players, associates each coalition S ⊆ N with a real number in such a way that v (S) describes the total gain that agents in S can obtain by cooperating with each other. The expected marginal contribution of a player i ∈ N, given by the difference of gain between S and S ∪ {i}, is v_{S
_i} = v (S ∪ {i})-v (S).

The Shapley Value φ_i (v) of the player i, given a characteristic function v, is computed as: $φ_{i} (v) = \sum_{S \subseteq N \ {i}} \frac{| S |! (| N | - | S | - 1)!}{| N |!} v_{S_{i}}$ (1)

The formula considers a random ordering of the agents, picked uniformly from the set of all |N| ! possible orderings. The value |S| ! (|N|-|S|-1) ! expresses the probability that all the agents in S come before i in a random ordering.

The second fair division scheme we use is the Banzhaf Index β_i (v), which evaluates each player i by using the notion of critical voter: given a coalition S ⊆ N \ {i}, a critical voter for S is a player i such that S ∪ {i} is a winning coalition, while S alone is not. In other words, i is a critical voter if it can change the outcome of the coalition it joins.

$β_{i} (v) = \frac{1}{2^{| N | - 1}} \sum_{S \subseteq N \ {i}} v_{S_{i}}$ (2)

The difference between the perhaps more famous Shapley Value and the Banzhaf index is that the latter does not take into account the order in which the players form the coalitions. Below, we give the definition of the ranking-based semantics, which we implement through the joint use of labelling and power indexes.

3 Model description

Our approach consists in assigning a value to each argument according to the labels in and out if it satisfies the considered classical semantics. Compared to extension-based semantics, the use of labellings allows one to further distinguish among arguments by taking into account the ones that are not accepted (that is the out arguments). There is no convenience in taking into account also the label undec since it is derived directly from the other two. A further advantage of considering labelling-based semantics is that the characteristic functions only depend on the structure of a given AF, without adding to the picture other parameters, or external/computed values, or ad-hoc functions. Power indexes provides an a priori evaluation of the position of each player in a cooperative game, based on the contribution that each player can make to the different coalitions; in our ranking-based semantics, that we call “PI-based”, such coalitions are the sets labelled with the semantics in Definition 3.

Definition 8. [Characteristic function] Consider an AF F = 〈A, R〉, a Dung semantics σ and the set L_σ of all possible labellings on F satisfying σ. For any S ⊆ A, the labelling-based characteristic functions $v_{σ}^{I} (S)$ and $v_{σ}^{O} (S)$ are defined as: $v_{σ}^{I} (S) = {\begin{matrix} 1, & if S \in in (L_{σ}) \\ 0, & if otherwise \end{matrix}$ $v_{σ}^{O} (S) = {\begin{matrix} 0, & if S \in out (L_{σ}) \\ 1, & if otherwise \end{matrix}$

The function $v_{σ}^{I} (S)$ takes into account the acceptability of a set of arguments S with respect to a certain semantics σ, assigning to such set a score equal to 1 if there exists a labelling L_σ in which all and only the arguments of S are labelled in. In other words, a set is positively evaluated by $v_{σ}^{I} (S)$ only if it represents an extension for the semantics σ, and the higher the score of the power index, the better the rank of an argument. A second characteristic function, $v_{σ}^{O} (S)$ , is also introduced to put attention on the negative effect of the attacks received by the arguments. The function $v_{σ}^{O} (S)$ considers the sets of arguments labelled out by σ, and the evaluation has the usual interpretation: the lower the score according to $v_{σ}^{O} (S)$ , the worse the rank.

Definition 9. [PI-based semantics] Let F = 〈A, R〉 be an AF, σ a Dung semantics, π ∈ Π :{φ, β} a power index, and v_σ a characteristic function. The PI-based semantics associates to F a ranking $≽_{σ}^{π}$ on A, such that ∀a, b ∈ A, $a ≽_{σ}^{π} b \Leftrightarrow π_{a} (v_{σ}) \geq π_{b} (v_{σ})$ The strict relation is derived in the usual way.

A ranking-based semantics designed in this way has the further advantage of automatically inheriting the properties of the Shaplye Value and the Banzhaf Index, like efficiency, symmetry, linearity, and zero players [26]. The lexicographic order on the pairs $(v_{σ}^{I} (S), v_{σ}^{O} (S))$ can be used to break possible ties in the final ranking, in the case two arguments of F have the same power index with respect to one of the two characteristic functions. An additional (partial) ordering can also be obtained as the Cartesian product of the two relations.

The PI-based semantics is capable of giving an overview of which are the most valuable arguments in a framework, from the point of view of their contribution to the existence of the various extensions belonging to different semantics. Indeed, it is reasonable to think that an argument which defend many other arguments should be given greater importance, when looking for sets satisfying the admissible semantics. Giving another example, the highest ranked arguments according to the conflict-free criterion are those that generate less conflict together with all the other possible subsets. The possibility of having a different ranking for each Dung semantics allows for obtaining results that can be more fitting the ultimate purpose (i.e., reasoning about a favourable outcome of a debate) of the ranking. In the following section, we study ranking-based semantics properties with respect to our approach and we show which are satisfied and which are not.

4 PI-based semantics properties

We check which of the properties in [1] are satisfied by the semantics we introduced. In detail, we study which properties among those in Definition 6 are satisfied by the PI-semantics obtained through the Shapley Value and the Banzhaf Index, with respect to the various semantics and the two characteristic function of Definition 8.

Theorem 1. Consider an AF F = 〈A, R〉, two arguments a, b ∈ A, a Dung semantics σ and a power index π ∈ {φ, β}. The PI-based semantics satisfies the following properties:

Abs, Ind and ToT for any σ ∈ {conflict-free, admissible, complete, preferred, stable}

SC only for σ = conflict-free, with respect to $v_{σ}^{I}$ .

NaE only for σ ∈ {complete, preferred, stable}, with respect to $v_{σ}^{I}$ , and for any σ ∈ {conflict-free, admissible, complete, preferred, stable}, with respect to $v_{σ}^{O}$ .

For any σ ∈ {conflict-free, admissible, complete, preferred, stable}, the PI-based semantics does not satisfy VP, CP and QP.

Proof. See Appendix A.□ The validity of all the properties we take into account is summarised in Table 1: each cell of the table shows if a certain property is satisfied with respect to a power index (between φ, β), a Dung semantics (conflict-free, admissible, complete, preferred and stable) and characteristic function ( $v_{σ}^{I}$ and $v_{σ}^{O}$ ). The different characteristic functions are represented by alternating in and out rows. We then mark with the cells representing combinations of power index, semantics and characteristic function for which a property is satisfied, and with the cell for which it is not. Note that, given a semantics σ and a function v_σ, both the power indexes φ and β satisfy the same properties.

Table 1
Properties of the PI-based semantics satisfied by φ and β

To show the correspondence with the classical semantics, in the last column, we also check the properties satisfied by the grounded semantics (that we consider as a degenerate ranking semantics with only two degrees of acceptability). We observe that the PI-based semantics is compatible with the grounded in terms of satisfied properties.

4.1 Evaluation of the arguments

Given a ranking, we can correlate the value given to each argument to its credulous/skeptical acceptance. The questions we want to answer are: what does the value of an argument mean? What is the implication one can derive by comparing the values of two arguments? Looking at the acceptability of an argument, we can have in advance some information about the value of its evaluation, without even computing the power index.

Theorem 2. Let F = 〈A, R〉 be an AF, σ a Dung semantics, π ∈ {φ, β} a power index, and v_σ a characteristic function.

if a is skeptically accepted implies $π_{a} (v_{σ}^{I}) > 0$ ;

if a is credulously rejected implies $π_{a} (v_{σ}^{I}) < 0$ ;

Proof. The proof is straightforward and can be derived from the definition of the power indexes.□

The properties we studied in Theorem 1 are mainly related to the structural configuration of the AF (e.g., incoming attacks of the arguments) and do not represent a valid measure of how the contribution of the arguments is considered in the final ranking. In order to make up for this lack, we introduce a coalition formation-related property for ranking semantics.

Skeptically accepted arguments according to any labelling should be ranked higher than credulously accepted and rejected arguments. Analogously, credulously accepted arguments should be ranked higher that rejected arguments.

Definition 10. Let F = 〈A, R〉 be an AF, a, b ∈ F two arguments, π ∈ {φ, β} a power index and σ a Dung semantics.

If a is skeptically accepted with respect to σ, while b is not, than $a ≻_{σ}^{π} b$ .

If a is credulously accepted with respect to σ and b is always rejected, than $a ≻_{σ}^{π} b$ .

The following proposition holds.

Theorem 3. The PI-based semantics satisfies σ-SkP and σ-CrP for any σ ∈ {conflict-free, admissible, complete, preferred, stable} and the characteristic function $v_{σ}^{I}$ .

Proof. We give the proof for Theorem 3. Given an AF F, a credulously accepted argument i with respect to σ and an evaluation function $v_{σ}^{I}$ , there exists at least one subset of arguments S such that $v_{σ}^{I} (S_{- i} \cup {i}) - v_{σ}^{I} (S_{- i}) > 0$ . Thus the value of i will always be higher than that of any rejected argument j, for which $v_{σ}^{I} (S_{- j} \cup {j}) - v_{σ}^{I} (S_{- j}) < 0$ for any S, and σ-CrP holds. We can make the same consideration for σ-SkP, showing that skeptically accepted arguments have higher value than the others.□

We now discuss the above introduced properties, checking for which existing ranking-based semantics they hold. Besides our semantics, for this study we focus on those surveyed in [14] that return a total ranking, namely Cat, SAF, M&T, Dbs, Bds. Consider the framework in Fig. 1: when σ = {admissible, complete, preferred, stable}, the argument d is always rejected, while e is credulously accepted. Moreover, e is also skeptically accepted by the complete, preferred and stable semantics. According to the CrP property, then, e should be ranked higher than d. For motivating such evaluation of the arguments, we can imagine that the AF of Fig. 1 represents a debate we want to win. We know that e is defended by an argument that represent an initiator of the underlying graph (i.e., the argument b), while d is never in according to any Dung semantics. In other words, choosing e over d means to select an argument inside the grounded semantics, that we can consider “winning” or “difficult” to defeat. If we choose d, instead, we are not able to reply to the attack of e and so we are defeated.

Fig.1

Example for σ-SkP and σ-CrP. We have d ≻ ^σe for σ∈ {Cat, Dbs, Bds}.

Proposition 2. The ranking-based semantics Cat, Dbs and Bds do not satisfy the σ-CrP property when σ∈ {admissible, complete, preferred, stable}.

Indeed, considering again the example in Fig. 1, we have that d is always preferred to e in the rankings obtained by using Cat, Dbs and Bds respectively (see Table 2 for details).

Table 2

Ranking of the arguments of the AF in Fig. 1 obtained by using the rankig-based semantics Cat, Dbs, Bds, SAF, M&T

Semantics	Ranking
Cat	b ≻ ^Catd ≻ ^Cate ≻ ^Catc ≻ ^Cata
Dbs	b ≻ ^Dbsd ≻ ^Dbsc ≻ ^Dbse ≻ ^Dbsa
Bds	b ≻ ^Bdsd ≻ ^Bdsc ≻ ^Bdse ≻ ^Bdsa
SAF	b ≻ ^SAFe ≻ ^SAFd ≻ ^SAFc ≻ ^SAFa
M&T	b ≻ ^M&Te ≻ ^M&Tc ≃ ^M&Td ≻ ^M&Ta

The categoriser function used by the Cat semantics only takes into account the value of the direct attackers of the arguments in the AF, so it is not possible to establish the importance a of particular argument with respect to the set of extensions of a certain semantics. Even if the CP property is not satisfied, the notion of “strength” that is used by Cat is not related to the acceptability of the arguments. Analogously, both the semantics Dbs and Bds, that satisfy CP and rely on the number of the paths ending to an argument, rank higher arguments that have has less direct attackers, without considering any notion of defence. This is the case of arguments d and e in Fig. 1: while d is only attacked by a single argument, e is attacked by a and c, so d ≻ ^Dbse (and d ≻ ^Bdse) in the final ranking, although e is defended by the initiator b and d is attacked by e.

Since the authors of [20] assume the sceptical definition for the justification of the arguments, the graded semantics satisfies both σ-SkP and σ-CrP. Also the subgraph-based semantics [18] satisfies σ-SkP and σ-CrP. The ranking is obtained by establishing a lexicographical ordering between the values of a tuple that contains, for each argument a, the label assigned to a by a certain Dung semantics, and the number of times a is labelled l over the total number of subgraphs, for l = in, out and undec, respectively. Although also our approach relies on reinstatement labelling, we omit arguments marked as undecided in the computation of the ranking: indeed, the set of undec arguments can be obtained starting from the whole set of arguments and subtracting those labelled either in or out.

5 An empirical analysis

In this section, we show the procedure for obtaining a ranking among the arguments of a given AF through the use of a power index. We also compare the results for the Shapley Value and the Banzhaf Index, highlighting the differences in terms of final ordering of the arguments. For our example, we consider the AF in Fig. 2, that has an initiator (i.e., the argument a, which is not attacked by any other argument), two symmetric attacks (both b, d, and d, e attack each other), and a cycle involving b, d and e.

Fig.2

Example of an AF. The sets of extensions for the conflict-free, admissible, complete, preferred and stable semantics are: CF = {∅ , {a} , {b} , {c} , {d} , {e} , {a, c} , {a, d} , {a, e} , {c, d} , {c, e} , {a, c, d} , {a, c, e}}, ADM = {∅ , {a} , {d} , {e} , {a, c} , {a, d} , {a, e} , {c, d} , {c, e} , {a, c, d} , {a, c, e}}, COM = {{a, c} , {a, c, d} , {a, c, e}}, and PRE = STB = {{a, c, d} , {a, c, e}}, respectively.

Below, we report the results for φ and β (that correspond to the functions for computing the Shapley Value and the Banzhaf Index, respectively), and the semantics conflict-free, admissible, complete and preferred. We omit the stable one since, in this example, it returns the same set of extensions as the preferred. For each semantics, the values of the power index obtained with respect to the sets of in and out arguments are alternated in each row. Tables 3 and 4 show the results for the aforementioned indexes.

Table 3

Ranking for the AF in Fig. 2 obtained through the Shapley Value

	a	b	c	d	e	Semantics	Ranking
$v_{CF}^{I}$	-0.05000	-0.46667	-0.05000	-0.21667	-0.21667	φ - CF	a ≻ c ≻ e ≻ d ≻ b
$v_{CF}^{O}$	-0.35000	0.06667	-0.26667	-0.18333	-0.26667	φ - CF	a ≻ c ≻ e ≻ d ≻ b
$v_{ADM}^{I}$	0.05000	-0.61667	-0.20000	-0.11667	-0.11667	φ - ADM	a ≻ d ⋍ e ≻ c ≻ b
$v_{ADM}^{O}$	-0.31667	0.10000	-0.31667	-0.23333	-0.23333	φ - ADM	a ≻ d ⋍ e ≻ c ≻ b
$v_{COM}^{I}$	0.11667	-0.13333	0.11667	-0.05000	-0.05000	φ - COM	a ⋍ c ≻ d ⋍ e ≻ b
$v_{COM}^{O}$	-0.11667	0.30000	-0.11667	-0.03333	-0.03333	φ - COM	a ⋍ c ≻ d ⋍ e ≻ b
$v_{PRE}^{I}$	0.06667	-0.10000	0.06667	-0.01667	-0.01667	φ - PRE	a ⋍ c ≻ d ⋍ e ≻ b
[1pt] $v_{PRE}^{O}$	-0.06667	0.10000	-0.06667	0.01667	0.01667	φ - PRE	a ⋍ c ≻ d ⋍ e ≻ b

Table 4

Ranking for the AF in Fig. 2 obtained through the Banzhaf Index

	a	b	c	d	e	Semantics	Ranking
$v_{CF}^{I}$	-0.06250	-0.68750	-0.06250	-0.31250	-0.31250	β - CF	a ≻ c ⋍ e ≻ d ≻ b
$v_{CF}^{O}$	-0.31250	0.06250	-0.18750	-0.06250	-0.18750	β - CF	a ≻ c ⋍ e ≻ d ≻ b
$v_{ADM}^{I}$	0.06250	-0.68750	-0.06250	-0.18750	-0.18750	β - ADM	a ≻ c ≻ d ⋍ e ≻ b
$v_{ADM}^{O}$	-0.25000	0.12500	-0.25000	-0.12500	-0.12500	β - ADM	a ≻ c ≻ d ⋍ e ≻ b
$v_{COM}^{I}$	0.18750	-0.18750	0.18750	-0.06250	-0.06250	β - COM	a ⋍ c ≻ d ⋍ e ≻ b
$v_{COM}^{O}$	-0.18750	0.18750	-0.18750	-0.06250	-0.06250	β - COM	a ⋍ c ≻ d ⋍ e ≻ b
$v_{PRE}^{I}$	0.12500	-0.12500	0.12500	0.00000	0.00000	β - PRE	a ⋍ c ≻ d ⋍ e ≻ b
$v_{PRE}^{O}$	-0.12500	0.12500	-0.12500	0.00000	0.00000	β - PRE	a ⋍ c ≻ d ⋍ e ≻ b

We now analyse the differences between the obtained rankings, following two levels of detail: we first compare, for each power index, the ranking obtained for all the Dung semantics. Then, for each Dung semantics, we consider the ranking obtained with respect to the different power indexes.

In this example, the Shapley Value (Table 3), provides a ranking without indifferences when the conflict-free semantics is considered. While φ-com, φ-pre and φ-stb return the same output, where in particular c ≻ d and c ≻ e, the ranking for the admissible semantics gives an opposite interpretation, that is d ≻ c and e ≻ c. This happens because both {d} and {e} are admissible extensions, while {c} is not. Hence, when the admissible semantics is taken into account, d and e are better arguments than c.

When Banzhaf Index is used (Table 4), such an inversion of preferences never occurs: there is no semantics for which d ≻ c or e ≻ c. Looking at the formulas of the Shapley Value φ (Equation 1) and the Banzhaf Index β (Equation 2), we can see that the only difference is the factor by which the gain v (S ∪ {i})-v (S) is multiplied. Contrary to Shapley, Banzhaf does not consider the order in which the coalitions form; since the acceptability of the arguments does not depend on how the extensions are formed, β produces more consistent results and, therefore, is a more appropriate index to be used for building a ranking-based semantics.

The ranking obtained through both the power indexes share some common features, that we discuss below. The argument a, that is not attacked by any other, is always in the first position of the rank, for every power index. Consequently, the argument b, that is attacked by a, always results to be the worst argument in the AF, excepted for indifferences. For the complete, preferred and stable semantics, the ranking does not distinguish between a and c, and between d and e. Indeed, the set a, c corresponds to the grounded semantics, that is a and c are equally “important” and should be evaluated the same. Similarly, e and d, that only appear in two distinct maximal admissible sets, receive the same value from both the power indexes. Finally, since the extensions of the preferred and the stable coincide, these two semantics always provide the same final ranking.

5.1 Comparison of ranking-based semantics

Now we show and discuss the main differences between the PI-based semantics and the ranking-based semantics in [14]. Looking at the various rankings provided for the same AF in Tables 2 and 5, we, first of all, notice that φ-CF and β-CF, as well as Cat, Dbs and Bds, are not able to capture the reinstatement of the arguments. For this reason, argument e, that is defended by the initiator b, is still considered worse than c or d. Then, we have d ≻ ^Catc and d ≻ ^Dbsc, but also $c ≻_{CF}^{φ} d$ . Indeed, according to our evaluation, d should not be better that c because it contributes more than c in forming out extensions, that is sets of out labelled arguments.

Table 5
Ranking of the AF in Fig. 1 with the PI-based semantics

Semantics Ranking through φ Ranking through β

CF b ≻ c ≻ d ≻ e ≻ a b ≻ c ≃ d ≻ e ≻ a

ADM b ≻ e ≻ d ≻ a ≃ c b ≻ e ≻ d ≻ a ≃ c

COM b ≃ e ≻ a ≃ c ≃ d b ≃ e ≻ a ≃ c ≃ d

Semantics	Ranking through φ	Ranking through β
CF	b ≻ c ≻ d ≻ e ≻ a	b ≻ c ≃ d ≻ e ≻ a
ADM	b ≻ e ≻ d ≻ a ≃ c	b ≻ e ≻ d ≻ a ≃ c
COM	b ≃ e ≻ a ≃ c ≃ d	b ≃ e ≻ a ≃ c ≃ d

For the admissible and complete semantics, the ranking obtained through power indexes takes into account the notion of defence, and so e is evaluated as the best argument after b. Also the SAF and M&T semantics assign to e the second best place in the ranking, after b. On the other hand, M&T does not distinguish between c and d, while φ-ADM, β-ADM and SAF produce the ranking d ≻ c, justified by the fact that c is directly attacked by b and d is not. Notice also that arguments b and e are indifferent for φ-COM and β-COM, because both are necessary to obtain a complete extension. As a last observation, all the considered semantics agree on a never being preferred to any other argument. Similarly to ours, the subgraph-based semantics LSI of [18] is parametric to a chosen Dung semantics. Below, we compare it to the PI-based semantics, showing the differences in the obtained rankings. Considering the AF in Fig. 3a and the grounded semantics, we have b ≃ ^LSIc ≻ ^LSIa and $a ≃_{GDE}^{φ} b ≃_{GDE}^{φ} c$ . The PI-based semantics gives the same position to all the arguments, since none of the them contributes to form the grounded extension (that indeed is empty for the considered AF). In Fig. 3b, instead, the rankings are: a ≻ ^LSIc ≻ ^LSIb and $a ≃_{GDE}^{φ} c ≻_{GDE}^{φ} b$ . Again, since a and c are both necessary for obtaining the grounded extension, they are given the same value.

Fig.3

Example of two AFs for which we provide the grounded extension.

5.2 A comparison over different instances

To better understand how the structure of an AF affects the score assigned to an argument, we study the behaviour of the PI-based semantics on some significant instances of AFs given in [18]. These instances represent various possible configurations of attacks and defences, with the respective rebuttal and reinstatement of arguments. Below, we present some remarks on the 15 AFs configurations we have analysed. The functions φ and β return equivalent rankings for the conflict-free, admissible, complete, preferred and stable semantics.

The ranking function based on the Shapley Value considers, in the computation of the ranking, all the possible permutations of the arguments in a coalition. Since the extensions of any Dung semantics do not depend on a particular ordering of the arguments, this aspect of the φ formula is not relevant for establishing the final ranking. Therefore, the Banzhaf Index β represents a more appropriate method for evaluating the contribution of the arguments that form the extensions.

Comparing the ranking resulting from β-CF and β-ADM for the AF in Fig. 4b, we notice that the argument a, that is worse than c according to the conflict-free semantics, is indifferent from c when considering the admissible one. The difference is due to the fact that, in β-ADM, a is able to defend itself from the attack of b, and so it is reinstated as an admissible extension, while, following the conflict-free semantics, the attack of b is sufficient for making a less preferable than c.

Fig.4

Example of AFs with different rebuttal/restatement configurations.

In the AF of Fig. 4c, β-CF ranks arguments b, c and d in a higher position than the others. Indeed, the Banzhaf Index computed with respect to the set of conflict-free extensions, assigns higher value to arguments that are less involved in attack relations (both as attackers and as attacked). On the other hand, for the admissible semantics, where the notion of defence plays a fundamental role, arguments b, c and d are worse than e and a. Also in Fig. 4d, for β-CF, a is the worst argument of the framework, because it receives more attacks than any other. According to β-ADM, instead, the argument a, that is attacked and defended, has a higher position than b, c and d, that are not defended. Hence, we believe that the acceptability conditions of the admissible semantics are more suitable for computing a ranking over the arguments of an AF, that those of the conflict-free.

Considering the admissible semantics also provide a better evaluation for the reinstated arguments than the complete one. For instance, in Fig. 4a, β-COM assigns the same score to a, c and d, since they appear together in the only complete extension, while the ranking returned by β-ADM is c ≃ d ≻ a ≻ b. It is straightforward that the admissible semantics, which correctly captures the notion of defence, is more appropriate for computing the ranking.

Due to the small number of arguments, the complete, preferred and stable semantics share the same set of extensions (and thus produce the same ranking) in all the instances we take into account. Following the previous considerations, β-ADM is the more reasonable ranking function among the PI-based semantics.

In the following section, we show how the PI-based ranking semantics have been implemented in ConArg.

6 ConArg

ConArg is a suite of tools that was started to be developed with the purpose to facilitate research in the field of Argumentation in Artificial Intelligence. Recent works (as the ones presented in [9, 10]) have been carried out with the help of ConArg. The project involves a series of components that address different aspects of argumentation, building on a constraint-based solver for argumentation problems [11, 13]. The tool has already been extended with two main additional features that allow for handling weighted [10, 12] and probabilistic [9] argumentation. While the former relies on algebraic structures (c-semirings) for dealing with weights, the latter makes use of a probabilistic logic programming language.

In classical argumentation, arguments can be either accepted or rejected according to their justification status, but no further distinction can be done beyond this division into these two categories. 4 On the other hand, ranking semantics allow for assigning an individual score to each argument so that an overall ranking of all arguments can be established by sorting the set of scores. Carrying on the work in [7, 8], we implemented of a ranking function based on the Shapley Value [26], a very well known concept in cooperative game theory, which we use to distribute the scores among the arguments: the more an argument contributes to the acceptability of an extension, the higher its score. In addition, we also take into account a different valuation scheme, the Banzhaf Index [3], and we implement it in order to study the differences with the results obtained through the Shapley Value. Given an argumentation framework, the tool computes the score of every argument over both the ranking schemes introduced above, and its output is a ranking of the arguments with respect to a given semantics.

The ConArg Web Interface (see Fig. 5 for an overview) allows one to easily perform complex argumentation related tasks. Below, we describe the main features of the tool, highlighting those introduced more recently.

Fig.5

A screenshot of the ConArg web interface. The highlighted elements are: 1. Options menu, 2. Semantics selection panel, 3. Canvas where the AF is visualised, 4. AF in input, 5. Output panel.

Menu. Positioned to the left side of the interface, it allows for choosing among different options for both visualising AFs and solving argumentation problems. In particular, it is possible to: import an AF from a local file in aspartix format, change the visualisation of the attacks for weighted AFs, switching the behaviour of the drag action between moving an argument in the canvas and drawing an attack, selecting the kind of problem to solve, run the computation, and save the output as a text file.

Semantics selection panel. Here it is possible to set the parameters for the resolution of several problems. First of all, one is required to select a Dung semantics through the dedicated drop-down menu. For each semantics, four different kinds of problem can be solved. In particular, one can: enumerate the extensions for the chosen semantics, check the credulous/sceptical acceptability of a particular argument, and rank the arguments by using a PI-based semantics. For the latter problem, it is required to select a power index among the those implemented.

Canvas. This area of the interface has a twofold purpose. On one hand, it is possible to define an AF by drawing nodes and edges. On the other hand, after the calculation of a solution for a certain problem, the canvas allows for visualising the output directly on the displayed AF, through a specific colouration of the arguments. For instance, to display the results of a ranking-based semantics, arguments are assigned a greyscale colour according to their ranking position.

AF in input. AFs can be entered in this panel. Changes to the canvas also affect this area, that maintains a coherent representation of the AF.

Output panel. The solutions for the various problems solved by ConArg are displayed here. It is also possible to download a text file containing the output.

6.1 Implementation of the PI-based semantics

Behind the web interface, ConArg has several modules (like the solver and the ranking script) that allow one to access different functionalities to cope with argumentation problems. In this section, we discuss, in particular, the component of the tool that concerns ranking-based semantics, putting attention on implementation aspects.

When we start the computation of the ranking over the arguments of an AF F, the interface calls the ConArg solver that returns the set S of extensions for the chosen Dung semantics σ. These extensions represent the sets of in arguments with respect to σ and are formatted as sets of strings (e.g., S = {{a} , {a, b} , {c, d}}, where a, b, c and d are arguments). Together with the set of extensions, also the framework F and the power index π that we want to use are passed to the ranking script. The script, then, computes the specified power index π for each of the argument in F. The obtained values are approximated to the nearest fifth decimal digit. The two functions that implement the equations of Section 2.2 share a common part, namely v_{S
_i}, that represents the evaluation of the contribution of the argument i in forming acceptable extensions. For the sake of efficiency, we compute π only with respect to those sets S such that either S or S ∪ {i} is an extension for σ. In any other case, the value of v (S ∪ {i})-v (S) is zero, so we don’t need to do the calculation.

We distinguish between two different characteristic functions: $v_{σ}^{I} (S)$ and $v_{σ}^{O} (S)$ . As stated in Definition 8, the former function takes into account the set of in arguments. Given a set of arguments S that does not contain i, if S ∪ {i} is an extension with respect to σ and S alone is not, then i brings a positive contribution to the coalition, and its own rank will be higher according to $v_{σ}^{I} (S)$ . On the other hand, the latter function ( $v_{σ}^{O} (S)$ ) only considers arguments that are labelled out by σ. In detail, i gets a positive value by π when S ∪ {i} is a set of out arguments and S alone is not. The set out (L_σ) is obtained by computing the sets of arguments that are attacked by the extensions of the semantics σ. At this point, each argument of F is associated with the values of the two functions; the resulting structure has the format of an array [arg _ name, pi _ in, pi _ out], where the three components are: the identifier of the argument, the value of the power index π obtained through $v_{σ}^{I} (S)$ , and the value of π obtained through $v_{σ}^{O} (S)$ , respectively.

In order to establish the preference relation between two arguments, the PI-based semantics considers the value pi _ in first: the greater the score of an argument with respect to $v_{σ}^{I} (S)$ , the higher its position in the ranking. In case of a tie, i.e., when the value of pi _ in is the same for both the arguments that we want to compare, we perform a further control looking at the value of $v_{σ}^{O} (S)$ . Following the principle that accepted arguments are better than rejected ones, the greater the value of an argument with respect to pi _ out, the lower its position in the ranking. Consider, for example, two arguments a and b, belonging to F, with the following evaluations obtained through π: [a, 0.2, - 0.5] and [b, 0.2, - 0.4]. The value pi _ in is equal for both a and b, therefore we proceed to confront the values for pi _ out. Since -0.5 < -0.4, we have that $a ≻_{F}^{π} b$ . The motivation to this kind of ranking is that, while a and b have the same contribution in forming acceptable extensions, a belongs to fewer sets of out arguments, that is, a is defeated less times than b. Hence, it is reasonable to prefer a to b.

Finally, when all the arguments are sorted according to the semantics and the power index that we have selected, the results of the computation are displayed in the output panel (frame 5 of Fig. 5). Along with the overall ranking, we show the pi_in and pi_out values of each argument. For providing a visual hint about which arguments are the most preferred and which ones the least, we assign a colour to each node of the AF visualised in the canvas. The assigned colours vary in a greyscale, according to the position of the corresponding argument in the obtained ranking: the lighter the colour, the higher the rank (as depicted in the frame 3 of Fig. 5).

7 Related work

Several works can be found in the literature on ranking-based semantics, with different interpretations of the values associated to the arguments. The authors in [6] propose a categoriser function that assigns a value to each argument, given the value of its direct attackers. Since only direct attackers are considered in order to compute the ranking, if an argument is attacked by two weak arguments, it is ranked below an argument that is attacked only once by a stronger argument. Differently from our approach, the categoriser does not consider the importance of the arguments, but the structure of the framework.

The semantics described in [16] is based on the principle that an argument is more acceptable if it can be preferred to its attackers. The authors take into account all the ancestor branches of an argument (defending and attacking) and compare their length. However, the produced ranking is only partial: for example, if an argument has strictly more attack branches and more defence branches than another one, then the two arguments are incomparable.

The authors in [24] introduce the formalism for Social Abstract Argumentation Frameworks, an extension of classical AFs, where arguments are associated with a value that represents the social support/vote. In the computation of the ranking, the strength of the attackers is more important than their number, and different methods can be employed for aggregating the votes altogether. This social model-based semantics requires exogenous information, not directly deductible from the relations among the arguments, and thus differs from our intention to provide an approach that can be used with classical settings.

Two different semantics are introduced in [1]: the Discussion-based semantics and the Burden-based semantics. The former, compares arguments by counting the number of paths ending to them; in case of a tie, the length of paths is recursively increased until a difference is found. The latter semantics assigns a Burden Number to every argument, which depends on the Burden Number of its direct attackers. In both the presented approaches, the number of attackers is more important than their strength, i.e., the notion of acceptability is not taken into account.

In [25], the strength of a given argument is computed by instantiating a non-cooperative game between a proponent and an opponent of that argument. In this model, defended arguments are stronger than non defended ones, although the final evaluation does not consider the contribution of each arguments in forming acceptable extensions, but is rather determined by the outcome of a fictitious two-person game. In addition, proponent and opponent choose mixed strategies, according to some probability distributions, that have to be fixed in advance.

The work in [2] introduces the concept of contribution measure, which evaluates the intensity of each attack in an argumentation framework, in order to establish the loss, in terms of acceptability, undergone by attacked arguments. The attackers of each argument can be then ranked from the most to the least harmful ones, according to their contribution measure. The Shapley Value is shown to be the unique measure that satisfies some crucial axioms, e.g., the independence between the contribution of an argument and its identifier. Also in this case, the notion of defence is not used for the evaluation of the contribution, while our idea of a ranking semantics relies on the acceptability status of arguments in the extensions.

The graded semantics proposed in [20] takes into account extensions of classical semantics in order to determine an ordering between arguments of an AF. The two principles on which the semantics is based are: having fewer attackers is better than having more; having more defenders is better than having fewer. The used order relation is only partial (and thus some of the arguments may be incomparable). Moreover, the ranking being built on the two principles mentioned above does not allow to catch the real contribution of the arguments in forming the extensions, that, instead, is the intention of the power index-based semantics.

Next, we discuss the ranking semantics, based on subgraphs analysis, introduced in [18]. This semantics produces a ranking by counting how many times a certain argument is accepted, rejected or undecided, according to the reinstatement labelling of [15]. The main difference with our approach is that, while we only consider acceptable extensions for obtaining the evaluation of an argument, the semantics in [18] uses all the possible subsets of arguments for computing the ranking, thus not considering the definition of the chosen Dung semantics.

Notions from cooperative game theory have been used in many Artificial Intelligence related works for estimating the contribution of a particular factor to a given phenomenon. For example, in [21] and [27], the Shapley Value is used for obtaining inconsistency measures for knowledge bases. In particular, the measure devised in [21] indicates the contribution of each formula of a belief base to the overall inconsistency of the base, while the author of [27] provide a Shapley Value-based measure that shows how inconsistency is distributed on a probabilistic knowledge base, so to also identify the causes for the inconsistency. Similarly, in the PI-based semantics, the Shapley Value is used to identify the role that arguments play in forming extensions of a given semantics.

8 Conclusion and future perspectives

In this paper we introduce a general definition of power index-based semantics, by extending what presented in [8] that only considered the Shapley Value. We use this generalisation to compare how the Shapley value and the Banzhaf index satisfy some of the classical properties of ranking-based semantics in the literature. Differently from other ranking-based semantics defined in the literature, our approach allows for distributing preferences among arguments taking into account classical Dung/Caminada semantics. In this way, we obtain a more accurate ranking with respect to the desired acceptability criterion. We have also presented an online tool capable of dealing with ranking-based semantics. The tool implements the definition of the PI-based semantics [8] with respect to the Shapley Value and the Banzhaf Index.

In the future, we plan to implement other indexes in the tool, or combinations of them. As a starting point, we could use the work in [23], where various power indexes are grouped according to some criteria that qualify them for certain applications. In particular, we may consider the Public Good index, that is said to detect “special games”. We aim to understand which ranking properties (or families of them, i.e., local or global) listed in [14] such indexes can successfully capture. With the comparison of different indexes, we aim to determine if there is a link between ties on rankings and the possible resolution of ambiguities. So far, we have only captured properties that are local to an argument, i.e., they can be checked by inspecting the immediate neighbourhood of an argument. Global properties derive, instead, from the whole framework structure (e.g., full attacking or defending paths), and could be exploited for further refining the ranking returned by our semantics. We are also interested in extending our work on weighted AFs, where a different notion of defence is used.

Another direction we plan to investigate concerns the characteristic functions we use for evaluating the arguments. Similarly to what is done in [17] for studying coalitions with particular properties, we want to restrict the set of possible extensions by considering only the subsets of arguments that are in a given semantics. In this way, we can exclude all the arguments that are not even credulously accepted. For instance, we could devise a PI-based semantics where the arguments are evaluated with respect to the stable semantics, while the only coalitions to be taken into account are the admissible ones.

Footnotes

ConArg Website:

We just write L_σ when the reference to F is clear and unambiguous.

Other power indexes exist, such as the Deegan-Packel Index and the Johnston Index [], that are relevant in cooperative game theory, and that could be useful for special purpose ranking that we plan to study in the future.

More than just two categories have been proposed in the literature, but still from a qualitative point of view.

Proof of Theorem 1

In the following, we provide proofs or counterexamples for all the properties in Theorem 1.

Proof. For each power index, characteristic function and semantics, we state if the properties are satisfied.

Abs: Any extension of every semantics σ is computed starting from the set of attack relations among arguments, thus the ranking is preserved up to isomorphisms of the framework.

Ind: The semantics we propose computes the ranking starting from the sets of extensions of a chosen semantics σ. Since the labelling of each argument a is determined by the other arguments in the same connected component of a, also the ranking between every pair of arguments a and b is independent of any other argument outside the connected component of a and b.

VP: The PI-based semantics never satisfies VP for any σ∈ {conflict-free, admissible, complete, preferred, stable}, with respect to $v_{σ}^{I}$ and $v_{σ}^{O}$ , and for both φ and β. Counterexamples are provided in Figs. 6, 7, and 8.

SC: Consider σ = conflict-free. If (a, a) ∉ R and (b, b) ∈ R, we can state that $\exists E \subset A \land a \notin E : v_{σ}^{I} (E \cup {a}) - v_{σ}^{I} (E) > - 1 \land$ $∄ E \subset A \land b \notin E : v_{σ}^{I} (E \cup {b}) - v_{σ}^{I} (E) > - 1$ Thus $π_{a} (v_{σ}^{I}) > π_{b} (v_{σ}^{I})$ from which we conclude that $a ≻_{σ, I}^{π} b$ when σ = conflict-free. In Fig. 8 we show a counterexample for the other cases.

CP: For both φ and β, the CP property is not satisfied for any σ∈ {conflict-free, admissible, complete, preferred, stable} with respect to $v_{σ}^{I}$ and $v_{σ}^{O}$ . Counterexamples in Figs. 8 and 9.

QP: For both φ and β, QP is not satisfied for any σ∈ {conflict-free, admissible, complete, preferred, stable} with respect to $v_{σ}^{I}$ and $v_{σ}^{O}$ . See Figs. 10, 11 and 12 for counterexamples.

NaE: Non-attacked arguments are labelled in in every complete extension, thus, for any F and π ∈ {φ, β}, we have that if a, b ∈ A are non-attacked, then $π_{a} (v_{σ}^{I}) = π_{b} (v_{σ}^{I})$ and $π_{a} (v_{σ}^{O}) = π_{b} (v_{σ}^{O})$ . Hence $a ≃_{σ, I}^{π} b$ and $≃_{σ, O}^{π}$ , when σ ∈ {complete}. Since all the preferred and stable extensions are also complete, NaE holds for σ ∈ {complete, preferred, stable}. On the other hand, for σ ∈ {conflict-free, admissible} the property is not satisfied (see the counterexample in Fig. 13).

ToT: Any π ∈ {φ, β} associate a real number to every arguments of an AF, thus all pairs of arguments can be compared through the order of $ℝ$ .

□

We conclude that the Shapley Value and the Banzhaf Index satisfy the same properties, among those we checked.

Acknowledgment

This work was partially supported by “Argumentation 360” (Ricerca di Base 2017-2019), “RACRA” (Ricerca di Base 2018-2020) and “ASIA” (Social Interaction with Argumentation - GNCS-INDAM).

References

Amgoud

, Ben-Naim

, Ranking-Based Semantics for Argumentation Frameworks. In Liu

Weiru

, Subrahmanian

V.S.

, and Wijsen

Jef

, editors, Scalable Uncertainty Management - 7th International Conference, SUM 2013, volume 8078 of LNCS, (2013), pp. 134–147. Springer.

Amgoud

, Ben-Naim

, Vesic

, Measuring the Intensity of Attacks in Argumentation Graphs with Shapley Value. In Sierra

Carles

, editor, Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, (2017), pp. 63–69. ijcai.org.

Banzhaf

J.F.

, Weighted Voting Doesn’t Work: A Mathematical Analysis, Rutgers Law Review19(2) (1965), 317–343.

Baroni

, Caminada

, Giacomin

, An introduction to argumentation semantics, Knowl. Eng Rev.,26(4) (2011), 365–410.

Baroni

, Gabbay

, Giacomin

, van der Torre

, Handbook of Formal Argumentation, College Publications, 2018.

Besnard

, Hunter

, A logic-based theory of deductive arguments, Artif Intell128(1-2) (2001), 203–235.

Bistarelli

, Faloci

, Santini

, Taticchi

, A Tool For Ranking Arguments Through Voting-Games Power Indexes. In Casagrande

Alberto

and Omodeo

Eugenio G.

, editors, Proceedings of the 34th Italian Conference on Computational Logic, volume 2396 of CEUR Workshop Proceedings, (2019), pp. 193–201. CEUR-WS.org.

Bistarelli

, Giuliodori

, Santini

, Taticchi

, A Cooperative-game Approach to Share Acceptability and Rank Arguments. In Dondio

Pierpaolo

and Longo

Luca

, editors, Proceedings of the 2nd Workshop on Advances In Argumentation In Artificial Intelligence, Co-Located with XVII International Conference of the Italian Association for Artificial Intelligence, AI3@AI*IA, volume 2296 of CEUR Workshop Proceedings, (2018), pp. 86–90. CEUR-WS.org.

Bistarelli

, Mantadelis

, Santini

, Taticchi

, Probabilistic Argumentation Frameworks with MetaProbLog and ConArg. In Tsoukalas

Lefteri H.

, Grégoire

Éric

, and Alamaniotis

Miltiadis

, editors, IEEE 30th International Conference on Tools with Artificial Intelligence, ICTAI, (2018), pp 675–679. IEEE.

10.

Bistarelli

, Rossi

, Santini

, ConArg: A Tool for Classical andWeighted Argumentation. In Baroni

Pietro

, Gordon

Thomas F.

, Scheffler

Tatjana

, and Stede

Manfred

, editors, Computational Models of Argument - Proceedings of COMMA, volume 287 of Frontiers in Artificial Intelligence and Applications, (2016), pp. 463–464. IOS Press.

11.

Bistarelli

, Rossi

, Santini

, A ConArg-Based Library for Abstract Argumentation. In 29th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2017, Boston, MA, USA, November 6–8, 2017, (2017), pp. 374–381. IEEE Computer Society.

12.

Bistarelli

, Rossi

, Santini

, A novel weighted defence and its relaxation in abstract argumentation, Int J Approx Reason92 (2018), 66–86.

13.

Bistarelli

, Santini

, Modeling and Solving AFs with a Constraint-Based Tool: ConArg. In Modgil

Sanjay

, Oren

Nir

, and Toni

Francesca

, editors, 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, (2011), pp. 99–116. Springer.

14.

Bonzon

, Delobelle

, Konieczny

, Maudet

, A Comparative Study of Ranking-Based Semantics for Abstract Argumentation. In Schuurmans

Dale

and Wellman

Michael P.

, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (2016), pp. 914–920. AAAI Press.

15.

Caminada

, On the Issue of Reinstatement in Argumentation. In Fisher

Michael

, van der Hoek

Wiebe

, Konev

Boris

, and Lisitsa

Alexei

, editors, Logics in Artificial Intelligence, 10th European Conference, JELIA, volume 4160 of LNCS, (2006), pp. 111–123. Springer.

16.

Cayrol

, Lagasquie-Schiex

M.-C.

, Graduality in Argumentation, J Artif Intell Res23 (2005), 245–297.

17.

Derks

, Peters

, A Shapley Value for Games with Restricted Coalitions, Int J Game Theory21(4) (1993), 351–60, December.

18.

Dondio

, Ranking Semantics Based on Subgraphs Analysis. In André

Elisabeth

, Koenig

Sven

, Dastani

Mehdi

, and Sukthankar

Gita

, editors, Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS, pages 1132–1140. International Foundation for Autonomous Agents and Multiagent Systems Richland, SC, USA / ACM, 2018.

19.

Dung

P.M.

, On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games, Artif Intell77(2) (1995), 321–358.

20.

Grossi

, Modgil

, On the Graded Acceptability of Arguments. In Yang

Qiang

and Wooldridge

Michael J.

, editors, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI, (2015), pp. 868–874. AAAI Press.

21.

Hunter

, Konieczny

, On the measure of conflicts: Shapley Inconsistency Values, Artificial Intelligence174(14) (2010), 1007–1026.

22.

Keith

, Encyclopedia of Power. SAGE Publications, Inc., 2011.

23.

Kurz

, Which criteria qualify power indices for applications? - A comment to “The story of the poor Public Good index”, CoRR, abs/1812.05808, 2018.

24.

Leite

, Martins

, Social Abstract Argumentation. In Walsh

Toby

, editor, IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, (2011), pp. 2287–2292. IJCAI/AAAI.

25.

Matt

P.-A.

, Toni

, A Game-Theoretic Measure of Argument Strength for Abstract Argumentation. In Hölldobler

Steffen

, Lutz

Carsten

, and Wansing

Heinrich

, editors, Logics in Artificial Intelligence, 11th European Conference, JELIA, volume 5293 of LNCS, (2008), pp. 285–297. Springer.

26.

Shapley

L.S.

, Contributions to the Theory of Games, volume II of AM-28. Princeton University Press, 1953.

27.

Thimm

, Measuring Inconsistency in Probabilistic Knowledge Bases. In Bilmes

Jeff A.

and Ng

Andrew Y.

, editors, UAI 2009, Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, Montreal, QC, Canada, June 18–21, 2009, (2009), pp. 530–537. AUAI Press.

28.

Winter

, The Shapley Value. In Aumann

R. J.

and Hart

, editors, Handbook of Game Theory with Economic Applications, volume 3, pp. 2025–2054. Elsevier.

Power index-based semantics for ranking arguments in abstract argumentation frameworks

Abstract

Keywords

1 Introduction

2 Preliminaries

2.1 Argumentation

2.2 Power indexes

4 PI-based semantics properties

Table 1 Properties of the PI-based semantics satisfied by φ and β

Table 5 Ranking of the AF in Fig. 1 with the PI-based semantics Semantics Ranking through φ Ranking through β CF b ≻ c ≻ d ≻ e ≻ a b ≻ c ≃ d ≻ e ≻ a ADM b ≻ e ≻ d ≻ a ≃ c b ≻ e ≻ d ≻ a ≃ c COM b ≃ e ≻ a ≃ c ≃ d b ≃ e ≻ a ≃ c ≃ d

7 Related work

8 Conclusion and future perspectives

Footnotes

Proof of Theorem 1

Acknowledgment

References

Table 1
Properties of the PI-based semantics satisfied by φ and β

Table 5
Ranking of the AF in Fig. 1 with the PI-based semantics

Semantics Ranking through φ Ranking through β

CF b ≻ c ≻ d ≻ e ≻ a b ≻ c ≃ d ≻ e ≻ a

ADM b ≻ e ≻ d ≻ a ≃ c b ≻ e ≻ d ≻ a ≃ c

COM b ≃ e ≻ a ≃ c ≃ d b ≃ e ≻ a ≃ c ≃ d