A principle-based robustness analysis of admissibility-based argumentation semantics

Abstract

The principle-based approach is a methodology to classify and analyse argumentation semantics. In this paper we classify seven of the main alternatives for argumentation semantics using a set of new robustness principles. These principles complement Baroni and Giacomin’s original classification and deal with the behaviour of a semantics when the argumentation framework changes due to the addition or removal of an attack between two arguments. We distinguish so-called persistence principles and monotonicity principles, where the former deal with the question of whether a labelling or extension of an argumentation framework under a given semantics persists after a change, and the latter with the question of whether new labellings or extensions are created after a change. We furthermore show in which sense labelling-based and extension-based semantics lead to subtly different principles and results. Our results can be used for choosing a semantics for a particular application, or to guide the search for new argumentation semantics, but they have been used also in the design of algorithms.

1. Introduction

Many semantics have been proposed in the literature on abstract argumentation. One way to compare and evaluate them is to look at examples of argumentation frameworks that bring to light important differences between semantics or highlight a particular strength or weakness of a semantics. While such an example-based approach may produce valuable insights, a deeper understanding of the differences and similarities of semantics requires a more systematic study of their properties. Baroni et al. introduced the so called principle-based approach [4,60], which takes as a starting point principles – that may or may not be satisfied by a semantics – representing various intuitions and requirements, which are used to evaluate a semantics or to guide the search for new semantics. These principles range from basic properties of extensions such as conflict-freeness and admissibility to principles that reflect desirable behaviour in certain classes of examples, such as crash-resistance, non-interference and directionality [4,30]. Semantics for argumentation may also be characterised in terms of strong equivalence conditions, which identify the syntactical differences that are semantically indistinguishable under a given semantics [7–10,18,54], or in terms of their signature, which identifies the set of all possible sets of extensions or labellings that can be expressed under a given semantics [42,44,47]. The general approach of focusing on general properties in the evaluation of a semantics has also been applied to ranking-based semantics [2,19,24] and instantiated argumentation formalisms [27,29].

In this paper we extend the principle-based investigation of semantics for abstract argumentation and study principles that characterise the robustness of extensions or labellings under a semantics with respect to the removal or addition of attacks. These principles are relative to the status assigned to the two arguments between which the attack is added or removed. The set of different statuses we can distinguish depends on whether we look at labelling-based or extension-based semantics. A labelling-based semantics σ maps every argumentation framework to a set of labellings, which are functions that assign to each argument a label $\mathbf{\text{I}}$ (or accepted), $\mathbf{\text{O}}$ (or rejected) or $\mathbf{\text{U}}$ (or undecided) [28]. Given a labelling-based semantics σ we define, for each combination X and Y of labels, the following four principles:

• $\mathit{X}\mathit{Y}$ addition persistence: a σ labelling of an argumentation framework F in which x is labelled X and y is labelled Y is still a σ labelling of F after adding an attack from x to y.

• $\mathit{X}\mathit{Y}$ removal persistence: a σ labelling of an argumentation framework F in which x is labelled X and y is labelled Y is still a σ labelling of F if removing the attack from x to y.

• $\mathit{X}\mathit{Y}$ addition monotonicity: if in all σ labellings of an argumentation framework F, x is labelled X and y is labelled Y, then adding an attack from x to y does not lead to new σ labellings.

• $\mathit{X}\mathit{Y}$ removal monotonicity: if in all σ labellings of an argumentation framework F, x is labelled X and y is labelled Y, then removing an attack from x to y does not lead to new σ labellings.

For the extension-based setting we define the same set of principles except that the status of an argument is either in an extension (or, equivalently, labelled $\mathbf{\text{I}}$ ) or not in an extension (or, equivalently, labelled either $\mathbf{\text{O}}$ or $\mathbf{\text{U}}$ ). Thus, in the extension-based setting we do not have the ability to distinguish rejected and undecided arguments. The extension-based principles therefore have less discriminative power than the labelling-based ones. Nevertheless, the results obtained in the extension-based setting do provide additional insights. In particular, the extension-based setting leads to weaker forms of addition and removal monotonicity than in the labelling-based setting. That is, even if a semantics σ violates all variants of addition/removal monotonicity in the labelling-based setting, it may still satisfy variants of addition/removal under the extension-based setting.

We investigate the principles discussed here with respect to all the admissibility-based semantics that have been defined in the literature. Thus, we focus on the complete, grounded, preferred and stable semantics, which were defined by Dung in terms of extensions [40] and by Caminada in terms of labellings [28], as well as the semi-stable [30], ideal [41] and eager [26] semantics. The investigation of non-admissible semantics is planned for a future publication.

The results we obtain provide insight into the robustness of the evaluation of an argumentation framework under a given semantics when the argumentation framework changes. While we do not argue that any of the principles we investigate must necessarily be satisfied by a semantics in general, some principles can be regarded as reflecting reasonable or desirable requirements. Let us demonstrate this point by considering $\mathbf{OO}$ addition persistence. This principle reflects the intuition that a point of view on argument acceptance represented by a labelling L still represents a valid point of view after adding an attack from x to y, if both x and y are rejected in L. This can be regarded as reasonable because the added attack does not introduce a conflict with respect to L and does not change the justification for the rejection of x and y. Thus, the added attack provides no explicit reason to give up on L as a reasonable point of view on argument acceptance. Indeed, this is true under the complete semantics, which satisfies $\mathbf{OO}$ addition persistence. The complete semantics similarly satisfies $\mathbf{OU}$ , $\mathbf{UO}$ , $\mathbf{UU}$ , $\mathbf{OI}$ and $\mathbf{IO}$ addition persistence, as well as $\mathbf{OI}$ , $\mathbf{OU}$ , $\mathbf{UO}$ and $\mathbf{OO}$ removal persistence, where the removal of the attack does not invalidate the justification of the label of the second argument. Our results show, however, that not all the semantics we consider satisfy these principles, even though all of them associate an argumentation framework with a set of complete labellings. Other principles can similarly be regarded as undesirable. For instance, $\mathbf{II}$ addition persistence reflects the intuition that a point of view on argument acceptance survives even if we add an attack between two arguments that are both accepted. This amounts to permitting points of view on argument acceptance that contain conflicts, which is not desirable unless one considers a conflict-tolerant semantics [3]. In general, whether a principle is desirable depends on how one expects a semantics to behave with the argumentation framework changes, and this depends on the application. The results we obtain can therefore be used to determine whether a semantics is suitable for a given application.

The principles we investigate are also useful in the design of algorithms. For example, Niskanen et al. [51] use persistence principles in the design of an algorithm for computing extensions of incomplete argumentation frameworks, where one can specify that attacks between certain arguments may or may not exist. Persistence and monotonicity principles are also useful in addressing enforcement problems in abstract argumentation [11,12,25,34,53]. This is the problem of determining minimal sets of changes to an argumentation framework in order to enforce some result, such as the acceptance of a given set of arguments. Because persistence and monotonicity principles can be used to determine which changes to the attack relation of an argumentation framework do or do not change its evaluation, these principles can be used to guide the search for sets of changes in the enforcement problem. This idea has already been used for extension enforcement under the grounded semantics [53].

This paper extends results presented earlier [56], which focused on addition and removal persistence as well as addition monotonicity, but did not consider removal monotonicity and did not include results for the ideal and eager semantics. In the current paper we additionally examine persistence and monotonicity principles from the extension-based perspective, where we distinguish arguments that are accepted from those that are not, but where no distinction is made between rejected and undecided arguments. In case of addition and removal monotonicity, this different perspective yields a set of principles that are distinct from the labelling-based ones.

The layout of this paper is as follows. In Section 2 we recall the necessary definitions concerning abstract argumentation theory. Then we first focus on labelling-based semantics. The addition and removal persistence principles are discussed in Section 3 and 4, while addition and removal monotonicity principles are discussed in Section 5 and 6. We then discuss, in Section 7, persistence and monotonicity principles for extension-based semantics, and summarise and contrast our results in Section 8. We discuss directions for future work in Section 9, survey related work in Section 10, and conclude in Section 11.

2. Preliminaries

An argumentation framework is a directed graph represented by a set A of arguments and a binary relation ⇝ over A called the attack relation [40]. We assume throughout this paper that a set $\mathcal{U}$ , called the universe of arguments and whose elements are called arguments, is given, and that the set of arguments in an argumentation framework is finite.

Definition 1.

Let $\mathcal{U}$ be a set called the universe of arguments. An argumentation framework is a pair $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ where A is a finite subset of $\mathcal{U}$ and ⇝ is a binary relation over A called the attack relation. We denote by $\mathcal{F}$ the set of all argumentation frameworks.

Given an argumentation framework $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ we say that an argument $\mathit{a}\in \mathit{A}$ attacks an argument $\mathit{b}\in \mathit{A}$ if and only if $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in ⇝$ . We will mostly use infix notation and write $\mathit{a}⇝\mathit{b}$ instead of $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in ⇝$ . Given an argumentation framework $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ and an argument $\mathit{x}\in \mathit{A}$ we denote by ${\mathit{x}}^{-}$ the set of arguments attacking x and by ${\mathit{x}}^{+}$ the set of arguments attacked by x. Given a set $\mathit{B}\subseteq \mathit{A}$ we denote by ${\mathit{B}}^{-}$ the set of arguments attacking some $\mathit{x}\in \mathit{B}$ and by ${\mathit{B}}^{+}$ the set of arguments attacked by some $\mathit{x}\in \mathit{B}$ .

A labelling-based semantics maps every argumentation framework to a set of labellings, which are functions that map every argument of an argumentation framework to a label. All the labelling-based semantics considered in this paper are defined using three possible labels: $\mathbf{\text{I}}$ indicates that the argument is accepted, $\mathbf{\text{O}}$ that the argument is rejected, and $\mathbf{\text{U}}$ that the acceptance of the argument is undecided [28].

Definition 2.

A labelling of an argumentation framework $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ is a function $\mathit{L}:\mathit{A}\to \{\mathbf{\text{I}}\mathrm{,}\mathbf{\text{O}}\mathrm{,}\mathbf{\text{U}}\}$ . Given a label $\mathit{l}\in \{\mathbf{\text{I}}\mathrm{,}\mathbf{\text{O}}\mathrm{,}\mathbf{\text{U}}\}$ we define ${\mathit{L}}^{-1}\mathrm{(}\mathit{l}\mathrm{)}$ as $\{\mathit{x}\in \mathit{A}\mid \mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathit{l}\}$ . We denote by ${\mathcal{L}}_{}\mathrm{(}\mathit{F}\mathrm{)}$ the set of all labellings of F. We also denote a labelling L by the set of pairs $\{\mathrm{(}{\mathit{x}}_1\mathrm{,}\mathit{L}\mathrm{(}{\mathit{x}}_1\mathrm{)}\mathrm{)}\mathrm{,}\dots \mathrm{,}\mathrm{(}{\mathit{x}}_{\mathit{n}}\mathrm{,}\mathit{L}\mathrm{(}{\mathit{x}}_{\mathit{n}}\mathrm{)}\mathrm{)}\}$ where $\mathit{A}=\{{\mathit{x}}_1\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{n}}\}$ .

Definition 3.

A labelling-based semantics σ defines a function ${\mathcal{L}}_{\mathit{\sigma }}$ that associates every $\mathit{F}\in \mathcal{F}$ with a set ${\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathit{F}\mathrm{)}\subseteq {\mathcal{L}}_{}\mathrm{(}\mathit{F}\mathrm{)}$ .

A complete labelling is a labelling in which an argument is accepted if and only if all attackers are rejected, and an argument is rejected if and only if some attacker is accepted. All the semantics we consider in this paper are based on complete labellings.

Definition 4.

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ be an argumentation framework. A labelling $\mathit{L}\in {\mathcal{L}}_{}\mathrm{(}\mathit{F}\mathrm{)}$ is complete if and only if, for all $\mathit{x}\in \mathit{A}$ :

$\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{I}}$ if and only if, for all $\mathit{y}\in {\mathit{x}}^{-}$ , $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ .

$\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ if and only if, for some $\mathit{y}\in {\mathit{x}}^{-}$ , $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{I}}$ .

Given two labelling L, ${\mathit{L}}^{\prime }$ , we say that ${\mathit{L}}^{\prime }$ is at least as committed as L (written ${\mathit{L}}^{\prime }⊑\mathit{L}$ ) if every argument that is labelled $\mathbf{\text{I}}$ (resp. $\mathbf{\text{O}}$ ) by ${\mathit{L}}^{\prime }$ is also labelled $\mathbf{\text{I}}$ (resp. $\mathbf{\text{O}}$ ) by L.

Definition 5.

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ be an argumentation framework. The committedness relation $⊑\subseteq {\mathcal{L}}_{}\mathrm{(}\mathit{F}\mathrm{)}\times {\mathcal{L}}_{}\mathrm{(}\mathit{F}\mathrm{)}$ is defined by $\mathit{L}⊑{\mathit{L}}^{\prime }$ if and only if ${\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}\subseteq {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}$ and ${\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{O}}\mathrm{)}\subseteq {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{O}}\mathrm{)}$ .

We furthermore write $\mathit{L}⊏{\mathit{L}}^{\prime }$ as shorthand for $\mathit{L}⊑{\mathit{L}}^{\prime }\wedge \mathit{L}⋣{\mathit{L}}^{\prime }$ . Given a set M of labellings we denote by $\sqcap \mathit{M}$ the labelling in which an argument x is labelled $\mathbf{\text{I}}$ (resp. $\mathbf{\text{O}}$ ) if the argument is labelled $\mathbf{\text{I}}$ (resp. $\mathbf{\text{O}}$ ) by all elements of M, and x is labelled $\mathbf{\text{U}}$ otherwise. Intuitively, $\sqcap \mathit{M}$ represents the “consensus” among M in terms of the arguments that are accepted and rejected.

Definition 6.

Given an argumentation framework $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ and a set $\mathit{M}\subseteq {\mathcal{L}}_{}\mathrm{(}\mathit{F}\mathrm{)}$ we define $\sqcap \mathit{M}$ by $\sqcap \mathit{M}=\mathit{L}$ , where L is the labelling of F defined by

$\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{I}}$ if and only if $\forall {\mathit{L}}^{\prime }\in \mathit{M}$ , $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{I}}$ , and

$\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ if and only if $\forall {\mathit{L}}^{\prime }\in \mathit{M}$ , ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ .

The following definition introduces the labelling-based complete ( $\mathit{\text{co}}$ ), grounded ( $\mathit{\text{gr}}$ ), preferred ( $\mathit{\text{pr}}$ ), stable ( $\mathit{\text{stb}}$ ), semi-stable ( $\mathit{\text{ss}}$ ), ideal ( $\mathit{\text{id}}$ ), and eager ( $\mathit{\text{ea}}$ ) semantics [26,28,30,41].

Definition 7.

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ be an argumentation framework.

${\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathit{F}\mathrm{)}=\{\mathit{L}\in {\mathcal{L}}_{}\mathrm{(}\mathit{F}\mathrm{)}\mid \mathit{L}\text{ is a complete labelling of }\mathit{F}\}$

${\mathcal{L}}_{\mathit{\text{gr}}}\mathrm{(}\mathit{F}\mathrm{)}=\{\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathit{F}\mathrm{)}\mid \nexists {\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathit{F}\mathrm{)}\text{ such that }{\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}\subset {\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}\}$

${\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}\mathit{F}\mathrm{)}=\{\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathit{F}\mathrm{)}\mid \nexists {\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathit{F}\mathrm{)}\text{ such that }{\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}\subset {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}\}$

${\mathcal{L}}_{\mathit{\text{ss}}}\mathrm{(}\mathit{F}\mathrm{)}=\{\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathit{F}\mathrm{)}\mid \nexists {\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathit{F}\mathrm{)}\text{ such that }{\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{U}}\mathrm{)}\subset {\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{U}}\mathrm{)}\}$

${\mathcal{L}}_{\mathit{\text{stb}}}\mathrm{(}\mathit{F}\mathrm{)}=\{\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathit{F}\mathrm{)}\mid {\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{U}}\mathrm{)}=\varnothing \}$

${\mathcal{L}}_{\mathit{\text{id}}}\mathrm{(}\mathit{F}\mathrm{)}=\{\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathit{F}\mathrm{)}\mid \mathit{L}⊑\sqcap {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}\mathit{F}\mathrm{)}\text{ and }\nexists {\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathit{F}\mathrm{)}\text{ such that }{\mathit{L}}^{\prime }⊑\sqcap {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}\mathit{F}\mathrm{)}\text{ and }\mathit{L}⊏{\mathit{L}}^{\prime }\}$

${\mathcal{L}}_{\mathit{\text{ea}}}\mathrm{(}\mathit{F}\mathrm{)}=\{\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathit{F}\mathrm{)}\mid \mathit{L}⊑\sqcap {\mathcal{L}}_{\mathit{\text{ss}}}\mathrm{(}\mathit{F}\mathrm{)}\text{ and }\nexists {\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathit{F}\mathrm{)}\text{ such that }{\mathit{L}}^{\prime }⊑\sqcap {\mathcal{L}}_{\mathit{\text{ss}}}\mathrm{(}\mathit{F}\mathrm{)}\text{ and }\mathit{L}⊏{\mathit{L}}^{\prime }\}$

We now state two well-known facts about the semantics defined in Definition 7 that will be used throughout this paper. First of all, under all semantics except for the stable semantics, every argumentation framework has at least one labelling.

Proposition 1.

Let F be an argumentation framework and $\mathit{\sigma }\in \{\mathit{\text{co}}\mathrm{,}\mathit{\text{gr}}\mathrm{,}\mathit{\text{pr}}\mathrm{,}\mathit{\text{ss}}\mathrm{,}\mathit{\text{id}}\mathrm{,}\mathit{\text{ea}}\}$ . Then ${\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathit{F}\mathrm{)}\ne \varnothing$ .

The grounded, ideal and eager semantics are unique status semantics, meaning that they map every argumentation framework to a unique labelling. Proposition 2.

Let F be an argumentation framework and let $\mathit{\sigma }\in \{\mathit{\text{gr}}\mathrm{,}\mathit{\text{id}}\mathrm{,}\mathit{\text{ea}}\}$ . Then $|{\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathit{F}\mathrm{)}|=1$ .

3. Addition persistence

We say that a semantics σ satisfies $\mathit{X}\mathit{Y}$ addition persistence if every σ labelling of an argumentation framework F in which x is labelled X and y is labelled Y is still a σ labelling of F after adding an attack from x to y. Formally:

Definition 8.

Let σ be a semantics and let $\mathit{X}\mathrm{,}\mathit{Y}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{I}}\mathrm{,}\mathbf{\text{U}}\}$ . We say that σ satisfies $\mathit{X}\mathit{Y}$ addition persistence if and only if for all $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\in \mathcal{F}$ and $\mathit{x}\mathrm{,}\mathit{y}\in \mathit{A}$ , if $\mathit{L}\in {\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ , $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathit{X}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathit{Y}$ , then $\mathit{L}\in {\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\cup \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}\mathrm{)}\mathrm{)}$ .

Table 1 shows the full overview of addition persistence under the semantics we consider. A gray cell means that the combination is satisfied and a white cell means that it is violated. The white and gray cells refer to the counterexamples and proofs provided in this section.

Table 1

Addition persistence for labelling-based semantics

We can distinguish two types of addition persistence principles. The first are $\mathbf{UI}$ , $\mathbf{IU}$ , and $\mathbf{II}$ addition persistence. Intuitively, these principles deal with the addition of attacks where the label of the newly attacked argument is no longer justified under the complete semantics. They are violated under the complete semantics and consequently under all the other semantics as well. The stable semantics is the only exception here, and satisfies $\mathbf{UI}$ , $\mathbf{IU}$ addition persistence due to the fact that no argument is ever labeled $\mathbf{\text{U}}$ under the stable semantics. The $\mathbf{UI}$ , $\mathbf{IU}$ , and $\mathbf{II}$ addition persistence may be considered as desirable principles for semantics that tolerate conflicts, which we do not consider in this paper [3].

The remaining combinations form the second type. These are $\mathbf{OO}$ , $\mathbf{OU}$ , $\mathbf{UO}$ , $\mathbf{UU}$ , $\mathbf{OI}$ and $\mathbf{IO}$ addition persistence. All these principles are satisfied by the complete semantics. Thus, they cover the complete range of possible additions of attacks that do not invalidate a complete labelling. On this ground, these principles may be regarded as reasonable or desirable principles for all semantics we consider in this paper, since they are all based on complete labellings. The question of whether they are satisfied does not only depend on whether the added attack invalidates a complete labelling, however. It also depends on whether the added attack changes the set of complete labellings as a whole, which in turn may lead to a change in the set of labellings that are grounded, preferred, semi-stable, and so on. Indeed, apart from the complete semantics, the only semantics that satisfies all principles of the second type is the stable semantics. All the other semantics violate one or more principles of the second type. In particular:

• The grounded semantics violates $\mathbf{OI}$ addition persistence. This arises from the fact that the grounded semantics is $\mathbf{\text{U}}$ -maximising. As demonstrated in Example 8, if x is $\mathbf{\text{O}}$ and y is $\mathbf{\text{I}}$ in the grounded labelling of an argumentation framework then adding an attack from x to y may lead to an additional complete labelling in which both x and y are $\mathbf{\text{U}}$ . This new complete labelling has a strictly larger set of $\mathbf{\text{U}}$ -labelled arguments and thus becomes the new grounded labelling that replaces the old one. Note that this phenomenon does not occur under the preferred semantics, which does satisfy $\mathbf{OI}$ addition persistence.

• The preferred semantics violates $\mathbf{UU}$ addition persistence. The $\mathbf{\text{I}}$ -maximising behaviour of the preferred semantics is responsible for this. As demonstrated in Example 7, if x and y are both $\mathbf{\text{U}}$ in a preferred labelling of an argumentation framework then adding an attack from x to y may lead to a new complete labelling in which x is $\mathbf{\text{I}}$ . This new complete labelling has a strictly larger set of arguments that are labelled $\mathbf{\text{I}}$ , and thus becomes a new preferred labelling that replaces the initial one. Note that this phenomenon does not occur under the grounded semantics, which does satisfy $\mathbf{UU}$ addition persistence.

• The semi-stable, eager and ideal violate all addition persistence principles. For the semi-stable semantics, the $\mathbf{\text{U}}$ -minimising behaviour is responsible for this. All the examples involve situations where there is a semi-stable labelling with at least one $\mathbf{\text{U}}$ -labelled argument, while after adding the attack, there is an additional complete labelling with no $\mathbf{\text{U}}$ -labelled arguments, which becomes a new semi-stable labelling that replaces the initial one. The same examples can also be used to show violation of addition persistence principles under the ideal and eager semantics.

In the remainder of this section, we present the counterexamples for the white cells in Table 1 and proofs for the gray cells.

Example 1 (Failure of $\mathbf{OO}$ addition persistence $\mathit{\text{ss}}$ and $\mathit{\text{ea}}$ semantics).

In the argumentation framework shown in Fig. 1 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer a semi-stable or eager labelling after adding the attack drawn with a dotted line. The new unique semi-stable and eager labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ .

Fig. 1.

$\mathbf{OO}$ addition persistence $\mathit{\text{ss}}$ , $\mathit{\text{id}}$ and $\mathit{\text{ea}}$ .

Example 2 (Failure of $\mathbf{OO}$ addition persistence $\mathit{\text{id}}$ semantics).

In the argumentation framework shown in Fig. 1 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer the ideal labelling after adding the attack drawn with a dotted line. The new ideal labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ .

Example 3 (Failure of $\mathbf{OU}$ addition persistence $\mathit{\text{ss}}$ and $\mathit{\text{ea}}$ semantics).

In the argumentation framework shown in Fig. 2 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ is no longer a semi-stable or eager labelling after adding the attack drawn with a dotted line. The new unique semi-stable and eager labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\}$ .

Fig. 2.

$\mathbf{OU}$ addition persistence $\mathit{\text{ss}}$ , $\mathit{\text{id}}$ and $\mathit{\text{ea}}$ .

Example 4 (Failure of $\mathbf{OU}$ addition persistence $\mathit{\text{id}}$ semantics).

In the argumentation framework shown in Fig. 2 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ is no longer the ideal labelling after adding the attack drawn with a dotted line. The new ideal labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ .

Example 5 (Failure of $\mathbf{UO}$ addition persistence $\mathit{\text{ss}}$ and $\mathit{\text{ea}}$ semantics).

In the argumentation framework shown in Fig. 3 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer a semi-stable or eager labelling after adding the attack drawn with a dotted line. The new unique semi-stable and eager labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\}$ .

Fig. 3.

$\mathbf{UO}$ addition persistence $\mathit{\text{ss}}$ and $\mathit{\text{id}}$ .

Example 6 (Failure of $\mathbf{UO}$ addition persistence $\mathit{\text{id}}$ semantics).

In the argumentation framework shown in Fig. 3 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer the ideal labelling after adding the attack drawn with a dotted line. The new ideal labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ .

Example 7 (Failure of $\mathbf{UU}$ addition persistence $\mathit{\text{pr}}$ , $\mathit{\text{id}}$ , $\mathit{\text{ss}}$ and $\mathit{\text{ea}}$ semantics).

In the argumentation framework shown in Fig. 4 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer a $\mathit{\text{pr}}$ , $\mathit{\text{id}}$ , $\mathit{\text{ss}}$ or $\mathit{\text{ea}}$ labelling after adding the attack drawn with a dotted line. The new $\mathit{\text{pr}}$ , $\mathit{\text{id}}$ , $\mathit{\text{ss}}$ and $\mathit{\text{ea}}$ labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\}$ .

Fig. 4.

$\mathbf{UU}$ addition persistence $\mathit{\text{pr}}$ , $\mathit{\text{id}}$ , $\mathit{\text{ss}}$ and $\mathit{\text{ea}}$ .

Example 8 (Failure of $\mathbf{OI}$ addition persistence $\mathit{\text{gr}}$ , $\mathit{\text{id}}$ semantics).

In the argumentation framework shown in Fig. 5 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer a $\mathit{\text{gr}}$ or $\mathit{\text{id}}$ labelling after adding the attack drawn with a dotted line. The new $\mathit{\text{gr}}$ and $\mathit{\text{id}}$ labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ .

Fig. 5.

$\mathbf{OI}$ addition persistence $\mathit{\text{gr}}$ , $\mathit{\text{id}}$ , $\mathit{\text{ss}}$ and $\mathit{\text{ea}}$ .

Example 9 (Failure of $\mathbf{OI}$ addition persistence $\mathit{\text{ss}}$ and $\mathit{\text{ea}}$ semantics).

In the argumentation framework shown in Fig. 5 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer a semi-stable or eager labelling after adding the attack drawn with a dotted line. The new semi-stable and eager labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ .

Example 10 (Failure of $\mathbf{UI}$ addition persistence $\mathit{\text{gr}}$ , $\mathit{\text{co}}$ , $\mathit{\text{pr}}$ , $\mathit{\text{ss}}$ , $\mathit{\text{id}}$ and $\mathit{\text{ea}}$ semantics).

In the argumentation framework shown in Fig. 6 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\}$ is no longer a $\mathit{\text{gr}}$ , $\mathit{\text{co}}$ , $\mathit{\text{pr}}$ , $\mathit{\text{ss}}$ , $\mathit{\text{id}}$ or $\mathit{\text{ea}}$ labelling after adding the attack drawn with a dotted line. The new labelling under these semantics is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ .

Fig. 6.

$\mathbf{UI}$ addition persistence $\mathit{\text{gr}}$ , $\mathit{\text{co}}$ , $\mathit{\text{pr}}$ , $\mathit{\text{ss}}$ , $\mathit{\text{id}}$ and $\mathit{\text{ea}}$ .

Example 11 (Failure of $\mathbf{IO}$ addition persistence $\mathit{\text{ss}}$ and $\mathit{\text{ea}}$ semantics).

In the argumentation framework shown in Fig. 7 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer a semi-stable or eager labelling after adding the attack drawn with a dotted line. The new semi-stable and eager labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ .

Fig. 7.

$\mathbf{IO}$ addition persistence $\mathit{\text{ss}}$ and $\mathit{\text{id}}$ .

Example 12 (Failure of $\mathbf{IO}$ addition persistence $\mathit{\text{id}}$ semantics).

In the argumentation framework shown in Fig. 7 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer the ideal labelling after adding the attack drawn with a dotted line. The new ideal labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ .

Example 13 (Failure of $\mathbf{IU}$ addition persistence under all semantics except stable).

In the argumentation framework shown in Fig. 8 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer a $\mathit{\text{gr}}$ , $\mathit{\text{co}}$ , $\mathit{\text{pr}}$ , $\mathit{\text{ss}}$ and $\mathit{\text{id}}$ labelling after adding the attack drawn with a dotted line. The new labelling under these semantics is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ .

Fig. 8.

$\mathbf{IU}$ addition persistence.

Example 14 (Failure of $\mathbf{II}$ addition persistence all semantics).

In the argumentation framework shown in Fig. 9 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\}$ is no longer a labelling under any semantics after adding the attack drawn with a dotted line. The new labelling under all semantics is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ .

Fig. 9.

$\mathbf{II}$ addition persistence.

The following two propositions will be used in the proofs that follow. The first states that, given any pair of complete labellings L, ${\mathit{L}}^{\prime }$ of an argumentation framework, it holds that ${\mathit{L}}^{\prime }$ accepts more arguments than L if and only if ${\mathit{L}}^{\prime }$ rejects more arguments than L.

Proposition 3.

Let $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ be an argumentation framework and let $\mathit{L}\mathrm{,}{\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . Then ${\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}\subseteq {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}$ if and only if ${\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{O}}\mathrm{)}\subseteq {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{O}}\mathrm{)}$ .

Proof.

For the only if direction, assume ${\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}\subseteq {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}$ . Let $\mathit{x}\in \mathit{A}$ and assume $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ . Definition 4 implies that there is a $\mathit{y}\in \mathit{A}$ such that $\mathit{y}⇝\mathit{x}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{I}}$ . Our assumption then implies ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{I}}$ . Using again Definition 4 it follows that ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ . Hence ${\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{O}}\mathrm{)}\subseteq {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{O}}\mathrm{)}$ .

For the if direction, assume ${\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{O}}\mathrm{)}\subseteq {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{O}}\mathrm{)}$ . Let $\mathit{x}\in \mathit{A}$ and assume $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{I}}$ . Definition 4 implies that for all $\mathit{y}\in \mathit{A}$ such that $\mathit{y}⇝\mathit{x}$ we have $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ . Our assumption then implies that, for all $\mathit{y}\in \mathit{A}$ such that $\mathit{y}⇝\mathit{x}$ , ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ . Using again Definition 4 it follows that ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{I}}$ . Hence ${\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}\subseteq {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}$ . □

The second proposition concerns some facts that we can learn about the grounded labelling of an argumentation framework F on the basis of a complete labelling of F.

Proposition 4.

Let F be an argumentation framework, let $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathit{F}\mathrm{)}$ and ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{gr}}}\mathrm{(}\mathit{F}\mathrm{)}$ . Then:

If $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ then ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}\ne \mathbf{\text{I}}$ .

If $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{I}}$ then ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}\ne \mathbf{\text{O}}$ .

If $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{U}}$ then ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{U}}$ .

Proof.

Let F be an argumentation framework, let $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathit{F}\mathrm{)}$ and ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{gr}}}\mathrm{(}\mathit{F}\mathrm{)}$ .

(1) From the definition of grounded labelling it follows that ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{I}}$ implies $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{I}}$ . By contraposition it follows that $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ implies ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}\ne \mathbf{\text{I}}$ .

(2) From the definition of grounded labelling together with Proposition 3 it follows that ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ implies $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ . By contraposition it follows that $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{I}}$ implies ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}\ne \mathbf{\text{O}}$ .

(3) If $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{U}}$ then $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}\ne \mathbf{\text{I}}$ and hence, from the definition of grounded labelling it follows that ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}\ne \mathbf{\text{I}}$ . Furthermore $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}\ne \mathbf{\text{O}}$ and hence, from the definition of grounded labelling together with Proposition 3, it follows that ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}\ne \mathbf{\text{O}}$ . Hence ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{U}}$ . □

Proposition 5.

The $\mathit{\text{co}}$ semantics satisfies $\mathbf{OU}$ , $\mathbf{OI}$ , $\mathbf{OO}$ , $\mathbf{UO}$ , $\mathbf{UU}$ and $\mathbf{IO}$ addition persistence.

Proof.

Follows directly from the definition of a complete labelling (Definition 4). □

Proposition 6.

The $\mathit{\text{gr}}$ semantics satisfies $\mathbf{OO}$ and $\mathbf{UO}$ addition persistence.

Proof.

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ and ${\mathit{F}}^{\prime }=\mathrm{(}\mathit{A}\mathrm{,}⇝\cup \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}\mathrm{)}$ . We assume that $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\notin ⇝$ (the case $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in ⇝$ is trivial). Let L be the grounded labelling of F and assume $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{U}}\}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ . Let z be an argument such that $\mathit{z}\ne \mathit{x}$ , $\mathit{L}\mathrm{(}\mathit{z}\mathrm{)}=\mathbf{\text{I}}$ , and $\mathit{z}⇝\mathit{y}$ (existence of z follows from Definition 4). Because the complete semantics satisfies $\mathbf{OO}$ and $\mathbf{UO}$ addition persistence (Proposition 5) L is a complete labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . Suppose L is not the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . We show that this leads to a contradiction. Then let ${\mathit{L}}^{\prime }$ be the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . Proposition 4 implies that ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}\in \{\mathbf{\text{U}}\mathrm{,}\mathbf{\text{O}}\}$ and ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}\in \{\mathbf{\text{U}}\mathrm{,}\mathbf{\text{O}}\}$ . We distinguish two cases:

${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{U}}$ : Using Definition 4 it follows that ${\mathit{L}}^{\prime }\mathrm{(}\mathit{z}\mathrm{)}\ne \mathbf{\text{I}}$ . Furthermore since $\mathit{L}\mathrm{(}\mathit{z}\mathrm{)}=\mathbf{\text{I}}$ , Proposition 4 implies ${\mathit{L}}^{\prime }\mathrm{(}\mathit{z}\mathrm{)}=\mathbf{\text{U}}$ . Using Definition 4 again it follows that ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ .

${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ : Since $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{U}}\}$ it then follows from Definition 4 that ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ .

It thus follows that ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . But this is a contradiction because it implies that L cannot be the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ . Hence L is the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . □

Proposition 7.

The $\mathit{\text{gr}}$ semantics satisfies $\mathbf{IO}$ addition persistence.

Proof.

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ and ${\mathit{F}}^{\prime }=\mathrm{(}\mathit{A}\mathrm{,}⇝\cup \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}\mathrm{)}$ . We assume that $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\notin ⇝$ (the case $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in ⇝$ is trivial). Let L be the grounded labelling of F and assume $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{I}}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ . Let z be an argument such that $\mathit{z}\ne \mathit{x}$ , $\mathit{L}\mathrm{(}\mathit{z}\mathrm{)}=\mathbf{\text{I}}$ , and $\mathit{z}⇝\mathit{y}$ (existence of z follows from Definition 4). Because the complete semantics satisfies $\mathbf{IO}$ addition persistence (Proposition 5) L is a complete labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . Suppose L is not the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . We show that this leads to a contradiction. Let ${\mathit{L}}^{\prime }$ be the actual grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . Proposition 4 implies that ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}\in \{\mathbf{\text{I}}\mathrm{,}\mathbf{\text{U}}\}$ and ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{U}}\}$ . We distinguish four cases:

${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{U}}$ and ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{U}}$ : Using Definition 4 it follows that ${\mathit{L}}^{\prime }\mathrm{(}\mathit{z}\mathrm{)}\ne \mathbf{\text{I}}$ . Furthermore since $\mathit{L}\mathrm{(}\mathit{z}\mathrm{)}=\mathbf{\text{I}}$ , Proposition 4 implies ${\mathit{L}}^{\prime }\mathrm{(}\mathit{z}\mathrm{)}=\mathbf{\text{U}}$ . Definition 4 then implies that ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . But this is a contradiction because it implies that L cannot be the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ .

${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{I}}$ and ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{U}}$ : This case is not possible as it implies that ${\mathit{L}}^{\prime }$ is not a complete labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ .

${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{U}}$ and ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ : Definition 4 then implies that ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . But this is a contradiction because it implies that L cannot be the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ .

${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{I}}$ and ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ : We distinguish two sub-cases:

• ${\mathit{L}}^{\prime }\mathrm{(}\mathit{z}\mathrm{)}=\mathbf{\text{I}}$ : Using Definition 4 it then follows that ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ .

• ${\mathit{L}}^{\prime }\mathrm{(}\mathit{z}\mathrm{)}=\mathbf{\text{U}}$ : For this case we transform ${\mathit{L}}^{\prime }$ into a new labelling ${\mathit{L}}^{″}$ by repeatedly relabelling arguments as follows. For every argument x:

• if x is $\mathbf{\text{I}}$ and x is attacked (in $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ ) by an argument labelled $\mathbf{\text{U}}$ then relabel x as $\mathbf{\text{U}}$ .

If we repeat these steps until no more arguments are relabelled then the resulting labelling ${\mathit{L}}^{″}$ is a complete labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ such that ${\mathit{L}}^{″-1}\mathrm{(}\mathbf{\text{U}}\mathrm{)}\subset {\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{U}}\mathrm{)}$ . But this is a contradiction because it implies that L cannot be the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ .

Therefore L is the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . □

Proposition 8.

The $\mathit{\text{gr}}$ semantics satisfies $\mathbf{UU}$ and $\mathbf{OU}$ addition persistence.

Proof.

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ and ${\mathit{F}}^{\prime }=\mathrm{(}\mathit{A}\mathrm{,}⇝\cup \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}\mathrm{)}$ . We assume that $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\notin ⇝$ (the case $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in ⇝$ is trivial). Let L and ${\mathit{L}}^{\prime }$ be the grounded labelling of F and ${\mathit{F}}^{\prime }$ , respectively. We assume $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{U}}\}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{U}}$ and prove that $\mathit{L}={\mathit{L}}^{\prime }$ . If $\mathit{x}⇝\mathit{y}$ we are done. For the case $\mathit{x}⇝̸\mathit{y}$ , we assume $\mathit{L}\ne {\mathit{L}}^{\prime }$ and derive a contradiction. Let $\mathit{z}\in \mathit{A}$ be an argument such that $\mathit{z}\ne \mathit{x}$ , $\mathit{L}\mathrm{(}\mathit{z}\mathrm{)}=\mathbf{\text{U}}$ and $\mathit{z}⇝\mathit{y}$ (existence of z follows from Definition 4). Because the complete semantics satisfies $\mathbf{UU}$ and $\mathbf{OU}$ addition persistence (Proposition 5) we get $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}{\mathit{F}}^{\prime }\mathrm{)}$ . Using Proposition 4 it then follows that ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}={\mathit{L}}^{\prime }\mathrm{(}\mathit{z}\mathrm{)}=\mathbf{\text{U}}$ . Using Definition 4 it then follows that ${\mathit{L}}^{\prime }$ is also a complete labelling of F. But this is a contradiction because it implies that L cannot be the grounded labelling of F. Hence $\mathit{L}={\mathit{L}}^{\prime }$ . □

Proposition 9.

The $\mathit{\text{stb}}$ semantics satisfies $\mathbf{OO}$ , $\mathbf{IO}$ and $\mathbf{OI}$ addition persistence.

Proof.

Follows directly from definition of a stable labelling (Definition 7). □

Proposition 10.

The $\mathit{\text{pr}}$ semantics satisfies $\mathbf{OI}$ , $\mathbf{OO}$ and $\mathbf{OU}$ addition persistence.

Proof.

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ and ${\mathit{F}}^{\prime }=\mathrm{(}\mathit{A}\mathrm{,}⇝\cup \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}\mathrm{)}$ . We assume that $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\notin ⇝$ (the case $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in ⇝$ is trivial). Suppose $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}\mathit{F}\mathrm{)}$ . Assume $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ . We prove that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}{\mathit{F}}^{\prime }\mathrm{)}$ . If $\mathit{x}⇝\mathit{y}$ we are done. For the case $\mathit{x}⇝̸\mathit{y}$ , assume the contrary. Because the complete semantics satisfies $\mathbf{OI}$ , $\mathbf{OO}$ and $\mathbf{OU}$ addition persistence (Proposition 5) we have $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}{\mathit{F}}^{\prime }\mathrm{)}$ and thus there must be an ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}{\mathit{F}}^{\prime }\mathrm{)}$ such that ${\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}\subset {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}$ . Proposition 3 then implies ${\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{O}}\mathrm{)}\subset {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{O}}\mathrm{)}$ and hence ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ . Since $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ , Definition 4 then implies that ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathit{F}\mathrm{)}$ . But this is a contradiction because it implies that L cannot be a preferred labelling of F. Hence $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}{\mathit{F}}^{\prime }\mathrm{)}$ . □

Proposition 11.

The $\mathit{\text{pr}}$ semantics satisfies $\mathbf{UO}$ and $\mathbf{IO}$ addition persistence.

Proof.

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ and ${\mathit{F}}^{\prime }=\mathrm{(}\mathit{A}\mathrm{,}⇝\cup \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}\mathrm{)}$ . We assume that $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\notin ⇝$ (the case $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in ⇝$ is trivial). Suppose $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}\mathit{F}\mathrm{)}$ . Assume $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ . We prove that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}{\mathit{F}}^{\prime }\mathrm{)}$ . If $\mathit{x}⇝\mathit{y}$ we are done. For the case $\mathit{x}⇝̸\mathit{y}$ , assume the contrary. Let $\mathit{z}\in \mathit{A}$ be an argument such that $\mathit{z}\ne \mathit{x}$ , $\mathit{L}\mathrm{(}\mathit{z}\mathrm{)}=\mathbf{\text{I}}$ and $\mathit{z}⇝\mathit{y}$ (existence of z follows from Definition 4). Because the complete semantics satisfies $\mathbf{UO}$ and $\mathbf{IO}$ addition persistence (Proposition 5) we get $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}{\mathit{F}}^{\prime }\mathrm{)}$ and thus there must be an ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}{\mathit{F}}^{\prime }\mathrm{)}$ such that ${\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}\subset {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}$ . This implies ${\mathit{L}}^{\prime }\mathrm{(}\mathit{z}\mathrm{)}=\mathbf{\text{I}}$ and therefore ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ . Because the complete semantics satisfies $\mathbf{IO}$ , $\mathbf{UO}$ and $\mathbf{OO}$ addition persistence (Proposition 5) it follows that ${\mathit{L}}^{\prime }$ is a complete labelling of F. But this is a contradiction because it implies that L cannot be a preferred labelling of F. Hence $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}{\mathit{F}}^{\prime }\mathrm{)}$ . □

Proposition 12.

The $\mathit{\text{stb}}$ semantics satisfies $\mathbf{OU}$ , $\mathbf{UO}$ , $\mathbf{UU}$ , $\mathbf{UI}$ and $\mathbf{IU}$ addition persistence.

Proof.

This follow vacuously because, in a stable labelling, no argument is labelled $\mathbf{\text{U}}$ . □

4. Removal persistence

We say that a semantics σ satisfies $\mathit{X}\mathit{Y}$ removal persistence whenever every σ labelling of an argumentation framework F in which two arguments x and y are labelled X and Y, respectively, is still a σ labelling of F after removing the attack from x to y. Formally:

Definition 9.

Let σ be a semantics and let $\mathit{X}\mathrm{,}\mathit{Y}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{I}}\mathrm{,}\mathbf{\text{U}}\}$ . We say that σ satisfies $\mathit{X}\mathit{Y}$ removal persistence if and only if for all $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\in \mathcal{F}$ and $\mathit{x}\mathrm{,}\mathit{y}\in \mathit{A}$ , if $\mathit{L}\in {\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ , $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathit{X}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathit{Y}$ , then $\mathit{L}\in {\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\setminus \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}\mathrm{)}\mathrm{)}$ .

Table 2 shows the full overview of removal persistence under the semantics we consider. Like before, gray cells refer to proofs and indicate that removal persistence holds, while white cells refer to counterexamples and indicate that removal persistence does not hold.

Table 2

Removal persistence for labelling-based semantics

We can distinguish three types of removal persistence principles. First of all, $\mathbf{UI}$ , $\mathbf{IU}$ and $\mathbf{II}$ removal persistence are trivially satisfied under all semantics we consider, where these combinations of labels are never assigned to two arguments where one attacks the other.

The $\mathbf{UU}$ and $\mathbf{IO}$ removal persistence principles are of the second type. These principles fail under the complete semantics, where the attack that is removed may be required for the justification of label of second argument. As a direct consequence, these principles fail under all semantics, since they are all based on complete labellings. The only exception here is $\mathbf{UU}$ removal persistence, which is vacuously satisfied under the stable semantics.

The $\mathbf{OO}$ , $\mathbf{OU}$ , $\mathbf{UO}$ and $\mathbf{OI}$ removal persistence principles are of the third type. They are all satisfied by the complete semantics. Thus, they cover the complete range of possible removals of attacks that do not invalidate a complete labelling. On this ground, these principles may be regarded as reasonable or desirable principles for all semantics we consider in this paper, since they are all based on complete labellings. Whether they are satisfied under these semantics does not only depend on whether the removed attack invalidates a complete labelling, however. It also depends on whether the removal changes the set of complete labellings as a whole, which in turn may lead to a change in the set of labellings that are grounded, preferred, semi-stable, and so on. Thus, the situation is similar to that of addition persistence in the previous section. Interestingly, the results here show a sharp contrast between the grounded, preferred and stable semantics, which satisfy all principles of the third type, and the semi-stable, ideal and eager semantics, which satisfy none.

In the remainder of this section, we present the counterexamples for the white cells in Table 2 and proofs for the gray cells.

Example 15 (Failure of $\mathbf{OO}$ removal persistence under the semi-stable and eager semantics).

In the argumentation framework shown in Fig. 10 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer a semi-stable or eager labelling after removing the attack drawn with a dotted line. The new semi-stable and eager labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ .

Fig. 10.

$\mathbf{OO}$ removal persistence $\mathit{\text{ss}}$ , $\mathit{\text{id}}$ and $\mathit{\text{ea}}$ .

Example 16 (Failure of $\mathbf{OO}$ removal persistence under the ideal semantics).

In the argumentation framework shown in Fig. 10 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer the ideal labelling after removing the attack drawn with a dotted line. The new ideal labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ .

Example 17 (Failure of $\mathbf{OU}$ removal persistence semi-stable and eager semantics).

In the argumentation framework shown in Fig. 11 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{f}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer a semi-stable or eager labelling after removing the attack drawn with a dotted line. The new semi-stable and eager labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{f}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ .

Fig. 11.

$\mathbf{OU}$ removal persistence $\mathit{\text{ss}}$ , $\mathit{\text{id}}$ and $\mathit{\text{ea}}$ .

Example 18 (Failure of $\mathbf{OU}$ removal persistence ideal semantics).

In the argumentation framework shown in Fig. 11 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{f}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer the ideal labelling after removing the attack drawn with a dotted line. The new ideal labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{f}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ .

Example 19 (Failure of $\mathbf{UO}$ removal persistence semi-stable and eager semantics).

In the argumentation framework shown in Fig. 12 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer a semi-stable or eager labelling after removing the attack drawn with a dotted line. The new semi-stable and eager labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ .

Fig. 12.

$\mathbf{UO}$ removal persistence $\mathit{\text{ss}}$ , $\mathit{\text{id}}$ and $\mathit{\text{ea}}$ .

Example 20 (Failure of $\mathbf{UO}$ removal persistence ideal semantics).

In the argumentation framework shown in Fig. 12 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer the ideal labelling after removing the attack drawn with a dotted line. The new ideal labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ .

Example 21 (Failure of $\mathbf{UU}$ removal persistence under all but the stable semantics).

This case is trivial: consider an argumentation framework consisting of one self-attacking argument. This argument is undecided, but is no longer undecided if the self-attack is removed.

Example 22 (Failure of $\mathbf{OI}$ removal persistence semi-stable and eager semantics).

In the argumentation framework shown in Fig. 13 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{f}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer a semi-stable or eager labelling after removing the attack drawn with a dotted line. The new semi-stable and eager labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{f}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ .

Fig. 13.

$\mathbf{OI}$ removal persistence $\mathit{\text{ss}}$ , $\mathit{\text{id}}$ and $\mathit{\text{ea}}$ .

Example 23 (Failure of $\mathbf{OI}$ removal persistence ideal semantics).

In the argumentation framework shown in Fig. 13 the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{f}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is no longer the ideal labelling after removing the attack drawn with a dotted line. The new ideal labelling is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{f}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ .

Example 24 (Failure of $\mathbf{IO}$ removal persistence under all semantics).

This case is trivial: consider an argumentation framework consisting of two arguments a and b where a attacks b. Under all semantics considered here, a is labelled $\mathbf{\text{I}}$ and b is labelled $\mathbf{\text{O}}$ . If we remove the attack from a to b then a and b are both labelled $\mathbf{\text{I}}$

Proposition 13.

The $\mathit{\text{gr}}$ semantics satisfies $\mathbf{OO}$ and $\mathbf{OU}$ removal persistence.

Proof.

Let L be the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ , let ${⇝}^{\prime }=⇝\setminus \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}$ , and let ${\mathit{L}}^{\prime }$ be the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . We assume that $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in ⇝$ (the case $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\notin ⇝$ is trivial). We assume $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{U}}\}$ and prove that $\mathit{L}={\mathit{L}}^{\prime }$ . If $\mathit{x}⇝̸\mathit{y}$ we are done. For the case $\mathit{x}⇝\mathit{y}$ , we assume $\mathit{L}\ne {\mathit{L}}^{\prime }$ and derive a contradiction. Since $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ , Definition 4 then implies that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}\mathrm{)}$ . Proposition 4 then implies that ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{U}}\}$ and ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{U}}\}$ . Because the complete semantics satisfies $\mathbf{OO}$ , $\mathbf{OU}$ , $\mathbf{UO}$ and $\mathbf{UU}$ addition persistence (Proposition 5) we have ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . But this is a contradiction because it implies that L is not the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ . Hence $\mathit{L}={\mathit{L}}^{\prime }$ . □

Proposition 14.

The $\mathit{\text{co}}$ semantics satisfies $\mathbf{OO}$ removal persistence.

Proof.

Follows directly from Definition 4. □

Proposition 15.

The $\mathit{\text{pr}}$ semantics satisfies $\mathbf{OO}$ , $\mathbf{OU}$ and $\mathbf{OI}$ removal persistence.

Proof.

Let $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ be an argumentation framework and let $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . Assume $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ . Let ${⇝}^{\prime }=⇝\setminus \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}$ . We assume that $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in ⇝$ (the case $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\notin ⇝$ is trivial). We prove that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}\mathrm{)}$ . If $\mathit{x}⇝̸\mathit{y}$ we are done. For the case $\mathit{x}⇝\mathit{y}$ , assume the contrary. Since $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ , Definition 4 then implies that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}\mathrm{)}$ . It follows that there is an ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}\mathrm{)}$ such that ${\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}\subset {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}$ . Proposition 3 then implies ${\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{O}}\mathrm{)}\subset {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{O}}\mathrm{)}$ and hence ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ . Because the complete semantics satisfies $\mathbf{OO}$ , $\mathbf{OU}$ and $\mathbf{OI}$ addition persistence (Proposition 5) it follows that ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . But this is a contradiction because it implies that L is not a preferred labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ . Hence $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}\mathrm{)}$ . □

Proposition 16.

The $\mathit{\text{pr}}$ semantics satisfies $\mathbf{UO}$ removal persistence.

Proof.

Let $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ be an argumentation framework and let $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . Assume $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{U}}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ . Let ${⇝}^{\prime }=⇝\setminus \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}$ . We assume that $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in ⇝$ (the case $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\notin ⇝$ is trivial). We prove that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}\mathrm{)}$ . If $\mathit{x}⇝̸\mathit{y}$ we are done. For the case $\mathit{x}⇝\mathit{y}$ , assume the contrary. Since $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ , Definition 4 then implies that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}\mathrm{)}$ . It follows that there is an ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}\mathrm{)}$ such that ${\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}\subset {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{I}}\mathrm{)}$ . Proposition 3 then implies ${\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{O}}\mathrm{)}\subset {\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{O}}\mathrm{)}$ and hence ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ . Because the complete semantics satisfies $\mathbf{OO}$ , $\mathbf{UO}$ and $\mathbf{IO}$ addition persistence (Proposition 5) it follows that ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . But this is a contradiction because it implies that L is not a preferred labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ . Hence $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{pr}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}\mathrm{)}$ . □

Proposition 17.

The $\mathit{\text{stb}}$ semantics satisfies $\mathbf{OO}$ and $\mathbf{OI}$ removal persistence.

Proof.

Follows directly from Definition 7. □

Proposition 18.

The $\mathit{\text{gr}}$ semantics satisfies $\mathbf{OI}$ removal persistence.

Proof.

Let $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ be an argumentation framework. Let ${⇝}^{\prime }=⇝\setminus \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}$ . We assume that $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in ⇝$ (the case $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\notin ⇝$ is trivial). Let L be the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ and assume $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{I}}$ . Since $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ , Definition 4 then implies that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}\mathrm{)}$ . We now suppose L is not the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ and prove that this leads to a contradiction. Then let ${\mathit{L}}^{\prime }$ be the actual grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . We then have ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{U}}\}$ and ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}\in \{\mathbf{\text{I}}\mathrm{,}\mathbf{\text{U}}\}$ . We distinguish two cases:

${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ or ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{U}}$ : Because the complete semantics satisfies $\mathbf{OI}$ , $\mathbf{OU}$ and $\mathbf{UU}$ addition persistence (Proposition 5) it follows that ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . But this is a contradiction, since L is the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ and we have ${\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{U}}\mathrm{)}\subset {\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{U}}\mathrm{)}$ .

${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{U}}$ and ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{I}}$ : For this case we transform ${\mathit{L}}^{\prime }$ into a new labelling ${\mathit{L}}^{″}$ by repeatedly relabelling arguments as follows. For every argument x:

if x is $\mathbf{\text{I}}$ and x is attacked (in $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ ) by an argument labelled $\mathbf{\text{U}}$ then relabel x as $\mathbf{\text{U}}$ .

if x is $\mathbf{\text{O}}$ and x is not attacked (in $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ ) by an argument labelled $\mathbf{\text{I}}$ then relabel x as $\mathbf{\text{U}}$ .

If we repeat these steps until no more arguments are relabelled then the resulting labelling ${\mathit{L}}^{″}$ is a complete labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ such that ${\mathit{L}}^{″}\mathrm{(}\mathit{x}\mathrm{)}={\mathit{L}}^{″}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{U}}$ . But this is a contradiction, since L is the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ and we have ${\mathit{L}}^{″-1}\mathrm{(}\mathbf{\text{U}}\mathrm{)}\subset {\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{U}}\mathrm{)}$ .

Since both cases lead to contradiction it follows that L is the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . □

Proposition 19.

The $\mathit{\text{gr}}$ semantics satisfies $\mathbf{UO}$ removal persistence.

Proof.

Let $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ be an argumentation framework. Let ${⇝}^{\prime }=⇝\setminus \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}$ . We assume that $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in ⇝$ (the case $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\notin ⇝$ is trivial). Let L be the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ and assume $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{U}}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ . Since $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ , Definition 4 then implies that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}\mathrm{)}$ . We now suppose L is not the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ and prove that this leads to a contradiction. Then let ${\mathit{L}}^{\prime }$ be the actual grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . We then have ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{U}}$ and ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{U}}\}$ . Because the complete semantics satisfies $\mathbf{UO}$ and $\mathbf{UU}$ addition persistence (Proposition 5 and 5) it follows that ${\mathit{L}}^{\prime }\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . But this is a contradiction, since L is the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ and we have ${\mathit{L}}^{\prime -1}\mathrm{(}\mathbf{\text{U}}\mathrm{)}\subset {\mathit{L}}^{-1}\mathrm{(}\mathbf{\text{U}}\mathrm{)}$ . Hence L is the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . □

Proposition 20.

The $\mathit{\text{co}}$ semantics satisfies $\mathbf{OU}$ , $\mathbf{OI}$ and $\mathbf{UO}$ removal persistence.

Proof.

Follows directly from Definition 4. □

Proposition 21.

Any complete-based semantics satisfies $\mathbf{UI}$ , $\mathbf{IU}$ , and $\mathbf{II}$ removal persistence.

Proof.

This holds vacuously because, in a complete labelling, these combinations of labels are never assigned to two arguments of which one attacks the other. □

Proposition 22.

The $\mathit{\text{stb}}$ semantics satisfies $\mathbf{OU}$ , $\mathbf{UO}$ and $\mathbf{UU}$ removal persistence.

Proof.

This holds vacuously because, in a stable labelling, no argument is labelled $\mathbf{\text{U}}$ . □

5. Addition monotonicity

We now consider addition monotonicity for labelling-based semantics. Suppose x and y are labelled X and Y, respectively, in every σ labelling of an argumentation framework F. The $\mathit{X}\mathit{Y}$ addition persistence principle then implies that no σ labelling gets destroyed if we add an attack from x to y to F. The principles we consider now state, on the other hand, that no additional σ labelling is created, if we add an attack from x to y.

Definition 10.

Let σ be a semantics and let $\mathit{X}\mathrm{,}\mathit{Y}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{I}}\mathrm{,}\mathbf{\text{U}}\}$ . We say that σ satisfies $\mathit{X}\mathit{Y}$ addition monotonicity if and only if for all $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\in \mathcal{F}$ such that ${\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}\ne \varnothing$ , and for all $\mathit{x}\mathrm{,}\mathit{y}\in \mathit{A}$ : $$\begin{array}{c}\text{If for all }\mathit{L}\in {\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}\mathrm{,}\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathit{X}\text{ and }\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathit{Y}\text{ then }{\mathcal{L}}_{\mathit{\sigma }}\mathrm{\left(}\mathrm{\right(}\mathit{A}\mathrm{,}⇝\cup \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}\mathrm{\left)}\mathrm{\right)}\subseteq {\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}.\end{array}$$

Remark 1.

Addition monotonicity is concerned only with how the set of σ labellings of an argumentation framework $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ changes if the initial set of labellings is nonempty (i.e., if ${\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}\ne \varnothing$ ). This allows us to obtain informative results for the stable semantics, which would otherwise vacuously fail all variants of addition monotonicity. To see why, consider the argumentation framework $\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\{\mathrm{(}\mathit{b}\mathrm{,}\mathit{b}\mathrm{)}\}\mathrm{)}$ . We have ${\mathcal{L}}_{\mathit{\text{stb}}}\mathrm{(}\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\{\mathrm{(}\mathit{b}\mathrm{,}\mathit{b}\mathrm{)}\}\mathrm{)}\mathrm{)}\mathrm{)}=\varnothing$ and hence $$\begin{array}{}\text{(1)}& \text{for all }\mathit{L}\in {\mathcal{L}}_{\mathit{\text{stb}}}\mathrm{\left(}\mathrm{\right(}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\{\mathrm{(}\mathit{b}\mathrm{,}\mathit{b}\mathrm{)}\}\mathrm{\left)}\mathrm{\right)}\mathrm{,}\mathit{L}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{O}}\text{ and }\mathit{L}\mathrm{(}\mathit{b}\mathrm{)}=\mathbf{\text{O}}.\end{array}$$ Moreover we have $$\begin{array}{}\text{(2)}& {\mathcal{L}}_{\mathit{\text{stb}}}\mathrm{\left(}\mathrm{\right(}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\{\mathrm{(}\mathit{b}\mathrm{,}\mathit{b}\mathrm{)}\}\cup \{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\}\mathrm{\left)}\mathrm{\right)}=\left\{\right\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\left\}\right\}⊈{\mathcal{L}}_{\mathit{\text{stb}}}\mathrm{\left(}\mathrm{\right(}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\{\mathrm{(}\mathit{b}\mathrm{,}\mathit{b}\mathrm{)}\}\mathrm{\left)}\mathrm{\right)}.\end{array}$$ If we do not require the initial set of labellings to be nonempty then this example would imply failure of $\mathbf{OO}$ addition monotonicity under the stable semantics. This is, however, not informative, as it is due to the fact that (1) holds vacuously.

For any unique status semantics (cf. Proposition 2) it holds that addition monotonicity coincides with addition persistence.

Proposition 23.

If σ is a unique status semantics then σ satisfies XY addition monotonicity if and only if σ satisfies XY addition persistence.

We now show which of the labelling-based semantics that we consider satisfy or violate addition monotonicity. Table 3 shows the full overview: a gray cell means that the principle is satisfied and a white cell means that it is violated. The white and gray cells refer to the counterexamples and proofs provided in this section.

Table 3

Addition monotonicity for labelling-based semantics

	Addition monotonicity
	$\mathbf{OO}$	$\mathbf{OU}$	$\mathbf{UO}$	$\mathbf{UU}$	$\mathbf{OI}$	$\mathbf{UI}$	$\mathbf{IO}$	$\mathbf{IU}$	$\mathbf{II}$
Grounded	Prp. 24	Prp. 24	Prp. 24	Prp. 24	Ex. 32	Ex. 25	Prp. 24	Ex. 26	Ex. 27
Complete	Prp. 25	Prp. 25	Prp. 26	Ex. 31	Ex. 32	Ex. 25	Prp. 26	Ex. 26	Ex. 27
Preferred	Ex. 28	Ex. 29	Ex. 30	Ex. 31	Ex. 32	Ex. 25	Ex. 33	Ex. 26	Ex. 27
Stable	Ex. 28	Prp. 27	Prp. 27	Prp. 27	Ex. 32	Prp. 27	Ex. 33	Prp. 27	Ex. 27
Semi-stable	Ex. 28	Ex. 29	Ex. 30	Ex. 31	Ex. 32	Ex. 25	Ex. 33	Ex. 26	Ex. 27
Ideal	Ex. 2	Ex. 4	Ex. 6	Ex. 7	Ex. 32	Ex. 25	Ex. 12	Ex. 26	Ex. 27
Eager	Ex. 1	Ex. 3	Ex. 5	Ex. 7	Ex. 9	Ex. 25	Ex. 11	Ex. 26	Ex. 27

Three types of addition monotonicity principles can be distinguished. The $\mathbf{UI}$ , $\mathbf{IU}$ and $\mathbf{II}$ addition monotonicity principles represent the first type. Like the corresponding addition persistence principles, they are violated under the complete semantics because they deal with the addition of an attack after which the label of the attacked argument is no longer justified under the complete semantics. A direct consequence is that these principles are violated under all the semantics we consider, since they are all based on complete labellings. The exception is the stable semantics, which vacuously satisfies $\mathbf{UI}$ and $\mathbf{IU}$ addition monotonicity.

The remaining principles form the second type: $\mathbf{UU}$ , $\mathbf{OI}$ , $\mathbf{OO}$ , $\mathbf{OU}$ , $\mathbf{UO}$ and $\mathbf{IO}$ addition monotonicity. First note that the addition persistence principles for these combinations of labels are all satisfied under the complete semantics. The addition monotonicity principles are only partially satisfied, however. In particular, $\mathbf{UU}$ and $\mathbf{OI}$ addition monotonicity fail under the complete semantics, as demonstrated in Examples 31 and 32. These principles are also violated by all the other semantics, with the exception of $\mathbf{UU}$ addition monotonicity, which is satisfied by the grounded semantics and vacuously satisfied by the stable semantics. The remaining principles, i.e., $\mathbf{OO}$ , $\mathbf{OU}$ , $\mathbf{UO}$ and $\mathbf{IO}$ addition monotonicity, are all satisfied under the complete semantics. They are also satisfied under the grounded semantics, but this follows from the corresponding results for addition persistence (see Proposition 23). However, the preferred, semi-stable, ideal and eager semantics violate these four principles. The stable semantics furthermore vacuously satisfies $\mathbf{OU}$ , $\mathbf{UO}$ addition monotonicity but violates $\mathbf{OO}$ and $\mathbf{IO}$ addition monotonicity.

In the remainder of this section, we present the counterexamples for the white cells in Table 3 and proofs for the gray cells.

Example 25 (Failure of $\mathbf{UI}$ addition monotonicity under the all but the stable semantics.).

Consider an argumentation framework with two arguments a, b, where a is self-attacking. The unique labelling under all but the stable semantics assigns $\mathbf{\text{U}}$ to a and $\mathbf{\text{I}}$ to b. If we add an attack from a to b the new unique labelling under all but the stable semantics assigns $\mathbf{\text{U}}$ to both a and b.

Example 26 (Failure of $\mathbf{IU}$ addition monotonicity under all but the stable semantics.).

Consider an argumentation framework with two arguments a, b, where b is self-attacking. The unique labelling under all but the stable semantics assigns $\mathbf{\text{I}}$ to a and $\mathbf{\text{U}}$ to b. If we add an attack from a to b the new unique labelling under all but the stable semantics assigns $\mathbf{\text{I}}$ to a and $\mathbf{\text{O}}$ to b.

Example 27 (Failure of $\mathbf{II}$ addition monotonicity under all semantics).

Consider an argumentation framework with two arguments a, b and no attacks. The unique labelling under all semantics assigns $\mathbf{\text{I}}$ to both a and b. If we add an attack from a to b the new unique labelling under all semantics assigns $\mathbf{\text{I}}$ to a and $\mathbf{\text{O}}$ to b.

Example 28 (Failure of $\mathbf{OO}$ addition monotonicity under the $\mathit{\text{pr}}$ , $\mathit{\text{stb}}$ and $\mathit{\text{ss}}$ semantics).

Let F be the argumentation framework shown in Fig. 14 (not including the attack drawn with a dotted line). The labelling $\mathit{L}=\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ is the unique preferred, stable and semi-stable labelling of F. If we add an attack from e to c (drawn with a dotted line), which are both labelled $\mathbf{\text{O}}$ in L, then a new preferred, stable and semi-stable labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\}$ appears.

Fig. 14.

Failure of $\mathbf{OO}$ addition monotonicity.

Fig. 15.

Failure of $\mathbf{OU}$ addition monotonicity under the preferred and semi-stable semantics.

Example 29 (Failure of $\mathbf{OU}$ addition monotonicity under the $\mathit{\text{pr}}$ and $\mathit{\text{ss}}$ semantics).

Let F be the argumentation framework shown in Fig. 15 (not including the attack drawn with a dotted line). The labelling $\mathit{L}=\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is the unique preferred and semi-stable labelling of F. If we add an attack attack from c to a (drawn with a dotted line), which are labelled, respectively, $\mathbf{\text{O}}$ and $\mathbf{\text{U}}$ in L, then a new preferred and semi-stable labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ appears.

Example 30 (Failure of $\mathbf{UO}$ addition monotonicity under the preferred and semi-stable semantics).

Let F be the argumentation framework shown in Fig. 16 (not including the attack drawn with a dotted line). The labelling $\mathit{L}=\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is the unique preferred and semi-stable labelling of F. If we add an attack attack from e to a (drawn with a dotted line), which are labelled, respectively, $\mathbf{\text{U}}$ and $\mathbf{\text{O}}$ in L, then a new preferred and semi-stable labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\}$ appears.

Fig. 16.

Failure of $\mathbf{UO}$ addition monotonicity under the preferred and semi-stable semantics.

Example 31 (Failure of $\mathbf{UU}$ addition monotonicity under the $\mathit{\text{co}}$ , $\mathit{\text{pr}}$ and $\mathit{\text{ss}}$ semantics).

Consider an argumentation framework F with two arguments a and b where a attacks b and a is self-attacking. Let L be the labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ . We have that L is the unique complete labelling of F as well as the unique preferred and semi-stable labelling. If we add an attack from b to a, a new complete labelling ${\mathit{L}}^{\prime }=\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\}$ appears, and ${\mathit{L}}^{\prime }$ is also preferred and semi-stable.

Example 32 (Failure of $\mathbf{OI}$ addition monotonicity under all semantics).

Consider an argumentation framework F with two arguments a and b where a attacks b. Let ${\mathit{F}}^{\prime }$ be the same argumentation framework with an additional attack from b to a. Under all semantics we consider, the unique labelling of F is $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ , while ${\mathit{F}}^{\prime }$ possesses a labelling (such as $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ or $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\}$ ) that is not a labelling of F under that semantics.

Example 33 (Failure of $\mathbf{IO}$ addition monotonicity under the preferred, stable and semi-stable semantics).

Let F be the argumentation framework shown in Fig. 17 (not including the attack drawn with a dotted line). The labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ is the unique preferred, stable and semi-stable labelling of F. If we add an attack from b to c (drawn with a dotted line), which are labelled, respectively, $\mathbf{\text{I}}$ and $\mathbf{\text{O}}$ in L, then a new preferred, stable and semi-stable labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\}$ appears.

Fig. 17.

Failure of $\mathbf{IO}$ addition monotonicity.

Proposition 24.

The $\mathit{\text{gr}}$ semantics satisfies $\mathbf{OO}$ , $\mathbf{OU}$ , $\mathbf{UO}$ , $\mathbf{UU}$ and $\mathbf{IO}$ addition monotonicity.

Proof.

Follows from Proposition 6 and 8 together with Proposition 23. □

Proposition 25.

The $\mathit{\text{co}}$ semantics satisfies $\mathbf{OO}$ and $\mathbf{OU}$ addition monotonicity.

Proof.

Let $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ be an argumentation framework. Let ${⇝}^{\prime }=⇝\cup \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}$ . We assume that $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\notin ⇝$ (the case $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in ⇝$ is trivial). Suppose for all $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ we have $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{U}}\}$ . Let $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}\mathrm{)}$ . We prove that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . Let ${\mathit{L}}^{\prime }$ be the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ . Our assumption implies ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ and ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{U}}\}$ . Because the grounded semantics satisfies $\mathbf{OO}$ and $\mathbf{OU}$ addition persistence (Proposition 6 and 8) it follows that ${\mathit{L}}^{\prime }$ is the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ and hence $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ . Because the complete semantics satisfies $\mathbf{OO}$ , $\mathbf{OU}$ and $\mathbf{OI}$ removal persistence (Proposition 14 and 20), it finally follows that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . □

Proposition 26.

The $\mathit{\text{co}}$ semantics satisfies $\mathbf{IO}$ and $\mathbf{UO}$ addition monotonicity.

Proof.

Let $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ be an argumentation framework. Let ${⇝}^{\prime }=⇝\cup \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}$ . We assume that $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\notin ⇝$ (the case $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in ⇝$ is trivial). Suppose for all $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ we have $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}\in \{\mathbf{\text{I}}\mathrm{,}\mathbf{\text{U}}\}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ . Let $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}\mathrm{)}$ . We prove that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . Let ${\mathit{L}}^{\prime }$ be the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ . Our assumption implies that ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}\in \{\mathbf{\text{I}}\mathrm{,}\mathbf{\text{U}}\}$ and ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ . Then let z be argument such that $\mathit{z}\ne \mathit{x}$ , ${\mathit{L}}^{\prime }\mathrm{(}\mathit{z}\mathrm{)}=\mathbf{\text{I}}$ and $\mathit{z}⇝\mathit{y}$ (existence of z follows from Definition 4). Because the grounded semantics satisfies $\mathbf{IO}$ and $\mathbf{UO}$ addition persistence (Proposition 7) it follows that ${\mathit{L}}^{\prime }$ is the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . Hence $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ and $\mathit{L}\mathrm{(}\mathit{z}\mathrm{)}=\mathbf{\text{I}}$ . Definition 4 then implies that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . □

Proposition 27.

The $\mathit{\text{stb}}$ semantics satisfies $\mathbf{OU}$ , $\mathbf{UO}$ , $\mathbf{UU}$ , $\mathbf{UI}$ and $\mathbf{IU}$ addition monotonicity.

Proof.

This holds vacuously because, in a stable labelling, no argument is labelled $\mathbf{\text{U}}$ . □

6. Removal monotonicity

We finally consider removal monotonicity in the labelling-based setting. Like before, we require that the initial set of labellings is non-empty (see Remark 1).

Definition 11.

Let σ be a semantics and let $\mathit{X}\mathrm{,}\mathit{Y}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{I}}\mathrm{,}\mathbf{\text{U}}\}$ . We say that σ satisfies $\mathit{X}\mathit{Y}$ removal monotonicity if and only if for all $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\in \mathcal{F}$ such that ${\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}\ne \varnothing$ , and for all $\mathit{x}\mathrm{,}\mathit{y}\in \mathit{A}$ : $$\begin{array}{c}\text{If for all }\mathit{L}\in {\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}\mathrm{,}\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathit{X}\text{ and }\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathit{Y}\text{ then }{\mathcal{L}}_{\mathit{\sigma }}\mathrm{\left(}\mathrm{\right(}\mathit{A}\mathrm{,}⇝\setminus \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}\mathrm{\left)}\mathrm{\right)}\subseteq {\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}.\end{array}$$

Removal monotonicity coincides with removal persistence for any unique status semantics (cf. Proposition 2).

Proposition 28.

If σ is a unique status semantics then σ satisfies XY removal monotonicity if and only if σ satisfies XY removal persistence.

We now show which of the labelling-based semantics that we consider satisfy or violate removal monotonicity. Table 4 shows the full overview: a gray cell means that the principle is satisfied and a white cell means that it is violated. The white and gray cells refer to the counterexamples and proofs provided in this section.

Table 4

Removal monotonicity for labelling-based semantics

	Removal monotonicity
	$\mathbf{OO}$	$\mathbf{OU}$	$\mathbf{UO}$	$\mathbf{UU}$	$\mathbf{OI}$	$\mathbf{UI}$	$\mathbf{IO}$	$\mathbf{IU}$	$\mathbf{II}$
Grounded	Prp. 29	Prp. 29	Prp. 29	Ex. 34	Prp. 29	Prp. 32	Ex. 35	Prp. 32	Prp. 32
Complete	Prp. 30	Prp. 30	Prp. 31	Ex. 34	Prp. 30	Prp. 32	Ex. 35	Prp. 32	Prp. 32
Preferred	Ex. 36	Ex. 37	Ex. 38	Ex. 34	Ex. 39	Prp. 32	Ex. 35	Prp. 32	Prp. 32
Stable	Ex. 36	Prp. 33	Prp. 33	Prp. 33	Ex. 39	Prp. 32	Ex. 35	Prp. 32	Prp. 32
Semi-stable	Ex. 36	Ex. 37	Ex. 38	Ex. 34	Ex. 39	Prp. 32	Ex. 35	Prp. 32	Prp. 32
Ideal	Ex. 16	Ex. 18	Ex. 20	Ex. 34	Ex. 23	Prp. 32	Ex. 35	Prp. 32	Prp. 32
Eager	Ex. 15	Ex. 17	Ex. 19	Ex. 34	Ex. 22	Prp. 32	Ex. 35	Prp. 32	Prp. 32

We can distinguish three types of removal monotonicity principles. The $\mathbf{UI}$ , $\mathbf{IU}$ and $\mathbf{II}$ removal monotonicity principles represent the first type. Like removal persistence for these combinations of labels, these principles are trivially satisfied by all semantics we consider, under which these combinations of labels are never assigned to two arguments where the first attacks the second.

The $\mathbf{UU}$ and $\mathbf{IO}$ removal monotonicity principles represent the second type. Like the removal persistence principles for these combinations of labels, these principles fail under the complete semantics, where the attack that is removed may be required for the justification of label of second argument. Removal of these attacks may therefore lead to new labellings, as demonstrated in Examples 35 and 34. As a consequence $\mathbf{UU}$ and $\mathbf{IO}$ removal monotonicity fail under all the other semantics as well, since they are all based on complete labellings. The only exception is the stable semantics, which trivially satisfies $\mathbf{UU}$ removal monotonicity.

The remaining removal monotonicity principles represent the third type. These are $\mathbf{OO}$ , $\mathbf{OU}$ , $\mathbf{UO}$ and $\mathbf{OI}$ removal monotonicity. Like the removal persistence principles for these combinations of labels, these principles are all satisfied under the complete semantics. The grounded semantics also satisfies all these principles. None of the other semantics satisfy any of these principles, however, except for the stable semantics, which trivially satisfies $\mathbf{OU}$ and $\mathbf{UO}$ removal monotonicity.

In the remainder of this section, we present the counterexamples for the white cells in Table 4 and proofs for the gray cells.

Example 34 (Failure of $\mathbf{UU}$ removal monotonicity under all but the stable semantics.).

Consider an argumentation framework with two arguments a, b, where a is self-attacking and a attacks b. The unique labelling under all but the stable semantics assigns $\mathbf{\text{U}}$ to both a and b. If we remove the attack from a to b the new unique labelling under all but the stable semantics assigns $\mathbf{\text{U}}$ to a and $\mathbf{\text{I}}$ to b.

Example 35 (Failure of $\mathbf{IO}$ removal monotonicity under all semantics.).

Consider an argumentation framework with two arguments a, b, where a attacks b. The unique labelling under all semantics assigns $\mathbf{\text{I}}$ to a and $\mathbf{\text{O}}$ to b. If we remove the attack from a to b the new unique labelling under semantics assigns $\mathbf{\text{I}}$ to both a and b.

Example 36 (Failure of $\mathbf{OO}$ removal monotonicity under the $\mathit{\text{pr}}$ , $\mathit{\text{stb}}$ and $\mathit{\text{ss}}$ semantics).

Let F be the argumentation framework shown in Fig. 18 (including the attack drawn with a dotted line). The labelling $\mathit{L}=\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ is the unique preferred, semi-stable and stable labelling of F. If we remove the attack from a to c (drawn with a dotted line), which are both labeled $\mathbf{\text{O}}$ in L, then a new preferred, semi-stable and stable labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\}$ appears.

Fig. 18.

Failure of $\mathbf{OO}$ removal monotonicity.

Example 37 (Failure of $\mathbf{OU}$ removal monotonicity under the $\mathit{\text{pr}}$ and $\mathit{\text{ss}}$ semantics).

Let F be the argumentation framework shown in Fig. 19 (including the attack drawn with a dotted line). The labelling $\mathit{L}=\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{f}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}$ is the unique preferred and semi-stable labelling of F. If we remove the attack from c to b (drawn with a dotted line), which are labeled $\mathbf{\text{O}}$ and $\mathbf{\text{U}}$ , respectively, then a new preferred and semi-stable labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{f}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ appears.

Fig. 19.

Failure of $\mathbf{OU}$ removal monotonicity.

Example 38 (Failure of $\mathbf{UO}$ removal monotonicity under the $\mathit{\text{pr}}$ and $\mathit{\text{ss}}$ semantics).

Let F be the argumentation framework shown in Fig. 20 (including the attack drawn with a dotted line). The labelling $\mathit{L}=\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\}$ is the unique preferred and semi-stable labelling of F. If we remove the attack from a to b (drawn with a dotted line), which are labeled, respectively, $\mathbf{\text{U}}$ and $\mathbf{\text{O}}$ in L, then a new preferred and semi-stable labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ appears.

Fig. 20.

Failure of $\mathbf{UO}$ removal monotonicity.

Example 39 (Failure of $\mathbf{OI}$ removal monotonicity under the $\mathit{\text{pr}}$ , $\mathit{\text{stb}}$ and $\mathit{\text{ss}}$ semantics).

Let F be the argumentation framework shown in Fig. 21. has a unique preferred, semi-stable and stable labelling $\mathit{L}=\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}$ . Removal of the attack from c to b (labelled $\mathbf{\text{O}}$ and $\mathbf{\text{I}}$ in L) leads to an additional preferred, semi-stable and stable labelling $\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\}$ .

Fig. 21.

Failure of $\mathbf{OI}$ removal monotonicity.

Proposition 29.

The $\mathit{\text{gr}}$ semantics satisfies $\mathbf{OO}$ , $\mathbf{OU}$ , $\mathbf{OI}$ and $\mathbf{UO}$ removal monotonicity.

Proof.

Follows from Proposition 28 together with Propositions 13, 18 and 19. □

Proposition 30.

The $\mathit{\text{co}}$ semantics satisfies $\mathbf{OO}$ , $\mathbf{OU}$ and $\mathbf{OI}$ removal monotonicity.

Proof.

Let $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ be an argumentation framework. Let ${⇝}^{\prime }=⇝\setminus \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}$ . We assume that $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in ⇝$ (the case $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\notin ⇝$ is trivial). Suppose for all $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ we have $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ . Let $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}\mathrm{)}$ . We prove that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . Let ${\mathit{L}}^{\prime }$ be the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ . Our assumption implies that ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ . Because the grounded semantics satisfies $\mathbf{OO}$ , $\mathbf{OU}$ and $\mathbf{OI}$ removal persistence (Proposition 13 and 18) it follows that ${\mathit{L}}^{\prime }$ is the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . Hence $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{O}}$ . Because the complete semantics satisfies $\mathbf{OO}$ , $\mathbf{OU}$ and $\mathbf{OI}$ addition persistence (Proposition 5), it follows that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . □

Proposition 31.

The $\mathit{\text{co}}$ semantics satisfies $\mathbf{UO}$ removal monotonicity.

Proof.

Let $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ be an argumentation framework. Let ${⇝}^{\prime }=⇝\setminus \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}$ . We assume that $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\in ⇝$ (the case $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\notin ⇝$ is trivial). Suppose for all $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ we have $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{U}}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ . Let $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}\mathrm{)}$ . We prove that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . Let ${\mathit{L}}^{\prime }$ be the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ . Our assumption implies that ${\mathit{L}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{U}}$ and ${\mathit{L}}^{\prime }\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ . Because the grounded semantics satisfies $\mathbf{UO}$ removal persistence (Proposition 19) it follows that ${\mathit{L}}^{\prime }$ is the grounded labelling of $\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ . Hence $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ . Because the complete semantics satisfies $\mathbf{OO}$ , $\mathbf{UO}$ and $\mathbf{IO}$ addition persistence (Proposition 5), it follows that $\mathit{L}\in {\mathcal{L}}_{\mathit{\text{co}}}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . □

Proposition 32.

Any complete-based semantics satisfies $\mathbf{UI}$ , $\mathbf{IU}$ , and $\mathbf{II}$ removal monotonicity.

Proof.

This holds vacuously because, in a complete labelling, these combinations of labels are never assigned to two arguments of which one attacks the other. □

Proposition 33.

The $\mathit{\text{stb}}$ semantics satisfies $\mathbf{OU}$ , $\mathbf{UO}$ and $\mathbf{UU}$ removal monotonicity.

Proof.

This holds vacuously because, in a stable labelling, no argument is labelled $\mathbf{\text{U}}$ . □

7. Persistence and monotonicity in the extension-based setting

Most of the semantics we consider in this paper were originally defined in terms of extensions. These extension-based definitions can also be derived from the labelling-based Definitions [31]. Given a semantics σ, a σ-extension of an argumentation framework $\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ is a set E such that $\mathit{E}=\{\mathit{x}\in \mathit{A}\mid \mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{\text{I}}\}$ for some $\mathit{L}\in {\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ . In this section, we examine persistence and monotonicity principles from the extension-based perspective. We do this by only distinguishing arguments that are in an extension from those that are not. In other words, we distinguish arguments that are labelled $\mathbf{\text{I}}$ from those that are not labelled $\mathbf{\text{I}}$ , but we do not distinguish whether an argument is labelled $\mathbf{\text{O}}$ or $\mathbf{\text{U}}$ . Given a labelling L and argument x we use (with abuse of notation) $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=/\backslash \mathbf{\text{I}}$ to denote $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}\ne \mathbf{\text{I}}$ . Combining this with the definitions of addition and removal persistence and monotonicity (Definitions 8, 9, 10 and 11) leads to a number additional variants of these principles, namely $/\backslash \mathbf{\text{I}}\mathbf{\text{I}}$ , $\mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ and $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition/removal persistence and monotonicity. These variants can be understood as being about persistence and monotonicity of extensions. For example, $/\backslash \mathbf{\text{I}}\mathbf{\text{I}}$ addition persistence is equivalent to the property that a σ extension E is still a σ extension after adding an attack from x to y, if $\mathit{x}\notin \mathit{E}$ and $\mathit{y}\in \mathit{E}$ . In most cases we can derive results for these additional principles from the results for the three-valued label combinations. In particular, for addition and removal persistence we have the following fact, which follows directly from the definition of addition and removal persistence and therefore holds not just for the semantics we consider, but for every three-valued labelling-based semantics.

Proposition 34.

For every semantics σ we have:

σ satisfies $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition/removal persistence if and only if σ satisfies $\mathbf{OO}$ , $\mathbf{UO}$ , $\mathbf{OU}$ and $\mathbf{UU}$ addition/removal persistence.

σ satisfies $/\backslash \mathbf{\text{I}}\mathbf{\text{I}}$ addition/removal persistence if and only if σ satisfies $\mathbf{OI}$ and $\mathbf{UI}$ addition/removal persistence.

σ satisfies $\mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition/removal persistence if and only if σ satisfies $\mathbf{IO}$ and $\mathbf{IU}$ addition/removal persistence.

Proof.

We prove this for item a and for addition persistence. Removal persistence, as well as items b and c, follow similarly.

For the only if direction, assume that σ satisfies $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition persistence. We will prove that σ satisfies $\mathbf{OO}$ addition persistence. Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ , let $\mathit{x}\mathrm{,}\mathit{y}\in \mathit{A}$ , let ${\mathit{F}}^{\prime }=\mathrm{(}\mathit{A}\mathrm{,}⇝\cup \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}\mathrm{)}$ and let $\mathit{L}\in {\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathit{F}\mathrm{)}$ be a labelling such that $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}=\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\mathbf{\text{O}}$ . Then $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}\ne \mathbf{\text{I}}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}\ne \mathbf{\text{I}}$ . Since σ satisfies $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition persistence it follows that $\mathit{L}\in {\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}{\mathit{F}}^{\prime }\mathrm{)}$ , which proves that σ satisfies $\mathbf{OO}$ addition persistence. The $\mathbf{UO}$ , $\mathbf{OU}$ and $\mathbf{UU}$ addition persistence principles follow similarly.

For the if direction, assume that σ satisfies $\mathbf{OO}$ , $\mathbf{UO}$ , $\mathbf{OU}$ and $\mathbf{UU}$ addition persistence. We will prove that σ satisfies $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition persistence. Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ , let $\mathit{x}\mathrm{,}\mathit{y}\in \mathit{A}$ , let ${\mathit{F}}^{\prime }=\mathrm{(}\mathit{A}\mathrm{,}⇝\cup \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\}\mathrm{)}$ and let $\mathit{L}\in {\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathit{F}\mathrm{)}$ be a labelling such that $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}\ne \mathbf{\text{I}}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}\ne \mathbf{\text{I}}$ . Then $\mathit{L}\mathrm{(}\mathit{x}\mathrm{)}\in \{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{U}}\}$ and $\mathit{L}\mathrm{(}\mathit{y}\mathrm{)}=\{\mathbf{\text{O}}\mathrm{,}\mathbf{\text{U}}\}$ . Therefore it follows that $\mathit{L}\in {\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}{\mathit{F}}^{\prime }\mathrm{)}$ , which proves that σ satisfies $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition persistence. □

For addition and removal monotonicity things look different. Again, the following fact follows directly from the definition of addition and removal monotonicity.

Proposition 35.

For every semantics σ we have:

σ satisfies $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition/removal monotonicity only if σ satisfies $\mathbf{OO}$ , $\mathbf{UO}$ , $\mathbf{OU}$ and $\mathbf{UU}$ addition/removal monotonicity.

σ satisfies $/\backslash \mathbf{\text{I}}\mathbf{\text{I}}$ addition/removal monotonicity only if σ satisfies $\mathbf{OI}$ and $\mathbf{UI}$ addition/removal monotonicity.

σ satisfies $\mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition/removal monotonicity only if σ satisfies $\mathbf{IO}$ and $\mathbf{IU}$ addition/removal monotonicity.

Proof.

Similar to the proof of the only if direction in Proposition 34. □

The if direction of the three statements in Proposition 35 does not hold in general, and this is where the extension-based perspective is different from the labelling-based one. For instance, the combination of $\mathbf{OO}$ , $\mathbf{UO}$ , $\mathbf{OU}$ and $\mathbf{UU}$ addition monotonicity does not imply $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition monotonicity. Indeed, it is possible define a semantics that satisfies $\mathbf{OO}$ , $\mathbf{UO}$ , $\mathbf{OU}$ and $\mathbf{UU}$ addition monotonicity but not $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition monotonicity.1 ¹

As an example, consider a semantics σ that, given that $\mathit{F}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{a}\mathrm{)}\}\mathrm{)}$ and ${\mathit{F}}^{\prime }=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{a}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\}\mathrm{)}$ , satisfies ${\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathit{F}\mathrm{)}=\{\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{U}}\mathrm{)}\}\}$ and ${\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}{\mathit{F}}^{\prime }\mathrm{)}={\mathcal{L}}_{\mathit{\sigma }}\mathrm{(}\mathit{F}\mathrm{)}\cup \{\{\mathrm{(}\mathit{a}\mathrm{,}\mathbf{\text{I}}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathbf{\text{O}}\mathrm{)}\}\}$ .

Using Proposition 34 we can derive results for $/\backslash \mathbf{\text{I}}\mathbf{\text{I}}$ , $\mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ and $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition and removal persistence under all the semantics we consider. Using Proposition 35 we can furthermore derive most of the results for $/\backslash \mathbf{\text{I}}\mathbf{\text{I}}$ , $\mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ and $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition and removal monotonicity. The following Propositions establish results for addition and removal monotonicity principles that do not follow using Proposition 35. A complete overview of these results can be found in Section 11. Proposition 36.

The grounded semantics satisfies $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition monotonicity and $/\backslash \mathbf{\text{I}}\mathbf{\text{I}}$ removal monotonicity.

Proof.

This follows from the fact that the grounded semantics is a unique status semantics and satisfies $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition persistence and $/\backslash \mathbf{\text{I}}\mathbf{\text{I}}$ removal persistence. □

Proposition 37.

The complete semantics satisfies $/\backslash \mathbf{\text{I}}\mathbf{\text{I}}$ removal monotonicity.

Proof.

This follows from the fact that the complete semantics satisfies $\mathbf{OI}$ removal monotonicity (Proposition 30) together with the fact that, if x attacks y, there is no complete labelling in which x is labelled $\mathbf{\text{U}}$ and y is labelled $\mathbf{\text{I}}$ . □

8. Discussion

In this section, we summarise and discuss the results obtained so far. Table 5 provides an overview of all the labelling-based robustness principles. Table 6 provides a similar overview for the extension-based robustness principles. Note that Table 5 is a duplicate of the tables included in earlier sections, while the results in Table 6 follow from the results on labelling-based principles via Propositions 34 and 35, and otherwise from Propositions 36 and 37.

Table 5

Addition/removal persistence/monotonicity for labelling-based semantics

Table 6

Addition/removal persistence/monotonicity for extension-based semantics

A number of general insights can be extracted from these tables. If we look at the extension-based robustness principles we see that the semi-stable, ideal, and eager do not satisfy any robustness principle, that the preferred semantics satisfies one, the complete semantics three, the grounded semantics four, and the stable semantics five. Moreover, of the few principles satisfied, most are persistence principles. In the labelling-based setting things look very different. Here, almost half of the principles are satisfied. This supports the intuition that the additional discriminative power of labellings is very useful in describing the robustness of semantics.

Dung’s traditional admissibility-based semantics (grounded, complete, preferred and stable) all behave differently with respect to the desirable robustness principles, so these principles are useful to distinguish these semantics in this respect. However, our principles do not distinguish the semi-stable, ideal and eager semantics, as none of these semantics satisfy any of the desirable principles (extension-based or labelling-based). The stable semantics appears to be the best behaved one with respect to the extension-based persistence principles. The same holds for the labelling-based persistence principles. Note however, that all the labelling-based principles involving $\mathbf{\text{U}}$ -labelled arguments are trivially satisfied under the stable semantics.

Throughout this paper, we made a distinction between persistence and monotonicity principles. We can also combine the two principles. Let us say that a semantics satisfies $\mathit{X}\mathit{Y}$ addition/removal robustness whenever it satisfies both $\mathit{X}\mathit{Y}$ addition/removal persistence and $\mathit{X}\mathit{Y}$ addition/removal monotonicity. Thus, $\mathit{X}\mathit{Y}$ addition/removal robustness, if satisfied by a semantics σ, means that if in all σ labellings, the arguments x and y are labelled X and Y, then the set of σ labellings remains the same when adding or removing an attack between x and y. Tables 7 and 8 provide overviews of robustness under both the labelling-based and extension-based settings.

Table 7

Addition/removal robustness for labelling-based semantics

Table 8

Addition/removal robustness for extension-based semantics

Note that for the grounded, ideal and eager semantics, which are unique status semantics, robustness coincides with persistence and monotonicity. The preferred, semi-stable, ideal and eager semantics violate all robustness principles, except for the $\mathbf{UI}$ , $\mathbf{IU}$ , $\mathbf{II}$ removal robustness principles, which are trivially satisfied. Furthermore, the results for extension-based robustness principles look quite different from the labelling-based robustness principles. Here we have that the grounded semantics satisfies $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ addition robustness and $/\backslash \mathbf{\text{I}}\mathbf{\text{I}}$ removal robustness. Other than that, the complete semantics satisfies $/\backslash \mathbf{\text{I}}\mathbf{\text{I}}$ removal robustness, but no further robustness principles are satisfied under any of the semantics we consider.

9. Future work

The results of the robustness principles introduced and analyzed in this paper give rise to three main lines of further research. First, the analysis can be extended to other semantics, such as non-admissible-based semantics. Second, the set of principles discussed in this chapter can be further extended. Third, relations between principles can be studied, such as relations between the robustness principles introduced in this paper and principles discussed in the literature like directionality and SCC decomposability. We consider these three lines of research below.

9.1. Semantics

The first topic for further research is to verify whether other semantics proposed in the literature satisfy our new principles. In some cases this will be easy. For example, given the construction of prudent semantics [33], it is easy to show that most of our principles are not satisfied. However, for naive-based semantics such as the Stage, Stage2 and CF2 semantics [5,43,61], it is often more difficult to see whether our robustness principles are satisfied or not. This is analogous to the case for many other principles, where for naive-based semantics often larger counter-examples are given [60]. Recently, a range of new semantics based on the notion of weak admissibility have been introduced [15]. Dauphin et al. [35] provide a principle-based analysis of these semantics, and also define the closely related qualified and semi-qualified semantics. Whether these new semantics satisfy our robustness principles is also an open question.

The second topic for further research is the consideration of other semantic frameworks such as other labelling conventions. As we have shown, there is a clear distinction between the extension-based results in Table 5 and the labelling-based results in Table 6. Whereas for extension-based semantics very few principles are satisfied, many more principles are satisfied for labelling-based semantics. This can be readily explained: the distinction between out and undecided arguments makes the principles more precise. However, it also raises a question: if we adopt another way to describe the semantics, for example using four valued labelling functions, would that further increase the precision of the analysis? We can invert the question: which set of truth values can be defined such that we have maximal persistence and monotonicity principles?

The third topic of further research is to use the robustness principles to guide the search for new semantics, as in general suggested by van der Torre and Vesic [60]. However, whereas robustness may be desirable in some applications, it may be seen as a drawback in others. For example, the most robust semantics is one in which the set of extensions is always the same. In other words, the search for new semantics may require to make additional requirements explicit, for example in terms of additional principles. Moreover, we need to decide which of our robustness principles can play the role of desiderata in such a search, maybe in the form of meta-principles.

Finally, a fourth topic for further research is to consider robustness for ranking semantics, or other semantics functions. Likewise, one can extend the definition of robustness and the analysis to more expressive argumentation frameworks, for example expressing collective or set attack, higher-order attack, support relation in bipolar argumentation frameworks, or abstract dialectical frameworks.

9.2. Principles

The fifth topic for further research is to define principles by weakening or adapting the existing principles. This can be done to find principles which are more discriminative, or that correspond to particular intuitions. For example, since we are typically interested only in the accepted arguments, we may require that a labelling does not have to be exactly the same, only the in-part needs to remain unchanged. As another example, since self-attacks are known to cause problems in many examples, we may consider only frameworks that do not contain self-attacks, or that more generally do not contain odd loops.

9.3. Relations between principles

The sixth topic for further research is to study logical relations among the principles, independently of the semantics. For example, we may verify whether one property implies another one. In particular, the relation between our principles and existing ones needs to be further studied. The most obvious ones are directionality, and SCC decomposability.

The seventh topic for further research is to consider sets of principles. For example, as common in social choice, there may be sets of principles such that there are no semantics satisfying all of them, or there may be sets of principles such that there is exactly one semantics satisfying all of them. We are not aware of such impossibility or characterisation results in the literature on formal argumentation.

10. Related work

The robustness principles investigated in this paper build on earlier work by Boella et al. [22,23], who studied refinement and abstraction principles, which are conditions under which the evaluation of an argumentation framework remains unchanged when an attack is added or removed. However, they consider only semantics that yield a single extension or labelling. The results we obtained for addition and removal persistence under the grounded semantics coincide with theirs.

Our principles are related to the so called explicit conflict conjecture which was introduced by Baumann et al. [17] in the investigation of the notion of compact argumentation frameworks. These are argumentation frameworks that are minimal in the sense that no argument can be removed from the argumentation framework without affecting the set of extensions. For the definition, let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ be an argumentation framework and let σ be a semantics. Two arguments $\mathit{x}\mathrm{,}\mathit{y}\in \mathit{A}$ are said to be in conflict with respect to F and σ if no σ extension of F contains both x and y. If x and y are in conflict with respect to F and σ then this conflict is called an explicit conflict if $\mathit{x}⇝\mathit{y}$ and an implicit conflict if $\mathit{x}⇝̸\mathit{y}$ . The explicit conflict conjecture is said to hold for a semantics σ if, for every argumentation framework $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ there exists an argumentation framework ${\mathit{F}}^{\prime }=\mathrm{(}\mathit{A}\mathrm{,}{⇝}^{\prime }\mathrm{)}$ such that the σ extensions of F and ${\mathit{F}}^{\prime }$ coincide, while all the conflicts with respect to ${\mathit{F}}^{\prime }$ and σ are explicit. While this principle was initially conjectured to hold for the stable semantics [17], in a later publication it is actually shown not to hold for the stable semantics, nor for the preferred or semi-stable semantics [16]. The relationship with our principles is the following. If a semantics σ satisfies $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ robustness, then between any pair of arguments in an implicit conflict, we can add an attack without causing a change in the set of extensions or labellings. Hence, for every argumentation framework (possibly containing implicit conflicts) we can construct an argumentation framework with the same set of σ extensions that contains no implicit conflicts. Hence, $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ robustness implies the explicit conflict conjecture. Table 8 shows that, apart from the grounded semantics (for which the explicit conflict conjecture can easily be shown to hold) none of the semantics we consider satisfy $/\backslash \mathbf{\text{I}}/\backslash \mathbf{\text{I}}$ robustness. This is consistent with the findings of Baumann et al. [16].

Cayrol et al. [32] studied the impact on the evaluation of an argumentation framework when new arguments and attacks are added. The main difference with our approach is that they focus on different ways in which the evaluation changes, rather than conditions under which the evaluation does not change. Some types of change that they define are changes leading to a larger, unique, or smaller set of extensions, changes that are monotonic (every extension of the old argumentation framework is included in an extension of the changed argumentation framework) and changes that are monotonous with respect to an argument (every argument included in an extension of the old argumentation framework is also included in an extension of the changed argumentation framework). They then define conditions under which the addition of an argument to an argumentation framework leads to these types of change.

The notion of strong equivalence in abstract argumentation deals with an alternative perspective on robustness in abstract argumentation. Given two argumentation frameworks $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}⇝\mathrm{)}$ and ${\mathit{F}}^{\prime }=\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{⇝}^{\prime }\mathrm{)}$ , let $\mathit{F}\cup {\mathit{F}}^{\prime }$ denote the argumentation framework $\mathrm{(}\mathit{A}\cup {\mathit{A}}^{\prime }\mathrm{,}⇝\cup {⇝}^{\prime }\mathrm{)}$ . Two argumentation frameworks F and G are strongly equivalent with respect to a semantics σ if, for every argumentation framework H, the σ extensions of the argumentation frameworks $\mathit{F}\cup \mathit{H}$ and $\mathit{G}\cup \mathit{H}$ are equivalent. A natural question to ask is: in what kind of way can an argumentation framework F be changed into another argumentation framework ${\mathit{F}}^{\prime }$ such that F and ${\mathit{F}}^{\prime }$ are strongly equivalent? Oikarinen and Woltran [54] address this question by characterising strong equivalence under various semantics using the notion of kernel. A kernel of an argumentation framework F is another argumentation framework that is the same as F except that certain attacks are deleted according to a given syntactic or graph structural criterion. A kernel characterises strong equivalence under a semantics σ if it holds, for any two argumentation frameworks F and G, that F and G are strongly equivalent whenever the kernels of F and G are equivalent. An example is the kernel where every attack is deleted between pairs of distinct arguments where both arguments are self-attacking, which characterises strong equivalence under the complete semantics. A different way of stating this result is that, under the complete semantics, the addition and removal of attacks between two self-attacking arguments of an argumentation framework F has no effect on the set of complete extensions of F, even if F is extended with additional arguments and attacks. This result (and similar results for other semantics) may be contrasted with the results we obtained in this paper, which also imply that under certain conditions, the addition or removal of an attack between two arguments x and y has no effect on the set of extensions or labellings. The difference is that we use conditions that refer to the status of x and y, while strong equivalence results refer to syntactic or graph structural conditions and not on the status of arguments. Further research in this direction includes the study of various other notions of equivalence, which deal with deletions, updates or restricted forms of change [7,8]. Baumann furthermore studied equivalence notions for labelling-based semantics [9], and Baumann and Spanring studied equivalence notions in the unrestricted case (i.e., not assuming finite argumentation frameworks) [18]. A recent overview of results can be found in [10].

Bistarelli et al. [21] study so called local-expansion invariant operators for abstract argumentation frameworks. These operators are functions that take an argumentation framework as input and return the same argumentation framework except that zero or more attacks are added. They then determine conditions under which such operators are invariant with respect to a semantics σ. An operator is invariant with respect to a semantics σ precisely when the set of σ extensions remains unchanged after applying the operator. They focus only on conflict-freeness and admissibility but plan to study further semantics in future work.

Sakama studied counterfactuals in the context of abstract argumentation [58]. Such counterfactuals have the form $\mathit{\alpha }\square \to \mathit{\beta }$ (meaning “if α were true then β would be true”) where α and β are literals of the form $\mathbf{\text{I}}\mathrm{(}\mathit{x}\mathrm{)}$ or $\mathbf{\text{O}}\mathrm{(}\mathit{x}\mathrm{)}$ for some argument x. A counterfactual $\mathit{\alpha }\square \to \mathit{\beta }$ is entailed by an argumentation framework F and semantics σ if the change of F represented by α leads to the truth of β in all σ labellings of F. Here, the premise $\mathbf{\text{O}}\mathrm{(}\mathit{x}\mathrm{)}$ represents the addition of a new argument attacking x, while $\mathbf{\text{I}}\mathrm{(}\mathit{x}\mathrm{)}$ represents the removal of all attacks pointing to x. In this setting, the persistence and monotonicity principles translate to properties of the set of counterfactuals entailed by an argumentation framework. Similarly, Rienstra defined a form of meta-inference for abstract argumentation frameworks [55]. Formally, an argumentation framework F and semantics σ defines a relation between so called interventions and consequences. An intervention is a set of literals of the form $\mathbf{\text{O}}\mathrm{(}\mathit{x}\mathrm{)}$ or $\neg \mathbf{\text{I}}\mathrm{(}\mathit{x}\mathrm{)}$ that represent, respectively, the addition of a new argument attacking x or of a new self-attacking argument attacking x. A formula ϕ is a consequence of an intervention Φ (written ) if the change represented by Φ leads to the truth of ϕ in all σ labellings of F. Like in Sakama’s approach, the principles defined in this paper for a semantics σ translate to properties that characterise the behaviour of the inference relation . Rienstra considers a number of common inference rules such as Cautious Monotonicity and Cut. Cautious Monotonicity states that, if and , then . Cut states that, if and , then . While these are properties that are generally considered desirable, Rienstra showed that they are not satisfied under all semantics. For example, Cautious Monotonicity does not hold under the preferred semantics. This follows from the violation of $\mathbf{IO}$ addition monotonicity under the preferred semantics (Example 33). Similarly, failure of Cut under the semi-stable semantics follows from the failure of $\mathbf{IO}$ addition persistence (Example 11).

Much work has been done in the past decade on what is often referred to as dynamics of argumentation. What unifies this work is its motivation, namely that argumentation is a dynamic process, which means that argumentation frameworks are not static entities but evolve over time. The current paper extends this line of work, as it contributes to the understanding of how admissibility-based semantics behave when the argumentation framework changes. There is a large amount of further work on dynamics of argumentation. For example, the question of whether and how an argumentation framework can be changed in order to enforce some result, such as the acceptance of a given set of arguments, is referred to as the enforcement problem [11,12,20,39,52,53,62]. Change in argumentation has furthermore been related to (or modelled using tools of) theories of belief change, often taking an AGM-inspired approach [13,14,25,34,36–38,45,48–50,57,59]. Computational issues in a dynamic setting have also been studied, such as efficiently (re)computing extensions after an argumentation framework changes [1,6,46]. In general, we believe that the robustness principles studied in this paper are relevant to much of the research on dynamics of argumentation. In the introduction we already discussed ways in which earlier work on robustness principles has been applied in the design of algorithms for the enforcement problem [53] and incomplete argumentation frameworks [51].

11. Summary and conclusion

We have defined a set of general principles for argumentation semantics expressing robustness of labellings and extensions against the addition and removal of attacks, and investigated all the admissibility-based semantics with respect to these principles. The results we obtain provide insight into the behaviour of these semantics in a dynamic context. For example, while the grounded, complete, preferred and stable semantics satisfy some of the desirable robustness principles, the semi-stable, eager and ideal semantics satisfy none. Furthermore, Dung’s traditional semantics (i.e., grounded, complete, preferred and stable) all satisfy different sets of robustness principles, so these principles are useful to distinguish these semantics in this respect.

The robustness principles we investigate are also useful in the design of algorithms. As we have discussed, addition and removal persistence properties have already been applied in the design of algorithms. For instance, knowledge about whether the addition or removal of an attack has an effect on the evaluation of an argumentation framework may be used to optimise search problems connected with the enforcement problem in argumentation [53]. In this context an interesting observation is that the semi-stable, ideal and eager semantics do not satisfy any useful robustness principle, which implies that these semantics cannot benefit from such optimisations, because there are no conditions under robustness against addition or removal of attacks is guaranteed.

We discussed a number of directions for future research, such as extending our analysis by weakening or adapting the robustness principles, and studying relationships between our robustness principles and other principles studied in the literature. We may furthermore consider robustness in the context of more expressive argumentation formalisms, such as frameworks supporting collective or set attacks, higher-order attacks, support relations (bipolar argumentation frameworks) or abstract dialectical frameworks. Finally, we focused in this paper only on admissibility-based semantics. We plan to extend our investigation of robustness to non-admissibility-based semantics in a follow-up publication.