Dynamic of Argumentation Frameworks

1 Background

Our work focuses on argumentation systems. Those systems are an efficient way to reason with contradictory information. An abstract argumentation system [Dung, 1995] is a directed graph where nodes represent abstract arguments and edges represent the attack between arguments. (a, b) is an attack of the system (with a and b two arguments) means that if a is accepted by the agent then b must be rejected. An agent can reason with an argumentation system choosing sets of arguments that can be jointly accepted without conflict with respect to the attack relation. Dung defines several acceptability semantics which lead an agent to compute sets of socalled extension. These extensions are conflict-free sets of arguments which are admissible (defends the set w.r.t. each attack) and satisfy some other criteria (for instance, maximality w.r.t. set inclusion). Some semantics lead to more than one extension for a given argumentation system, in this case the agent can use different inference relations such as credulous (an argument is accepted if and only if it belongs to at least one extension) or skeptical (an argument is accepted if and only if it belongs to every extension). Another way to represent the accepted arguments is the labellings representation. A labelling is a mapping associating a label in, undec or out to every argument in the argumentation system. Caminada [2006] defines the stronger notion of reinstatement labellings : in such a labelling, an argument a is in if and only if every argument attacking a is out ; an argument a is out if and only if there exists an argument b attacking a so that b is in ; an argument is undec if and only if it is nor in neither out. Those reinstatement labellings correspond in a bijective way to Dung's complete extensions, and other semantics can be represented adding constraints on labellings.

2 Thesis subject

In the usual logical framework, change operations are characterized by some axiomatic approaches, such as the AGM framework for belief revision and contraction [Alchourr´on et al., 1985]. This kind of approach does not exist in the framework of argumentation systems.

Thus, my thesis aims to define change operations on argumentation systems `a la Dung giving for every kind of operation some logical properties (the rationality postulates) that an operator must satisfy to be a "good" operator.

3 Recent work

The first work is the adaptation of AGM belief revision [Alchourr´on et al., 1985] to Dung's argumentation systems. We have to fix our framework before starting the actual work. We point out that the change constraint on an argumentation system can have two distinct natures : one can change a system so as to accept (or do not accept) some arguments, and one can change a system in order to force a given attack to belong to its attack relation. On a similar way, the minimality of change associated to the revision can concern the accepted arguments or the attack relation.

Our study focuses on constraints on the accepted arguments, with minimal change on the sets of accepted arguments. Moreover, we fix the set of arguments : no new argument can be added when a revision is performed. The first step of this work is to define a way to express complex information from an argumentation system. So we consider a logical language built on the set of arguments, with the negation to express the rejection of an argument (¬α), the conjunction and disjunction to connect formulae (ϕ1 ∧ ϕ2, ϕ1 ∨ ϕ2). We associate a semantics to this language, using extensions: an extension satisfy an atomic formula ϕ = a if and only if the considered argument belongs to it. Recursive definitions of satisfaction are given for the negation, the conjunction and the disjonction, in a similar way to propositionnal logic. Then, an argumentation system satisfies a formula with respect to a given acceptability semantics if and only if every of its extension satisfies the formula (skeptical approach). With this notion, we can intuitively explain that the revision of an argumentation system is the minimal change to obtain a system satisfying the formula.

We revisit Katsuno's and Mendelzon's postulates for AGM revision in propositionnal logic [1991] in a set-theoretic framework suited to the argumentation case. These postulates are proved to be associated to a family of revision operators through a representation theorem which adapts the notion of faithful assignment to argumentation. In our case, the faithful assignment defines a pre-order between sets of arguments: a set of arguments E is "smaller" than a set E′ w.r.t. the pre-order if E is closer to the extensions of the system than E′ . The representation theorem allows the identification of some family of revision operators which satisfy the rationality postulates. These operators are based on distances. The most simple one is the Hamming distance between extensions, but we can also use the labellings to define other families of distances. The interesting point is that these distances can change the result of the revision, depending on wether it is less costly to change the status of an argument to in or to out. We also use distances on attack relations as a second minimality criterion to choose the argumentation systems which are as close as possible from the input system.

A possible application is the case of persuasion in a social network debate [Gabbriellini and Torroni, 2013]. When an agent A initiates a debate about an argument α, if another agent B does not agree with A about α but considers that A is trustworthy, B has to revise her beliefs to include α in at least one of her extensions. This kind of reasoning uses credulous inference, but it can be replaced by skeptical inference and so the revised system can be computed with one of the distance based operators defined during this thesis.

4 Related works

Some change operations on argumentation systems have been studied in the past years, but none of them studied rationality postulates. In [Boella et al., 2009b; 2009a], the authors studied the case of semantics which ensure the existence of a unique extension (especially the grounded semantics) and formulated some principles of the form "if we do this particular change, then the extension of the result is like this", pointing out which ones are satisfied by the grounded semantics. In [Cayrol et al., 2010; Bisquert et al., 2011], the authors stated some properties that can be satisfied when a change occurs in an argumentation system, and pointed out which ones are satisfied by some particular changes (adding and removing an argument with the attacks concerning it). [Baumann, 2012] gave the bounds of the number of modifications to make in an argumentation system to ensure that a set of arguments is accepted. The bounds depend of the chosen acceptability semantics and the type of change allowed.

5 Future works

Until now, the complexity of the problem seems to be an obstacle to the computation of revision. Nevertheless, we plan to encode revision operators with logical constraints, in a similar way to Besnard and Doutre [2004], so as to be able to benefit of the power of constraint solvers to compute revised argumentation systems.

Another perspective consists of enlarging the study to credulous inference.

The study of other change operations on argumentation systems is another perspective for research: for instance the AGM contraction or the iterated revision, which are very close to AGM revision in logical framework, or the merging of argumentation systems.

Finally, we can consider the opposite view concerning the minimal change and study the case when the conservation of the attack relation has priority on the conservation of the set of extensions, and mix these two kinds of minimal change with change constraints on the attack relation.