A Cooperative-game Approach to Share Acceptability and Rank Arguments?

Abstract

We deploy a game-theoretic approach for analysing the acceptability of arguments in a generic Abstract Argumentation Framework. The result is a ranking-based semantics, which sorts arguments from the most to the least acceptable. In the computation of such a ranking, we adopt the Shapley Value formula, since it is usually used to fairly distribute costs to several entities in coalitions (labelled sets of arguments in our case). Finally, we show that some well-known properties are satisfied by the ranked-semantics we designed, and we provide an example of how our approach works.

Keywords

• Argumentation
• semantics
• ranking
• cooperative game theory

Introduction

Argumentation represents a qualitative and logical method to deal with uncertain and defeasible reasoning. Defining the properties of an argumentation semantics [ 5 ] amounts to specifying the criteria for deriving subsets of arguments (called extensions) from an Abstract Argumentation Framework (AAF), which is defined by a set of arguments A and an attack relation R on A. On the basis of such extensions, three justification statuses can be assigned to each argument [ 7 ]: an argument is justified, w.r.t. a given semantics, if it belongs to all its extensions, defensible if it belongs to at least one (and it is not justified), or overruled if it does not belong to any extension. For some applications (e.g., Decision-making [ 1 ] or Strategic Games [ 6 ]), it is important to provide a ranking over the arguments. However, the three levels of justification previously introduced are not enough to obtain a detailed ranking. This is the main motivation behind rankingbased semantics [ 1 ], which define an order that can be interpreted as corresponding to a classification into finer acceptability levels.

The aim of our work is to design a ranking-based semantics based on the Shapley Value (SV ) scheme taking advantage of labelling semantics [ 2 ]. The SV formula is a well-known concept in cooperative game theory, and it is usually deployed to share fairly cost or gains according to a valuation function. By exploiting the SV formula, we can build a ranking among arguments by taking into account how much an argument ? This work has been supported by: “ComPAArg” (Ricerca di base 2016–2018), “Argumentation 360” (Ricerca di Base 2017–2019) and “RACRA” (Ricerca di base 2018–2020). participates to make an extension admissible (or complete, preferred, etc.). Designing a ranking-based semantics in this way has the advantage of automatically inheriting the properties of the SV, like efficiency, symmetry, linearity, and zero players [ 8 ]. 2

Preliminaries

The most used fair division scheme used in cooperative game theory is the Shapley Value [ 8, 9 ], that takes a random ordering of the agents picked uniformly from the set of all n! possible orderings, and charges each agent with her expected marginal contribution. Since for any agent i 2 G and any set S i G r fig with jS ij = s, the probability that the set of agents S i comes before i in a random ordering is s!(n 1 s)!=n!, the Shapley Value can be defined by the following formula, for each agent i: n 1 s!(n fi(v) = å s=0 1 n! s)!

å S i Grfig jS ij=s (v(S i [ fig) v(S i)) (1) where v : 2n ! f0; 1g for simple cooperation games. Computing the SV is O(n2).

An AAF [ 5 ] is a pair hA; Ri consisting of a set A of arguments and of a binary relation R on A, called attack relation. Defining an argumentation semantics consists in providing criteria ruling which subsets of A can be accepted. Some well-known semantics are, for instance: conflict-free, admissible, complete, preferred, grounded and stable. Two main definition styles can be identified in the literature: extension-based and labelling-based ones [ 2 ]. In this section, we focus on reinstatement labelling [ 4 ]. Definition 1 (Labelling). Let F = hA; Ri be an argumentation framework and L = fin; out; undecg. A labelling of F is a total function L : A ! L such that 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. We say that L is a reinstatement labelling if and only if it satisfies the following: – 8a 2 A j a 2 in(L), 8b 2 A j (b; a) 2 R; b 2 out(L); – 8a 2 A j a 2 out(L), 9b 2 A j (b; a) 2 R; b 2 in(L).

The idea underlying the labelling-based approach is to give each argument a label, with the purpose to define a labelling-based semantics as follows.

Definition 2 (Labelling-based semantics). A labelling-based semantics s associates with an AAF F a subset of all the possible labellings for F, denoted as Ls (F). Let L be a labelling of F = hA; Ri, then L is – conflict-free iff for each a 2 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 iff the attackers of each in-labelled argument are labelled out, and each out-labelled argument has at least one attacker that is in; – complete iff for each a 2 A, a is labelled in iff all its attackers are labelled out, and a is out iff 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 (w.r.t. set-inclusion) among all complete labellings – stable iff it is a complete labelling and undec(L) = 0/ .

In a framework F, the set of arguments labelled in for a labelling-based semantics s corresponds to an extension of the semantics s . We denote with Ls a labelling L satisfying a semantics s . Accordingly, in(Ls ), out(Ls ) and undec(Ls ) refer to sets of arguments that are labelled in, out or undec, respectively, in at least one labelling of F. In Dung’s framework [ 5 ], the acceptability of an argument depends on its membership to previously described sets. Another way to select a set of acceptable arguments is to rank arguments [ 1 ] from the most to the least acceptable ones.

Definition 3 (Ranking-based semantics). A ranking-based semantics associates to any F = hA; Ri a ranking <F on A, where <F is a pre-order (a reflexive 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).

In the following we will use <, ', and omitting F when it is clear from the context. To describe some of the properties, we also need to define isomorphisms between AFs.

Definition 4 (AAF isomorphism). An isomorphism g between two AAFs F = hA; Ri and F0 = hA0; R0i is a bijective function g : A ! A0 such that 8a; b 2 A; (a; b) 2 R iff (g(a); g(b)) 2 R0.

We now recall some of the logical properties for ranking-based semantics [ 1, 3 ] proposed in the literature.

Definition 5 (Properties). Let F = hA; Ri be an AAF and a; b 2 A and denote with P(b; a) a path from b to a. The multi-set of defenders and attackers of a are Rn+(a) = fb j 9P(b; a) with length n 2 2Ng and Rn (a) = fb j 9P(b; a) with length n 2 2N + 1g, respectively. R1 (a) = R (a) is the set of direct attackers of a. 3

Model Description

Our approach consists in assigning a boolean value to a subset of arguments 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.

Definition 6. Let F = hA; Ri, s be a semantics and Ls the set of all possible labellings on F satisfying s . Consider S A. The “SV-based” ranking function is defined as: vIs;F (S) = (1; if S 2 in(Ls ) 0; if otherwise vsO;F (S) = (1; if S 2 out(Ls ) 0; if otherwise

We obtain a couple of values hvIs;F (S); vsO;F (S)i for each considered S. The ranking among arguments is then produced by considering a lexicographic ordering on the pairs, giving precedence to in and then to out. In particular, we can establish the rank of an argument a 2 A by computing its Shapley Values fa(vIs=;OF (S)).

Definition 7 (SV-based semantics). The SV-based semantics associates to any framework F = hA; Ri a ranking <SFV on A such that 8a; b 2 A, a SFV b iff – fa(vIs;F ) > fb(vIs;F ), or – fa(vIs;F ) = fb(vIs;F ) and fa(vsO;F ) < fb(vsO;F ) and a 'SFV b iff fa(vIs;F ) = fb(vIs;F ) and fa(vsO;F ) = fb(vsO;F ).

In the following, we show the properties that are satisfied by the proposed semantics. Theorem 1 (Properties). Considering two arguments a; b 2 A and the set S = fconflictfree, admissible, complete, preferred, stableg with s 2 S , the SV ranked-semantics satisfies the following properties: Abs, Ind, NaE, AE, ToT for any s 2 S , and SC only if s = conflict-free.

Theorem 2. Given a; b 2 A, if 9S 2 in(L) s.t. a 2 S and @S0 2 in(L) s.t. b 2 S0 implies that fa(vIs;F ) > fb(vIs;F ) =) a b.

Consider the example in Figure 1. The score of every argument in F, according to the considered semantics, is shown in Table 1, together with the final ranking for each SV-based semantics. We have that vIc f ;F (S¯) = 1 for S¯ 2 ffag; fcg; fdg; fa; cg; fa; dgg. The SV for the argument a is given by fi(v) = 1!5!3! (v(fa; bg) v(fbg)) + 2!5!2! (v(fa; b; dg) v(fb; dg)) = 0:084. All other terms of the formula are equal to zero, since the gain given by a to any other sets of arguments is null. Due to the fact that the ranking function is non-monotone, the SV can be negative.

a b c d e d c c ' d c ' d e e b b SV-STA a ' d b ' c ' e

Conclusion

We have modelled a ranking-based semantics that takes advantage of two well-established concepts in the literature: Shapley Value [ 8 ] and semantics [ 2 ]. The semantics inherits all the good properties of SV and does not require external values to be computed. Moreover, our approach is able to distribute preferences among arguments by taking into account a particular semantics, allowing to obtain more precise rankings.

As future work, we would like to derive more SV functions than those presented in Section 3, with the purpose to further refine the ranking. Having more labels than just in, out, and undec would allow SV to distribute strength according to more levels of acceptance. Finally, we will check if all the properties in [ 3 ] are satisfied.

References

1. Amgoud , L. , Ben-Naim , J. : Ranking-based semantics for argumentation frameworks . In: Proceedings of SUM 2013. LNCS , vol. 8078 , pp. 134 - 147 . Springer ( 2013 )

2. Baroni , P. , Caminada , M. , Giacomin , M.: An introduction to argumentation semantics . Knowledge Eng. Review 26 ( 4 ), 365 - 410 ( 2011 )

3. Bonzon , E. , Delobelle , J. , Konieczny , S. , Maudet , N.: A comparative study of ranking-based semantics for abstract argumentation . In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence . pp. 914 - 920 . AAAI Press ( 2016 )

4. Caminada , M. : On the issue of reinstatement in argumentation . In: Proceedings of JELIA 2006. Lecture Notes in Computer Science , vol. 4160 , pp. 111 - 123 . Springer ( 2006 )

5. 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 )

6. Matt , P. , Toni , F. : A game-theoretic measure of argument strength for abstract argumentation . In: Proceedings of JELIA 2008. LNCS , vol. 5293 , pp. 285 - 297 . Springer ( 2008 )

7. Pollock , J.L. : How to reason defeasibly . Artif. Intell . 57 ( 1 ), 1 - 42 ( 1992 )

8. Shapley , L.S. : Contributions to the Theory of Games (AM-28) , Volume II. Princeton University Press ( 1953 )

9. Winter , E. : The shapley value . In: Aumann, R. , Hart , S. (eds.) Handbook of Game Theory with Economic Applications , vol. 3 , chap. 53, pp. 2025 - 2054 . Elsevier, 1 edn . ( 2002 )