Measuring the Intensity of Attacks in Argumentation Graphs with Shapley Value

1 Introduction

An argumentation framework is a reasoning model based on the justification of claims by arguments. It is made of a graph and a semantics. The nodes of the graph are arguments, each of which is assigned a basic strength, and the arcs are attacks between pairs of arguments. The semantics is a function assigning to each argument of the graph a value representing its overall strength or acceptability degree. See [Simari and Rahwan, 2009] for an overview on argumentation in AI.

Recently, Amgoud et al. [2016; 2017] have argued that the acceptability degree of an argument should be equal to the basic strength of the argument, if the latter is not attacked. Otherwise, the argument is weakened by its attackers and thus looses weight, leading to an acceptability degree lower than the basic strength. Hence, from the outcome of a semantics, it is possible to compute the global loss undergone by each argument because of its attackers. It is the difference between the basic strength of the argument and its acceptability degree. However, it is not possible to say anything on the contribution of each attack to that loss. That contribution represents, in some sense, the intensity of the attack. The greater the contribution of an attack, the more harmful the attack.

Information on attacks' contributions is very useful since it allows a better understanding of the impact of each attack. Namely, it allows detecting worthless attacks (i.e., attacks that do not have any impact on the target), and redundant ones (i.e., attacks that lead to the same loss for their target).

Attacks' contributions allow also to rank order the attackers of each argument of a graph from the most to the least harmful ones. This ranking is very useful, especially in persuasion dialogues where agents have to choose the best counter-attack in order to win a dialogue. Assume a dialogue between two agents who exchange arguments in order to persuade each other. At each step of the dialogue, an agent presents a new argument attacking one of those uttered by the other party. For that purpose, the agent should choose i) which argument of the opponent to attack, and ii) with which argument. A reasonable strategy consists of targeting an argument that is very harmful for the agent's arguments.

This paper studies for the first time the question of measuring the contribution of each attack to the global loss of its target. It introduces the novel concept of contribution measure, which takes as input an argumentation framework, and returns as output a weight for each attack, representing the contribution of the attack. It considers a broad range of semantics including extension-based ones [Dung, 1995]. The paper starts by defining a set of axioms that a reasonable measure should satisfy. Then, it provides a characterization theorem, which states that Shapley value [Shapley, 1953] is the unique measure that satisfies the axioms. Finally, it investigates properties of that measure under extension semantics, and h-categorizer semantics defined by Besnard and Hunter [2001].

The paper is structured as follows: Section 2 defines argumentation frameworks. Section 3 shows examples of semantics covered by the study. Section 4 introduces contribution measures as well as the set of axioms that they would satisfy. Section 5 provides our characterization result. Section 6 instantiates the Shapely measure with some existing semantics.

2 Argumentation Frameworks

An argumentation framework is made of an argumentation graph and an acceptability semantics. Throughout the paper, we focus on argumentation graphs whose nodes are arguments and arcs are attacks between arguments. An argument is an abstract entity whose internal structure is not specified, however, it has an initial value representing its basic strength. The latter may represent different issues, like certainty degree of argument's premises [Benferhat et al., 1993], trustworthiness in argument's source [da Costa Pereira et al., 2011], etc. Before defining formally argumentation frameworks, we start by introducing the useful notion of weighting.

Definition 1 (Weighting) A weighting on a set X is a function from X to [0, 1].

Let Arg be an infinite set of all possible arguments. An argumentation graph is defined as follows:

Definition 2 (Argumentation Graph) An argumentation graph is an ordered tuple A = 〈A, w, R〉, where A is a finite subset of Arg, w is a weighting on A, and R ⊆ A × A. Let AG be the universe of all argumentation graphs built on Arg.

For two arguments a, b of an argumentation graph A = 〈A, w, R〉, w(a) represents the basic strength of the argument a, and (a, b) ∈ R means that argument a attacks argument b.

Notations: Let A = 〈A, w,R〉 be an argumentation graph. Elements of R will be denoted by r1, r2, . . . , rn. Note that R is finite since A is finite. ScA(.) and TrA(.) are two functions, which return respectively the source a and the target b of an attack (a, b) ∈ R. AttA(.) is a function, which returns all the attacks on an argument (i.e. for a ∈ A, AttA(a) = {r ∈ R | TrA(r) = a}). Let X ⊆ R, A ⊖ X = 〈A, w, R \ X〉.

A semantics is a function assigning to every argument in an argumentation graph an acceptability degree. The greater this degree, the more acceptable the argument. The degree is between 0 and the basic strength of the argument. The idea is: If an argument is not attacked, then it keeps its full basic strength, otherwise it may lose weight if its attackers are sufficiently strong. In [Amgoud et al., 2017], we provided an axiomatic justification for this definition of semantics.

Definition 3 (Semantics) A semantics is a function S transforming any argumentation graph A = 〈A, w, R〉 ∈ AG into a weighting on A s.t. for any a ∈ A, if AttA(a) = ∅, then DegAS (a) = w(a), else DegAS (a) ∈ [0, w(a)]. DegAS (a) is the image of a by S(A), and is called acceptability degree of a.

Throughout the paper, the semantics is left unspecified. However, without loss of generality, it satisfies the very basic syntax-independence, proposed in [Amgoud et al., 2017], and monotonicity properties. The former ensures that the acceptability degree of an argument is independent of the argument's identity. Before defining formally the property, let us first recall the notion of isomorphism of graphs.

Definition 4 (Isomorphism) Let A = 〈A,w,R〉,A′ = 〈A′ ,w′ ,R′ 〉 ∈ AG. An isomorphism from A to A′ is a bijective function f fromA to A′ such that the following hold:

• ∀ a ∈ A, w(a) = w′ (f(a)),
• ∀ a, b ∈ A, (a, b) ∈ R iff (f(a), f(b)) ∈ R′ ,

Definition 5 (Syntax-Indep.) A semantics S is syntaxindependent iff for all A = 〈A,w,R〉,A′ = 〈A′ ,w′ ,R′ 〉 ∈ AG, for any isomorphism f fromA to A′ , the following holds: for any a ∈ A, DegAS (a) = DegA′ S (f(a)).

The monotonicity property ensures that attacks cannot be beneficial for arguments. It is worth pointing out that this property is different from the monotony axiom from [Amgoud and Ben-Naim, 2016; Amgoud et al., 2017], which states the following: if the attackers of an argument a are also attackers of b, then a is at least as acceptable as b. This axiom assumes that a and b are in the same graph, thus the attackers of both arguments have fixed acceptability degrees. Our monotonicity axiom goes one step further by assuming that a and b are in different graphs. Hence, the acceptability degrees of their attackers may vary from one graph to the other. To sum up, it is possible for a semantics to satisfy one of the two forms of monotony and violates the other.

Definition 6 (Monotonicity) A semantics S is monotone iff for any argumentation graph A = 〈A, w, R〉 ∈ AG, ∀a ∈ A, ∀X ⊆ AttA(a), it holds that DegAS (a) ≤ DegA⊖X S (a).

Notation: Let Sem be the universe of all syntax-independent and monotone semantics defined on AG.

When the acceptability degree of an argument is lower than its basic strength, the argument has lost strength due to its attackers. The total amount of that loss is defined as follows.

Definition 7 (Loss) Let S ∈ Sem, A = 〈A, w, R〉 ∈ AG, and a ∈ A. The loss of a is LossAS (a) = w(a) - DegAS (a).

From the definitions, we get the following obvious results.

Property 1 Let S ∈ Sem, A = 〈A, w, R〉 ∈ AG, a ∈ A.

• LossAS (a) ∈ [0, 1].
• If AttA(a) = ∅, then LossAS (a) = 0.

The following property follows also straightforwardly from the monotonicity of semantics of the set Sem.

Property 2 Let S ∈ Sem, A = 〈A, w, R〉 ∈ AG, and a ∈ A. For any X ⊆ AttA(a), LossAS (a) ≥ LossA⊖X S (a).

3 Examples of Covered Semantics

The previous section introduced the set Sem of semantics we consider in this paper, namely syntax-independent and monotone semantics. Before defining contribution measures that share the loss of an argument under such semantics among the argument's attacks, we need first to show that the set Sem is not empty. In other words, we should prove that there exist semantics that satisfy the two above properties. Hopefully, this is the case of at least Dung's extension semantics [1995] and Besnard and Hunter's h-Categorizer semantics [2001].

In his seminal paper, Dung assumed all arguments have the same basic strength. Thus, we consider argumentation graphs whose arguments have each the basic strength 1. An extension semantics starts by computing subsets of arguments (called extensions), which are conflict free (i.e., they do not contain two arguments that attack each others). Furthermore, they defend their elements (i.e., they attack any argument attacking one of their elements). Let A = 〈A,w,R〉 be an argumentation graph such that for any a ∈ A, w(a) = 1, and let E ⊆ A be a conflict-free set.

• E is a complete extension iff it defends all its elements and contains any argument it defends.
• E is a preferred extension iff it is a maximal (w.r.t. set ⊆) complete extension.
• E is a stable extension iff it attacks any a ∈ A \ E.

• E is a grounded extension iff it is a minimal (w.r.t. set ⊆) complete extension.

Let Extx(A) denote the set of all extensions of A under semantics x, where x ∈ {st, pr, gr, co} and st (resp. pr, gr, co) stands for stable (resp. preferred, grounded, complete) semantics. Once extensions are computed, acceptability degrees are assigned to arguments. In what follows, we slightly modify the definition given by Amgoud and BenNaim [2016], in particular the case where a graph has no stable extensions. Instead of assigning the degree 0.3 to each argument of the graph, we assume that arguments keep their basic strengths. The idea is that there is no reason for losing strength. Formally, for any a ∈ A, if Extx(A) = ∅, then DegAx (a) = w(a) = 1, otherwise:

• DegAx (a) = 1 iff a ∈ ⋂ E∈Extx(A) E.
• DegAx (a) = 0.5 iff ∃E, E ′ ∈ Extx(A) s.t a ∈ E, a /∈ E ′ .
• DegAx (a) = 0.3 iff a /∈ ⋃ E∈Extx(A) E and ∄E ∈ Extx(A) s.t ∃b ∈ E and (b, a) ∈ R.
• DegAx (a) = 0 iff a /∈ ⋃ E∈Extx(A) E and ∃E ∈ Extx(A) s.t ∃b ∈ E and (b, a) ∈ R.

We show next that the four semantics are part of the set Sem. Indeed, they are in accordance with Definition 3 of semantics, and are all syntax-independent and monotone.

Besnard and Hunter [2001] proposed h-categorizer semantics for evaluating arguments in acyclic graphs. This semantics was extended by Pu et al. [2014] to any graph structure. It considers as input an argumentation graph whose arguments have all the same basic strength 1, and returns an acceptability degree in the interval (0, 1] to each argument a as follows:

with ∑ b:bRa DegAh (b) = 0 if AttA(a) = ∅.

It was shown in [Amgoud and Ben-Naim, 2016] that hcategorizer is in accordance with Definition 3, and is syntaxindependent. We implemented this semantics, and run several experiments, which all show that the semantics is monotone.

Conjecture 1 h-categorizer semantics is monotone. It is thus a member of the set Sem.

The two previous results show that the set of semantics investigated in the paper is not empty (Sem ̸= ∅) and covers the main existing semantics.

4 ContributionMeasures

A contribution measure takes as input an argumentation framework (an argumentation graph and a semantics, which evaluates the arguments of the graph), and assigns to each attack in the graph a value between 0 and 1. This value represents the contribution of the attack to the loss undergone by its target. In other words, for each attacked argument in the graph, the measure divides the total loss of the argument among the attacks received by the argument.

Definition 8 (ContributionMeasure) A contribution measure is a function C on Sem × AG such that, ∀S ∈ Sem, ∀A = 〈A,w,R〉 ∈ AG, C(S,A) is a weighting f on R satisfying the following condition: ∀a ∈ A such that AttA(a) ̸= ∅,

f(r) is called the contribution of r to the loss of Tr(r). Let CtrS,A C (r) denote f(r), i.e. the image of r by C(S,A).

Equation 1 provides an efficiency condition, which ensures that the entire loss of an argument is divided among the argument's attacks. This leads to the following obvious property.

Property 3 For any S ∈ Sem, any A = 〈A,w,R〉 ∈ AG, any contribution measure C on (S, A), any a ∈ A such that AttA(a) ̸= ∅, the following two properties hold:

• If AttA(a) = {r}, then CtrS,A C (r) = LossAS (a).
• If LossAS (a) = 0, then ∀r ∈ AttA(a), CtrS,A C (r) = 0.

In addition to the efficiency condition, the division of a loss should be both reasonable and fair. In what follows, we define properties (called axioms in the paper) that describe what a reasonable and fair measure is.

The first axiom guarantees syntax-independence. It states that the identities of arguments cannot change the outcome of a contribution measure.

Axiom 1 (Anonymity) A contribution measure C satisfies anonymity iff, ∀S ∈ Sem, ∀A = 〈A,w,R〉 ∈ AG and ∀A′ = 〈A′ ,w′ ,R′ 〉 ∈ AG, for any isomorphism f from A to A′ , it holds that ∀ r ∈ R,

A fair division of an argument's loss among the argument's attacks should take into account the effective impact of each attack. The second axiom concerns worthless attacks. It states that if an attack is not harmful to its target, then its contribution should be 0. An important question then is: what is a worthless, called here dummy, attack? A possible definition is: an attack whose source has an acceptability degree 0. Consider the following example.

Example 1 Consider the semantics S1 defined as follows: for any argumentation graph A = 〈A, w, R〉, for any a ∈ A,

.

This semantics is clearly syntax-independent and monotone, thus it belongs to the set Sem. Consider now the argumentation graph A1 = 〈A1,w1,R1〉, where A1 = {a, b}, R1 = {(b, a)}, w1(a) = 1 and w1(b) = 0. Clearly, DegA1 S1 (a) = 0. Thus, LossA1 S1 (a) = 1 meaning that a loses all its basic strength. This loss is due to the attack from b even if DegA1 S1 (b) = 0 (since AttA1 (b) = ∅ and w1(b) = 0). Hence, (b, a) is certainly not a dummy attack.

It is worth noticing that a contribution measure should be rational whatever its input. Namely, it should be able to perform fair division whatever the semantics that is considered, even very basic ones like S1. From the example, it follows that the above definition of dummy attack is not suitable for semantics S1, and more generally for semantics that do not take into account the acceptability degrees of attackers. We will see in Section 6 that it is not suitable for some extension semantics as well. To sum up, a good definition of dummy attack should be independent of acceptability degrees of arguments. A natural candidate is a definition that is based on the marginal contributions of attacks. The marginal contribution of an attack is the difference between the loss undergone by the target and the loss of the target when the attack is removed from the argumentation graph. A dummy attack is an attack whose marginal contribution is 0. Let us illustrate this idea with an example.

Example 1 (Cont) Recall that LossA1 S1 (a) = 1. Consider the argumentation graph A′1 = A1 ⊖ {(b, a)}. In A′1 , a is not attacked, then DegA′1 S1 (a) = 1 and LossA′1 S1 (a) = 0. The attack (b, a) is not dummy since LossA1 S1 (a) - LossA′1 S1 (a) ̸= 0.

Unfortunately, this new definition is still not fully satisfactory as shown in the following example.

Example 2 Consider the argumentation graph A2 depicted below, where each argument has the basic strength 1.

Let r1 = (a1, a) and r2 = (a2, a). Consider stable semantics (st) proposed by Dung [1995]. The graph A2 has one stable extension {a1, a2}. Thus, DegA2 st (a) = 0, and LossA2 st (a) = 1. In order to check whether r1 is a dummy attack of a, we consider the graph A′2 = A2 ⊖{r1}. Clearly, DegA′2 st (a) = 0 (since A′2 has one stable extension {a1, a2}) and LossA′2 st (a) = 1. Note that LossA2 st (a) = LossA′2 st (a). Thus, r1 is a dummy attack, and for any contribution measure C, Ctr st,A2 C (r1) = 0. However, it is easy to check that r2 is also dummy, and its contribution is 0. This violates the efficiency condition of Equation 1. Indeed, Ctr st,A2 C (r1) + Ctr st,A2 C (r2) = 0 while Loss st A2 (a) = 1. Furthermore, this is not intuitive since the argument a has lost its entire basic strength because of its two attackers.

In order to avoid the previous problems, we propose to check the marginal contribution of an attack in the initial graph as well as in all sub-graphs of the initial graph where some target's attacks are removed.

Axiom 2 (Dummy) A contribution measure satisfies dummy iff, ∀S ∈ Sem, ∀A = 〈A,w,R〉 ∈ AG, ∀a ∈ A s.t. AttA(a) ̸= ∅, ∀r ∈ AttA(a), if ∀X ⊆ AttA(a) \ {r}, LossA⊖X S (a) = LossA⊖(X∪{r}) S (a), then CtrS,A C (r) = 0. We say that r is a dummy attack.

Example 2 (Cont) Even if one of the two attacks is sufficient to kill the argument a, none of them is dummy. Let us analyze r1 (the same reasoning holds for r2). We should check any X ⊆ AttA(a) \ {r1} = {r2}. There are two cases:

• X = ∅: LossA2⊖X st (a) = 1, LossA2⊖(X∪{r1}) st (a) = 1.

Note that when X = {r2}, the argument a is not attacked in the graph A2 ⊖ (X ∪ {r1}), and it is attacked only by a1 in the graph A2 ⊖X. Thus, r1 taken alone is harmful for a.

We show that a dummy attack cannot weaken its target even when it is the only attack received by its target.

Proposition 2 Let C be a contribution measure, which satisfies Dummy. For any semantics S ∈ Sem, any argumentation graph A = 〈A,w,R〉 ∈ AG, any a ∈ A s.t. AttA(a) ̸= ∅, any r ∈ AttA(a), if r is dummy, then DegA′ S (a) = w(a) and LossA′ S (a) = 0, with A′ = A⊖ (AttA(a) \ {r}).

The next axiom defines when two attacks targeting the same argument should receive the same contribution. Such attacks are said to be symmetric. One might think that two attacks are symmetric if their sources have the same acceptability degree. However, the following example shows that this definition may lead to an unfair division of the loss.

Example 3 Consider the argumentation graph A3 depicted below, where each argument has a basic strength equal to 1.

Under preferred semantics, pr, the empty set is the sole extension of A3. Thus, the four arguments get the same acceptability degree 0.3 (DegA3 pr (.) = 0.3). Consequently, LossA3 pr (a) = 0.7. Since the two attackers (a1 and a2) of a have the same degree, the previous definition declares their attacks as symmetric and assigns to them the same contribution (0.35 each). However, this division is unfair. Consider the two argumentation graphs A′3 = A3 ⊖ {(a1, a)} and A′′ 3 = A3 ⊖ {(a2, a)}. It is easy to check that A′3 has one preferred extension, {a, a1}. Thus, DegA′3 pr (a) = 1, LossA′3 pr (a) = 0, and the marginal contribution of the attack (a1, a) is 0.7. However, the sole preferred extension of A′′ 3 is the empty set. Hence, DegA′′ 3 pr (a) = 0.3, LossA′3 pr (a) = 0.7, and the marginal contribution of the attack (a2, a) is 0. This shows that the two attacks do not have the same impact on a.

The previous example suggests that the notion of symmetric attacks should not be defined on the basis of acceptability degrees, but rather be based on the comparison of the marginal contributions of the two attacks. However, like with dummy, the marginal contributions in the initial graph may lead to unfair divisions as shown by the following example.

Example 4 Consider the argumentation graph A4 depicted below, where each argument has a basic strength equal to 1.

Consider stable semantics st. The graph A4 has two stable extensions {a1, a2, a3} and {a1, a2, a4}. Thus, DegA4 st (a) = 0 and LossA4 st (a) = 1.

Let A4i = A4 ⊖ {(ai, a)}, with i ∈ {1, 2, 3}. For any i ̸= j, LossA4i st (a) = LossA4j st (a). Hence, the three attacks on a are symmetric, and get the same contribution ( 13 ). While (a1, a) and (a2, a) are clearly symmetric, this is not the case for (a1, a) (respectively (a2, a)) and (a3, a). Indeed, (a1, a) alone leads to a loss of 1 for a, while (a3, a) alone (i.e., in graph A4 ⊖ {(a1, a), (a2, a)}) leads only to a loss of 0.5.

Symmetric attacks should then be defined by comparing the marginal contributions of those attacks in all the possible graphs where subsets of the target's attacks are removed.

Axiom 3 (Symmetry) A contribution measure C satisfies symmetry iff, ∀S ∈ Sem, ∀A = 〈A,w,R〉 ∈ AG, ∀a ∈ A with |AttA(a)| ≥ 2, ∀ri, rj ∈ AttA(a) with ri ̸= rj, if ∀X ⊆ AttA(a) \ {ri, rj}, LossA⊖(X∪{ri}) S (a) = LossA⊖(X∪{rj }) S (a), then CtrS,A C (ri) = CtrS,A C (rj). We say that the two attacks ri and rj are symmetric.

Example 4 (Cont) Under stable semantics, a contribution measure satisfying symmetry declares the two attacks (a1, a), (a2, a) symmetric, and both are not symmetric with (a3, a).

A fair division of an argument's loss among attacks should take into account the power of each attack. In A4, the attack (a3, a) is less harmful than both (a1, a) and (a2, a). Thus, the former should receive a lower part than the latter. The next axiomcaptures this idea. It states that the greater themarginal contribution of an attack, the greater its contribution.

Axiom 4 (Dominance) A contribution measure C satisfies dominance iff, ∀S ∈ Sem, ∀A = 〈A,w,R〉 ∈ AG, ∀a ∈ A with |AttA(a)| ≥ 2, ∀ri, rj ∈ AttA(a) with ri ̸= rj , if

• ∃X ⊆ AttA(a) \ {ri, rj} such that LossA⊖(X∪{ri}) S (a) > LossA⊖(X∪{rj}) S (a), and

All the previous axioms assume a fixed semantics, and discuss how weights are assigned to attacks under that semantics. The last axiom shows how those weights may vary from one semantics to another. It states that if the marginal contribution of an attack is the same under two different semantics, then it will receive the same contribution in both cases. This axiom ensures that the contribution of an attack depends solely on its marginal contribution to the loss of its target. This prevents measures from taking into account features of semantics like its name, whether it is extensionbased, whether it is binary (i.e., it allows two degrees), etc.

Axiom 5 (Coherence) A contribution measure C satisfies coherence iff, ∀S, S′ ∈ Sem, ∀A = 〈A, w, R〉 ∈ AG, ∀a ∈ A with AttA(a) ̸= ∅, ∀r ∈ AttA(a), if ∀X ⊆ AttA(a) \ {r}, LossA⊖X S (a) - LossA⊖(X∪{r}) S (a) = LossA⊖X S′ (a) - LossA⊖(X∪{r}) S′ (a), then CtrS,A C (r) = CtrS′ ,A C (r).

Example 2 (Cont) Consider the argumentation graph A2. Any contribution measure satisfying the axiom of Coherence assigns the same value to r1 (respectively r2) under stable, grounded, complete, and preferred semantics [Dung, 1995].

The five axioms are not fully independent. Indeed, Anonymity, Dummy and Dominance follow from the two other axioms (i.e., from Coherence and Symmetry).

Proposition 3 Let C be a contribution measure.

• If C satisfies Coherence, then C satisfies Dummy.
• If C satisfies Coherence and Symmetry, then C satisfies Anonymity and Dominance.

Coherence and Symmetry are however independent, i.e., none of them is implied by the other.

Proposition 4 Symmetry and Coherence are independent.

Hopefully, the five axioms are compatible, i.e., they can all be satisfied by a given contribution measure.

Proposition 5 Symmetry and Coherence are compatible.

From propositions 3 and 5, it follows that the five axioms are compatible.

5 Shapley ContributionMeasure

The previous section introduced the notion of contribution measure, and five axioms that fair and reasonable measures should satisfy. The following questions raise then naturally:

• Existence: is there a measure which satisfies the axioms?
• Uniqueness: if yes, is it unique?

Hopefully, the answers to both questions are positive. Before presenting the formal results, let us start by introducing the key function Sh, called Shapley measure in the paper.

Definition 9 (Sh) Sh is the function on Sem × AG such that ∀S ∈ Sem, ∀A = 〈A,w,R〉 ∈ AG, Sh(S,A) is the function s from R to R defined as follows: ∀r = (b, a) ∈ R,

The function Sh assigns a real value to each attack, which is the weighted sum of its marginal contributions to the global loss of the targeted argument. It is easy to show that the previous definition of Sh is equivalent to the following one.

Theorem 1 Let S ∈ Sem, A = 〈A,w,R〉 ∈ AG, and s = Sh(S,A). It holds that ∀(b, a) ∈ R,

It is worth noticing that Sh(S,A) is the well-known Shapley value, proposed as a solution for transferable utility games (TU games) by Shapley [1953]. A TU game is a set of agents and a real-valued characteristic function assigning a value to each subset of agents. Each subset is a coalition and its value represents how much the coalition can get for itself. The key problem is then, how the agents of the game divide the value of the grand coalition (the one made of all agents). Shapley value provides a unique division for each game.

In an argumentation context, each pair (S,A), with A = 〈A,w,R〉, can be seen as a set of TU games (one per argument in A). The agents of the game corresponding to an argument a ∈ A are the attacks on a, and the characteristic function is Loss. The latter evaluates the loss of a under semantics S when a is attacked by any subset of its attackers. Those subsets play the role of coalitions.

Shapley characterized his value with axioms, one of which is additivity. The latter shows how different games can be combined. Despite the relationship between a contribution measure and TU games, Additivity has no counter-part in the previous section since it does not make sense in the argumentation context. Shubik [1962] has shown, however, that symmetry follows from Shapley's axiom of anonymity. Note that the latter is based on permutations in the roles of agents, and thus is different from our Anonymity axiom.

We show next that Sh is a contribution measure. Indeed, it assigns a value in the interval [0, 1] to each attack. Furthermore, it satisfies the efficiency condition of Definition 8.

Theorem 2 Sh is a contribution measure.

Let us illustrate this measure on the running examples.

Example 1 (Cont) In the graph A1, CtrS1,A1 Sh ((b, a)) = 1.

Example 2 (Cont) In the graph A2, Ctrx,A2 Sh (r1) = Ctrx,A2 Sh (r2) = 1 2 for x ∈ {gr, co, pr, co}. Consider now h-categorizer semantics. DegA2 h (a) = 1 3 , and thus LossA2 h (a) = 23 . So, Ctrh,A2 Sh (r1) = Ctrh,A2 Sh (r2) = 13 .

Example 3 (Cont) In the graph A3, Ctr pr,A3 Sh ((a1, a)) = 0.7, Ctr pr,A3 Sh ((a2, a)) = 0. Note that (a2, a) is a dummy attack under preferred semantics. However, as we will see in the next section, it is not dummy under h-categorizer semantics.

Example 4 (Cont) In the graph A4, Ctrx,A4 Sh ((a1, a)) = Ctrx,A4 Sh ((a2, a)) = 5 12 and Ctrx,A4 Sh ((a3, a)) = 16 , where x ∈ {pr, st}. The two first attacks are more harmful than (a3, a).

The following result is of great importance since it positively answers the two questions on the existence and uniqueness of a contribution measure that satisfies the axioms. Indeed, it provides a characterization, which states that not only Sh satisfies the axioms (existence), but also it is the unique contribution measure that satisfies them.

Theorem 3 A contribution measure C satisfies the two axioms of Symmetry and Coherence if and only if C = Sh.

From the previous result and the links between the five axioms, it follows that Sh satisfies the five axioms.

6 Properties Related to Semantics

Shapley measure Sh can be applied to any semantics in Sem. We show that the contributions it assigns to attacks respect however, properties of the underlying semantics. For that purpose, we consider the semantics defined in Section 3, a given argumentation graph A = 〈A,w,R〉, and a ∈ A such that AttA(a) ̸= ∅. Let AttA(a) = {r1, . . . , rn} and Sc(ri) = ai. Hence, the attackers of a are {a1, . . . , an}. We focus on the following properties: For any i, j ∈ {1, . . . , n},

(P1) states that there is no dummy attack. (P2) follows from (P1) and ensures that each serious attacker contributes to the loss of a. (P3) ensures that killed attackers do not contribute to the loss of their target. The two last properties state that the order between acceptability degrees is preserved.

Proposition 6 Table 1 resumes the properties that are satisfied/violated by the semantics introduced in Section 3.

The results show that under h-Categorizer semantics, there is no dummy attack. They also confirm the necessity of defining contribution measures on the basis of marginal contributions of attackers rather than on their acceptability degrees.

7 Conclusion

The paper introduced a novel concept, contribution measure, which evaluates the intensity of each attack in an argumentation graph. It followed an axiomatic approach. Indeed, it defined axioms that characterize reasonable measures. Then, it showed that there is a unique measure which satisfies them, and it is the well-known Shapley value.

Future work consists of investigating the properties of Shapley measure under semantics like the ones proposed in [Dung et al., 2007; Grossi and Modgil, 2015; Gabbay and Rodrigues, 2015; da Costa Pereira et al., 2011], those proposed in probabilistic argumentation settings [Hunter, 2013; Li et al., 2011], or in weighted argumentation graphs, i.e., graphs where attacks are assigned weights (see [Cayrol et al., 2010; Dunne et al., 2011; 2010]).

Acknowledgments

This work was supported by ANR-13-BS02-0004 and ANR11-LABX-0040-CIMI.