=Paper=
{{Paper
|id=Vol-2296/paper_08
|storemode=property
|title=A Cooperative-game Approach to Share Acceptability and Rank Arguments
|pdfUrl=https://ceur-ws.org/Vol-2296/AI3-2018_paper_8.pdf
|volume=Vol-2296
|authors=Stefano Bistarelli,Paolo Giuliodori,Francesco Santini,Carlo Taticchi
|dblpUrl=https://dblp.org/rec/conf/aiia/BistarelliG0T18
}}
==A Cooperative-game Approach to Share Acceptability and Rank Arguments==
<pdf width="1500px">https://ceur-ws.org/Vol-2296/AI3-2018_paper_8.pdf</pdf>
<pre>
                A Cooperative-game Approach to Share
                 Acceptability and Rank Arguments?

       Stefano Bistarelli1 , Paolo Giuliodori2 , Francesco Santini1 , and Carlo Taticchi3
         1 Department of Mathematics and Computer Science, University of Perugia, Italy
2    School of Science and Technology, Computer Science Division, University of Camerino, Italy
                          3 Gran Sasso Science Institute, L’Aquila, Italy




          Abstract. We deploy a game-theoretic approach for analysing the acceptabil-
          ity 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.


1      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 ranking-
based 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 contri-
bution. Since for any agent i ∈ G and any set S−i ⊆ Gr{i} with |S−i | = 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 − 1 − s)!
                  φi (v) = ∑
                                     n!         ∑ (v(S−i ∪ {i}) − v(S−i ))                    (1)
                           s=0                S ⊆Gr{i}
                                               −i
                                                |S−i |=s

where v : 2n → {0, 1} 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 se-
mantics 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 =
{in, out, undec}. A labelling of F is a total function L : A → L such that 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:

    – ∀a ∈ A | a ∈ in(L), ∀b ∈ A | (b, a) ∈ R, b ∈ out(L);
    – ∀a ∈ A | a ∈ out(L), ∃b ∈ A | (b, a) ∈ R, b ∈ 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 σ associates
with an AAF F a subset of all the possible labellings for F, denoted as Lσ (F). Let L be
a labelling of F = hA, Ri, then L is

    – conflict-free iff 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 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 ∈ 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
σ corresponds to an extension of the semantics σ . We denote with Lσ a labelling L
satisfying a semantics σ . Accordingly, in(Lσ ), out(Lσ ) and undec(Lσ ) 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 tran-
sitive 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 con-
text. To describe some of the properties, we also need to define isomorphisms between
AFs.
Definition 4 (AAF isomorphism). An isomorphism γ between two AAFs F = hA, Ri
and F 0 = hA0 , R0 i is a bijective function γ : A −→ A0 such that ∀a, b ∈ A, (a, b) ∈ R iff
(γ(a), γ(b)) ∈ 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 ∈ A and denote with
P(b, a) a path from b to a. The multi-set of defenders and attackers of a are R+    n (a) =
{b | ∃P(b, a) with length n ∈ 2N} and R−   n (a) =  {b | ∃P(b, a)  with length n ∈ 2N + 1},
respectively. R−
               1 (a) = R− (a) is the set of direct attackers of a.

Abstraction (Abs): For any isomorphism γ s.t. F 0 = γ(F), a <F b iff γ(a) <F 0 γ(b).
Independence (Ind): ∀F 0 ∈ cc(F), ∀a, b ∈ Arg(F 0 ), then a <F 0 b ⇒ a <F b, where
    cc(F) denotes the set of connected components in F.
Self-contradiction (SC): (a, a) 6∈ R and (b, b) ∈ R ⇒ a  b.
Non-attacked Equivalence (NaE): R− (a) = 0/ and R− (b) = 0/ ⇒ a ' b.
Argument Equivalence (AE): for any F = hA, Ri and ∀x, y ∈ A, for every isomor-
    phism λ such that AncF (x) = λ (AncF (y)), then x 'σF y.
Total (ToT): a < b or b < a.

3     Model Description
Our approach consists in assigning a boolean value to a subset of arguments accord-
ing 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, σ be a semantics and Lσ the set of all possible labellings
on F satisfying σ . Consider S ⊆ A. The “SV-based” ranking function is defined as:

                       (                                                (
                        1, if S ∈ in(Lσ )                                1, if S ∈ out(Lσ )
        vIσ ,F (S) =                                      vO
                                                           σ ,F (S) =
                        0, if otherwise                                  0, if otherwise

    We obtain a couple of values hvIσ ,F (S), vO
                                               σ ,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
                                                           I/O
argument a ∈ A by computing its Shapley Values φa (vσ ,F (S)).

Definition 7 (SV-based semantics). The SV-based semantics associates to any frame-
work F = hA, Ri a ranking <SV                             SV
                           F on A such that ∀a, b ∈ A, a F b iff

  – φa (vIσ ,F ) > φb (vIσ ,F ), or
  – φa (vIσ ,F ) = φb (vIσ ,F ) and φa (vO             O
                                         σ ,F ) < φb (vσ ,F )

and a 'SV           I             I               O             O
       F b iff φa (vσ ,F ) = φb (vσ ,F ) and φa (vσ ,F ) = φb (vσ ,F ).

    In the following, we show the properties that are satisfied by the proposed semantics.

Theorem 1 (Properties). Considering two arguments a, b ∈ A and the set Σ = {conflict-
free, admissible, complete, preferred, stable} with σ ∈ Σ , the SV ranked-semantics sat-
isfies the following properties: Abs, Ind, NaE, AE, ToT for any σ ∈ Σ , and SC only if
σ = conflict-free.

Theorem 2. Given a, b ∈ A, if ∃S ∈ in(L) s.t. a ∈ S and @S0 ∈ in(L) s.t. b ∈ S0 implies
that φa (vIσ ,F ) > φb (vIσ ,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̄ ∈ {{a}, {c}, {d}, {a, c}, {a, d}}.
The SV for the argument a is given by φi (v) = 1!·3!                                   2!·2!
                                                        5! · (v({a, b}) − v({b})) + 5! ·
(v({a, b, d}) − v({b, d})) = −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


Fig. 1. Example of an AAF F. The computed sets of extensions for the conflict-fee, admissible,
complete, preferred and stable semantics are: CF = {{}, {a}, {b}, {c}, {d}, {a, c}, {a, d}, {b, d}},
ADM = {{}, {a}, {c}, {d}, {a, c}, {a, d}}, COM = {{a}, {a, c}, {a, d}}, PRE = {{a, c}, {a, d}}
and STA = {{a, d}}, respectively.
                    a        b        c        d       e     Semantics      Ranking
        INCF     −0.084 −0.167 −0.167 −0.084         −0.5
                                                              SV-CF      adcbe
       OUTCF     −0.167 0.25    0.0 −0.084            0.0
        INADM  0.0   −0.417 −0.084 −0.084 −0.417
                                                 SV-ADM a  d  c  e  b
       OUTADM −0.167 0.25    0.0 −0.084 0.0
        INCOM  0.3   −0.117 −0.034 −0.034 −0.117
                                                 SV-COM a  c ' d  e  b
       OUTCOM −0.133 0.283 −0.05 −0.05 −0.05
        INPRE   0.1 −0.0667 0.0167 0.0167 −0.0667
                                                  SV-PRE a  c ' d  e  b
       OUTPRE −0.0833 0.0833  0.0    0.0    0.0
        INSTA    0.05 −0.0333 −0.0333 0.05 −0.0333
                                                   SV-STA a ' d  b ' c ' e
       OUTSTA    −0.05 0.0333 0.0333 −0.05 0.0333

 Table 1. SV for the arguments of the AAF in Figure 1, with final rankings for each semantics.



4   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: Pro-
   ceedings of SUM 2013. LNCS, vol. 8078, pp. 134–147. Springer (2013)
2. Baroni, P., Caminada, M., Giacomin, M.: An introduction to argumentation semantics. Knowl-
   edge 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 Univer-
   sity 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)

</pre>