Power Index-Based Semantics for Ranking Arguments in Abstract Argumentation Frameworks: an Overview

Abstract

Ranking-based semantics for Abstract Argumentation Frameworks represent a well-established concept used for sorting arguments from the most to the least acceptable. This paper presents an overview of our ranking-based semantics that makes use of power indexes such as Shapley Value and Banzhaf Index. Such power index-based semantics is parametric to a chosen Dung semantics and inherits their properties.

Keywords

• Argumentation
• Theory
• Power Indexes

Introduction

Argumentation Theory is a eld of Arti cial Intelligence that provides formalisms for reasoning with con icting information. Arguments from a knowledge base are modelled by Dung [ 11 ] as nodes in a directed graph, that we call Abstract Argumentation Framework (AF in short), where edges represent attacks. Many semantics have been de ned in order to establish di erent kinds of acceptability (see [ 2 ] for a survey). All these semantics return two disjoint sets of arguments: \accepted" and \not accepted". An additional level of acceptability is introduced in [ 9 ] with the reinstatement labelling, a semantics that marks as undecided the arguments that can be neither accepted nor rejected. Dividing the arguments into just three partitions could be not su cient when dealing with very large AFs, so a di erent family of semantics has been de ned for obtaining a broader range of acceptability levels for the arguments. Each of the de ned ranking-based semantics [ 1,3,6,10,13,16,17 ] focus on a di erent criterion for identifying the best arguments in an AF.

In this paper, we give an overview of our work [ 4,5,6,7 ] towards the de nition of a ranking-based semantics that relies on power indexes, like the Shapley Value and the Banzhaf index [ 14 ]. 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. To complete our study and support the research in this eld, we also provide an online tool (ConArg1) capable of dealing with AFs and reasoning with our ranking-based semantics, besides classical ones.

Preliminaries on Argumentation and Power Indexes

An Abstract Argumentation Framework [ 11 ] hA; Ri consists of a set of arguments A and the relations among them R A A. Such relations, which we call \attacks", are interpreted as con ict conditions that allow for determining the arguments in A that are acceptable together (i.e., collectively). 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. Two leading characterisations can be found in the literature, namely extension-based [ 11 ] and labelling-based [ 9 ] semantics. While providing the same outcome in terms of accepted arguments, labelling-based semantics permits to di erentiate between three levels of acceptability. In detail, a labelling of an AF is a total function L : A ! fin; out; undecg, with in(L) = fa 2 A j L(a) = ing, out(L) = fa 2 A j L(a) = outg and undec(L) = fa 2 A j L(a) = undecg. L is a reinstatement labelling if and only if it satis es the following conditions: { 8a; b 2 A, if a 2 in(L) and (b; a) 2 R then b 2 out(L); { 8a 2 A, if a 2 out(L) then 9b 2 A such that b 2 in(L) and (b; a) 2 R.

A labelling-based semantics associates with an AF F = hA; Ri a subset of all the possible labellings for F, denoted as L (F ). For instance, we say that a labelling L of F is 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 in2. 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.

In order to further discriminate among arguments, ranking-based semantics [ 8 ] can be used for sorting the arguments from the most to the least preferred. A ranking-based semantics associates with any F = hA; Ri a ranking <F on A, where <F is a pre-order (a re exive and transitive relation) on A. a <F b means that a is at least as acceptable as b (a ' b is a shortcut for a <F b and b <F a, and a F b is a shortcut for a <F b and b 6<F b). Such kind of semantics can be analysed in terms of properties de ned on the obtained ranking of arguments [ 1 ]. For example, a ranking-based semantics satis es Cardinality Precedence when arguments with more direct attackers are ranked lower than those with less direct attackers; and it satis es Totality if all pairs of arguments can be compared.

In building our ranking-based semantics, we rely on power indexes for establishing a total order between the arguments of a framework. 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 speci c rules. In order to identify the \value" brought from a single player to a coalition, power indexes are used to de ne a preference relation between di erent agents, computed on 2 There are other semantics that we consider in our work and which are omitted here due to space limitations. all the possible coalitions. In our work [ 4,5,6,7 ], we studied and implemented Shapley Value, Banzhaf, Deegan-Packel and Johnston Index [ 14 ]3. We provide here some intuition using the Banzhaf Power Index.

Every power index relies on a characteristic function v : 2N ! R 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 2 N , given by the di erence of gain between S and S [ fig, is vSi = v(S [ fig) v(S). The Banzhaf Index i(v) evaluates each player i by using the notion of critical voter : given a coalition S N n fig, a critical voter for S is a player i such that S [ fig 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) =

1 2jNj 1

X

vSi

S Nnfig

The di erence between the 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. Deegan and Packel assume that only minimal winning coalitions are formed, that they do so with equal probability, and that if such a coalition is formed it divides the ( xed) spoils of victory equally among its members. Finally, the Johnston index di ers from Banzhaf's for the fact that critical voters in winning coalitions are rewarded with a fractional score instead of one whole unit. (1) 3

Model Description

Our approach consists in assigning a value to each argument according to the labels in and out if it satis es the considered classical semantics. An 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. Power indexes provides an a priori evaluation of the position of each player in a cooperative game, based on the contribution that each player brings to the di erent coalitions; in our rankingbased semantics, that we call PI-based, such coalitions are extension computed using classical Dung semantics.

De nition 1 (Characteristic function). Consider an AF F = hA; Ri, a Dung semantics and the set L of all possible labellings on F satisfying . For any S A, the labelling-based characteristic functions vI (S) and vO(S) are de ned as: vI (S) = (1; if S 2 in(L ) 0; if otherwise vO(S) = (0; if S 2 out (L ) 1; if otherwise 3 Other power indexes exist, such as the Public Good Index [ 15 ], that are relevant in cooperative game theory, and that we plan to study in the future.

The function vI (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. The higher the score of the power index, the better the rank of an argument. A second characteristic function, vO(S), is also introduced to put attention on the negative e ect of the attacks received by the arguments. The function vO(S) considers the sets of arguments labelled out by , and the evaluation has the usual interpretation: the lower the score according to vO(S), the worse the rank. Note that if S 2 in(L ) we can have S0 S such that S0 2= (L ). For instance, in Figure 1, fa; cg is an extension of the admissible semantics, while fcg is not.

In this paper, we use the Banzhaf Index to provide an overview our rankingbased semantics, although any other power index can be used for evaluating the arguments.

De nition 2 (PI-based semantics). Let F = hA; Ri 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 8a; b 2 A, a < b () a(v ) 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 power indexes, like e ciency, symmetry, linearity, and zero players [ 19 ]. The lexicographic order on the pairs (vI (S); vO(S)) can be used to break possible ties in the nal 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 di erent 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. In Table 1, we provide an example of ranking obtained through the PI-based semantics for the AF in Figure 1, with respect to the Banzhaf Index and the admissible semantics.

Besides conducting empirical experiments, in [ 7 ] we studied our semantics with respect to the properties introduced in [ 1 ], which describe and characterise the obtained rankings. We remark that those properties are not mandatory for obtaining a well-de ned ranking and that di erent properties can be suitable for di erent applications [ 8 ]. For instance, the ranking produced by the power index in combination with the characteristic function vAIDM satis es the Totality property, but not the Cardinality Precedence (indeed, since we only take into account the acceptability of an argument, the number of direct attackers is not relevant to establish its value).

Finally, we implemented the PI-based semantics in the web interface of ConArg [ 7 ], a suite of tools developed with the purpose to facilitate research in the eld of Argumentation in Arti cial Intelligence. Four power indexes (Shapley Value, Banzhaf, Deegan-Packel and Johnston Index [ 14 ]) are available to compute the ranking, and can be chosen in combination with any Dung semantics for evaluating the arguments of a given AF. The output is provided for both the characteristic functions vI and vO. Besides ranking-based semantics, ConArg o ers di erent functionalities to cope with various argumentation problems (like the computation of extensions). 4

Conclusion

In this paper we summarized the PI-based semantics presented in [ 4,5,6,7 ]. Di erently from other ranking-based semantics de ned 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, which implements the de nition of the PI-based semantics [ 6 ].

The interest in solving argumentation problems has increased in the last few years, as also highlighted by the organisation of three editions of the International Competition on Computational Models of Argumentation (ICCMA 2015 [ 18 ], 2017 [ 12 ] and 2019). So far, ranking-based semantics have never been included in the competition and we believe that employing them in future editions can be useful to advance the research in this direction.

Acknowledgement

I want to thank with gratitude my supervisor, Professor Stefano Bistarelli, for his support in carrying out this work.

References

1. Amgoud , L. , Ben-Naim , J. : Ranking-Based Semantics for Argumentation Frameworks . In: SUM 2013. LNCS , vol. 8078 , pp. 134 { 147 . Springer ( 2013 )

2. Baroni , P. , Caminada , M. , Giacomin , M.: An introduction to argumentation semantics . Knowl. Eng Rev . 26 ( 4 ), 365 { 410 ( 2011 )

3. Besnard , P. , Hunter , A.: A logic-based theory of deductive arguments . Artif. Intell . 128 ( 1-2 ), 203 { 235 ( 2001 )

4. Bistarelli , S. , Faloci , F. , Santini , F. , Taticchi , C. : A Tool For Ranking Arguments Through Voting-Games Power Indexes . In: CILC 2019. CEUR Workshop Proceedings , vol. 2396 , pp. 193 { 201 . CEUR-WS.org ( 2019 )

5. Bistarelli , S. , Faloci , F. , Taticchi , C. : Implementing Ranking-Based Semantics in ConArg . In: ICTAI 2019 (to appear) . IEEE Computer Society ( 2019 )

6. Bistarelli , S. , Giuliodori , P. , Santini , F. , Taticchi , C. : A Cooperative-game Approach to Share Acceptability and Rank Arguments . In: AI3@AI*IA 2018. CEUR Workshop Proceedings , vol. 2296 , pp. 86 { 90 . CEUR-WS.org ( 2018 )

7. Bistarelli , S. , Taticchi , C. : Power Index-Based Semantics for Ranking Arguments in Abstract Argumentation Frameworks . Intelligenza Arti ciale (to appear) ( 2019 )

8. Bonzon , E. , Delobelle , J. , Konieczny , S. , Maudet , N.: A Comparative Study of Ranking-Based Semantics for Abstract Argumentation . In: AAAI-16 . pp. 914 { 920 . AAAI Press ( 2016 )

9. Caminada , M. : On the Issue of Reinstatement in Argumentation . In: JELIA 2006. LNCS , vol. 4160 , pp. 111 { 123 . Springer ( 2006 )

10. Dondio , P. : Ranking Semantics Based on Subgraphs Analysis . In: AAMAS 2018 . pp. 1132 { 1140 . IFAAMAS Richland, SC , USA / ACM ( 2018 )

11. Dung , P.M. : On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games . Artif Intell 77 ( 2 ), 321 { 358 ( 1995 )

12. Gaggl , S.A. , Linsbichler , T. , Maratea , M. , Woltran , S. : Introducing the second international competition on computational models of argumentation . In: SAFA@COMMA 2016. CEUR Workshop Proceedings , vol. 1672 , pp. 4 { 9 . CEURWS.org ( 2016 )

13. Grossi , D. , Modgil , S. : On the Graded Acceptability of Arguments . In: IJCAI 2015 . pp. 868 { 874 . AAAI Press ( 2015 )

14. Keith , D. : Encyclopedia of Power. SAGE Publications, Inc. ( 2011 )

15. Kurz , S. : Which criteria qualify power indices for applications? - A comment to "The story of the poor Public Good index" . CoRR abs/ 1812 .05808 ( 2018 )

16. Leite , J. , Martins , J.: Social Abstract Argumentation . In: IJCAI 2011 . pp. 2287 { 2292 . IJCAI/AAAI ( 2011 )

17. Matt , P.A. , Toni , F. : A Game-Theoretic Measure of Argument Strength for Abstract Argumentation . In: JELIA. LNCS , vol. 5293 , pp. 285 { 297 . Springer ( 2008 )

18. Thimm , M. , Villata , S.: The rst international competition on computational models of argumentation: Results and analysis . Artif. Intell . 252 , 267 { 294 ( 2017 )

19. Winter , E. : The Shapley Value . In: Handbook of Game Theory with Economic Applications , vol. 3 , pp. 2025 { 2054 . Elsevier ( 2002 )