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

Constraints and changes: A survey of abstract argumentation dynamics

Abstract

This paper addresses the issue of the dynamic enforcement of a constraint in an argumentation system. The system consists in (1) an argumentation framework, made up, notably, of a set of arguments and of an attack relation, (2) an evaluation semantics, and (3) the evaluation result, computed from (1) and (2). An agent may want another agent to consider a new attack, or to have a given argument accepted, or even to relax the definition of the semantics. A constraint on any of the three components is thus defined, and it has to be enforced in the system. The enforcement may result in changes on components of the system. The paper surveys existing approaches for the dynamic enforcement of a constraint and its consequences, and reveals challenging enforcement cases that remain to be investigated.

1.Introduction

Abstract argumentation is an elegant way to tackle reasoning problems in presence of conflicting information. The seminal paper by Dung [44] defines an argumentation framework as a digraph whose nodes are abstract entities called arguments, and edges are attacks representing the conflicts between these arguments. Several acceptability semantics allow to decide which sets of arguments are accepted, depending on the properties which are expected to be satisfied by a set of arguments to be a rational “outcome” of the framework. Numerous enrichments of Dung’s framework have been proposed, for example, to take into account some supports between arguments besides the attacks, or some preferences between arguments. In this paper, we consider an argumentation system as defined by an underlying abstract framework, a semantics to evaluate the status of arguments, and the result of the evaluation of the argumentation framework by the semantics.

The question of the dynamics of abstract argumentation settings has recently been addressed. This dynamics is particularly at stake in a multi-agent context: the framework evolves as the agents put forward new arguments. In such a context, it may also be the case that an agent may want another one to consider a given argument as accepted, whereas, currently, it is not; the system may have to be changed to fulfill this goal. An agent may even want to change the way arguments are evaluated, for instance because the current evaluation semantics may produce several acceptable sets of arguments, and a single one is required to quickly get to some decision.

In this paper, we address the question of enforcing such constraints (evolution of the framework, need of a different evaluation result, change of the evaluation semantics) in an argumentation system. We present a typology of constraints and changes that can occur in dynamic argumentative scenarios. Most of the existing approaches to deal with this kind of scenarios consider Dung’s framework and extension-based semantics. However, we mention some open research questions that show that our typology is also suitable for other argumentation frameworks and semantics.

The paper begins with an introduction of the different components of an argumentation system in a generic way, with a focus on the classical Dung’s framework. Section 3 describes the existing work on change in argumentation systems, which mainly concerns Dung’s argumentation framework. Section 4 presents our categorization of constraints and change in argumentation. We exemplify this categorization with state-of-the-art approaches, and motivate some kinds of change which have not been considered until now. Then, Section 5 explains how the quality of enforcement can be measured, in particular with some notions borrowed from belief change theory. Last, Section 6 concludes the paper and recalls the most interesting research tracks.

2.Argumentation system

2.1.General setting

An argumentation system is defined as a set of three components:

  • (1) an argumentation framework F, which generally consists in a set of arguments and in one or several relation(s) between them;

  • (2) a semantics σ that gives a formal definition of a method (either declarative or procedural) ruling the argument evaluation process;

  • (3) an argument evaluation σ(F), which is the result of the application of the semantics (component (2)) on the argumentation framework (component (1)).1

The argumentation framework and the semantics can be seen as the input of the system, the argument evaluation as the output. Figure 1 illustrates this structure.

Fig. 1.

Argumentation System.

Argumentation System.

As an example of an argumentation framework (component (1)), one may consider Dung’s framework [44], that consists in a set of abstract arguments A, the structure and the origin of which are left unspecified, along with an attack relation between arguments, RA×A. One may consider as well an extended version of this framework, such as: the bipolar argumentation framework (BAF) by Cayrol and Lagasquie-Schiex [29], that additionally takes into account a support relation between arguments; the preference-based argumentation framework (PAF) by Amgoud and Cayrol [6], that considers a preference relation which influences the success of attacks; the value-based argumentation framework (VAF) by Bench-Capon [16], related to the previous one, that attaches values to arguments and handles preferences over values; the constrained argumentation framework (CAF) by Coste-Marquis et al. [32], that adds a constraint over the set of arguments and the attack relation to be taken into account; the partial argumentation framework (denoted here ParAF to avoid confusion with PAF) of Coste-Marquis et al. [31], that takes into account ignorance about the existence of some attacks. Frameworks different from Dung’s one may be considered as well, such as the abstract dialectical framework (ADF) by Brewka and Woltran [25], that is based on a set of arguments and that attaches an acceptability condition to each argument.

A huge range of semantics (component (2)) have been defined so far (see Baroni et al. [8] for an overview). They can be classified into three categories: extension-based semantics (e.g. Dung [44]), labelling-based semantics (e.g. Caminada [26]), and ranking-based semantics (e.g. Amgoud and Ben-Naim [3]). A semantics is usually defined for a certain kind of argumentation framework. When applied to an appropriate argumentation framework (component (1)): an extension-based semantics produces a set of extensions (component (3)), that is, a set of sets of collectively acceptable arguments; a labelling-based semantics produces a set of labellings (component (3)), that is, assignments to each argument of a label from a predefined set, e.g. {in,out,undec}, which indicates whether the argument is acceptable (in), or not acceptable (out), or whether its status is undecided (undec); a ranking-based semantics produces a pre-order over the set of arguments. Evaluation principles that underlie most of the existing semantics have been identified (e.g. Baroni and Giacomin [9] for extension-based semantics, Baroni et al. [11] for ranking-based semantics). For instance, extension-based semantics are supposed to satisfy conflict-freeness (i.e. two arguments cannot belong to the same extension if they are conflicting), while ranking-based semantics are supposed to satisfy maximality (if an argument is not attacked, then it should be maximally acceptable).

Each of the three components of an argumentation system may be subject to some dynamics: some constraint may have to be enforced on one or several of them, and the enforcement generally causes changes on the system. Such constraints and changes are presented in Section 4.

2.2.Dung’s framework

We have briefly described Dung’s framework [44] previously. Since it is one of the most known setting for abstract argumentation, it is now presented more formally.

Definition 1

Definition 1([44]).

Let A be a finite set of abstract entities called arguments. The argumentation framework built on A is the pair F=A,R, with RA×A the attack relation between arguments.

Given a,bA, we say that a attacks b if (a,b)R. This definition can be extended: a set SA attacks b if aS such that a attacks b. On the opposite, if b is an argument attacked by the argument c, then the argument a (respectively the set of arguments S) defends b against c if a (respectively S) attacks c.

An argumentation framework is a directed graph, whose vertices are the arguments and whose edges are the elements of R.

Example 1.

Figure 2 describes an argumentation framework F=A,R, where A={a1,a2,a3,a4,a5,a6,a7} and R={(a1,a2),(a2,a3),(a3,a4),(a4,a3),(a4,a5),(a5,a6),(a6,a7),(a7,a5)}.

Fig. 2.

An Example of Argumentation Framework F.

An Example of Argumentation Framework F.

Given an argumentation framework, the acceptance status of arguments can be evaluated by applying several semantics. The three families of semantics which have been briefly described in the previous section are now more formally presented.

Extension-based semantics. A popular way to evaluate arguments is based on extensions, which are sets of arguments that can be jointly accepted. The different extension-based semantics correspond to different properties required to accept a set of arguments. Most of extension-based semantics select the extensions among the admissible sets.

Definition 2

Definition 2([44]).

Let F=A,R be an argumentation framework. A set of arguments SA is:

  • conflict-free if a,bS,(a,b)R;

  • admissible if it is conflict-free and aS, S defends a against each attacker;

  • a complete extension if S is admissible and contains each argument that it defends;

  • a preferred extension if S is a maximal (with respect to ⊆) admissible set;

  • a stable extension if S is conflict-free and attacks each argument in AS;

  • the single grounded extension if S is the minimal (with respect to ⊆) complete extension.

Moreover, when a set of extensions σ(F) is obtained from an argumentation framework for a given semantics σ, we can define:
  • the set of credulously accepted arguments credσ(F)=Eσ(F)E;

  • the set of skeptically accepted arguments skepσ(F)=Eσ(F)E.

Numerous other extension-based semantics have been defined. An extension under a semantics σ is called a σ-extension. For σ a semantics and F an argumentation framework, σ(F) is the set of σextensions of F.

Example 2.

The extensions of the argumentation framework F of Fig. 2, with respect to the grounded, stable, preferred and complete semantics, are given in Table 1, along with the sets of credulously and skeptically accepted arguments.

Table 1

The Set of Extensions σ(F), the Credulous credσ(F) and Skeptical skepσ(F) Acceptance Statuses for F, w.r.t. Semantics σ

Semantics σσ(F)credσ(F)skepσ(F)
grounded{{a1}}{a1}{a1}
stable{{a1,a4,a6}}{a1,a4,a6}{a1,a4,a6}
preferred{{a1,a4,a6},{a1,a3}}{a1,a3,a4,a6}{a1}
complete{{a1,a4,a6},{a1,a3},{a1}}{a1,a3,a4,a6}{a1}

Labelling-based semantics. A second view on the evaluation of arguments is based on 3-valued labellings introduced in Caminada [26], and further developed in [27].

Definition 3.

Let F=A,R be an argumentation framework. A labelling on F is a mapping from A to {in,undec,out}. A labelling is said to be admissible if, for every argument aR,

  • if a is labelled in then all its attackers are labelled out;

  • if a is labelled out then at least one of its attackers is labelled in.

This definition of admissibility is not equivalent to admissibility for extensions, since there may be more admissible labellings than admissible extensions. However, for the semantics which are based on completeness, the labelling approach can be seen as a refinement of the extension-based semantics.

While an extension only allows to decide if an argument is accepted or not, a labelling permits to assign an “intermediate” status to arguments: intuitively, an argument is undecided if it cannot be accepted and there are not enough reasons to reject it.

Definition 4

Definition 4([26]).

Let F=A,R be an argumentation framework. Given an extension-based semantics σ, and S a σ-extension of F, the labelling

ainif aSaoutif bS such that (b,a)Raundecotherwise
is a σ-labelling. Given such a labelling L, in(L)={aAL(a)=in}, and similarly for out(L) and undec(L).

Example 3.

Let us consider again the argumentation framework F of Fig. 2. Its labellings, with respect to the grounded, stable, preferred and complete semantics, are given in Table 2.

Table 2

Labellings on F w.r.t. to the Grounded, Stable, Preferred and Complete Semantics

Semantics σin(L)undec(L)out(L)
grounded{a1}{a3,a4,a5,a6,a7}{a2}
stable{a1,a4,a6}{a2,a3,a5,a7}
preferred{a1,a4,a6}{a2,a3,a5,a7}
{a1,a3}{a5,a6,a7}{a2,a4}
complete{a1,a4,a6}{a2,a3,a5,a7}
{a1,a3}{a5,a6,a7}{a2,a4}
{a1}{a3,a4,a5,a6,a7}{a2}

Ranking-based and graded semantics. Finally, a more gradual way to determine the acceptability of arguments has been proposed. Instead of assigning each argument a value in a finite set (binary set in the case of extensions, or ternary set in the case of labellings), it is possible to compare the arguments to determine which ones are more acceptable than the other ones. Two methods have been proposed in the literature: either arguments are mapped to a numerical acceptability degree, as, for instance in Amgoud and Ben-Naim [4,5] (e.g. a value between 0 and 1; the closer to 1, the higher the acceptability of the argument), or a ranking between the arguments is mapped to the argumentation graph, as, for instance in Bonzon et al. [23].

Definition 5.

A gradual acceptability semantics associates to an argumentation framework F=A,R a function Deg:A[0,1]. A ranking-based acceptability semantics associates to an argumentation framework F=A,R a pre-order on A, i.e. a reflexive and transitive binary relation on A.

Let us notice that every gradual acceptability semantics yields a ranking-based semantics (the natural order of real numbers in [0,1] can be used to define the pre-order between arguments); for this reason, gradual acceptability semantics and ranking-based semantics are generally considered as the same family of semantics.

There are many different ranking-based and graded semantics. A recent overview is presented by Delobelle [36]. Here we give an example borrowed from [36].

Example 4.

Let F=A,R be an argumentation framework. For aA, Att(a)={bA(b,a)R} is the set of attackers of A. The categoriser function Cat:A]0,1], by Besnard and Hunter [17], is defined by

Cat(a)=1if Att(a)=11+bAtt(a)Cat(b)otherwise

[17] defines a ranking from the categoriser function, when the argumentation framework is a tree. Pu et al. [62] have proved that this semantics always yields a (unique) result for any argumentation framework. The categoriser ranking-based semantics associates to any argumentation framework F=A,R a ranking FCat on A such that, a,bA:

aFCatbif and only ifCat(a)Cat(b)

Figure 3 describes an argumentation framework F. The real numbers and fractions on the figure correspond to the categoriser value of each argument.

Fig. 3.

An Example of Argumentation Framework F.

An Example of Argumentation Framework F′.

Then, the ranking of arguments is given at Fig. 4; the higher an argument, the more acceptable it is. This ranking defines σ(F). If we want to define a graded semantics instead of a ranking-based semantics, then σ(F)={(a,Cat(a))aA}.

Fig. 4.

The Ranking of Arguments FCat.

The Ranking of Arguments ⩽F′Cat.

3.Main approaches on change in argumentation frameworks

In this section, we briefly describe the existing approaches on the topic of change in Dung’s argumentation framework.

3.1.Elementary changes

We call an elementary change in an argumentation framework the addition (or removal) of atomic elements of the framework. An elementary change captures some structural dynamics.

In the case of Dung’s framework, an atomic element means either an attack, or an argument (with the set of attacks concerning it). Boella et al. [21,22], Cayrol and colleagues [19,28], study the effects of such a change, depending on the semantics. In these papers, the authors study the consequences on the set of extensions of a particular change on the structure of the graph.

In the works by Boella et al. [21,22], these elementary changes are called refinement and abstraction, which are respectively the addition and the removal of an atomic element.

Definition 6

Definition 6([21,22]).

Let F=A,R and F=A,R be two argumentation frameworks.

  • F is an argument refinement from F if and only if AA, and ai,ajA,(ai,aj)R only if (ai,aj)R.

  • F is an attack refinement from F if and only if A=A and RR.

  • F is an argument-attack refinement from F if and only if AA and RR.

  • F is an argument abstraction from F if and only if AA, and ai,ajA,(ai,aj)R only if (ai,aj)R.

  • F is an attack abstraction from F if and only if A=A and RR.

  • F is an argument-attack abstraction from F if and only if AA and RR.

For both kinds of operations, a set of principles is defined, which are properties of the form “If an argument (or an attack) is removed (or added), such that a given property P1 is satisfied, then the outcome of the argumentation framework satisfies P2”. Concretely, in the papers about refinement and abstraction, the outcome which is considered is the single grounded labelling of the argumentation framework, and the property P2 expresses a relation between the outcome of F and the outcome of F.

For a matter of illustration, we give here the first Principle proposed in [21]. We reformulate it to be consistent with our notations and terminology.

Attack Abstraction

A labelling-based semantics satisfies the x,y attack abstraction principle, with x,y{in,undec,out}, if for every argumentation framework F=A,R, ax(F),by(F), in(A,R{(a,b)})=in(F).

Since this work considers single extension semantics, in(F) (respectively undec(F), out(F)) is the set of arguments which are accepted (respectively undecided, rejected) with respect to the single labelling of F. This principle is abstract, and can be instanciated by fixing the values of x and y. It means that if an attack (a,b) is removed from an argumentation framework, such that a has the status x and b has the status y, then the set of accepted arguments does not change. The satisfaction of this principle depends on the values of x and y, and on the choice of a semantics. For instance, [21] states that the undec,in attack abstraction principle is satisfied by the grounded semantics, but not by the skeptical preferred semantics.

Then, Cayrol and colleagues [19,28] have studied a similar topic. Herein, refinement and abstraction are defined as addition and removal operators.

Definition 7

Definition 7([19,28]).

Let F=A,R be an argumentation framework. The following change operations are defined:

  • the addition of an attack (ai,aj) with aiA and ajA is defined by Fi(ai,aj)=A,R{(ai,aj)};

  • the removal of an attack (ai,aj) with aiA, ajA and (ai,aj)R is defined by Fi(ai,aj)=A,R{(ai,aj)};

  • the addition of an argument akA with a set of attacks concerning it, noted Rak, is defined by Fia(ak,Rak)=A{ak},RRak. We suppose that Rak is a non-empty set of attacks concerning ak, meaning that Rak(A{ak})×(A{ak}) such that (al,am)Rak, al=ak or am=ak;

  • the removal of an argument akA with the attacks concerning it is defined by Fia(ak,Rak)=A{ak},RRak; Rak is defined as the set {(ak,al)R}{(al,ak)R}.

Cayrol and colleagues focus on addition of an argument ia [28] and removal of an argument ia [19]. For both operations, they propose some properties about the structure2 of the set of extensions which may hold or not, and they study which of them are satisfied for some of Dung’s semantics. For instance, a change is called decisive if the original argumentation framework admits more than one extension, or no extension, or only the empty set, and if the result of the change admits exactly one non-empty extension. They classify exhaustively the impact that a change can have on the set of extensions, and they state which properties hold (or do not hold) for ia and ia for some of Dung’s semantics.

In Liao et al. [55] and in Baroni et al. [10], the change which can be performed in the argumentation framework is a composition of the elementary changes defined in [28]. The main contribution of this paper is a division method to partition the set of arguments in two: the part which is affected by the change, and the part which is unaffected. Then, computing the new extensions is less costly from a computational point of view, since only the statuses of the affected argument should be computed, the other ones remaining the same as before the change. The recent work by Alfano et al. [2] shares the same intuition.

The approaches presented in this section are summarized in Table 3 in Section 6, taking into account the typology that will be presented in Section 4 and the criteria of Section 5.

3.2.Extension enforcement

Enforcing a set of arguments as an extension is a modification of an argumentation framework F into an argumentation framework F such that a given set of arguments S is an extension (which is called strict enforcement) or is included in an extension (which is called non-strict enforcement) of F.

These concepts have first been defined in Baumann and Brewka [14]. In that paper, it is supposed that the new argumentation framework can only be obtained from a “classical” debate, which admits the rule that all the arguments previously stated and the attacks concerning them are fixed. So it is only possible to add new arguments and attacks which concern at least one new argument, but there is no change in the attack relation between previous arguments. This change is called a normal expansion.3 Two particular types of normal expansions are also defined: the strong expansion only adds strong arguments, which are arguments unattacked by the previous arguments; and the weak expansion, on the opposite, only adds weak arguments, which cannot attack the previous ones.

Example 5.

We present here an example of strong enforcement as defined in [14]. When the stable semantics is considered, the argumentation framework F given in Fig. 5(a) has exactly one extension {a1,a4}. If the goal of the agent is to enforce E={a2,a3} (i.e. to ensure that E becomes (included in) an extension), a possible solution is to add an argument b which attacks a1 (see Fig. 5(b)). In this case, there is a single extension {b,a2,a3}. This enforcement is non-strict, because E is included in an extension, but E is not an extension.

Fig. 5.

Strong Enforcement of an Extension.

Strong Enforcement of an Extension.

In Baumann [12], minimal change enforcement is studied. Here, minimal change is the minimization of the number of attacks which are added during the expansion process. Baumann gives a way to compute, for a given argumentation framework, a set of arguments, a semantics, and the sort of expansion which is used, the minimal number of attacks to add to perform the enforcement. This number is 0 if the set is already enforced, + if it is impossible, and a strictly positive natural number otherwise.

Coste-Marquis et al. [35] propose new enforcement approaches, called argument-fixed enforcement and general enforcement, which are more related to belief revision process than to classical dialogue. Here, the hypothesis is that the agent may be unable to add new arguments, then the only way to perform the enforcement is to consider that previous attacks are questionable, and so to change some of them; this is the argument-fixed enforcement. The general enforcement combines this possibility to change the attacks with the possibility to add arguments. Now minimal change is the minimization of the number of attacks which are added or removed. A logical encoding is proposed for each of the enforcement approaches, and an implementation via the Pseudo-Boolean optimization paradigm is proposed.

Example 6

Example 6(Continuation of Example 5).

Instead of adding a new argument b to enforce E={a2,a3}, the solution prescribed by [35] is to add an attack from a2 to a1, as described in Fig. 6. With this solution, the new argumentation framework has two stable extensions: one is the initial extension {a1,a4}, and the other one is exactly E={a2,a3}.

Fig. 6.

Argument-Fixed Enforcement of an Extension.

Argument-Fixed Enforcement of an Extension.

Wallner et al. [66] study the complexity of extension enforcement, focusing mainly on the argument-fixed enforcement defined in [35]. The logic-based approach previously proposed by [35] is pushed forward: methods based on MaxSAT and CEGAR (Clarke et al. [30]) are proposed, respectively for the NP-complete and Σ2P-complete variants of the problem.

“Classical” enforcement operators take as input an argumentation framework F=A,R and a set of arguments SA; their outcome is an argumentation framework F such that S is (included in) a σ-extension of F. In this context, the semantics σ is usually supposed to be fixed. While Baumann and Brewka [14] propose the notion of liberal enforcement (the semantics after performing the enforcement could be different from the semantics before the enforcement), they do not discuss why the semantics could be modified, nor how the new semantics could be chosen. Doutre and Mailly [42] propose to generalize the definition of enforcement operators. In this paper, it is proposed to define enforcement operators which take as input F, S, but also a set of semantics Σ, and σΣ the initial semantics. Then, the outcome of the enforcement operator is made of F and σΣ, such that S is (included in) a σ-extension of F, and σ is as close as possible to σ (where the closeness between semantics is measured with distances proposed by Doutre and Mailly [41]). The intuition behind this generalization of enforcement operators is that semantic change can guarantee the success of enforcement with less syntactical modifications of the argumentation framework than “classical” enforcement.

Example 7.

We illustrate the usefulness of changing the semantics. Let us consider the argumentation framework F given in Fig. 7. If the agent uses the stable semantics, is has only one extension st(F)={{a1,a4,a6}}. When the goal of the agent is to enforce E={a1,a3}, all the enforcement approaches which do not change the semantics (Baumann and Brewka [14], Coste-Marquis et al. [35]) need to modify the graph. But if the agent is authorized to modify the semantics, E can be enforced without any modification of the graph, since pr(F)={{a1,a3},{a1,a4,a6}}.

Fig. 7.

Enforcement of an Extension with Semantic Change.

Enforcement of an Extension with Semantic Change.

Finally, a recent approach extends extension enforcement with a notion of uncertainty. Control Argumentation Frameworks (CAFs), by Dimopoulos et al. [38], are a generalization of Dung’s argumentation frameworks, where the arguments are divided into three parts: the fixed part (arguments which are not subject to the evolution of the environment nor the agent’s behaviour), the uncertain part (the arguments which are influenced by the environment) and the control part (the arguments which depend on the agent’s behaviour). Similarly, the attacks are split into fixed attacks and uncertain attacks (which may or may not actually exist, depending on the context). The goal of an agent using such a CAF is to select a subset of the control argument such that, whatever happens in the uncertain part, a subset of the fixed arguments (called the target) is accepted. [38] proves that this reasoning task generalizes extension enforcement.

A summary of the approaches presented in this section, in the light of the typology that will be presented in Section 4 and of the possible enforcement quality criteria of Section 5, is shown in Table 4 in Section 6.

3.3.Change in argumentation through belief update

In a logical setting, belief update is the incorporation in an agent’s beliefs of a new piece of information which expresses some evolution of the world. Two different contributions have benefited from the properties of logical belief update to define update operators for argumentation frameworks.

In Dupin de Saint-Cyr et al. [46], the authors propose to translate the argumentation frameworks and the meaningful information (like arguments statuses) into a formula from a logical language called YALLA, and to use logical update operators to perform the change. They propose an adaptation of the classical rationality postulates for belief update (Katsuno and Mendelzon [52]) which takes into account a notion of possible transition: some changes from a possible world, represented by an argumentation framework, to another one, may be impossible. Then the update operator has to respect a set of authorized transitions T. A refinement of the notion of faithful assignment allows to define the assignment respecting T, which are used in a representation theorem to define the class of update operators which satisfy the postulates.

Doutre et al. [39] also propose to translate the argumentation framework and the semantics into logic, to perform the update. In this case, the Dynamic Logic of Propositional Assignments, by Herzig and colleagues [7,50], is used to represent update operators as executable programs. The piece of information which causes the update is a formula ϕ about acceptance statuses, which should be satisfied by at least one extension of the result (credulous enforcement of ϕ) or by each extension of the result (skeptical enforcement of ϕ). Forbus’ update operator is used to change minimally the attack relation such that the extensions of the new argumentation framework comply with the expected enforcement. Doutre et al. [40] extend [39], by considering also addition and removal of arguments.

Table 5 in Section 6 sums up these approaches, in the light of the typology that will be presented in Section 4 and of the possible enforcement quality criteria of Section 5.

3.4.Change in argumentation through belief revision

At a high level, belief revision has the same goal as belief update: the incorporation of a new piece of information in the agent’s beliefs. But the difference between update and revision is that, in the second case, the new piece of information does not express an evolution of the world, it only expresses an evolution of the agent’s beliefs. Roughly speaking, it means that the agent was making a mistake, the new piece of information aims at correcting this mistake. Similarly to belief update, belief revision has been used to propose several original approaches to revise argumentation frameworks.

In Booth et al. [24], it is considered that the belief state of an agent is composed of a Dung’s argumentation framework F and a propositional formula which represents a constraint which should be satisfied by the complete labellings of F. In the case when the argumentation framework and the constraint are not consistent with each other (meaning that no complete labelling of F satisfies the constraint), two methods are proposed to restore the consistency. First, the authors have proven that it is possible to perform a normal expansion (in the spirit of Baumann and Brewka [14]) of F which is consistent with the constraint. But in this case, there is no direct relation between the original set of complete labellings and the new one. With the second approach, belief revision techniques are used to obtain a new set of complete labellings which satisfy the constraint and which are as close as possible to the original ones.

A direct adaptation of Katsuno and Mendelzon’s (KM) revision [51] has been proposed in Coste-Marquis et al. [33]. In the logical setting, the rationality postulates express constraints to be satisfied by the models of the revised formula, and the revision operators are represented by some particular pre-order between propositional interpretations. The adaptation of KM revision for abstract argumentation proposes rationality postulates which express conditions to be satisfied by the extensions of the revised argumentation frameworks, and now the revision operators are represented by pre-orders between extensions. In this first work on extension-based revision, the result of the revision is a set of argumentation frameworks. Diller et al. [37] refine this work to ensure that the result of the revision is a single argumentation framework. Intuitively, the idea is that the pre-order between extensions must be compliant with the semantics σ, which means that the best extensions with respect to this pre-order must be σ-realizable (Dunne et al. [45]). Linsbichler and Woltran [56] adapt this approach for Abstract Dialectical Frameworks (Brewka and Woltran [25]).

In Coste-Marquis et al. [34], the idea is similar to what has been proposed for belief update. A logical encoding permits to represent the links between the structure of the argumentation framework and the evaluation with respect to the semantics (here in particular, the evaluation is given by the skeptical acceptance statuses). Then a KM revision operator is used to obtain the result. It is possible to revise an argumentation framework by a formula which expresses some information about acceptance statuses and the attack relation at the same time.

Nouioua and Würbel [60] propose a syntactic revision approach, inspired by Papini [61] and Würbel et al. [67]. This approach is only suitable for reasoning with stable semantics. In a nutshell, the revision approach considers an input framework F=A,R and a new piece of information represented by the framework F=A,R. Each of them are supposed to be consistent, meaning that they admit at least one stable extension. If their union FF=AA,RR is also consistent, then it is kept as the result of the revision. It is the counterpart of the equivalence between belief revision and belief expansion when the input belief base and the new piece of information are consistent with each other. In the remaining case, some attacks must be dropped from R to obtain a consistent argumentation framework.

Finally, Baumann and Brewka [15] define a new family of logics, called Dung-logics, which are built from a language which is a set of argumentation frameworks and a consequence relation between argumentation frameworks. The authors have shown that it is possible to adapt the rationality postulates for expansion and revision from Alchourrón, Gärdenfors, and Makinson (AGM) [1] in the setting of Dung-logics, and they exhibit some operators which satisfy these postulates.

A summary of the approaches presented in this section, in the light of the typology that will be presented in Section 4 and of the possible enforcement quality criteria of Section 5, is shown in Table 6 in Section 6.

3.5.Other kinds of approaches

In [63], Rienstra states a parallel between the notion of intervention and observation in causal networks with change in argumentation frameworks. Intuitively, when an intervention occurs it means that the agent has performed an action to reach a given goal, and when an observation occurs the agent learns that some change happened, but she does not know exactly which change. So, for instance, if the agent realizes an intervention to reject an argument a, it means that she has added an unattacked argument b which attacks a. On the opposite, if she observes that a is now rejected, she can deduce that an argument has been added somewhere in the graph, but she does not know exactly where. Rienstra defines non-monotonic inference relations from these processes, and studies their properties (Kraus et al. [54]).

In Kontarinis et al. [53], the setting is a dialogue between agents, where each of them has a goal expressed in term of acceptance statuses of some arguments. The aim is to define which move (so which addition or removal of argument or attack) should be played to ensure that the agent will reach her goal.

Finally, Baumann [13] studies the notion of update and deletion in argumentation frameworks. Deletions are somehow the negative counterpart of expansions [14], while updates are a more general category of change, which includes both expansions and deletions. Updates defined by Baumann are different from the approaches based on belief update [39,46]. Let us mention that, contrary to expansions, the use of deletions for extension enforcement has not been considered yet.

The approaches of this section are summarized in Table 7 in Section 6, in the light of the typology that will be presented in the next section and of the possible enforcement quality criteria of Section 5.

4.Constraints

This section presents the different kinds of constraints that can be considered in an argumentation system, and the changes that their enforcement implies. This typology aims at being general enough to concern any kind of argumentation system, not only Dung’s framework. Since the existing works on this topic consider Dung’s framework, we will illustrate the different kinds of constraints and changes with these examples, but we also sketch some constraints and changes which make sense for other settings.

4.1.Structural constraints

The first kind of constraint that may have to be taken into account, concerns the argumentation framework (component 1 in Fig. 1). Typically, when an argumentation-based debate takes place between agents, new arguments, new attacks, may have to be additionally considered. These new elements concern the structure of the argumentation framework, and represent constraints that must be taken into account. For this reason, we call them structural constraints.

If these constraints directly concern the elements of the argumentation framework, namely the arguments and the relations between arguments, they may be called elementary structural constraints. Other structural constraints may address the whole structure of the argumentation framework; these constraints are global structural constraints. As an example of such global constraints, one may wish the argumentation framework to be acyclic, or without any odd length cycle, or to be made of only one connected component. The need for such global constraints may be motivated by computational concerns: it is known that argument evaluation, under some semantics, for argumentation frameworks with particular properties, are easier to compute than for argumentation frameworks without these properties. For instance, we know that Dung’s argumentation frameworks possess a single extension which is grounded, stable, preferred and complete when they are acyclic; similarly, the stable semantics and the preferred semantics coincide when the argumentation framework does not contain any odd length cycle. When these properties are satisfied, reasoning with argumentation frameworks is tractable (in the case of acyclic argumentation frameworks), or at worst at the first level of the polynomial hierarchy instead of the second level (when the preferred semantics is used).

As far as we know, only elementary structural constraints have been studied in the existing approaches on change in argumentation systems, although some of them could be easily adapted to tackle global constraints. For instance, as said previously, Cayrol et al. [28] list the elementary constraints existing in Dung’s framework: adding or removing one attack between two arguments which belong to the framework, and adding or removing an argument (with the attacks which concern it). The existing approaches on change in argumentation use these kinds of constraints, or combination of them. For instance, the logical encodings which are proposed in Bisquert et al. [20], Doutre and colleagues [39,40], Coste-Marquis et al. [34], allow to use formulae which can represent constraints like “an attack from a to c and an attack from c to b must be added”. This kind of logical language allows to combine elementary constraints to express more complex ones.

The enforcement of a structural constraint on an argumentation framework F obviously leads to a change of the argumentation framework (what we call a structural change), to an argumentation framework F, but it may also impact the argument evaluation (acceptability change): σ(F) may be different from σ(F). For example, if one considers Dung’s framework, an argument which was previously attacked may become unattacked after the enforcement of the semantics. If one would like, however, the argument evaluation to keep the same, then the structural constraint would have to be accompanied with an acceptability constraint (see Section 4.2), which would require the evaluation to be the same. Cayrol et al. [28] propose a typology of the acceptability changes induced by the enforcement of some elementary structural constraints.

Structural constraints also make sense if extended versions of Dung’s framework are considered. For instance, any kind of attack-addition or attack-removal operation can have a support-addition or support-removal counterpart when considering bipolar argumentation frameworks (Cayrol and Lagasquie-Schiex [29]). If we work with preference-based argumentation framework (Amgoud and Cayrol [6]) or value-based argumentation frameworks (Bench-Capon [16]), then a change of the preference relation between arguments or between the values can occur. In this last case, there can also be directly a change of the values associated to the arguments. Structural constraints in such frameworks remain to be formally investigated.

4.2.Acceptability constraints

The dynamics of an argumentation framework may also originate in a need for a change of the argument evaluation. For example, an agent may want another one to consider an argument as acceptable, or to consider it “better” than another one, whereas it currently is not the case. This is what we call an acceptability constraint that has to be enforced on an argumentation system (component (3) in Fig. 1). This acceptability constraint depends on the kind of evaluation which is used, among the extension-based semantics, the labelling-based semantics and the ranking-based semantics. For each of these evaluation approaches, several kinds of constraints make sense.

Extension-based semantics are maybe the most well-known method for argument evaluation (Dung [44]). The first work on acceptability constraints was extension enforcement, which tackled the problem of modifying an argumentation framework to ensure that a given set of arguments becomes an extension for the chosen semantics (Baumann and Brewka [14]). Coste-Marquis and colleagues, in two different approaches ([32] and [33]) express the acceptability constraint as a propositional formula over the set of arguments, which has to be satisfied by each extension of the argumentation framework. The same approach is developed by Diller et al. [37], who also propose to represent this acceptability constraint by an argumentation framework F such that the extensions of the outcome of the enforcement are a subset of σ(F). In Bisquert et al. [20], Doutre et al. [39] and Coste-Marquis et al. [34], it is possible to express a constraint on the acceptance status of an argument, such that “argument a must be credulously (or skeptically) accepted”, credulous (resp. skeptical) acceptance meaning that a must belong to at least one (resp. every) extension. Like structural constraints, acceptability constraints can be categorized into elementary acceptability constraints, that concern the particular acceptability of some arguments, or of some sets of arguments, and global acceptability constraints, that concern the structure of the argument evaluation (number of extensions, size of the extensions, for instance).

The same kind of acceptability constraints can be considered for labelling-based semantics, since they are a refinement of the extension-based semantics, but with more expressivity. For instance, it is possible to require an argument evaluation to satisfy the constraint “argument a must be out”, which is more precise than requiring an argument not to belong to an extension (since in this case, the argument may be either out or undecided). Such labelling-based constraints are considered by Booth et al. [24] and by Mailly [57].

Ranking-based semantics are also subject to “acceptability” constraints. In this case, it is more accurate to speak about “evaluation” constraint, since these semantics do not lead to decide if an argument is accepted or not. Several levels of constraints can be defined. It makes sense to enforce a constraint such that “argument ai is ranked lower than argument aj is true in the outcome of the enforcement”. These constraints, of course, can be combined together for different values of ai,aj, and these combinations may lead to require the argument evaluation to be exactly a given order when each possible pair (ai,aj) is considered.4 Up to our knowledge, the characterization and the enforcement of such evaluation constraints have not yet been addressed.

Regarding the enforcement of an acceptability constraint, the most common method that can be found in the literature consists in changing the argumentation system so that the argument evaluation of the modified system satisfies the constraint; this is structural change. Another possible method for such an enforcement is semantic change.

For instance, Baumann and Brewka [14] and Baumann [12] expand an argumentation framework à la Dung by a set of new arguments and a set of new attacks concerning these new arguments (and possibly the former ones). These approaches also consider the possibility to change the semantics, even if it is not explained why the semantics should change, nor how the new semantics is selected. The work presented by Coste-Marquis et al. [35] is a follow-up of the previous ones, in which arbitrary modifications of the structure of the graph are allowed. The revision approach described by Coste-Marquis et al. [33] and Doutre et al. [39] only permits to change the attack relation to satisfy the constraint, while Coste-Marquis et al. [34] and Doutre et al. [40] also propose an extended approach which allows to add arguments. In other words, the enforcement is done by a structural change. We recall that Booth et al. [24] proposes two approaches to satisfy the acceptability constraint. This extension of Dung’s framework uses a propositional formula on labellings as an integrity constraint, and considers that the agent’s beliefs are the complete labellings of the argumentation framework which satisfy this integrity constraint. Both approaches are used to restore consistency if there is no complete labelling of the framework which satisfies the integrity constraint. The first one is similar to the extension enforcement described by Baumann and Brewka [14]. The other one also uses framework expansion, but is a bit more subtle. It takes advantage of belief revision techniques to compute what is called the “fallback beliefs”, which are a consistent subset of the current agent beliefs which are the most plausible. Then a framework expansion is performed to match these fallback beliefs.

Doutre and Mailly [42] combine structural change and semantic change to perform the extension enforcement. Here, semantic change is a mean to minimize the number of changes required on the structure of the graph. It can be noticed that the enforcement of an acceptability constraint, by a semantic change only, has not yet been addressed. Such an enforcement may however be relevant in case where a structural change is not possible, or nor suitable.

The resulting argumentation system after the enforcement of an acceptability constraint may be such that the initial argumentation framework F is modified into an F (structural change), and/or the initial semantics σ has turned into a σ (semantic change). In any case, there is an acceptability change, that captures the enforcement of the acceptability constraint, but that may also partly result from the structural/semantic change which has been set up to enforce the acceptability constraint. For example, if an acceptability constraint consists in requiring that “argument a belongs to every extension”, a structural change that consists in removing all the attacks to this argument, may be carried out; but with this new status, a may now be able to make other arguments to belong to some or every extensions: additional acceptability changes hence occur. Minimizing the impact of the enforcement of an acceptability constraint, is a quality requirement that has already been addressed in several contributions; this issue is addressed in Section 5.

Another method to enforce an acceptability constraint consists in using an integrity constraint. Such an approach has been proposed in Coste-Marquis et al. [32]. In this extension of Dung’s framework (called CAF, for Constrained Argumentation Framework), the constraint is a propositional formula on the extensions of the framework. Contrary to Booth et al. [24], this constraint does not lead to a change of the argumentation framework. The semantics which have been defined for, and which have to be used with a CAF, take into account the integrity constraint, and ensure that it is satisfied in the argument evaluation.

As far as we know, ranking-based semantics have not been considered yet in the studies on acceptability constraint. However, it makes sense to consider constraints like “argument a should me more acceptable than argument b”, or “argument a should be the most acceptable argument with respect to the ranking”. For instance, we come back to Example 4. We recall that a1,a5,a6 are the maximally accepted arguments of the argumentation framework F with respect to the categoriser semantics. If a constraint “a1 should be strictly more acceptable than a5” has to be enforced, several options can be considered. Similarly to what is done with extension-based semantics, the goal can be reached through modifications of the argumentation framework itself (e.g. adding an attack from a1 to a5), some change of the semantics itself, or a combination of both kinds of changes.

4.3.Semantic constraints

Now, let us focus on the constraints dealing with component (2) of the argumentation system (Fig. 1): its semantics. We have seen in the previous section that a semantic change is a way to enforce an acceptability constraint. It may as well be the case that an agent may want a semantics to change, wholly, or partly; that is, the agent may want a semantic constraint to be enforced.

The motivations for such constraints are diverse. For instance, the case of the empty set of extensions, which is permitted for some semantics (the stable semantics for example), may be a weakness for some applications which absolutely require a solution. This may lead to a semantic constraint such that “replace the stable semantics by the complete semantics” (the complete semantics ensuring that there exists always at least one extension, may it be the empty set). On the other hand, we know that the number of extensions may be exponential in the number of arguments for some semantics. This may be a problem from a computational point of view to enumerate an exponential number of extensions. Some applications may also need a “simple” answer, and so it makes sense to replace the semantics σ by another one σ which guarantees that |σ(F)|<|σ(F)|. The extreme scenario is to require a single extension in the evaluation of the system (which can be obtained e.g. by a replacement of σ by the grounded or ideal semantics).

The semantic constraint may concern the semantics on its whole (as indicated in the previous paragraph). But a more elaborated kind of semantic constraint can be defined, dealing with the semantics principles: if some of the principles of the semantics cause a problem (from a computational or a reasoning point of view) they can be dropped. On the opposite, the agent can consider that her reasoning scheme is not demanding enough, and add some principle to its current semantics. For instance, the maximality principle may be too costly to compute, and then should be relaxed, while the principle that ensures that each argument which is not in an extension is rejected for a good reason, may be required.

The enforcement of a semantic constraint results in a semantic change (the original semantics σ evolves to σ). This change may lead to an acceptability change, as it may have an impact on the argument evaluation (σ(F) may be different from σ(F)).

Few approaches study semantic constraint and semantic change in argumentation. First, Dvořák and Woltran [48] study the relative expressiveness of a wide range of usual acceptability semantics: they provide some translations from an argumentation framework à la Dung F and a semantics σ to a framework F and a semantics σ such that σ(F) and σ(F) satisfy some property. For instance, this translation is called “exact” if and only if σ(F)=σ(F), and “faithful” if each element from σ(F) is equal to an element from σ(F) plus some new arguments which belong to F but not to F. This study has been further developed in [47].

The framework described by Baumann and Brewka [14] and by Baumann [12] for the enforcement of a set of arguments, takes a semantics as a parameter; so the target set of arguments does not necessarily have to be (included in) a σ-extension of the expanded argumentation framework, but possibly (included in) a σ-extension. They distinguish “conservative” enforcement (if σ=σ) and “liberal” enforcement (if σσ).

Another existing work on semantic constraints is Dunne et al. [45]. The aim of this approach is to check if a set of sets of arguments E={ϵ1,,ϵn} can be the set of extensions of any argumentation framework F with respect to a given semantics σ. This property is the realizability of E with respect to σ. The authors identify some necessary and sufficient conditions, for some usual semantics, for such sets E to be realizable with respect to σ, and they prove that this test can be done in polynomial time for most of the usual semantics.

4.4.Combinations of constraints

Of course, the different kinds of constraints described previously can be combined with each other. It is already the case with realizibility checking (Dunne et al. [45]), which is the combination of a semantic constraint (the expected extension-based semantics σ is a parameter) and of an acceptability constraint (demanding a particular set of sets of arguments to be the σ-extensions). The work by Dvořák and Woltran [48] may also be seen as a combination of a semantic constraint, along with an acceptability constraint (the extensions under the new semantics should be in correspondence with the ones under the original one). Similarly, extension enforcement approaches by Baumann and Brewka [14] and Baumann [12] combine an acceptability constraint (the set of arguments expected to be included in an extension) and a semantic constraint. On the other hand, Bisquert et al. [20], Doutre et al. [39,40], and Coste-Marquis et al. [34], combine acceptability and structural constraints in their propositional language over the set of arguments.

It seems that in a dynamic context, any kind of constraints combination makes sense. It can be noticed however that a constraint such as “The structure of the argumentation graph (resp. the semantics, the argument evaluation) must not change” makes sense only when it is considered in combination with another constraint.

Semantic constraints are particularly meaningful when considered in combination with an acceptability constraint. It is possible that a particular acceptability constraint cannot be enforced, with respect to some given semantics. In this case, it makes sense to have a possibility to switch the semantics for another one which permits to enforce the acceptability constraint. To illustrate this case, let us consider an agent which uses the preferred semantics pr to reason with arguments. She can receive a full piece of information about the evaluation, leading to demand a set E={ϵ1,,ϵn} to be the extensions of her argumentation framework. But the direct enforcement of the constraint “Build F such that pr(F)=E” may lead to an error, since each set of extensions is not realizable for each semantics. A more elaborated constraint like “Build F such that σ(F)=E for some σ” allows to avoid this problem.

Combining semantic constraints and acceptability constraints also makes sense in the setting of ranking-based semantics. For instance, it can be desirable to change the semantics from an extension-based semantics to a ranking-based semantics such that a specific argument becomes the most acceptable one.

5.Quality of enforcement

Whatever be the kind of enforcement, some notion of quality can be considered. Among several possible solutions to the expected enforcement request, all of them are not equally satisfying for the agent. It can be expressed in several different ways.

5.1.Minimal change

The most obvious one is probably minimality of change, borrowed from belief change (AGM [1], Katsuno and Mendelzon [51]). In this framework, minimal change is a desirable property because an agent expects to avoid any unnecessary loss of information when performing a belief change. The notion of minimality is not obviously defined in argumentation settings. As we explained in the previous section, enforcement in argumentation frameworks deals with three different kinds of constraints and changes. So, we can consider at least one kind of minimality for each of these kinds of constraints and change.

Minimal change on the argument graph (minimal structural change) is the first kind of notion of quality which has been studied: Baumann [12] considers that the predominant information for the agent is the structure of the graph, and minimal change is expressed as the minimization of the number of attacks which are changed in the argumentation framework. The same kind of minimality is used by Doutre et al. [39] and Coste-Marquis et al. [34]. Minimization of the changes on the set of arguments, or on other components of the argumentation framework if any, may also be considered. It is not the case in any of the approaches presented here.

Another kind of minimality concerns the changes on the output of the argumentation system: acceptability of arguments. The different possibilities to express minimal acceptability change in this case depend on the different expressions of acceptability: skeptical acceptance, credulous acceptance, extension (or labellings) enumerations, rankings For instance, a possible approach, borrowed from the notion of minimal change in belief revision in propositional logic, considers the set of extensions of the argumentation framework and uses distances between sets of extensions to decide which possible output is the minimal one for the revision of an argumentation framework (Coste-Marquis et al. [33]), that is, which one enforces the acceptability constraint, and induces a minimal additional acceptability changes. Another possible approach to define minimal change on the acceptability is to use distances between sets of arguments, for instance to quantify the difference between the skeptically accepted arguments of two different argumentation frameworks (Coste-Marquis et al. [34]).

As far as we know, semantic change has been barely studied; for this reason, the question of minimal semantic change has only arisen recently. Doutre and Mailly [41] define difference measures between semantics, and determine which of them are distances. Different intuitions have conducted to the definition of these measures. The first one is that graphs, where the nodes represent the semantics, can be defined based on the relations between the sets of extensions corresponding to different semantics. For instance, it is well-known that the preferred extensions of an argumentation framework are always complete extensions, for this reason an arrow can link the preferred semantics to the complete semantics in the graph. Then, computing the difference measure between semantics consists in computing the length of the path between the semantics in the graph. Other relations between semantics can be used. Another family of difference measures uses characterizations of the semantics with sets of logical properties. The difference between semantics is defined as the distance between the sets of properties corresponding to them, i.e. the number of properties which must be added or removed to make these sets equals. Weights can be used to differentiate the importance of some properties (meaning that the agent is reluctant to remove from the semantics a property which has a high weight). Finally, a third family of difference measures is based on distances between the sets of extensions or (credulously or skeptically) accepted arguments which are generated by the different semantics. Contrary to the previous measures, these ones are based on a specific argumentation framework.

5.2.Combining minimality criteria

Then, a very interesting question is the possibility to combine different kinds of minimality when several different kinds of constraints and change are involved in the enforcement process. The underlying problem is to know what kind of information is the most important for the agent, and consequently, which kind of minimal change must be applied first.

For instance, Coste-Marquis et al. [33] consider that the primitive information for an agent reasoning with an argumentation framework is its set of extensions. Minimal acceptability change is thus applied first. Two other kinds of minimality are then considered. The first one is minimal structural change, in terms of changes on the set of attacks. The second one comes from the nature of the output of their revision operators. They consider possible to obtain of set of revised argumentation frameworks. It seems natural, in this case, to regard minimal cardinality of the output as a natural desirable property. These two kinds of minimality are combined to define different families of revision operators.

Coste-Marquis et al. [34] combine structural change (additions and removals of attacks or arguments) and acceptability change (the constraints concern the fact that an argument is skeptically accepted or not). Minimal change on the structure of the graph and minimal change on the set of skeptically accepted arguments are considered, and combined through some weighted Hamming-like distances to be able to give some priority to one of them.

5.3.Rationality postulates for constraint enforcement

As we already explained, minimal change has been borrowed from the belief change framework in logical settings. This principle is not the only desirable property for belief change operations. It is usual for these applications to define a set of rationality postulates to be satisfied by any “good” operator. The AGM framework [1] is a well-known framework at the ground of numerous contributions on this topic. For instance, Katsuno and Mendelzon [51] adapted the AGM postulates for finite propositional logic, and explained how to define a revision operator which satisfies the postulates.

This idea has been adapted for revision of argumentation frameworks. Coste-Marquis et al. [33] adapt the postulates and revision operators from Katsuno and Mendelzon (KM) framework to the setting of extension-based semantics. They express the constraints on the acceptability of arguments as set-theoretical relations between the set of extensions of the argumentation framework, and they define the family of operators which satisfy these postulates. As previously mentioned, the same authors consider in [34] some revision operators dealing with structural and acceptability constraints, but they explain that a particular restriction on the definition of such a revision operator ensures that it satisfies another adaptation of the KM postulates. Some similar AGM-like family of rationality postulates have been described by Doutre et al. [39], Baumann and Brewka [15], Diller et al. [37] and Linsbichler and Woltran [56].

Katsuno and Mendelzon have also studied the update operation [52]. This operation is close to belief revision, but it is useful when the change of the beliefs comes from a change of the world, while belief revision concerns a change of beliefs about a static world. In [46], Dupin de Saint-Cyr et al. use a very expressive logical language called YALLA, able to represent information about an argumentation framework and its semantics, and they adapt the KM update postulates to enforce in an argumentation system any constraint which can be expressed in YALLA.

As illustrated in this section, the only postulate-based approaches for change in argumentation frameworks are borrowed from logical belief change frameworks (namely, revision, expansion and update). It is reasonable to suppose that some change operations are specific to argumentation scenarios, so an interesting research track is to define axiomatic characterization of such approaches. For instance, even if enforcement of an extension by Baumann and Brewka [14] and Baumann [12] is very close to revision, it is not at all defined like revision by Coste-Marquis et al. [33,34]. We can suppose that postulates for extension enforcement would be different from postulates for revision.

6.Conclusion and perspectives

This paper is an extended and updated version of a previous work by Doutre and Perrussel [43]. We consider some recent contributions on dynamics of argumentation systems, and we present other enforcement cases that remain to be investigated.

Table 3, 4, 5, 6 and 7 sum up the existing approaches in the topic of change in argumentation systems. They are classified depending on the kind of approach promoted, as described in Section 3. We recall, for each of the listed contribution, which kind of constraints are considered, which kind of change is applied to enforce them, and when it is relevant, which quality of enforcement is used. The table only mentions the changes which are applied to enforce a given constraint (structural and/or semantic), and not the changes that this enforcement may imply. In particular, acceptability changes are a usual side effect of the enforcement of structural and semantic constraints, but they are not considered as a first-class citizen of the change operation.

Table 3

Summary of Existing Approaches of Change in Argumentation (Elementary Change)

Boella et al. 2009 [21,22]Cayrol et al. 2010 [28]Bisquert et al. 2011 [19]Liao et al. 2011 [55]Baroni et al. 2014 [10]Alfano et al. 2017 [2]
ConstraintStructural

Semantic

Acceptability
ChangeStructural

Semantic
QualityStructural

Semantic

Acceptability

Postulates
Table 4

Summary of Existing Approaches of Change in Argumentation (Extension Enforcement)

Baumann and Brewka 2010 [14]Baumann 2012 [12]Coste-Marquis et al. 2015 [35]Wallner et al. 2017 [66]Doutre and Mailly 2017 [42]Dimopoulos et al. 2018 [38]
ConstraintStructural

Semantic

Acceptability
ChangeStructural

Semantic
QualityStructural

Semantic

Acceptability

Postulates
Table 5

Summary of Existing Approaches of Change in Argumentation (Belief Update)

Dupin de Saint-Cyr et al. 2013, 2016 [20,46]Doutre et al. 2014, 2017 [39,40]
ConstraintStructural

Semantic

Acceptability
ChangeStructural

Semantic
QualityStructural

Semantic

Acceptability

Postulates
Table 6

Summary of Existing Approaches of Change in Argumentation (Belief Revision)

Booth et al. 2013 [24]Coste-Marquis et al. 2014 [33]Diller et al. 2018 [37]Linsbichler, Woltran 2016 [56]Coste-Marquis et al. 2014 [34]Nouioua, Würbel 2014 [60]Baumann, Brewka 2015 [15]
ConstraintStructural

Semantic

Acceptability
ChangeStructural

Semantic
QualityStructural

Semantic

Acceptability

Postulates
Table 7

Summary of Existing Approaches of Change in Argumentation (Other Approaches)

Rienstra 2014 [63]Kontarinis et al. 2013 [53]Dvořák et al. 2011, 2017 [47,48]Baumann 2014 [13]Dunne et al. 2015 [45]
ConstraintStructural

Semantic

Acceptability
ChangeStructural

Semantic
QualityStructural

Semantic

Acceptability

Postulates

The study shows that many challenging enforcement problems of interest remain to be explored in abstract argumentation. In particular, semantic change has received far less attention than other kinds of change. More than the question of enforcing a semantic constraint, a challenging problem is to enforce an acceptability constraint by a semantic change only; studying the quality of semantic change is then a mean to choose the best option among several possible semantic changes. A last relevant perspective for future work with Dung’s framework is the combination of constraints and changes. Some combinations of constraints and “quality of change” criteria have already been considered, but the rich level of expressiveness of argumentation systems allows to consider many other ones.

This study has mainly been conducted with Dung’s abstract argumentation framework. However, as we have exemplified, the problems typology that has been set in this paper may apply to other argumentation frameworks as well. Adapting existing work about change in Dung’s framework to other argumentation frameworks is not necessarily straightforward, and this is a stimulating question for future work. Also, the investigation of change in ranking-based semantics is an interesting topic which has not been studied yet.

Finally, a remark about the question of structured argumentation frameworks. In such frameworks, two levels of constraints and changes may occur: either it is observed on the underlying structure of arguments, and it may have some effects on the argument graph, or on the opposite, the agent may enforce a constraint at the graph level, which impacts the underlying structure of arguments. This topic is out of the scope of the current paper, but a classification of the existing work on argumentation dynamics in structured frameworks is interesting (see e.g. Falappa et al. [49], Moguillansky et al. [59], Shakarian et al. [64], Mailly [58] and Snaith and Reed [65]). Similarly to what is done here for abstract argumentation, this could highlight some open questions for these settings, and maybe some interesting relations with the work about abstract argumentation.

Notes

1 Notice that σ(F) represents the evaluation in a general meaning; for instance, in the case where an extension-based (resp. a ranking-based) semantics is considered, it represents the set of extensions of F under σ (resp. the preorder on the set of arguments that σ associates to F).

2 The word “structure” is used in [19,28] with a different meaning than our meaning in the next sections. [19,28] consider the conformation of the set of extensions, while we consider the argumentation graph.

3 Normal expansion also makes sense in structured argumentation frameworks like Deductive Argumentation by Besnard and Hunter [18]. Indeed, if an argumentation graph is built from a logical knowledge base, adding new formulas in the knowledge base will (possibly) add new arguments and attacks, but the existing ones remain the same.

4 Somehow, this constraint about the full ordering of arguments may be seen as the counterpart of realizability (Dunne et al. [45]) for ranking-based semantics.

Acknowledgements

This work benefited from the support of the AMANDE project (ANR-13-BS02-0004) of the French National Research Agency (ANR). We would like to thank Laurent Perrussel for fruitful discussions on preliminary versions of this study.

References

[1] 

C. Alchourrón, P. Gärdenfors and D. Makinson, On the logic of theory change: Partial meet contraction and revision functions, Journal of Symbolic Logic 50 (1985), 510–530. doi:10.2307/2274239.

[2] 

G. Alfano, S. Greco and F. Parisi, Efficient computation of extensions for dynamic abstract argumentation frameworks: An incremental approach, in: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19–25, 2017, pp. 49–55.

[3] 

L. Amgoud and J. Ben-Naim, Ranking-based semantics for argumentation frameworks, in: Proceedings of the Seventh International Conference on Scalable Uncertainty Management (SUM’13), Springer, 2013, pp. 134–147.

[4] 

L. Amgoud and J. Ben-Naim, Axiomatic foundations of acceptability semantics, in: Principles of Knowledge Representation and Reasoning: Proceedings of the Fifteenth International Conference, KR 2016, Cape Town, South Africa, April 25–29, 2016, pp. 2–11, 2016.

[5] 

L. Amgoud and J. Ben-Naim, Evaluation of arguments from support relations: Axioms and semantics, in: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, 9–15 July, 2016, New York, NY, USA, pp. 900–906, 2016.

[6] 

L. Amgoud and C. Cayrol, A reasoning model based on the production of acceptable arguments, Annals of Mathematics and Artificial Intelligence 34(1–3) (2002), 197–215. doi:10.1023/A:1014490210693.

[7] 

P. Balbiani, A. Herzig and N. Troquard, Dynamic logic of propositional assignments: A well-behaved variant of PDL, in: Twenty-Eighth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2013), 2013, pp. 143–152.

[8] 

P. Baroni, M. Caminada and M. Giacomin, An introduction to argumentation semantics, Knowledge Engineering Review 26(4) (2011), 365–410. doi:10.1017/S0269888911000166.

[9] 

P. Baroni and M. Giacomin, On principle-based evaluation of extension-based argumentation semantics, Artificial Intelligence 171(10) (2007), 675–700. doi:10.1016/j.artint.2007.04.004.

[10] 

P. Baroni, M. Giacomin and B. Liao, On topology-related properties of abstract argumentation semantics. A correction and extension to dynamics of argumentation systems: A division-based method, Artif. Intell. 212 (2014), 104–115. doi:10.1016/j.artint.2014.03.003.

[11] 

P. Baroni, A. Rago and F. Toni, How many properties do we need for gradual argumentation?, in: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI’18), 2018.

[12] 

R. Baumann, What does it take to enforce an argument? Minimal change in abstract argumentation, in: Proceedings of the Twentieth European Conference on Artificial Intelligence (ECAI 2012), 2012, pp. 127–132.

[13] 

R. Baumann, Context-free and context-sensitive kernels: Update and deletion equivalence in abstract argumentation, in: ECAI 2014 – 21st European Conference on Artificial Intelligence, 2014, pp. 63–68.

[14] 

R. Baumann and G. Brewka, Expanding argumentation frameworks: Enforcing and monotonicity results, in: Proceedings of the Third International Conference on Computational Models of Argument (COMMA’10), 2010, pp. 75–86.

[15] 

R. Baumann and G. Brewka, AGM meets abstract argumentation: Expansion and revision for dung frameworks, in: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI’15), 2015.

[16] 

T.J. Bench-Capon, Persuasion in practical argument using value-based argumentation frameworks, Journal of Logic and Computation 13(3) (2003), 429–448. doi:10.1093/logcom/13.3.429.

[17] 

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

[18] 

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

[19] 

P. Bisquert, C. Cayrol, F. Dupin de Saint-Cyr and M.-C. Lagasquie-Schiex, Change in argumentation systems: Exploring the interest of removing an argument, in: Proceedings of the Fifth International Conference on Scalable Uncertainty Management (SUM’11), 2011, pp. 275–288. doi:10.1007/978-3-642-23963-2_22.

[20] 

P. Bisquert, C. Cayrol, F. Dupin de Saint-Cyr and M.-C. Lagasquie-Schiex, Enforcement in argumentation is a kind of update, in: Proceedings of the Seventh International Conference on Scalable Uncertainty Management (SUM’13), 2013, pp. 30–43.

[21] 

G. Boella, S. Kaci and L. van der Torre, Dynamics in argumentation with single extensions: Abstraction principles and the grounded extension, in: Proceedings of the Tenth European Conferences on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2009), 2009, pp. 107–118. doi:10.1007/978-3-642-02906-6_11.

[22] 

G. Boella, S. Kaci and L. van der Torre, Dynamics in argumentation with single extensions: Attack refinement and the grounded extension, in: Proceedings of the International Conference on Autonomous Agents and Multiagents Systems (AAMAS 2009), 2009, pp. 1213–1214.

[23] 

E. Bonzon, J. Delobelle, S. Konieczny and N. Maudet, A comparative study of ranking-based semantics for abstract argumentation, in: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, Arizona, USA, February 12–17, 2016, 2016, pp. 914–920.

[24] 

R. Booth, S. Kaci, T. Rienstra and L. van der Torre, A logical theory about dynamics in abstract argumentation, in: Proceedings of the Seventh International Conference on Scalable Uncertainty Management (SUM’13), Springer, 2013, pp. 148–161.

[25] 

G. Brewka and S. Woltran, Abstract dialectical frameworks, in: Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR’10), 2010.

[26] 

M. Caminada, On the issue of reinstatement in argumentation, in: Proceedings of the Tenth European Conference on Logics in Artificial Intelligence (JELIA’06), Springer, 2006, pp. 111–123.

[27] 

M.W. Caminada and D.M. Gabbay, A logical account of formal argumentation, Studia Logica 93(2–3) (2009), 109. doi:10.1007/s11225-009-9218-x.

[28] 

C. Cayrol, F. Dupin de Saint-Cyr and M. Lagasquie-Schiex, Change in abstract argumentation frameworks: Adding an argument, J. Artif. Intell. Res. (JAIR) 38 (2010), 49–84. doi:10.1613/jair.2965.

[29] 

C. Cayrol and M.-C. Lagasquie-Schiex, On the acceptability of arguments in bipolar argumentation frameworks, in: Proceedings of the Eight European Conferences on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU’05), Springer, 2005, pp. 378–389. doi:10.1007/11518655_33.

[30] 

E.M. Clarke, O. Grumberg, S. Jha, Y. Lu and H. Veith, Counterexample-guided abstraction refinement for symbolic model checking, J. ACM 50(5) (2003), 752–794. doi:10.1145/876638.876643.

[31] 

S. Coste-Marquis, C. Devred, S. Konieczny, M. Lagasquie-Schiex and P. Marquis, On the merging of Dung’s argumentation systems, Artif. Intell. 171(10–15) (2007), 730–753. doi:10.1016/j.artint.2007.04.012.

[32] 

S. Coste-Marquis, C. Devred and P. Marquis, Constrained argumentation frameworks, in: Proceedings of the Tenth International Conference on Principles of Knowledge Representation and Reasoning, KR’06, 2006, pp. 112–122.

[33] 

S. Coste-Marquis, S. Konieczny, J.-G. Mailly and P. Marquis, On the revision of argumentation systems: Minimal change of arguments statuses, in: Proceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning (KR’14), 2014.

[34] 

S. Coste-Marquis, S. Konieczny, J.-G. Mailly and P. Marquis, A translation-based approach for revision of argumentation frameworks, in: Proceedings of the Fourteenth European Conference on Logics in Artificial Intelligence (JELIA’14), 2014, pp. 397–411.

[35] 

S. Coste-Marquis, S. Konieczny, J.-G. Mailly and P. Marquis, Extension enforcement in abstract argumentation as an optimization problem, in: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI’15), 2015, pp. 2876–2882.

[36] 

J. Delobelle, Ranking-based Semantics for Abstract Argumentation, PhD thesis, Université d’Artois, France, 2017.

[37] 

M. Diller, A. Haret, T. Linsbichler, S. Rümmele and S. Woltran, An extension-based approach to belief revision in abstract argumentation, Int. J. Approx. Reasoning 93 (2018), 395–423. doi:10.1016/j.ijar.2017.11.013.

[38] 

Y. Dimopoulos, J.-G. Mailly and P. Moraitis, Control argumentation frameworks, in: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI’18), 2018.

[39] 

S. Doutre, A. Herzig and L. Perrussel, A dynamic logic framework for abstract argumentation, in: Proceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning (KR’14), 2014, pp. 62–71.

[40] 

S. Doutre, F. Maffre and P. McBurney, A dynamic logic framework for argumentation: Adding and removing arguments, in: Proceedings of the 30th International Conference on Industrial, Engineering, Other Applications of Applied Intelligent Systems (IEA/AIE’17), 2017, pp. 295–305.

[41] 

S. Doutre and J.-G. Mailly, Quantifying the difference between argumentation semantics, in: Proceedings of the 6th International Conference on Computational Models of Argument (COMMA’16), 2016, pp. 255–262.

[42] 

S. Doutre and J.-G. Mailly, Semantic change and extension enforcement in abstract argumentation, in: Proceedings of the 11th International Conference on Scalable Uncertainty Management (SUM’17), 2017, pp. 194–207. doi:10.1007/978-3-319-67582-4_14.

[43] 

S. Doutre and L. Perrussel, On enforcing a constraint in argumentation, in: 11th European Workshop on Multi-Agent Systems (EUMAS’13), 2013.

[44] 

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–357. doi:10.1016/0004-3702(94)00041-X.

[45] 

P.E. Dunne, W. Dvořák, T. Linsbichler and S. Woltran, Characteristics of multiple viewpoints in abstract argumentation, Artif. Intell. 228 (2015), 153–178. doi:10.1016/j.artint.2015.07.006.

[46] 

F. Dupin de Saint-Cyr, P. Bisquert, C. Cayrol and M. Lagasquie-Schiex, Argumentation update in YALLA (Yet Another Logic Language for Argumentation), Int. J. Approx. Reasoning 75 (2016), 57–92. doi:10.1016/j.ijar.2016.04.003.

[47] 

W. Dvořák and C. Spanring, Comparing the expressiveness of argumentation semantics, Journal of Logic and Computation 27(5) (2017), 1489–1521.

[48] 

W. Dvořák and S. Woltran, On the intertranslatability of argumentation semantics, Journal of Artificial Intelligence Research 41(2) (2011), 445–475. doi:10.1613/jair.3318.

[49] 

M.A. Falappa, G. Kern-Isberner and G.R. Simari, Belief revision and argumentation theory, in: Argumentation in Artificial Intelligence, 2009, pp. 341–360.

[50] 

A. Herzig, E. Lorini, F. Moisan and N. Troquard, A dynamic logic of normative systems, in: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), 2011, pp. 228–233.

[51] 

H. Katsuno and A.O. Mendelzon, Propositional knowledge base revision and minimal change, Artificial Intelligence 52 (1991), 263–294. doi:10.1016/0004-3702(91)90069-V.

[52] 

H. Katsuno and A.O. Mendelzon, On the difference between updating a knowledge base and revising it, in: Belief Revision, P. Gärdenfors, ed., Cambridge University Press, 1992, pp. 183–203.

[53] 

D. Kontarinis, E. Bonzon, N. Maudet, A. Perotti, L. van der Torre and S. Villata, Rewriting rules for the computation of goal-oriented changes in an argumentation system, in: Proceedings of the Fourteenth International Workshop on Computational Logic in Multi-Agent Systems (CLIMA XIV), Springer, 2013, pp. 51–68.

[54] 

S. Kraus, D.J. Lehmann and M. Magidor, Nonmonotonic reasoning, preferential models and cumulative logics, Artificial Intelligence 44(1–2) (1990), 167–207. doi:10.1016/0004-3702(90)90101-5.

[55] 

B. Liao, L. Jin and R.C. Koons, Dynamics of argumentation systems: A division-based method, Artificial Intelligence 175(11) (2011), 1790–1814. doi:10.1016/j.artint.2011.03.006.

[56] 

T. Linsbichler and S. Woltran, Revision of abstract dialectical frameworks: Preliminary report, in: First International Workshop on Argumentation in Logic Programming and Non-Monotonic Reasoning, Arg-LPNMR 2016, 2016.

[57] 

J.-G. Mailly, Dynamics of Argumentation Frameworks, PhD thesis, Université d’Artois, France, 2015.

[58] 

J.-G. Mailly, Using enthymemes to fill the gap between logical argumentation and revision of abstract argumentation frameworks, in: 16th International Workshop on Non-Momotonic Reasoning (NMR’16), 2016.

[59] 

M.O. Moguillansky, N.D. Rotstein, M.A. Falappa, A.J. García and G.R. Simari, Argument theory change through defeater activation, in: Proceedings of the Third International Conference on Computational Models of Argument (COMMA 2010), 2010, pp. 359–366.

[60] 

F. Nouioua and E. Würbel, Removed set-based revision of abstract argumentation frameworks, in: Proceedings of the Twenty-Sixth IEEE International Conference on Tools with Artificial Intelligence (ICTAI’14), 2014, pp. 784–791.

[61] 

O. Papini, A complete revision function in propositional calculus, in: Proceedings of the Tenth European Conference on Artificial Intelligence, (ECAI 1992), 1992, pp. 339–343.

[62] 

F. Pu, J. Luo, Y. Zhang and G. Luo, Argument ranking with categoriser function, in: Knowledge Science, Engineering and Management – 7th International Conference, KSEM 2014, Proceedings, Sibiu, Romania, October 16–18, 2014, 2014, pp. 290–301.

[63] 

T. Rienstra, Argumentation in Flux: Modelling Change in the Theory of Argumentation, PhD thesis, Université du Luxembourg and Université de Montpellier II, 2014.

[64] 

P. Shakarian, G.I. Simari, G. Moores, D. Paulo, S. Parsons, M.A. Falappa and A. Aleali, Belief revision in structured probabilistic argumentation – model and application to cyber security, Ann. Math. Artif. Intell. 78(3–4) (2016), 259–301. doi:10.1007/s10472-015-9483-5.

[65] 

M. Snaith and C. Reed, Argument revision, J. Log. Comput. 27(7) (2017), 2089–2134.

[66] 

J.P. Wallner, A. Niskanen and M. Järvisalo, Complexity results and algorithms for extension enforcement in abstract argumentation, J. Artif. Intell. Res. 60 (2017), 1–40. doi:10.1613/jair.5415.

[67] 

E. Würbel, R. Jeansoulin and O. Papini, Revision: An application in the framework of GIS, in: Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2000), 2000, pp. 505–515.