You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

A parametrized ranking-based semantics compatible with persuasion principles

Abstract

In this work, we question the ability of existing ranking-based semantics to capture persuasion settings, emphasising in particular the phenomena of procatalepsis (the fact that it is often efficient to anticipate the counter-arguments of the audience) and of fading (the fact that long lines of argumentation become ineffective). Some widely accepted principles of ranking-based semantics (like Void Precedence) are incompatible with a faithful treatment of these phenomena, which means that no existing ranking-based semantics can capture these two principles together. This motivates us to introduce a new parametrized ranking-based semantics based on the notion of propagation which extends the existing propagation semantics (In Proceedings of the 6th International Conference on Computational Models of Argument (COMMA’16) (2016) 139–150) by adding an additional parameter allowing us to gradually decrease the impact of arguments when the length of the path between two arguments increases. We show that this parameter gives the possibility of choosing if one wants to satisfy the property Void Precedence or not (and then capture procatalepsis) and to control the scope of the impact of the arguments (and then to capture fading principle). We also propose an experiment to show that the new semantics remains stable when this parameter varies and an axiomatic evaluation to compare it with existing ranking-based semantics in the literature.

1.Introduction

Expressing our opinions is common in our social worlds: from politics (in political debates), law (defense attorney vs. prosecutor), academia (debates between authors and reviewers), business (convincing others to buy a product) to our personal lives. In being as much at the heart of human reasoning and interactions, it is not surprising to find much research related to argumentation in disciplines such as psychology, linguistics or philosophy. However, argumentation is also by now an acknowledged branch of one of the main subfields of artificial intelligence (AI), namely knowledge representation and reasoning (KR), that is particularly concerned with reasoning with incomplete, uncertain and conflicting information. It is widely used in areas such as multi-agent systems, common-sense reasoning, and decision making. Argumentation, in the field of artificial intelligence, is a reasoning model based on the construction and evaluation of arguments [29].

The arguments and the conflicts between arguments involved in the argumentation process can be represented with an argumentation framework. In this work, we focus on the one proposed in [15] which is very abstract in order to grasp the characteristics of many other argumentation frameworks. An abstract argumentation framework is a set of abstract entities, called arguments, representing any piece of information (e.g. beliefs, statements or actions to be performed), linked with some attacks, which indicate the existence of conflicts between the arguments. Thus, an argumentation framework is often represented by a directed graph, in which nodes represent arguments and arrows represent the attack relation between arguments.

Once the argumentation framework is built (from a knowledge base [6] or from textual data [12,23]), the next goal concerns the evaluation of the arguments on the basis of their interaction. For this evaluation part, many methods, called semantics, have been introduced in the literature. Extension-based semantics (complete, grounded, preferred and stable) are the first family of semantics to be proposed in Dung’s seminal paper [15]. Their main task is to find sets of arguments which can be jointly considered as accepted. Sharing the view that identifying sets of mutually acceptable arguments is not sufficient for some applications (see [11,22] for more details), gradual (assigning a value to each argument) [6,14,22,24] or ranking-based (returning a ranking between arguments) [2,3,8,13,16,27,28] semantics have been proposed. Each of these proposals has some merit, and nicely designed examples convince indeed that, in some situations at least, they should be the method of choice.

When it comes to comparing these approaches (beyond their formal properties like convergence or uniqueness of solution), things become difficult. This is so because the basis of comparison is not so clear in the first place, with different proposals focusing on different properties. In [4,9], many existing semantics were compared on the basis of properties for ranking-based semantics mentioned in the literature. However, even the relevance of some axioms may be very much dependent on the context. This corroborates, to a certain extent, one of the aspects addressed by Prakken and De Winter [25] concerning the danger of abstracting from the context that gave rise to an argumentation framework. What is often missing to compare these approaches is thus a clear indication of applications (or contexts) they target. Is a given semantics appropriate for finding a “good” solution to a problem of decision making? Of negotiation? Of persuasion? All of these problems? We claim that even though a semantics satisfies interesting properties in theory, it does not necessarily mean that this semantics can be used to solve any kind of problem. In this work, we choose to focus on the context of persuasion to substantiate this claim. Persuasion is an activity that involves one party (the persuader) trying to induce another party (the persuadee) to believe (or not believe) certain information or to do (or not do) some action.

Among the different approaches used in persuasion, some well documented principles question some properties widely satisfied by existing ranking-based semantics: procatalepsis and fading.

∙ The procatalepsis principle aims to strengthen an argument by dealing with possible counter-arguments before their audience can raise them. To illustrate this principle, we extend an example from [7, p.85]: a (fictional) sales pitch intended to persuade someone to buy a specific car. The representation of this example as an argumentation framework is depicted in Fig. 1.

  • (a1) The car x is a high performance family car with a diesel engine and a price of 32000

  • (a2) In general, diesel engines have inferior performance compared with gasoline engines

  • (a3) But, with these new engines, the difference in performance [...] is negligible

  • (a4) In addition, even though the price of the car seems high

  • (a5) It will be amortized because the diesel engines run longer before breaking than any other kind of engine.

The seller’s objective is here to increase the acceptability of a1. For this purpose, he anticipates two arguments a2 and a4 (which could have been proposed by the customer later in the discussion) by providing two counter-arguments a3 and a5 which attack a2 and a4 respectively. According to the procatalepsis principle, it is more convincing to state the more plausible counter-arguments to a1 in order to provide some convincing defenses against them, than simply state a1 alone. A ranking-based semantics can then be used to check whether the ranking of a1 is better than the one obtained when a1 is alone (i.e. non-attacked). However, this principle contradicts the so-called property of Void Precedence (which is satisfied by all existing ranking-based semantics [9]), considering that a non-attacked argument should be strictly more acceptable than an attacked argument. While this property is considered as mandatory in [2], Void Precedence is also called into question in [7,31], arguing that arguments which are not attacked can be seen as arguments which have not yet proven their strength against counter-arguments. It seems that this question relates to the status of the missing information in argumentation frameworks. If all the information is available, then “truly non-attacked” arguments should be better that any attacked argument. However there are cases (e.g. during a debate or a discussion) where the argumentation frameworks encode the information currently available, and that is susceptible to be completed. This is this case that we consider here with the procatalepsis principle.

Fig. 1.

Argumentation framework illustrating a (fictional) sales pitch using the procatalepsis principle.

Argumentation framework illustrating a (fictional) sales pitch using the procatalepsis principle.

∙ The fading effect states that long lines of argumentation become ineffective in practice, because the audience easily loses track of the relation between the arguments. This principle is supported in practice by the work of Tan et al. [30] which shows (in the context of their study, an extensive analysis of persuasive debates which took place on the subreddit “ChangeMyView”1), that arguments located at a distance greater than 10 from another argument (i.e., 5 rounds of back-and-forth), have no impact in the debate. While some ranking-based semantics (e.g. [28]) incorporate features which can be used to discount the strength of arguments relatively to their distance, this is not the case of all semantics.

These elements show that current ranking-based semantics are poorly equipped to be used in a context of persuasion. Our contribution is a new ranking-based semantics which is able to account for these phenomena. More precisely, this semantics is based on the notion of propagation and extends the existing propagation semantics [8] by adding an additional parameter whose purpose is to gradually decrease the impact of arguments when the length of the path between two arguments increases. Most importantly, this parameter makes it possible to regulate how these principles are satisfied. In general, this contribution could thus be used as an ingredient for developing strategies for computational persuasion techniques [18].

After a refresher on abstract argumentation and on the ranking-based semantics in Section 2, we introduce, in Section 3, the two principles commonly used in persuasion (procatalepsis and fading) and explain why the existing ranking-based semantics are not able to capture these principles. Section 4.1 presents the basic principle of propagation on which our proposal, detailed in Section 4.2, is built. This new semantics uses two parameters and we show, in Section 5, that one of these parameters allows us to control the convergence speed, the score of influence of the arguments and it gives the opportunity to satisfy or not satisfy the procatalepsis principle. Finally, in Section 6, we provide an axiomatic evaluation of our new ranking-based semantics for the different values of this parameter and we compare the set of satisfied properties with the set of properties satisfied by existing ranking-based semantics in the literature.

This paper is a substantial development of the initial work presented in [10] in the sense that motivation, discussion, examples and analysis have been extended or added. More precisely, it extends this previous work as follows: additional properties for ranking-based semantics have been included, illustrated and formally defined in Section 2; a formal definition of the procatalepsis principle has been added in Section 3 to formally demonstrate its incompatibility with the Void Precedence (VP) property; the study of the influence of the parameters provided in Section 5 is expanded; the set of existing ranking-based semantics has been extended in Section 6 in order to compare axiomatically our semantics with all of them; all proofs together with the associated counter-examples have been included in the Appendix.

2.Preliminaries

2.1.Dung’s framework

In his seminal work [15], Dung formalizes argumentation through an abstract argumentation framework in which there is no assumption on the nature of the elements it contains. More precisely, neither the structure nor the origin of the arguments are required. Then, an argumentation framework is composed of a set of abstract arguments and of a relation of conflict between them.

Definition 2.1

Definition 2.1(Argumentation framework).

An (abstract) argumentation framework (AF) is a pair AF=A,R where A is a finite and non-empty set of (abstract) arguments and R is a binary relation on A, i.e. RA×A, called the attack relation. For two arguments x,yA, the notation (x,y)R means that x attacks y. We note Arg(AF)=A and AF represents the set of all argumentation frameworks.

From a mathematical point of view, an argumentation framework is a directed graph where a node represents one argument and an arrow between two nodes represents an attack from an argument to another one. Let us introduce different notions related to the graphs that we will use in this article.

Definition 2.2

Definition 2.2(Path).

Let AF=A,R be an argumentation framework and x,yA be two arguments. A sequence x0,,xn of arguments in A is a path of size n (the number of attacks it is composed of) from y to x if and only if x0=x, xn=y and for every i{0,1,,n1}, (xi+1,xi)R.

According to the length of a path between two arguments, the argument at the beginning of this path can be an attacker or a defender of the argument at the end of the path.

Definition 2.3

Definition 2.3(Attacker, Defender).

Let AF=A,R be an argumentation framework and x,yA be two arguments. Let Rn(x) be the set of arguments that are bound by a path of length n to the argument x. Thus, an argument yRn(x) is a direct attacker of x if n=1, a direct defender of x if n=2, an attacker of x if n is odd or/and a defender of x if n is even. Let us note R+(x)=n2NRn(x) and R(x)=n2N+1Rn(x) the set of all the defenders and all the attackers of x respectively.

A branch is a path such that the argument at the beginning of the path is not attacked.

Definition 2.4

Definition 2.4(Branch, Root).

Let AF=A,R be an argumentation framework and x,yA be two arguments. A defense root (respectively attack root) of x is a defender (respectively attacker) of x which is not attacked. Let Bn(x)={yRn(x)|R1(y)=} be the set of roots that are bound by a path of length n to the argument x. A path from y to x is a defense branch (respectively attack branch) for x if y is a defense root (respectively attack root) of x. Let us note B+(x)=n2NBn(x) and B(x)=n2N+1Bn(x) the set of all defense roots and all the attack roots of x respectively. A cycle is a path from x to x and a loop is a cycle of length 1.

The ancestors’ graph of an argument x is a subgraph of an argumentation framework, that contains x and its the attackers and defenders, as well as all the attack relations between these arguments.

Definition 2.5

Definition 2.5(Ancestors’ graph).

Let AF=A,R be an argumentation framework and xA. The ancestors’ graph of x is denoted by AncAF(x)=A,R with A={x}R+(x)R(x) and R={(x1,x2)R|x1Aandx2A}.

Example 2.1.

Fig. 2.

An argumentation framework.

An argumentation framework.

On the argumentation framework represented in Fig. 2, one can find:

  • a path of length 2 c2,b1,a from c2 to a whereas b1,a,b2 is not a path,

  • a cycle a1,a2,a3,a1 of length 3,

  • d2,d2 is a loop,

  • c1 and d1 are the attack roots of a,

  • c1 and c2 are the defense roots of a,

  • c1,a is an attack branch for a of length 1, d1,c3,b2,a is an attack branch for a of length 3,

  • d1,c3,b2, c1,a,a1 and c2,b1,a are three possible defense branches of length 2,

  • b1, b2 and c1 are the direct attackers of a,

  • c1, c2 and c3 are the direct defenders of a,

  • The argumentation framework AF, represented in the blue rectangle, is the ancestors’ graph of a.

2.2.Semantics and properties

Dung’s framework comes equipped with various types of semantics used to evaluate the arguments. Among these semantics, the ranking-based semantics aiming to rank-order a set of arguments in an argumentation framework from the most to the least acceptable. Thus, unlike classical semantics which assign an absolute status (accepted, rejected, undecided) to each argument, this semantics compares pairs of arguments. We refer the reader to [1,11] for a complete overview of the existing families of semantics in abstract argumentation and for the differences between these approaches (e.g., definitions, outcomes, applications).

Definition 2.6

Definition 2.6(Ranking-based semantics).

A ranking-based semantics σ associates to any argumentation framework AF=A,R a ranking AFσ on A, where AFσ is a preorder (a reflexive and transitive relation) on A. xAFσy means that x is at least as acceptable as y; xAFσy (shortcut for xAFσy and yAFσx) means that x and y are equally acceptable; xAFσy (shortcut for xAFσy and yAFσx) means that x is strictly more acceptable than y; xAFσy and yAFσx means that x and y are incomparable. We denote by σ(AF) the ranking on A returned by σ.

Many ranking-based semantics with different behaviors have been introduced in recent years [2,3,8,13,16,27,28]. These semantics have often been defined along with a set of properties, each of which represents a specific criterion (e.g. quantity or quality of the direct attackers of an argument), aiming to highlight the unique behaviour of the proposed semantics [2,13,24]. Bonzon et al. [9] grouped these properties, generalized and defined new ones in order to propose an axiomatic comparison of existing semantics. Note, however, that none of these properties are mandatory. Indeed, some of these properties are not independent of each other because incompatibilities and dependencies can exist between them [5,9]. These properties are therefore an excellent indication to better understand the behavior of these semantics and remain the only way to compare existing ranking-based semantics with new ones. They are also a first step to the ambitious research question of defining fully characterized classes of ranking-based semantics with respect to a subset of properties.

2.2.1.General properties

Let us begin with two general properties. First, it seems natural that the ranking on the set of abstract arguments should be defined only on the basis of the attacks between arguments and should not depend on the identity of the arguments.

Definition 2.7

Definition 2.7(Isomorphism).

An isomorphism γ between two argumentation frameworks AF=A,R and AF=A,R is a bijective function γ:AA such that x,yA, (x,y)R if and only if (γ(x),γ(y))R. With a slight abuse of notation, we will note AF=γ(AF).

The property Abstraction states that if there exists an isomorphism between two argumentation frameworks, then they should have the same ranking for a given ranking-based semantics.

Property 1

Property 1(Abstraction (Abs) [2]).

A ranking-based semantics σ satisfies Abstraction if and only if for any AF,AFAF, for every isomorphism γ such that AF=γ(AF), we have xAFσy if and only if γ(x)AFσγ(y).

The next property, called Independence, considers that the ranking between two arguments x and y should be independent of any argument that is neither connected to x nor to y. In other words, if the graph which represents the argumentation framework is composed of several disconnected subgraphs then the arguments in a subgraph have no influence on the arguments in another subgraph. The set of such subgraphs is called connected components.

Definition 2.8

Definition 2.8(Connected components).

The connected components of an argumentation framework AF are the set of largest subgraphs of AF, denoted by cc(AF), where two arguments are in the same component of AF if and only if there exists some path (ignoring the direction of the edges) between them.

Property 2

Property 2(Independence (In) [2,24]).

A ranking-based semantics σ satisfies Independence if and only if for any argumentation framework AF such that AFcc(AF), x,yArg(AF), xAFσy if and only if xAFσy.

The purpose of the Total property is to distinguish between semantics that return a total preorder and those that return a partial preorder between arguments.

Property 3

Property 3(Total (Tot) [9]).

A ranking-based semantics σ satisfies Total if and only if for any AF=A,R and x,yA, xAFσy or yAFσx.

2.2.2.Best and worst arguments

We may have expectations regarding the best and worst arguments that we may find in an argumentation framework.

Void Precedence states that a non-attacked argument should be strictly more acceptable than an attacked argument.

Property 4

Property 4(Void Precedence (VP) [2,24]).

A ranking-based semantics σ satisfies Void Precedence if and only if for any AF=A,R and x,yA, if R1(x)= and R1(y) then xAFσy.

Self-Contradiction states that an argument that attack itself should be strictly less acceptable than an argument that does not attack itself.

Property 5

Property 5(Self-Contradiction (SC) [24]).

A ranking-based semantics σ satisfies Self-Contradiction if and only if for any AF=A,R and x,yA, if (x,x)R and (y,y)R then xAFσy.

2.2.3.Direct attackers

Two criteria often used by the existing ranking-based semantics to compare arguments are the cardinality and the quality (i.e. level of acceptability) of the direct attackers.

Cardinality Precedence focuses on the cardinality of direct attackers in saying that the greater the number of direct attackers for an argument, the weaker the level of acceptability of this argument.

Property 6

Property 6(Cardinality Precedence (CP) [2]).

A ranking-based semantics σ satisfies Cardinality Precedence if and only if for any AF=A,R and x,yA, if |R1(x)|<|R1(y)| then xAFσy.

Quality Precedence focuses on the quality of direct attackers in saying that the greater the acceptability of the direct attackers for an argument, the weaker the level of acceptability of this argument.

Property 7

Property 7(Quality Precedence (QP) [2]).

A ranking-based semantics σ satisfies Quality Precedence if and only if for any AF=A,R and x,yA, if y1R1(y) such that x1R1(x), y1AFσx1 then xAFσy.

To compare the direct attackers of two arguments, let us introduce a relation that compares sets of arguments on the basis of their rankings.

Definition 2.9

Definition 2.9((Strict) group comparison [2]).

Let AFσ be a ranking on A. For any S1,S2A, S1SσS2 if and only if there exists an injective mapping f from S2 to S1 such that aS2,f(a)AFσa. Likewise S1>SσS2 if and only if S1SσS2 and (|S2|<|S1| or aS2,f(a)AFσa).

Counter-Transitivity states that if the direct attackers of y are at least as numerous and acceptable as those of x with respect to a ranking-based semantics σ, then x should be at least as acceptable as y.

Property 8

Property 8(Counter-Transitivity (CT) [2]).

A ranking-based semantics σ satisfies Counter-Transitivity if and only if for any AF=A,R and x,yA, if R1(y)SσR1(x) then xAFσy.

Strict Counter-Transitivity, states that if the conditions in the definition of Counter-Transitivity are satisfied and either the direct attackers of y are strictly more numerous or acceptable than those of x, then x should be strictly more acceptable than y.

Property 9

Property 9(Strict Counter-Transitivity (SCT) [2]).

A ranking-based semantics σ satisfies Strict Counter-Transitivity if and only if for any AF=A,R and x,yA, if R1(y)>SσR1(x) then xσy.

2.2.4.Direct defenders

Defense Precedence states that, when two arguments have the same number of direct attackers, an argument with at least one direct defender should be strictly more acceptable than an argument without any direct defender.

Property 10

Property 10(Defense Precedence (DP) [2]).

A ranking-based semantics σ satisfies Defense Precedence if and only if for any AF=A,R and x,yA such that |R1(x)|=|R1(y)|, if R2(x) and R2(y)= then xAFσy.

When DP says that it is better for an argument to be defended, it could be interesting to know if different kinds of defense of an argument have the same impact on it. Two kinds of defense of an argument are then defined: the simple defense and the distributed defense.

Definition 2.10

Definition 2.10(Simple defense and distributed defense [2]).

Let AF=A,R be an argumentation framework and xA. The defense of x is simple if and only if every direct defender of x directly attacks exactly one direct attacker of x (i.e. when |R1(x)|=1 because, by definition, there is only one direct attacker which can be attacked, or y,zR1(x), R1(y)R1(z)=). The defense of x is distributed if and only if every direct attacker of x is attacked by at most one argument (i.e. yR1(x), R1(y)= or !zR2(x) such that (z,y)R).

Distributed-Defense Precedence states that if two arguments have the same number of direct attackers and the same number of direct defenders, then it is preferable for an argument that each of its defender attacks a distinct direct attacker in order to weaken all of them instead of focusing on a specific direct attacker so as to greatly weaken it (but at the price of leaving its others attackers unaffected).

Property 11

Property 11(Distributed-Defense Precedence (DDP) [2]).

A ranking-based semantics σ satisfies Distributed-Defense Precedence if and only if for any AF=A,R and x,yA such that |R1(x)|=|R1(y)| and |R2(x)|=|R2(y)|, if the defense of x is simple and distributed and the defense of y is simple but not distributed, then xAFσy.

Example 2.2.

Consider the two argumentation frameworks illustrated in Fig. 3.

Fig. 3.

Distributed-defense precedence.

Distributed-defense precedence.

The two arguments a and b have the same number of direct attackers (R1(a)={a1,a3} and R1(b)={b1,b4}) and the same number of direct defenders (R2(a)={a2,a4} and R2(b)={b2,b3}). The defense of a is simple because R1(a1)R1(a3)={a2}{a4}= and distributed because a1 and a3 are attacked by exactly one argument (a2 and a4 respectively). Concerning b, its defense is also simple (R1(b1)R1(b4)={b2,b3}=) but not distributed because b1 is directly attacked by two arguments (b2 and b3). Thus, the property DDP ensures that a is more acceptable than b.

The property Attack vs Full Defense allows us to make a distinction between the semantics which consider that a defense just cancels the effect of an attack (which can thus have the consequence of maintaining or increasing the acceptability of the targeted argument) and those which consider a defense as a weak attack (the impact of the attack is less important but it still has a negative effect on the targeted argument). Thus, an argument without any attack branch should be ranked higher than an argument only attacked by one non-attacked argument.

Property 12

Property 12(Attack vs Full Defense (AvsFD) [9]).

A ranking-based semantics σ satisfies Attack vs Full Defense if and only if for any acyclic AF=A,R and x,yA, if |B(x)|=0, |R1(y)|=1 and |R2(y)|=0 then xAFσy.

2.3.Global properties

“Global” properties specify if some change related to the branches in an argumentation framework can improve or degrade the ranking of one argument. They help answer questions such as: what is the effect on the acceptability of a given argument with an additional attack branch? Is the effect the same if it is a defense branch? Does the length of the branch matter?

Let us first recall how the addition of an attack branch and the addition of a defense branch to an argument are formally defined.

Definition 2.11

Definition 2.11(Attack and defense branch added to an argument).

Let AF=A,R be an argumentation framework and xA be an argument. A defense branch added to x is P+(x)=A,R, with A={x0,,xn} such that n2N, x0=x, AA={x}, and R={(xi,xi1)in}. The attack branch added to x, denoted P(x) is defined similarly except that the sequence is of odd length (i.e. n2N+1).

In order to evaluate the impact of an additional branch on a given argument x of an argumentation framework AF, we “clone” this argumentation framework with an isomorphism γ (see Definition 2.7). Then, the argumentation framework γ(AF) can be modified (by adding one attack or defense branch for example) in order to analyse the impact on γ(x) compared to x. This approach allows us to focus exclusively on the impact of this change.

2.3.1.Addition of a branch

The first property concerns the attack branches and states that adding an attack branch to any argument decreases its level of acceptability.

Property 13

Property 13(Addition of an Attack Branch (+AB) [9]).

A ranking-based semantics σ satisfies Addition of an Attack Branch if and only if for any AF, AF and xArg(AF), for every isomorphism γ such that AF=γ(AF), if AF=AFAFP(γ(x)), then xAFσγ(x).

Example 2.3.

Let us consider the argumentation framework illustrated in Fig. 4. If σ satisfies +AB then a1, which has no attack branch, should be more acceptable than b2, b3, d3 and b4 which have one attack branch. In addition, a2 should be more acceptable than a4 because both have one defense branch with the same length but a4 has also an attack branch while a2 does not.

Fig. 4.

Argumentation framework with different configurations of branches.

Argumentation framework with different configurations of branches.

The two following properties concern the defense branches. The first one states that adding a defense branch to any argument increases its level of acceptability.

Property 14

Property 14(Strict Addition of a Defense Branch (⊕DB) [9]).

A ranking-based semantics σ satisfies Strict Addition of a Defense Branch if and only if for any AF,AFAF and xArg(AF), for every isomorphism γ such that AF=γ(AF), if AF=AFAFP+(γ(x)), then γ(x)AFσx.

Example 2.3

Example 2.3(cont.).

If σ satisfies ⊕DB then a3 should be more acceptable than a2 which should be more acceptable than a1. Indeed, a3 has one more defense branch than a2 which has one more defense branch than a1. In addition, a4, which has one defense branch and one attack branch, should be more acceptable than b2, b3, d3 and b4 which have no defense branch.

Addition of a Defense Branch is defined in a more specific way: adding a defense branch to any attacked argument (therefore excluding non-attacked arguments) increases its level of acceptability.

Property 15

Property 15(Addition of a Defense Branch (+DB) [9]).

A ranking-based semantics σ satisfies Addition of a Defense Branch if and only if for any AF,AFAF and xArg(AF), for every isomorphism γ such that AF=γ(AF), if AF=AFAFP+(γ(x)) and R1(x), then γ(x)AFσx.

Example 2.3

Example 2.3(cont.).

If σ satisfies +DB, the same conclusion as ⊕DB can be done except for a1. Indeed, as a1 is not attacked, nothing can be said about its ranking in comparison with the other arguments with respect to +DB.

2.3.2.Increasing the length of a branch

Two additional properties based on the increase of the length of a branch have been introduced. Let us recall that, for these properties, the “meaning” of the initial branch and the one of the increased branch have to be identical. In other words, if the initial branch is an attack (resp. defense) branch then the increased branch must be an attack (resp. defense) branch too. And, to keep the meaning of a branch, the only solution is to add a defense branch to the argument at the beginning of the branch.

Fig. 5.

Argumentation framework with different lengths of branch.

Argumentation framework with different lengths of branch.

The first property states that increasing the length of an attack branch of an argument increases its level of acceptability.

Property 16

Property 16(Increase of an Attack Branch (↑AB) [9]).

A ranking-based semantics σ satisfies Increase of an Attack Branch if and only if for any AF,AFAF and xArg(AF), for every isomorphism γ such that AF=γ(AF), if yB(x), yB+(x) and AF=AFAFP+(γ(y)), then γ(x)AFσx.

Example 2.4.

Let us consider the argumentation framework illustrated in Fig. 5. If σ satisfies ↑AB then a2 should be more acceptable than a1 because a2 has an attack branch of length 3 while a1 has an attack branch of length 1.

The second property concerns the defense branch and states that increasing the length of a defense branch of an argument decreases its level of acceptability.

Property 17

Property 17(Increase of a Defense Branch (↑DB) [9]).

A ranking-based semantics σ satisfies Increase of a Defense Branch if and only if for any AF,AFAF and xArg(AF), for every isomorphism γ such that AF=γ(AF), if yB+(x), yB(x) and AF=AFAFP+(γ(y)), then xAFσγ(x).

Example 2.4

Example 2.4(cont.).

If σ satisfies ↑DB then a3 should be more acceptable than a4 because a3 has a defense branch of length 2 while a4 has a defense branch of length 4.

2.4.Equal acceptability

The property Argument Equivalence ensures that the acceptability of an argument depends only on (the structure of) its attackers and defenders. Formally, two arguments with the “similar (isomorphic)” ancestors’ graph (which, as a reminder, is an argumentation framework containing the argument and its attackers and defenders) should have the same ranking.

Property 18

Property 18(Argument Equivalence (AE) [9]).

A ranking-based semantics σ satisfies Argument Equivalence if and only if for any AF=A,R and x,yA, for every isomorphism γ such that AncAF(x)=γ(AncAF(y)) then xAFσy.

The property Non-attacked Equivalence is a particular case of Argument Equivalence because it focuses on the comparison between the non-attacked arguments.

Property 19

Property 19(Non-attacked Equivalence (NaE) [9]).

A ranking-based semantics σ satisfies Non-Attacked Equivalence if and only if for any AF=A,R and x,yA, R1(x)= and R1(y)= then xAFσy.

Another possibility for detecting when two arguments are equally acceptable consists of taking into account their direct attackers. Suppose that two arguments, x and y, have the same number of direct attackers. If, for each direct attacker of x, there exists a direct attacker of y such that the two attackers are equally acceptable, then x and y are equally acceptable too.

Property 20

Property 20(Ordinal Equivalence (OE) [9]).

A ranking-based semantics σ satisfies Ordinal Equivalence if and only if for any AF=A,R and x,yA, if there exists a bijective function f from R1(x) to R1(y) such that zR1(x),zAFσf(z) then xAFσy.

3.Ranking-based semantics and existing persuasion principles

In the literature [2,9,17,26], many ranking-based semantics were compared on the basis of the properties recalled in the previous section. However, the relevance of some properties may be very much dependent on the context of application. Indeed, what is often missing to compare these approaches is thus a clear indication of the applications they target. For example, for online debate platforms, satisfying the property Total (Tot) may seem natural to ensure the comparison between all the arguments and thus guarantee a result to the users. Conversely, for the same platforms where votes are assigned to each argument and represent their social support, a possibility would be to reward a more aggressive non-attacked argument. Thus, such properties like Non-attacked Equivalence (NaE), considering that all the non-attacked arguments should be equally acceptable, should not be satisfied.

Among the many existing fields in argumentation (e.g., negotiation, persuasion, deliberation), we choose to focus on the context of persuasion in argumentation. Persuasion is an activity that involves one party (the persuader) trying to induce another party (the persuadee) to believe (or not believe) certain information or to do (or not do) some action. In our context, persuasion is unidirectional [19] and focused on a “targeted argument”, the aim being for the persuader to increase the ranking of this argument. The assumption is that it makes it more likely for the persuadee to believe the targeted fact (e.g., practizing exercise is good for your health) or perform the targeted action (e.g., buy a specific car). It has been observed that the three-valued approach of Dung was too restrictive in that context [19], and thus ranking-based approaches can be more appropriate.

Among the processes used in persuasion, we shall concentrate on two well documented phenomena in persuasion (procatalepsis and fading) and draw a parallel between each of them and existing properties for ranking-based semantics.

3.1.Procatalepsis

Procatalepsis, or prolepsis, is a figure of speech in which the speaker raises an objection to their own argument and then immediately answers it. The goal is to strengthen this argument by dealing with possible counter-arguments before their audience can raise them [33]. An example of the use of the principle of procatalepsis in practice is presented in the introduction and illustrated by an argumentation framework in Fig. 1. In this kind of persuasion context, it is clearly more convincing to state the more plausible counter-argument to a1 in order to provide some convincing defenses against them, than simply stating a1 alone. These anticipations make it possible to persuade the interlocutor that any attack against a1 is vain. In addition, it becomes difficult for the persuadee to find arguments against a1 if the persuader anticipates most of them. Thus, in terms of ranking, a1 with several defense branches could be seen as strictly more acceptable than a1 without any branch.

In order to formally define the procatalepsis principle in the context of abstract argumentation, we first need to formally define the argumentation frameworks that we call persuasion pitches. A persuasion pitch is a tree shaped argumentation framework where an argument x, called the targeted argument, has only defense branches.

Definition 3.1

Definition 3.1(Persuasion pitch).

An argumentation framework AF=A,R is a persuasion pitch with x as the targeted argument if the following conditions are satisfied:

  • (1) B(x)=,

  • (2) B+(x),

  • (3) yA{x}, there exists a unique path from y to x.

A persuasion pitch is denoted by Pk(x) where k=|B+(x)| is the number of defense branches of its targeted argument x. When the targeted argument x of the persuasion pitch is clear, we will use Pk instead of Pk(x).

Condition (1) means that the targeted argument has no attack branch while condition (2) states that it has at least one defense branch (the length of defense branches does not matter here). Condition (3) guarantees that the argumentation framework is in the shape of a tree centered on the targeted argument x, i.e. it contains only the arguments used in the pitch which are related to x (i.e. for which a path to x exists).

Example 3.1.

The argumentation framework depicted in Fig. 1 is a persuasion pitch P2 where a1 is the targeted argument with two defense branches.

Let us now formally define the procatalepsis principle in the context of abstract argumentation. We define this property by saying that a ranking-based semantics satisfies Procatalepsis if a number of defense branches is sufficient to make a targeted argument from a persuasion pitch at least as acceptable as when it does not have any (i.e. it is not attacked).

Property 21

Property 21(Procatalepsis (PR)).

A ranking-based semantics σ satisfies Procatalepsis if and only if there exists a Pk=A,R with k>0, xA as the targeted argument and yA as a non-attacked argument such that xPkσy.

We have deliberately made this definition a little more flexible than its original definition because we think it would be a mistake to claim that adding a unique defense branch will always be sufficient to make the targeted argument at least as acceptable as a non-attacked argument. Indeed, one can for example think that in Fig. 1, the defense branch composed of arguments a2 and a3 is not sufficient on its own to make a1 more acceptable than when it was not attacked and that it is the combination of the two defense branches that makes a1 more acceptable than when it was not attacked. However, this flexibility allows us to keep the idea that the more defense branches there are, the harder it will be for the opponent to find arguments to attack a1.

What is striking is that procatalepsis blatantly contradicts the property Void Precedence (VP), considering that a non-attacked argument is strictly more acceptable than an attacked argument. Recall that, as remarked in [9], this property is satisfied by all existing ranking-based semantics. Thus, no ranking-based semantics has yet been proposed where Void Precedence is not satisfied, implying that there exists no ranking-based semantics which can capture the procatalepsis principle.

Proposition 1.

No ranking-based semantics can satisfy both Void Precedence (VP) and Procatalepsis (PR).

3.2.Fading

The fading principle states that long lines of argumentation become ineffective in practice, because the audience easily loses track of the relations between the arguments.

Fig. 6.

Argumentation framework with a long line of arguments.

Argumentation framework with a long line of arguments.

In focusing on the argumentation framework depicted in Fig. 6, the fading principle concerns the limit until which the length of a path between an argument and another one is too long to have an impact on the targeted argument. For example, if one considers that the arguments situated at the beginning of the paths with a length greater or equal to 5 have no impact on a given argument, then arguments a6, a7 and a8 have no impact on a1. This limit is however not “radical” in the sense that before the limit, the arguments have the same impact and, after the limit, the arguments have no impact. Indeed, it seems natural to think that a closer attacker (respectively, defender) of an argument has more effect than a further one on the argument. For example, argument a2 should have more impact on a1 than any other argument in this argumentation framework because a2 is the direct attacker of a1. So, the impact is gradually reduced when the length of the path between two arguments increases. This idea of attenuation is already partially captured by two existing properties: Increase of an attack branch (↑AB) and Increase of a defense branch (↑DB) which state that increasing the length of an attack (resp. defense) branch of an argument increases (resp. decreases) its level of acceptability. However, we will explain in Section 6.2 why these two properties are not sufficient as they stand to catch the fading principle.

In practice, the fading principle is supported by the work of [30] which shows (in the context of their study, an extensive analysis of persuasive debates which took place on the subreddit “ChangeMyView”2), that arguments located at a distance greater than 10 from another argument (i.e., 5 rounds of back-and-forth), have no impact in the debate.

4.Ranking-based semantics taking into account the persuasion principles

In this section, our goal is to build a ranking-based semantics which allows us to catch the procatalepsis principle and the fading effect.

  • For the fading effect, a solution could be to use an attenuation factor to gradually decrease the impact of arguments. This is used for instance by the counting semantics [28] where the damping factor α (a value between 0 and 1) is used.

  • For the procatalepsis principle, we want that an attacked argument with many defense roots and few or no attack roots (like a1 in Fig. 1) can be more acceptable than a non-attacked argument. To achieve this goal, a solution is to only take into account the defense roots and the attack roots of an argument. Indeed, if we consider that a defense (respectively, attack) root has a positive (respectively, negative) effect on an argument, then, a sufficient number of defense roots (which can be caught by a parameter) would allow this argument to become more acceptable than a non-attacked argument.

4.1.Propagation with attenuation

We propose the extension of the propagation principle introduced in [8] with the elements previously put forward. Recall that the idea of propagation is to assign a positive initial value to each argument in the argumentation framework (arguments may start with the same initial value or start with distinct values where non-attacked arguments have greater value than attacked ones). Then each argument propagates its value into the argumentation framework, alternating the polarity according to the considered path (negatively if it is an attack path, positively if it is a defense one).

But, in order to catch the persuasion principles, we formally redefine the propagation mechanism by including a damping factor δ aiming to decrease the impact of attackers situated further away along a path (the longer the path length i, the smaller the δi).

Definition 4.1

Definition 4.1(Attenuated propagation).

Let A,R be an argumentation framework. The valuation P of xA, at step i, is given by:

Piϵ,δ(x)=vϵ(x) if i=0Pi1ϵ,δ(x)+(1)iδiyRi(x)vϵ(y)otherwise
with δ]0,1[ be an attenuation factor and vϵ:AR+ is a valuation function giving an initial weight to each argument, with ϵ[0,1] such that yA,
vϵ(y)=1if R1(y)=ϵotherwise

Example 4.1.

Let us compute the valuation P of each argument in AF1, depicted in Fig. 7, when ϵ=0.5 and δ=0.4. The results, at each step, are given in Table 1.

Let us focus on the argument f. One can see that f begins with an initial weight of 0.5 because it is attacked, P00.5,0.4(f)=0.5 Then, during the step i=1, it negatively receives the value attenuated by δ and sent by its direct attacker d which is also attacked, P10.5,0.4(f)=P00.5,0.4(f)0.4×v0.5(d)=0.3 During the second step (i=2), it positively receives the weights from a and c attenuated by δ2, P20.5,0.4(f)=P10.5,0.4(f)+0.42×(v0.5(a)+v0.5(c))=0.46 When i=3, it negatively receives the weight of 1 from b and the weight of 0.5 from e attenuated by δ3, P30.5,0.4(f)=P20.5,0.4(f)0.43×(v0.5(b)+v0.5(e))=0.364 and so on and so forth.

Fig. 7.

An argumentation framework AF1 with 6 arguments and an even cycle.

An argumentation framework AF1 with 6 arguments and an even cycle.
Table 1

Computation of the valuation P of each argument from AF1 when ϵ=0.5 and δ=0.4

Computation of the valuation P of each argument from AF1 when ϵ=0.5 and δ=0.4

The following proposition answers the question of convergence of the valuation P. The convergence is guaranteed by the use of the damping factor, but also because the set of arguments which attack or defend an argument for a given length of path is finite and limited by the number of arguments in an argumentation framework.

Proposition 2.

Let A,R be an argumentation framework, δ]0,1[ and ϵ]0,1]. For all xA, the sequence {Piϵ,δ(x)}i=0+ converges.

Let us now compute the propagation number of an argument by using a fixed-point iteration (the outcome is guaranteed with the previous proposition).

Definition 4.2

Definition 4.2(Propagation number).

Let A,R be an argumentation framework, δ]0,1[ and ϵ]0,1]. The propagation number of an argument xA is Pϵ,δ(x)=limi+Piϵ,δ(x).

We want to insist on the fact that the propagation number assigned to each argument is just used to relate and compare arguments of a given AF, and that it should not be used as an (isolated) measure.

Example 4.1

Example 4.1(cont.).

The propagation number of each argument in AF1 is represented in the shaded cell in Table 1. Thus, P0.5,0.4(a)=0.0402, P0.5,0.4(b)=1, P0.5,0.4(c)=0.1, P0.5,0.4(d)=0.3161, P0.5,0.4(e)=0.3506 and P0.5,0.4(f)=0.3736.

4.2.Variable-depth propagation

Let us now define a ranking-based semantics using the propagation number and taking into consideration the persuasion principles. As stated in the introduction of this section, a solution to catch the procatalepsis principle is to only take into account the roots of the arguments. Formally, it is possible when ϵ=0. Indeed, in this case, the non-attacked arguments propagate their weights (vϵ(y)=1) in the argumentation framework, while attacked arguments have an initial weight of 0. Thus, the propagation number of each argument is only based on the value received by their attack or defense roots. Any pairwise strict comparison (based on propagation number) resulting from this process is fixed. Let us take the example of the argumentation framework illustrated in Fig. 8. On the one hand, a1 and b1 have the same propagation number when ϵ=0 (P0,δ(a)=P0,δ(b)=2δ2) because they both have two defense branches and no attack branch. On the other hand, c1 has three defense branches (P0,δ(c)=3δ2). Therefore, since c1 has more branches of defense than a1 and b1, c1 must be more acceptable than a1 and b1 to be in agreement with the procatalepsis principle.

However, we do not want our semantics to be too “disconnected” from the principles that make the strength of ranking-based semantics: distinguishing arguments by taking into account the quality and the quantity of the arguments that attack or defend them. This is why we apply a second phase to break ties among arguments equally valued in the first phase. From a technical point of view, this means we re-run the propagation phase but this time setting an initial weight ϵ0 in order to take into account the attacked arguments. For example, a1 and b1 have the same propagation number when ϵ=0 in the argumentation framework represented in Fig. 8 because they both have exactly two defense branches. However, b1 is directly attacked only once while a1 is directly attacked twice, so one can consider that b1 could be more acceptable than a1.

Fig. 8.

Two arguments a1 and b1 with two defense branches (but with different configurations) involving a similar propagation number when ϵ=0 and c1 which has three defense branches.

Two arguments a1 and b1 with two defense branches (but with different configurations) involving a similar propagation number when ϵ=0 and c1 which has three defense branches.
Definition 4.3

Definition 4.3(Variable-Depth Propagation).

Let ϵ]0,1] and δ]0,1[. The ranking-based semantics Variable-Depth Propagation vdpϵ,δ associates to any argumentation framework AF=A,R a ranking AFvdpϵ,δ on A such that x,yA,

xAFvdpϵ,δyif and only ifP0,δ(x)>P0,δ(y) or (P0,δ(x)=P0,δ(y) and Pϵ,δ(x)Pϵ,δ(y))

Example 4.1

Example 4.1(cont.).

According to the previous definition, we first need to compute the propagation number of each argument when ϵ=0. Argument b is the only non-attacked argument, so the propagation number of each argument is only based on the value that it propagates (the valuations of each argument at each step is given in Table 2). It is why, until step i=3, e has a valuation of 0, but during step i=4, it receives a positive value from b, so P40,0.4(e)=0.44×v0(b)=0.0256.

We obtain the following propagation numbers: P0,0.4(a)=0.4105, P0,0.4(b)=1, P0,0.4(c)=0.4, P0,0.4(d)=0.1642, P0,0.4(e)=0.0263 and P0,0.4(f)=0.0657.

Thus, we obtain the following pre-ranking:

bdefca

Note that no arguments are equally acceptable here, so it is not necessary to perform the second phase. Thus, ϵ]0,1], vdpϵ,0.4 returns the following ranking:

bvdpϵ,0.4dvdpϵ,0.4evdpϵ,0.4fvdpϵ,0.4cvdpϵ,0.4a

Table 2

Computation of the valuation P of each argument from AF1 when ϵ=0 and δ=0.4

Computation of the valuation P of each argument from AF1 when ϵ=0 and δ=0.4

Let us give another example where the second phase is needed to distinguish two arguments.

Example 4.2.

Let us compute the ranking returned by vdp0.5,0.4 for the argumentation framework depicted in Fig. 8, beginning with the case ϵ=0 and then the case ϵ=0.5 (see Table 3).

Table 3

Valuation P for each argument in the argumentation framework depicted in Fig. 8 when ϵ=0 (above) and when ϵ=0.5 (below) with δ=0.4

Valuation P for each argument in the argumentation framework depicted in Fig. 8 when ϵ=0 (above) and when ϵ=0.5 (below) with δ=0.4

According to the definition of vdp, we first compare the propagation number of each argument when ϵ=0. The result is the following ranking:

a3a5b3b4c3c5c7a3a5b3a3a5b3c1a3a5b3a3a5b3a1b1a3a5b3a3a2a4c2c4c6a3a5b3a3a5b3b2
We can see that some arguments are still equally acceptable, in particular a1 and b1. So, according to the definition of vdp, we restart the process with a non-zero ϵ (here ϵ=0.5):
a3vdp0.5,0.4a5vdp0.5,0.4b3vdp0.5,0.4b4vdp0.5,0.4c3vdp0.5,0.4c5vdp0.5,0.4c7a3vdp0.5,0.4a5vdp0.5,0.4b3vdp0.5,0.4vdp0.5,0.4a3vdp0.5,0.4a5vdp0.5,0.4b3vdp0.5,0.4c1a3vdp0.5,0.4a5vdp0.5,0.4b3vdp0.5,0.4vdp0.5,0.4a3vdp0.5,0.4a5vdp0.5,0.4b3vdp0.5,0.4a1a3vdp0.5,0.4a5vdp0.5,0.4b3vdp0.5,0.4vdp0.5,0.4a3vdp0.5,0.4a5vdp0.5,0.4b3vdp0.5,0.4b1a3vdp0.5,0.4a5vdp0.5,0.4b3vdp0.5,0.4vdp0.5,0.4a3vdp0.5,0.4a2vdp0.5,0.4a4vdp0.5,0.4c2vdp0.5,0.4c4vdp0.5,0.4c6a3vdp0.5,0.4a5vdp0.5,0.4b3vdp0.5,0.4vdp0.5,0.4a3vdp0.5,0.4a5vdp0.5,0.4b3vdp0.5,0.4b2
With this second process, a1 and b1 can be distinguished. Indeed, they have two defense branches of length 2, so during the step where ϵ is 0, they receive the same values from their defense roots. However, one can remark that a1 is directly attacked twice while b1 is directly attacked once. So, during the second process where the initial score of the attacked arguments are also propagated, a1 receives one more negative value than b1 (P10.5,0.4(a1)=0.1<0.3=P10.5,0.4(b1)).

5.Influence of the parameters

The definition of the propagation number (see Definition 4.2) is based on two parameters: ϵ and δ. Let us, in this section, characterise their roles and their impacts on the ranking computed when the variable-depth propagation is used.

5.1.Parameter ϵ

Recall that the parameter ϵ has a key role to distinguish the two phases aiming to compute the ranking between arguments. However, a concern might be that the value of ϵ might change the ranking obtained. We show that this is not the case:

Proposition 3.

Let δ]0,1[ and ϵ,ϵ]0,1]. For any AF, we have vdpϵ,δ(AF)=vdpϵ,δ(AF).

Please note that even though different values of ϵ do not change the ranking between arguments returned by vdp, this parameter remains useful to distinguish the two steps used in the definition of vdp (see Definition 4.3): the first one where non-attacked arguments are the only arguments to propagate their value in the argumentation graph (ϵ=0) and the second one where all arguments propagate their value (ϵ0). However, this is a purely internal artefact without any effect on the outcome of the method. To make this clear, we note vdpδ instead of vdpϵ,δ to describe our parametrized ranking semantics in general.

5.2.Damping factor δ

5.2.1.Controlling the scope of influence of the arguments

The parameter δ is defined as the damping factor allowing us to decrease the impact of the argument when the length of the path increases. Following this, there intuitively exists a length such that the impact of arguments situating at the beginning of this path is negligible compared to the nearest arguments. Thus, the role of this parameter is to choose the scope of influence of the arguments in the argumentation framework, in addition to guarantee the convergence of the valuation P. For instance, with a value of δ close to 0, only the nearest arguments (so a small part of the argumentation framework) are taken into consideration to compute the different propagation numbers, whereas with a value of δ close to 1, (almost) all the argumentation framework will be inspected. Consequently, two different values of δ can produce different rankings for the same argumentation framework. Following the principle of the fading effect, it is natural to assume that arguments located at a long distance from another argument become ineffective. In terms of design, it seems very interesting to have the ability to control this parameter so as to specify a maximal depth after which arguments see their influence on the value of others vanish.

To better understand how to take the fading principle into account in using δ, let us detail the algorithm used to compute the propagation numbers.

  • 1) A positive number is assigned to each argument: aA, P0ϵ,δ(a)=1 if a is non-attacked or P0ϵ,δ(a)=ϵ otherwise,

  • 2) We increase the step i by 1 and we add (or subtract) the score computed during the previous step (Pi1ϵ,δ(a)) and the attenuated weights (vϵ and δi) received from defenders (or attackers) at the beginning of a path with a length of i (Ri(a)):

    Piϵ,δ(a)=Pi1ϵ,δ(a)+(1)iδibRi(a)vϵ(b)

  • 3) If, between two steps, the difference, for all valuations P, is smaller than a fixed precision threshold μ (i.e. aA, |Piϵ,δ(a)Pi1ϵ,δ(a)|<μ) then the process is stopped3 and the last values correspond to the propagation number of each argument. If it is not the case, we go back to 2).

Thus, given a precision threshold, one can choose δ according to the maximal expected depth.

Proposition 4.

Let AF=A,R be an argumentation framework, iN{0} be the maximal depth and μ be the precision threshold. If δ<μmaxaA(|Ri(a)|)i then, for all aA, the sequence {Piϵ,δ(a)}i=0+ converges before step i+1.

Example 5.1

Example 5.1(cont.).

Consider the argumentation framework AF1 depicted in Fig. 7. Suppose that one considers that the maximal depth should be 5. In using the previous formula with a precision μ=0.0001, then δ should be smaller than 0.0001250.1379. Thus, a value close to this limit, for instance δ=0.137, ensures that only the arguments until a depth of 5 (included) are considered.

Through the formula given in Proposition 4, we can determine, for each maximal depth, which value of δ should be used. For example, Fig. 9 represents the arguments which propagate their initial value to f (from AF1 illustrated in Fig. 7) before the convergence and the associated interval of values of δ. One can remark that AF1 contains a cycle a,d,f,e,a, it is why f can receive (according to the value of δ) a value from itself.

If the function defined in Proposition 4 allows us to select an appropriate δ in order to capture a given maximal expected depth (representing the fading effect), a legitimate question could concern the interval of values of δ to ensure the convergence at a specific depth i. However, it is not possible to answer this question in the general case, because of the diversity of argumentation frameworks. For example, suppose that one wants to consider a length up to 5 (no more no less). With an argumentation framework without cycles and with a maximal path smaller than 5, the process will be obviously stopped before. Thus the condition cannot be respected. It is for this reason that we only focus on the maximal depth.

Fig. 9.

Arguments which propagates their value to f according to the value of δ.

Arguments which propagates their value to f according to the value of δ.

Finally, we can also find a computational advantage to represent the fading effect. Indeed, as the number of steps needed to find the propagation number of each argument is smaller than (or, in the “worst” case, equal to) when all of the argumentation framework have to be considered, the ranking is computed faster. An example of a practical use of our semantics would be to apply it to the persuasive debates from the subreddit “ChangeMyView”. We would then have to parameterize delta in order to take this aspect into account. In addition to satisfying the fading principle, this will reduce the computation time because it will not be necessary to go through the whole graph to evaluate these arguments.

5.2.2.On the diversity of rankings

As shown in Fig. 10, for a given argumentation framework, different values of δ can produce different rankings. Indeed, when δ{0.0001,0.2,0.4,0.6}, vdpδ provides the same ranking, whereas, when δ0.8, c becomes more acceptable than f and d becomes more acceptable than b.

In light of these differences, one may be worried that the diversity of rankings could be so high that the semantics becomes too sensitive to small modifications of the parameter δ. To check this, we applied our variable-depth propagation on 1000 randomly generated argumentation frameworks4 for different values of δ{0.001,0.2,0.4,0.6,0.8,0.9}. Then, we measure the dissimilarity degree between two rankings from two different values of δ using the Kendall’s tau coefficient [21]. This coefficient corresponds to the total number of rank disagreements over all unordered pairs of arguments between two rankings. It therefore allows us to obtain a dissimilarity degree between two rankings.

Fig. 10.

An argumentation framework and the rankings returned by vdpδ for different values of δ.

An argumentation framework and the rankings returned by vdpδ for different values of δ.
Definition 5.1

Definition 5.1(Kendall’s tau coefficient).

Let AF=A,R be an argumentation framework and τσ1, τσ2 the rankings returned by the ranking semantics σ1 and σ2 respectively. The Kendall’s tau coefficient between τσ1 and τσ2 is calculated as follows:

K(τσ1,τσ2)={i,j}AKi,j(τσ1,τσ2)0.5×|A|×(|A|1)
with:
  • Ki,j(τσ1,τσ2)=0 if iAFσ1j and iAFσ2j, or iAFσ1j and iAFσ2j, or iAFσ1j and iAFσ2j;

  • Ki,j(τσ1,τσ2)=1 if iAFσ1j and iAFσ2j, or jAFσ1i and jAFσ2i;

  • Ki,j(τσ1,τσ2)=0.5 if (iAFσ1j or iAFσ1j and iAFσ2j), or (jAFσ1i or jAFσ1i and jAFσ2i).

A Kendall’s tau coefficient of 1 (K(τσ1,τσ2)=1) between two rankings means that both rankings are opposite (i.e. for all arguments x,yA, if xAFσ1y then yAFσ2x) while a Kendall’s tau coefficient of 0 (K(τσ1,τσ2)=0) means that both rankings are identical. So, the smaller the Kendall’s tau coefficient between two rankings, the higher their similarity.

Table 4 contains, for each pair of δ, the average Kendall’s tau coefficient, from the results previously computed, that we multiply by 100 to obtain a percentage of dissimilarity.

Table 4

Percentage of dissimilarity between the rankings from vdpδ with δ{0.001,0.2,0.4,0.6,0.8,0.9}

δ0.0010.20.40.60.80.9
0.00100.060.554.0910.6213.74
0.20.0600.524.1310.6313.64
0.40.550.5203.7110.1313.3
0.64.094.133.7106.829.86
0.810.6210.6310.136.8203.16
0.913.7413.6413.39.863.160

The results show that the obtained rankings stay pretty close since the biggest dissimilarity between the smallest and largest value of δ is 13.74%. This dissimilarity remains overall very small, showing that the semantics remain quite stable as the parameter varies.

The question now is whether these differences are only caused by the fading effect or if δ has an impact on other domains too. In the following section, we will check which properties recalled in Section 2.2 are satisfied by vdpδ to answer this question.

6.Properties satisfied by vdp

We now investigate the properties satisfied by our variable-depth propagation semantics vdp. Before checking all properties discussed in the literature, we start by inspecting the case of Void Precedence because this property contradicts the procatalepsis principle (see Section 3.1).

6.1.Void precedence

One of the very distinctive features of vdp is that an attacked argument can have a better score (and so a better rank) than a non-attacked argument. Indeed, when a given argument has many defense branches, it receives many positive weights. However, as depicted with the following example, this feature is not guaranteed for all values of δ.

Example 6.1.

Let us compute the rankings of the argumentation framework, which represents the sales pitch aiming to persuade someone to buy a car used to explain the procatalepsis principle (see Section 3), in using variable-depth propagation with several values of δ. The results are given in Fig. 11.

Fig. 11.

The different rankings computed with vdp for several values of δ applying to an argumentation framework.

The different rankings computed with vdp for several values of δ applying to an argumentation framework.

Indeed, one can remark that the non-attacked argument a3 (respectively a5) is strictly more acceptable than each attacked argument (including a1) when δ{0.0001,0.2,0.4,0.6} but a1 becomes strictly more acceptable than a3 (respectively a5) for the value of δ{0.8,0.9}. Thus, according to the choice of δ, this argument, which is attacked, can obtain a greater score than the score of non-attacked arguments.

Let us formally determine which are, for a given argumentation framework, the values of δ which ensure that the non-attacked arguments are more acceptable than the attacked arguments:

Proposition 5.

Let AF=A,R be an argumentation framework and x,yA such that R1(x)= and R1(y). If δ<δM such that δM=1maxzA(|R2(z)|) then P0,δ(x)>P0,δ(y).

De facto, there exists a threshold for the parameter δ which VP is satisfied.

Corollary 1.

For any argumentation framework, if δ<δM then vdpδ satisfies VP.

Example 6.1

Example 6.1(cont.).

The argument a1 has the highest number of direct defenders with |R2(a1)|=2. The value of δ should be δ<δM=1/20.7071 if one wants to satisfy VP.

So if δ=0.7, we obtain P0,0.7(a1)=0.98, P0,0.7(a2)=P0,0.7(a4)=0.7 and P0,0.7(a3)=P0,0.7(a5)=1 when ϵ=0 and P0.5,0.7(a1)=0.78, P0.5,0.7(a2)=P0.5,0.7(a4)=0.2 and P0.5,0.7(a3)=P0.5,0.7(a5)=1 when ϵ=0.5. These results imply the following ranking showing that the non-attacked arguments are strictly more acceptable than the attacked arguments: a3a5a1a2a4.

Thus, our method departs from other approaches in its treatment of the Void Precedence property, but to a certain extent only. Let us take the example of persuasion pitches to illustrate this. As a reminder, a persuasion pitch Pk is a tree shaped argumentation framework where an argument x, called targeted argument, has only defense branches (i.e. B(x)= and B+(x)) and k=|B+(x)|. In a persuasion pitch, a single line of defense is not enough to be more convincing than a non-attacked argument. On the other hand, when this condition is met, a simple condition for the violation of VP in persuasion pitches can be stated:

Proposition 6.

Let Pk=A,R be a persuasion pitch with xA as the targeted argument and yA be a non-attacked argument. Then,

  • (i) if k=1 then yPkvdpδx;

  • (ii) if k2 and δ>1km where m is the length of the longest defense branch of x then xPkvdpδy.

Interestingly, it turns out that in the context of our method, the Void Precedence property is related to the property Defense Precedence.

Proposition 7.

If vdpδ satisfies VP then it satisfies DP.

However please note that this is not the case for ranking-based semantics in general because some of them satisfy VP but not DP (see Table 5).

6.2.Other properties

Let us now check which properties, among those defined in Section 2.2, are satisfied by the variable-depth propagation semantics vdp.

Proposition 8.

Let δ]0,1[. vdpδ satisfies Abs, In, Tot, NaE, +AB, AE and AvsFD. The other properties are not satisfied.

Some global properties like +DB, ↑DB and ↑AB are not satisfied because of the fading effect. Indeed, when the branch, which is added or extended, is too long, the arguments at the end of this branch have no impact on the targeted argument. This is why we propose the definition of the corresponding properties (+DBi, DBi and ABi) which capture the same idea but with the additional condition that the property holds when the maximal length of the branch is i.

Table 5

Summary of the properties satisfied by vdp (δ, for max(δm,δM)<δ and for δm<δ<δM) and some existing ranking semantics studied in the literature. A cross × means that the property is not satisfied, symbol ✓means that the property is satisfied, and ✓i means that the i-version of the property (cf Property 9) is satisfied. Shaded cells are results proved in this paper

Summary of the properties satisfied by vdp (∀δ, for max(δm,δM)<δ′ and for δm<δ″<δM) and some existing ranking semantics studied in the literature. A cross × means that the property is not satisfied, symbol ✓means that the property is satisfied, and ✓i means that the i-version of the property (cf Property 9) is satisfied. Shaded cells are results proved in this paper

Formally, we need to redefine how an attack or a defense branch is added:

Definition 6.1

Definition 6.1(Attack and defense branch added to an argument with a limited length).

Let AF=A,R be an argumentation framework, xA be an argument and iN be a length. The defense branch added to x is Pi+(x)=A,R, with A={x0,,xn} such that n2N and ni, x0=x, AA={x}, and R={(xi,xi1)in}. The attack branch added to x, denoted Pi(x) is defined similarly except that the sequence is of odd length (i.e. n2N+1).

We are now able to define the “i-version” of +DB, ↑DB and ↑AB.

Property 22

Property 22(Addition of a Defense Branch with a maximal length i (+DBi)).

Let iN. A ranking-based semantics σ satisfies i-addition of a defense branch if and only if for any AF,AFAF and xArg(AF), for every isomorphism γ such that AF=γ(AF), if AF=AFAFPi+(γ(x)) and R1(x), then γ(x)AFσx.

Property 23

Property 23(Increase of an Attack Branch with a maximal length i (ABi)).

Let iN. A ranking-based semantics σ satisfies i-increase of an attack branch if and only if for any AF,AFAF and xArg(AF), for every isomorphism γ such that AF=γ(AF), if yB(x), yB+(x) and AF=AFAFPi+(γ(y)), then γ(x)AFσx.

Property 24

Property 24(Increase of a Defense Branch with a maximal length i (DBi)).

Let iN. A ranking-based semantics σ satisfies i-increase of a defense branch if and only if for any AF,AFAF and xArg(AF), for every isomorphism γ such that AF=γ(AF), if yB+(x), yB(x) and AF=AFAFPi+(γ(y)), then xAFσγ(x).

Consequently, for a given maximal depth i, it is enough to choose a value of δ large enough to guarantee that the sequence converges (see Proposition 4 page 21) after taking into account the added or extended branch. As we want vdp to satisfy these properties for all argumentation frameworks, we need to take the largest value of δ. Thus, according to the proposition, if μ and i are fixed, this happens when maxaA(|Ri(a)|) is minimal so when δ<μi.

Proposition 9.

Let μ be a precision threshold and i the expected maximal length. If δ]δm,1[ such that δm=μi then vdpδ also satisfies +DBi, DBi and ABi

All these results are reported in Table 5. For the purpose of comparison, we also include in this table the results of some existing ranking-based semantics from the literature where the same set of properties has been already checked [9]. Namely, these semantics are: the semantics h-categoriser Cat [6,27], the Discussion-based semantics Dbs and the Burden-based semantics Bbs [2], the α-Burden-based semantics α-Bbs [3], the Counting semantics CS [26,28], the three propagation semantics Propaϵ, Propa1+ϵ, Propa1ϵ [8], the Tuples-based semantics Tuples [13], the semantics M&T [24] and the Iterated Graded Defense semantics IGD [16,17].

Each of these existing ranking-based semantics satisfies Void Precedence and therefore violates the principle of procatalepsis (PR).

Proposition 10.

The ranking-based semantics Cat, Dbs, Bbs, α-Bbs, CS, Propaϵ, Propa1+ϵ, Propa1ϵ, Tuples, M&T and IGD do not satisfy PR.

We first remark that for any value of δ, vdp satisfies the properties accepted by almost all the existing ranking-based semantics (Abs, In, +AB, NaE, AE and Tot). The only exception concerns VP, but it is intended by design and discussed earlier. We can also note that vdp always satisfies property AvsFD, and for a specific δ (δm<δ) the property +DB. These three conditions are necessary to catch the procatalepsis principle. Indeed, AvsFD and +DB state that increasing the number of defense branches improves the acceptability of an argument, and the failure to satisfy VP is necessary to allow the attacked arguments to become more acceptable than non-attacked arguments.

It is clear that, like the Tuples-based semantics, the “local” properties like CT, SCT, CP, QP, DDP or SC cannot be satisfied by our semantics which mainly focus on the branch and not only on the direct attackers and direct defenders.

7.Conclusion

In this work, we have highlighted the fact that none of the existing ranking-based semantics is really appropriate for the context of persuasion, emphasizing in particular two well-documented phenomena occurring in practice: procatalepsis (the fact that it is often efficient to anticipate the counter-arguments of the audience) and fading (the fact that long lines of argumentation become ineffective). Indeed, all existing ranking-based semantics commit for instance to the Void Precedence property, which is incompatible with the procatalepsis principle. This motivated us to introduce a new parametrized ranking-based semantics based on the notion of propagation. More precisely, we extend the existing propagation semantics [8] by adding an additional parameter allowing us to gradually decrease the impact of arguments when the length of the path between two arguments increases. The role of this parameter is manifold because it allows:

  • (1) the convergence of the method which guarantees the existence of a result;

  • (2) the decrease of the impact of further arguments and then to capture the fading effect, by selecting a maximal influence depth;

  • (3) to give the possibility to choose if one wants to satisfy the Void Precedence property or not (and then represent procatalepsis in persuasion pitches).

We believe that this method offers a useful tool for persuasion, for instance to evaluate the relative impact that may have different persuasion pitches.

In addition to the study of our new ranking-based semantics, the message we want to convey through this work is that, despite detailed studies of the properties for ranking-based semantics, it is important to also evaluate existing semantics with respect to each targeted context/application. This will allow a potential user (expert or not in the field of argumentation) to facilitate her choice among existing ranking-based semantics. Of course, we are aware that this work is a preliminary step in order to formalize the process of persuasion. Indeed, many additional elements (beliefs of the opponent, credibility, personality, shared goals, length of a discussion, etc.) must be taken into consideration in order to properly formalize and evaluate the arguments and especially the impact they have on the opponent. It would be interesting, for example, to draw inspiration from what is done in computational persuasion (e.g., [1820]) where the role of the persuader is played by a system that can engage in dialogues with users to persuade them to accept or reject a given persuasion goal.

Finally, our methodology clearly focus on persuasion. However, it may also prove inspiring in other settings: by questioning the relevance of the existing semantics in other application contexts like negotiation (trying to resolve a conflict of interest by reaching a deal), deliberation (trying to reach a decision on a course of action), etc. We may find out that some specific phenomena are not properly captured, and that other adjustments are required.

Notes

3 In practice, we consider that a process is stopped when, for each valuation, the difference between two steps is smaller than a precision threshold.

4 The generation algorithms are based on the three algorithms used for producing the benchmarks of the competition ICCMA’15 [32].

Acknowledgements

We thank the reviewers for their useful comments on the previous version of the paper. This work benefited from the support of the project AMANDE ANR-13-BS02-0004 of the French National Research Agency (ANR).

Appendices

Appendix

AppendixProofs

Proposition 1.

Void Precedence (VP) and Procatalepsis (PR) are incompatible.

Proof.

(PR ⇒ ¬VP) Let Pk=A,R be a persuasion pitch where xA is the targeted argument and yA is a non-attacked argument. If a ranking-based semantics σ satisfies PR, then k>0 s.t. xPkσy. However, the fact that, by definition (see Definition 3.1), x has only defense branches means that it is attacked by at least one other argument (i.e. R1(x)). Consequently, the property VP says that y, which is non-attacked, should be strictly more acceptable that x for any k, so k>0 s.t. xPkσy, which contradicts PR.

(VP ⇒ ¬PR) Let AF=A,R be an argumentation framework with x,yA s.t. R1(x) and R1(y)=. If a ranking-based semantics σ satisfies VP, then y should be strictly more acceptable than x in AF. This conclusion also holds if AF is a persuasion pitch. Formally, it means that k>0, yPkσx. However, the property PR says that for any persuasion pitch k>0 s.t. xPkσy, which contradicts VP. □

Proposition 2.

Let A,R be an argumentation framework, δ]0,1[ and ϵ]0,1]. For all xA, the sequence {Piϵ,δ(x)}i=0+ converges.

Proof.

Let AF=A,R be an argumentation framework with aA and δ]0,1[.

To simplify the proof (and the formula), we focus on the “worst” case where each argument receives the maximal value of 1 from all others arguments at each step i (according to the parity of i). In this way, if the method converges in this case, the method will also converge when there are less attacks or with a smaller ϵ. Please note that the set of arguments is finite, so to each step the set of attackers/defenders is finite too. Let us suppose we have i>0, bRi(a)vϵ(b)=|A|=k>0. Let PP(a) (resp. NP(a)) be the positive (resp. negative) propagation that only focus on the score received by the defenders (resp. attackers) of a:

PPnϵ,δ(a)=vϵ(a)+i2N{0}nkδiandNPnϵ,δ(a)=i2N+1nkδiPnϵ,δ(a)=PPnϵ,δ(a)+(NPnϵ,δ(a))

We can observe that NP and PP (if we remove the initial value vϵ(a)) correspond to a geometric series with a common ratio δ]0,1[. As we know, when n goes to infinity, a geometric series always converges when the common ration (here δ) is strictly smaller than 1. Thus, PP and NP (and more precisely -NP) converge. In using these results, combined with the fact that the addition of two convergent functions converge too, we can conclude that Pnϵ,δ(a) converges. □

Proposition 3.

Let δ]0,1[ and ϵ,ϵ]0,1]. For any argumentation framework AF, vdpϵ,δ(AF)=vdpϵ,δ(AF).

Proof.

Let AF=A,R be an argumentation framework and a,bA be two arguments.

Given δ]0,1[, let us show that for all values of ϵ]0,1], the ranking returned by vdpϵ,δ(AF) stays identical.

During the step where ϵ=0, it is obvious that, for all values of ϵ, the obtained pre-order is identical because, by definition of vdp, the value of ϵ does not interfere in the computation of the propagation number. Thus, if P0,δ(a)>P0,δ(b) (resp. P0,δ(a)<P0,δ(b)), then ϵ]0,1], aAFvdpϵ,δb (resp. bAFvdpϵ,δa). However, if P0,δ(a)=P0,δ(b) then nothing can yet be deduced about the ranking of a compared to the ranking of b.

Consequently, let us check now what happens during the step ϵ0. By definition of vdp, this step aims to distinguish arguments which have the same propagation number when ϵ=0 (i.e. P0,δ(a)=P0,δ(b)). Thus, only attacked arguments can influence the ranking between two arguments. Indeed, if a distinction would have been made by the non-attacked arguments then this would have been captured in the first step where ϵ is 0. So, let a,bA be now two arguments s.t. P0,δ(a)=P0,δ(b).

In order to show that different values of ϵ do not change the result returned by vdp, we need to split the way to compute the propagation number when ϵ0 in two parts: the sum of the initial value and the scores received by the non-attacked arguments (P0,δ(a)) and the scores only received by the attacked arguments (APϵ,δ(a)). Formally, we have

Pϵ,δ(a)=P0,δ(a)+APϵ,δ(a)

We know that P0,δ(a)=P0,δ(b), so ab (the same reasoning holds with ≻ and ≺) only if APϵ,δ(a)=APϵ,δ(b). We denote by ki(x)=|{yA|yRi(x)Bi(x)}| the number of attacked arguments at the beginning of a path, with a length of i, to x.

Let us show that in the three configurations of a and b (both non-attacked, one attacked/one non-attacked, and both attacked), the value of ϵ is inoperative on the ranking returned by vdp.

1) a and b are both non-attacked arguments

As a and b are not attacked then APϵ,δ(a)=APϵ,δ(b)=0. Thus, for any value of ϵ[0,1], Pϵ,δ(a)=Pϵ,δ(b)=1 which implies that aAFvdpϵ,δb. This case is related to the Non-attacked Equivalence (NaE) property (see proof of Proposition 8).

2) a is an attacked attacked argument while b is an non-attacked argument

There exists cases where a non-attacked argument can have the same propagation number as an attacked argument when ϵ is 0 (depending on the value of δ). As b is not attacked then APϵ,δ(b)=0. Thus,

aAFvdpϵ,δbAPϵ,δ(a)=0(k1(a)ϵ)δ+(k2(a)ϵ)δ2(k3(a)ϵ)δ3+=0ϵ×(k1(a)δ+k2(a)δ2k3(a)δ3+)=0k1(a)δ+k2(a)δ2k3(a)δ3+=0
The fact that ϵ vanished from the formula means that the value of ϵ is inoperative on the ranking between a and b.

3) a and b are both attacked arguments

aAFvdpϵ,δbAPϵ,δ(a)=APϵ,δ(b)(k1(a)ϵ)δ+(k2(a)ϵ)δ2(k3(a)ϵ)δ3+=(k1(b)ϵ)δ+(k2(b)ϵ)δ2(k3(b)ϵ)δ3+ϵ×(k1(a)δ+k2(a)δ2k3(a)δ3+)=ϵ×(k1(b)δ+k2(b)δ2k3(b)δ3+)k1(a)δ+k2(a)δ2k3(a)δ3+=k1(b)δ+k2(b)δ2k3(b)δ3+
The fact that ϵ vanished from the formula means that the value of ϵ has no impact on the ranking between a and b. □

Proposition 4.

Let AF=A,R be an argumentation framework, iN{0} be the maximal depth and μ be the precision threshold. If δ<μmaxaA(|Ri(a)|)i then, for all aA, the sequence {Piϵ,δ(a)}i=0+ converges before step i+1.

Proof.

The process is stopped when, between two steps, the difference with the previous step for all the valuations P is smaller than a fixed precision threshold μ, i.e. aA,

|Piϵ,δ(a)Pi-1ϵ,δ(a)|<μ|Pi-1ϵ,δ(a)+(1)iδibRi(a)vϵ(b)Pi-1ϵ,δ(a)|<μδibRi(a)vϵ(b)<μ(1)i is negligable in our case
It is clear that aA, bRi(a)vϵ(b)|Ri(a)|maxaA(|Ri(a)|). Using the maximum guarantees that the difference between two steps is small enough w.r.t μ for all the arguments. So, if the method converges with maxaA(|Ri(a)|) then it also converges with the smallest values:
δimaxaA(|Ri(a)|)<μδi<μmaxaA(|Ri(a)|)δ<μmaxaA(|Ri(a)|)i

Proposition 5.

Let AF=A,R be an argumentation framework and x,yA such that R1(x)= and R1(y). If δ<δM such that δM=1maxzA(|R2(z)|) then P0,δ(x)>P0,δ(y).

Proof.

Let AF=A,R be an argumentation framework, yA be the argument with the biggest number of direct defenders (m=|R2(y)|=maxaA(|R2(a)|)) and xA be a non-attacked argument (implying, by definition, that P0,δ(x)=1).

Let us determine the case where an attacked argument y can obtain a maximal score. According to the formal definition of the propagation principle, this occurs when y does not have any attack branch (and so does not receive any negative value when ϵ=0). However, it must have many defense branches to receive a maximum of positive values. In addition, the best situation is when the values come from the direct defenders because of the attenuation factor. So the best score of y is when it receives m positive values from its m direct defenders: P0,δ(y)=mδ2. Recall that the condition is that δ<1m, so:

δ<1mδ2<1mmδ2<1P0,δ(y)<1P0,δ(y)<P0,δ(x)
 □

Proposition 6.

Let Pk=A,R be a persuasion pitch with xA as the targeted argument and yA be a non-attacked argument. Then,

  • (i) if k=1 then yPkvdpδx;

  • (ii) if k2 and δ>1km where m is the length of the longest defense branch of x then xPkvdpδy.

Proof.

(i) Let y be the only defense root of x (B+(x)={y} and B(x)=). The length of the path from y to x is n with n2N. According to the definition of the propagation principle, when ϵ=0, x only receives the score from y which is attenuated by δn. So, P0,δ(x)=δn but δ]0,1[ so n,δn<1=P0,δ(y) which implies that yP1vdpδx, in agreement with the property Void Precedence.

(ii) Let y be a non-attacked argument (P0,δ(y)=1) and x be an argument with only defense branches with a length of m (P0,δ(x)=|B+(x)|δm).

δ>1kmδ>1|B+(x)|mδm>1|B+(x)||B+(x)|δm>1P0,δ(x)>P0,δ(y)xPkvdpδy
The result is similar if x also has defense branches with lengths shorter than m. Indeed, let I(x)={i|Bi(x)} be the set of lengths such that there exists at least one defense branch of x with this length. As m is the length of the longest defense branch of x, we have, therefore, mI(x) and iI(x){m} then i<m. By definition, we have iI(x)|Bi(x)|=|B+(x)|. However, if i<m then δi>δm because δ]0,1[.

Consequently, if I(x){m} then iI(x)|Bi(x)|δi>|B+(x)|δm>1 which means that, in this case, if k2 and δ>1km then we still have xPkvdpδy. □

Proposition 7.

If vdpδ satisfies VP then it satisfies DP.

Proof.

Let a and b be two arguments with the same number of direct attackers (|R1(a)|=|R1(b)|=n with nN) but b is defended whereas a is not. DP states that b should be strictly more acceptable than a.

As VP is satisfied, each direct attacker of b which is attacked, is less acceptable than any direct attacker of a which are non-attacked: xR1(b) such that yR1(a), yvdpδx. That means that P0,δ(y)>P0,δ(x) or P0,δ(y)=P0,δ(x) and Pϵ,δ(y)>Pϵ,δ(x). Let us show that whatever the value of ϵ[0,1], we obtain the same result:

yvdpδxPϵ,δ(y)>Pϵ,δ(x)1>Pϵ,δ(x) because y is not attackedδ>Pϵ,δ(x)δ with δ]0,1[δ<Pϵ,δ(x)δ
a is only attacked by non-attacked arguments so Pϵ,δ(a)=ϵnδ=ϵ(n1)δδ. Suppose that b has only one direct attacker which is attacked (the same reasoning holds with more attacked attackers) then Pϵ,δ(b)=ϵ(n1)δPϵ,δ(x)δ. Consequently, according to the previous result (δ<Pϵ,δ(x)δ), we have ϵ(n1)δδ<ϵ(n1)δPϵ,δ(x)δPϵ,δ(a)<Pϵ,δ(b)avdpδb. □

Proposition 8.

Let δ]0,1[. vdpδ satisfies Abs, In, Tot, NaE, +AB, AE and AvsFD. The other properties are not satisfied.

Proof.

Properties satisfied.(Abs) The nature of an argument is not used in the computation of its score. Only the attack relation is considered.

(In) An argument a only receives the scores from its attackers and defenders. Thus, an argument b, such that there exists no path between a and b, cannot propagate its initial value to a and then cannot influence the propagation number of a.

(Tot) The semantics assigns a propagation number, which is real number, to each argument. As all the real numbers can be compared, all the arguments can be compared.

(AE) Obvious because two arguments with the same ancestor graph receive exactly the same value from their attackers and defenders whatever the values of ϵ and δ. Thus, they have the same propagation number which implies that they are equally acceptable.

(NaE) NaE is implied by AE which is satisfied.

(+AB) Let AF=A,R and AF=A,R be two argumentation frameworks such that there exists an isomorphism γ with AF=γ(AF). Let aA and its image γ(a)A be two arguments, ϵ]0,1] and δ]0,1[. As the semantics satisfies Argument Equivalence (AE), we can say that a and γ(a), which have the same ancestors’ graph, also have the same propagation number (Pϵ,δ(a)=Pϵ,δ(γ(a))).

Let us now add an attack branch from b to γ(a) with a length n2N+1.

There exists two possibilities with respect to δ:

  • If the maximal depth m is greater than n, then during the first phase where ϵ=0, γ(a) receives the negative value from b attenuated by δn: P0,δ(a)δn=P0,δ(γ(a))P0,δ(a)>P0,δ(γ(a))aAFvdpδγ(a).

  • If the maximal depth m is smaller than n, then during the first step (ϵ=0), we have P0,δ(a)=P0,δ(γ(a)) because the method converges before γ(a) receives the value from b. So, we restart with ϵ0, and γ(a) receives several additional values from its new attackers and defenders in the added attack branch. Thus, we have Pϵ,δ(a)+i=1m(1)iδiϵ=Pϵ,δ(γ(a)) but as i=1m(1)iδiϵ<0, then Pϵ,δ(a)>Pϵ,δ(γ(a))aAFvdpδγ(a).

Then, in both cases, when an attack branch is added to an argument, its acceptability decreases, in agreement with the property.

(AvsFD) Let AF=A,R be an argumentation framework where aA is attacked by only one non-attacked argument and bA is either not attacked or fully defended (i.e. it has no attack branch). The property says that b should be more acceptable than a.

If b is a not attacked then P0,δ(b)=1>δ=P0,δ(a)bAFvdpδa.

When b is attacked, we need to distinguish two cases with respect to δ:

  • If the length of all the defense branches of b are greater than the maximal depth, then b does not receive any value from its defense roots. But a always receives the score from its non-attacked direct attacker so: P0,δ(b)=0>δ=P0,δ(a)bvdpδa.

  • Otherwise, b receives only positive values from its defense roots, so P0,δ(b)>0>δ=P0,δ(a)bvdpδa.

In summary, for all values of δ, b is more acceptable than a in agreement with the property.

Counter-examples.(CT) Considering the argumentation framework depicted in Fig. 12, let us show that CT is not satisfied.

Fig. 12.

vdp falsifies the properties (S)CT and CP.

vdp falsifies the properties (S)CT and CP.

The property says that b should be at least as acceptable as a because there exists an injective function f from R1(b) to R1(a) such that bR1(b), f(b)b. Indeed, we have R1(b)={b1} and R1(a)={a1,a3} where a3b1. However, vdp0.5 considers that a is strictly more acceptable than b, contradicting the property.

(SCT) Considering the argumentation framework depicted in Fig. 12, let us show that SCT is not satisfied. The property says that b should be at least as acceptable as a because there exists an injective function f from R1(b) to R1(a) such that bR1(b), f(b)b and |R1(a)|>|R1(b)|. Indeed, we have R1(b)={b1} and R1(a)={a1,a3} (so |R1(a)|=2>1=|R1(b)|) where a3b1. However, vdp0.5 considers that a is strictly more acceptable than b, contradicting the property.

(CP) Considering the argumentation framework depicted in Fig. 12, let us show that CP is not satisfied. The property considers that b should be strictly more acceptable than a because |R1(a)|=2>1=|R1(b)|. However, vdp0.5 considers that a is strictly more acceptable than b, contradicting the property.

(QP) Considering the argumentation framework depicted in Fig. 13, let us show that QP is not satisfied.

Fig. 13.

vdp falsifies the property QP.

vdp falsifies the property QP.

The property says that a should be strictly more acceptable than b because b1vdp0.5a4 and b1vdp0.5a1. However, vdp0.5 considers that b is strictly more acceptable than a, contradicting the property.

(DDP) Considering the argumentation framework depicted in Fig. 14, let us show that DDP is not satisfied.

Fig. 14.

vdp falsifies the property DDP.

vdp falsifies the property DDP.

The definition says that a should be strictly more acceptable than b because they have the same number of direct attackers (|R1(a)|=|R1(b)|=2) and the same number of direct defenders (|R2(a)|=|R2(b)|=2) but the defense of a is simple and distributed whereas the defense of b is simple and not distributed. However, vdp0.5 considers that b is strictly more acceptable than a, contradicting the property.

(SC) Considering the argumentation framework depicted in Fig. 15, let us show that SC is not satisfied.

Fig. 15.

vdp falsifies the property SC.

vdp falsifies the property SC.

The definition says that b should be strictly more acceptable than a because a attacks itself while b does not. However, vdp0.5 considers that a is strictly more acceptable than b, contradicting the property.

(DB) Considering the argumentation framework depicted in Fig. 16, let us show that ⊕DB is not satisfied.

Fig. 16.

vdp falsifies the property ⊕DB.

vdp falsifies the property ⊕DB.

The property says that a should be strictly more acceptable than b because a has a defense branch while that b has not. However, vdp0.5 considers that b is strictly more acceptable than a, contradicting the property.

(OE) Considering the argumentation framework depicted in Fig. 17, let us show that OE is not satisfied. The property considers that a and b should be equally acceptable because there exists a bijective function f from R1(a) to R1(b) such that cR1(a),cf(c). Indeed, one can remark that a1b1 and a2b2. However, vdp0.2 considers that b is strictly more acceptable than a, contradicting the property. □

Fig. 17.

vdp falsifies the property OE.

vdp falsifies the property OE.

Proposition 9.

Let μ be a precision threshold and i the expected maximal length. If δ]δm,1[ such that δm=μi then vdpδ also satisfies +DBi, DBi and ABi.

Proof.

Proposition 4 shows that if δ>δm then the argument with an additional branch (+DB) or an extended branch (↑DB and ↑AB) will receive all the values from the arguments belonging to this branch.

Let AF=A,R and AF=A,R be two argumentation frameworks such that there exists an isomorphism γ with AF=γ(AF). Let aA and its image γ(a)A be two arguments, ϵ]0,1] and δ]0,1[. As the semantics satisfies the properties Argument Equivalence (AE), we can say that a and γ(a), with the same ancestors’ graph, always have the same propagation number (Pϵ,δ(a)=Pϵ,δ(γ(a))).

(+DB) Let us now add a defense branch from b to γ(a) (so R1(b)=) with a length of i2N. Recall that the first step of this semantics (when ϵ=0) consists in checking only the impact of non-attacked arguments. Consequently, γ(a) receives now one additional positive value from b (vϵ(b)=1), so Pϵ,δ(a)+δi=Pϵ,δ(γ(a))Pϵ,δ(a)<Pϵ,δ(γ(a))γ(a)AFvdpδa, in agreement with the property.

(AB) We suppose n2N+1 such that b is an argument situated at the beginning of an attack branch to a with a length of n. Thus a receives a score of δn from b during the first phase where ϵ=0. Now, we add a new defense branch to the non-attacked argument γ(b). We denote by b the argument at the beginning of this new branch which has a length of m. It is clear than γ(b) is now attacked so, during the step where ϵ=0, γ(b) does not send its negative value to γ(a) anymore but it receives the negative score of b (-δn+m): P0,δ(γ(a))=P0,δ(a)+δnδn+m. Consequently, δn>δm+n (because m+n>n) and P0,δ(γ(a))>P0,δ(a) implies that γ(a)AFvdpδa, in agreement with the property.

(DB) The proof is very similar to the one of ↑AB. The difference is that b is situated at the beginning of a defense branch. So P0,δ(γ(a))=P0,δ(a)δn+δm+n with δn>δm+n, which implies that P0,δ(a)>P0,δ(γ(a))aAFvdpδγ(a) in agreement with the property. □

Proposition 10.

The ranking-based semantics Cat, Dbs, Bbs, α-Bbs, CS, Propaϵ, Propa1+ϵ, Propa1ϵ, Tuples, M&T and IGD do not satisfy PR.

Proof.

All these ranking-based semantics satisfy Void Precedence (VP) [9]. As VP is incompatible with the procatalepsis principle (PR) (see Proposition 1), then all these semantics violate PR. □

References

[1] 

L. Amgoud, A replication study of semantics in argumentation, in: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI’19), 2019.

[2] 

L. Amgoud and J. Ben-Naim, Ranking-based semantics for argumentation frameworks, in: Proceedings of the 7th International Conference on Scalable Uncertainty Management (SUM’13), 2013, pp. 134–147. doi:10.1007/978-3-642-40381-1_11.

[3] 

L. Amgoud, J. Ben-Naim, D. Doder and S. Vesic, Ranking arguments with compensation-based semantics, in: Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR’16), 2016, pp. 12–21.

[4] 

P. Baroni, A. Rago and F. Toni, From fine-grained properties to broad principles for gradual argumentation: A principled spectrum, International Journal Approximate Reasoning 105 (2019), 252–286. doi:10.1016/j.ijar.2018.11.019.

[5] 

P. Besnard, V. David, S. Doutre and D. Longin, Subsumption and incompatibility between principles in ranking-based argumentation, in: Proceedings of the 29th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’17), 2017.

[6] 

P. Besnard and A. Hunter, A logic-based theory of deductive arguments, Artificial Intelligence 128(1–2) (2001), 203–235. doi:10.1016/S0004-3702(01)00071-6.

[7] 

P. Besnard and A. Hunter, Elements of Argumentation, MIT Press, 2008. ISBN 9780262250986.

[8] 

E. Bonzon, J. Delobelle, S. Konieczny and N. Maudet, Argumentation ranking semantics based on propagation, in: Proceedings of the 6th International Conference on Computational Models of Argument (COMMA’16), 2016, pp. 139–150.

[9] 

E. Bonzon, J. Delobelle, S. Konieczny and N. Maudet, A comparative study of ranking-based semantics for abstract argumentation, in: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI’16), 2016, pp. 914–920.

[10] 

E. Bonzon, J. Delobelle, S. Konieczny and N. Maudet, A parametrized ranking-based semantics for persuasion, in: Proceedings of the 11th International Conference on Scalable Uncertainty Management (SUM’17), 2017, pp. 237–251. doi:10.1007/978-3-319-67582-4_17.

[11] 

E. Bonzon, J. Delobelle, S. Konieczny and N. Maudet, Combining extension-based semantics and ranking-based semantics for abstract argumentation, in: Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR’18), 2018, pp. 118–127.

[12] 

E. Cabrio and S. Villata, Five years of argument mining: A data-driven analysis, in: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI’18), 2018, pp. 5427–5433.

[13] 

C. Cayrol and M. Lagasquie-Schiex, Graduality in argumentation, Journal of Artificial Intelligence Research 23 (2005), 245–297. doi:10.1613/jair.1411.

[14] 

C. da Costa Pereira, A. Tettamanzi and S. Villata, Changing one’s mind: Erase or rewind? in: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI’11), 2011, pp. 164–171.

[15] 

P.M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence 77(2) (1995), 321–358. doi:10.1016/0004-3702(94)00041-X.

[16] 

D. Grossi and S. Modgil, On the graded acceptability of arguments, in: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI’15), 2015, pp. 868–874.

[17] 

D. Grossi and S. Modgil, On the graded acceptability of arguments in abstract and instantiated argumentation, Artificial Intelligence 275 (2019), 138–173, http://www.sciencedirect.com/science/article/pii/S0004370219301237. doi:10.1016/j.artint.2019.05.001.

[18] 

A. Hunter, Opportunities for argument-centric persuasion in behaviour change, in: Proceedings of the 14th European Conference on Logics in Artificial Intelligence (JELIA’14), 2014, pp. 48–61. doi:10.1007/978-3-319-11558-0_4.

[19] 

A. Hunter, Towards a framework for computational persuasion with applications in behaviour change, Argument & Computation 9(1) (2018), 15–40.

[20] 

A. Hunter and N. Potyka, Updating probabilistic epistemic states in persuasion dialogues, in: Proceedings of the 14th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU’17), 2017, pp. 46–56. doi:10.1007/978-3-319-61581-3_5.

[21] 

M.G. Kendall, A new measure of rank correlation, Biometrika 30(1/2) (1938), 81–93. doi:10.1093/biomet/30.1-2.81.

[22] 

J. Leite and J. Martins, Social abstract argumentation, in: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI’11), 2011, pp. 2287–2292.

[23] 

M. Lippi and P. Torroni, Argumentation mining: State of the art and emerging trends, ACM Transactions Internet Technology 16(2) (2016), 10:1–10:25. doi:10.1145/2850417.

[24] 

P. Matt and F. Toni, A game-theoretic measure of argument strength for abstract argumentation, in: Proceedings of the 11th European Conference on Logics in Artificial Intelligence (JELIA’08), 2008, pp. 285–297. doi:10.1007/978-3-540-87803-2_24.

[25] 

H. Prakken and M.D. Winter, Abstraction in argumentation: Necessary but dangerous, in: Proceedings of the 7th International Conference on Computational Models of Argument (COMMA’18), 2018, pp. 85–96.

[26] 

F. Pu, J. Luo and G. Luo, Some supplementaries to the counting semantics for abstract argumentation, in: Proceedings of the 27th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’15), 2015, pp. 242–249.

[27] 

F. Pu, J. Luo, Y. Zhang and G. Luo, Argument ranking with categoriser function, in: Proceedings of the 7th International Conference on Knowledge Science, Engineering and Management (KSEM’14), 2014, pp. 290–301.

[28] 

F. Pu, J. Luo, Y. Zhang and G. Luo, Attacker and defender counting approach for abstract argumentation, in: Proceedings of the 37th Annual Meeting of the Cognitive Science Society (CogSci’15), 2015, pp. 1913–1918.

[29] 

G.R. Simari and I. Rahwan, Argumentation in Artificial Intelligence, Springer, 2009. ISBN 978-0-387-98196-3. doi:10.1007/978-0-387-98197-0.

[30] 

C. Tan, V. Niculae, C. Danescu-Niculescu-Mizil and L. Lee, Winning arguments: Interaction dynamics and persuasion strategies in good-faith online discussions, in: Proceedings of the 25th International Conference on World Wide Web, (WWW’16), 2016, pp. 613–624. doi:10.1145/2872427.2883081.

[31] 

M. Thimm and G. Kern-Isberner, On controversiality of arguments and stratified labelings, in: Proceedings of the 5th International Conference on Computational Models of Argument (COMMA’14), 2014, pp. 413–420.

[32] 

M. Thimm and S. Villata, First International Competition on Computational Models of Argumentation (ICCMA’15), 2015, see http://argumentationcompetition.org/2015/.

[33] 

D. Walton, Dialog Theory for Critical Argumentation, John Benjamins Publishing, 2007.