Constraints and changes: A survey of abstract argumentation dynamics

2.1.General setting

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

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.

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, R⊆A×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.

Given a,b∈A, we say that a attacks b if (a,b)∈R. This definition can be extended: a set S⊆A attacks b if ∃a∈S 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.

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.

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.

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].

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.

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].

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 a∈A, Att(a)={b∈A∣(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+∑b∈Att(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,b∈A:

a⩽FCatbif 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′.

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))∣a∈A}.

Fig. 4.

The Ranking of Arguments ⩽F′Cat.

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.

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.

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

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 structure22 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.33 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.

Fig. 5.

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.

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 S⊆A; 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.

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 F⊔F′=⟨A∪A′,R∪R′⟩ 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.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.44 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.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.