An Extension-Based Approach to Belief Revision in Abstract Argumentation

1 Introduction

Argumentation has become a major research area in Artificial Intelligence (AI) over the last two decades [Bench-Capon and Dunne, 2007; Rahwan and Simari, 2009]. This is not only because of the intrinsic interest of this topic and recent applications (e.g. in legal reasoning [Bench-Capon et al., 2009] and E-Governance [Cartwright and Atkinson, 2009]) but also because there are fundamental connections between argumentation and other areas of AI, mainly non-monotonic reasoning.

The work by Dung [1995] on abstract argumentation, in particular, is usually seen as a significant landmark in the consolidation of the field of argumentation in AI. The central concern of abstract argumentation is the evaluation of a set of arguments and their relations in order to be able to extract subsets of the arguments, so called "extensions", that can all be accepted together from some point of view. Dung's argumentation frameworks (AFs), which are still the most widely used and investigated among the several argumentation formalisms, are directed graphs where nodes represent arguments and links correspond to one argument attacking another. The criteria or methods used to settle the acceptance of arguments, on the other hand, are called "semantics" (see [Baroni et al., 2011] for a recent overview).

∗Supported by the Austrian Science Fund (FWF) under grants I1102, P25518, P25521, W1255, and Y698.

Given that argumentation can be viewed as a process as well as a product, recent years have seen an increasing number of studies on different problems in the dynamics of argumentation frameworks [Baumann, 2012; Bisquert et al., 2011; 2013; Boella et al., 2009; Booth et al., 2013; Cayrol et al., 2010; Doutre et al., 2014; Kontarinis et al., 2013; Kr¨umpelmann et al., 2012; Nouioua and W¨urbel, 2014; Sakama, 2014]. The problem we tackle here is how to revise an AF when some new information is provided. Along the lines of the AGM theory [Alchourr´on et al., 1985; G¨ardenfors, 1988], by revision we mean an operation that incorporates the new information while bringing minimal change to the extensions of the original AF.

To the best of our knowledge, this has first been considered for AFs explicitly in [Coste-Marquis et al., 2014a], where the problem of revision of AFs is defined as follows: given a semantics, an AF and a revision formula expressing how the status of some arguments has to be changed, find a set of AFs which satisfy the revision formula and whose extensions are as close as possible to the extensions of the input AF. Following the AGM approach, rationality postulates for a revision operator on AFs can be formulated and Coste-Marquis et al. [2014a] also provide a representation theorem. Such a result establishes a close link between obeying the postulates and exploiting a particular type of ranking on extensions of AFs in order to compute the output of revision. This approach is thus similar to the one by Katsuno and Mendelzon [1991].

In this work we study revision operators that produce a single AF as output. First, this is in accordance with the standard way of defining revision in the AGM theory where the result of revising an input theory by a revision formula is another theory. Second, revision yielding a single AF also makes concepts of iterated revision [Darwiche and Pearl, 1997; Spohn, 1988] amenable to argumentation. More specifically, we study two types of revision operators. The first type considers the new information represented as a propositional formula expressing the desired change in the extensions of the original AF. The second type is revision by an AF. Hence, the new information is restricted in the sense that it can only stem from another AF's outcome. While the first type follows the framework of [Coste-Marquis et al., 2014a], the latter assumes that the knowledge to be incorporated (e.g. another agent's beliefs) is in the form of an AF. It is more in line with work on Horn revision [Delgrande and Peppas, 2015] where all involved formulas stem from the same fragment.

Our main contributions are as follows:

• We derive full representation theorems for both mentioned types of revision; our results are, moreover, generic in the sense that they hold for a wide range of semantics including preferred, semi-stable, stage, and stable semantics.
• For the revision-by-formula approach, we give novel notions of compliance [Delgrande and Peppas, 2015] in order to restrict the rankings. This is required to guarantee that the outcome of the corresponding operators can be expressed by an AF under a given semantics. To this end, exact knowledge about the expressiveness of argumentation semantics is needed. For most of the standard semantics, [Dunne et al., 2014] provides the necessary results.
• In the revision-by-AF approach, we show that the concept of compliance can be dropped, thus standard revision operators satisfying all postulates like Dalal's [1988] operator can be directly applied to revision of AFs. However, an additional postulate (again borrowed from [Delgrande and Peppas, 2015]) is needed for the representation theorem.

2 Preliminaries

We first recall basic notions of Dungs's abstract frameworks (the reader is referred to [Dung, 1995; Baroni et al., 2011] for further background), then present recent results from [Dunne et al., 2014] which we require for our results and finally define rankings as used in belief change in terms of extensions.

We assume an arbitrary but finite domain A of arguments. An argumentation framework (AF) is a pair F = (A, R) where A ⊆ A is non-empty, and R ⊆ A × A is the attack relation. The collection of all AFs is given as AFA.

Given F = (A, R), an argument a ∈ A is defended (in F ) by a set S ⊆ A if for each b ∈ A such that (b, a) ∈ R, there is a c ∈ S with (c, b) ∈ R. A set T of arguments is defended (in F) by S if each a ∈ T is defended by S (in F). A set S ⊆ A is conflict-free (in F), if there are no arguments a, b ∈ S, such that (a, b) ∈ R. We denote the set of all conflict-free sets in F as cf(F). A set S ∈ cf(F) is called admissible (in F) if S defends itself. We denote the set of admissible sets in F as adm(F). For S ⊆ A, the range of S (wrt. F), denoted S+ F , is the set S ∪ {a | ∃s ∈ S : (s, a) ∈ R}.

A semantics maps each F ∈ AFA to a set of extensions S ⊆ 2A . For the stable, preferred, stage, and semi-stable semantics respectively, the extensions are defined as follows:

• S ∈ stb(F), if S ∈ cf(F) and S+ F = A;
• S ∈ prf(F), if S ∈ adm(F) and ∄T ∈ adm(F) s.t. T ⊃ S;
• S ∈ stg(F), if S ∈ cf(F) and ∄T ∈ cf(F) with T + F ⊃ S+ F ;
• S ∈ sem(F), if S∈adm(F) and ∄T∈adm(F) s.t. T + F ⊃S+ F .

The signature Σσ of a semantics σ is defined as Σσ = {σ(F) | F ∈ AFA} , containing exactly those sets of extension which can be realized under σ. Exact characterizations of those sets for the aforementioned semantics have been given in [Dunne et al., 2014]. If S1 and S2 are two extensions such that S1 ̸= S2, we say that S1 and S2 are ⊆-comparable if S1 ⊆ S2 or S2 ⊆ S1. We say that S1 and S2 are ⊆-incomparable if they are not ⊆-comparable. Some of our results will apply to semantics for which the following properties hold in terms of realizability:

Definition 1. A semantics σ is called proper I-maximal if for each S ∈ Σσ it holds that (i) for any S1, S2 ∈ S, S1 ⊆ S2 implies S1 = S2; (ii) S′ ∈ Σσ for any S′ ⊆ S with S′ ̸= ∅; and (iii) for any ⊆-incomparable S1, S2 ∈ 2A it holds that {S1, S2} ∈ Σσ.

In words, an I-maximal [Baroni and Giacomin, 2007] semantics σ is proper if, for any AF F, we can realize any non-empty subset of σ(F) under σ and on the other hand, for any pair of ⊆-incomparable sets of arguments, we can find an AF having exactly these as extensions under σ.

The next observation follows from [Dunne et al., 2014].

Proposition 1. Preferred, stable, semi-stable and stage semantics are proper I-maximal.

Definition 2. Given a semantics σ, we define the function fσ : 22A ↦→ AFA mapping sets of extensions to AFs such that fσ(S) = F with σ(F) = S if S ∈ Σσ and fσ(S) = (∅, ∅) otherwise.

Note that S ∈ Σσ guarantees that we can find an AF which, when evaluated under σ results in S. We leave the exact specifications of such AFs open; canonical constructions for the semantics we consider can be found in [Dunne et al., 2014]. Such constructions may result in AFs with additional arguments to those contained in a S ∈ Σσ, although recent work on realizability in compact AFs [Baumann et al., 2014] could pave the way for constructions of AFs without new arguments. In general, fσ is not unique. Nevertheless, throughout the paper we assume fσ to be fixed for every σ.

By PA we denote the set of propositional formulas over A, where the arguments in A represent propositional variables. A set of arguments E ⊆ A can be seen as an interpretation, where a ∈ E means that a is assigned true and a /∈ E means that a is assigned false. If a formula ϕ ∈ PA evaluates to true under an interpretation E, E is a model of ϕ. [ϕ] denotes the set of models of ϕ. Moreover, ϕ1 ≡ ϕ2 if [ϕ1] = [ϕ2].

A pre-order ⪯ on 2A is a reflexive, transitive binary relation on 2A . If E1 ⪯ E2 or E2 ⪯ E1 for any E1,E2 ∈ 2A , the pre-order ⪯ is total. Moreover, for E1,E2 ∈ 2A , E1 ≺ E2 denotes the strict part of ⪯, i.e. E1 ⪯ E2 and E2 ̸⪯ E1. We write E1 ≈ E2 the case E1 ⪯ E2 and E2 ⪯ E1. An I-total pre-order on 2A is a pre-order on 2A such that E1 ⪯ E2 or E2 ⪯ E1 for any pair E1, E2 of ⊆-incomparable extensions. Finally, for a set of sets of arguments S ⊆ 2A and a pre-order ⪯, min(S, ⪯) = {E1 ∈ S | ∄E2 ∈ S : E2 ≺ E1}.

3 Representation Theorems

A key insight in belief change is the realization that any belief revision operator can be characterized using rankings on the possible worlds described by the language. Intuitively, the rankings can be thought of as plausibility relations on possible worlds. Revision by a formula ϕ then amounts to choosing the most plausible worlds among the models of ϕ. The fact that this strategy is sound with respect to the postulates is guaranteed by a representation result [Katsuno and Mendelzon, 1991].

In our approach, subsets of 2A play the role both of extensions for AFs and models of propositional formulas, and will be the possible worlds that a revision operator chooses from. Consequently, we use rankings on 2A to characterize the class of revision operators for AFs. We employ two main types of rankings, introduced below.

Definition 3. Given a semantics σ, an (I-)faithful assignment maps every F ∈ AFA to an (I-)total pre-order ⪯F on 2A such that, for any (⊆-incomparable) E1, E2 ∈ 2A and F, F1, F2 ∈ AFA, it holds that:

• (ii) if E1 ∈ σ(F) and E2 /∈ σ(F), then E1 ≺F E2,

The pre-order ⪯F assigned to F by an (I-)faithful assignment is referred to as the (I-)faithful ranking associated with F .

Faithful assignments approximate the notion with the same name introduced by Katsuno and Mendelzon [1991]. I-faithful assignments differ in that they require the rankings to be Itotal, thus allowing (but not requiring) them to be partial with respect to ⊆-comparable pairs of extensions. Section 3.2 explains why we need to introduce this second type.

3.1 Revision by Propositional Formulas

We first consider revision of an AF by a propositional formula. Hence we are interested in operators of the form ⋆σ : AFA × PA ↦→ AFA mapping an AF F and a consistent 1 propositional formula ϕ to a revised AF F ⋆σ ϕ. Intuitively, ϕ describes information which should be incorporated in F . To this end, the operator revises F such that the σ-extensions of F change according to the models of ϕ. We define the revision postulates adjusted to the AF scenario in a similar manner to [CosteMarquis et al., 2014a].

P⋆1 says that when we revise by ϕ, the extensions of the revision output should be among the interpretations that satisfy ϕ. P⋆2 specifies that if ϕ is consistent with F (in the sense that they share models), revision amounts to nothing more than taking the common models. P⋆3 says that if ϕ is a consistent formula, then revision by ϕ should also be consistent. P⋆4 guarantees irrelevance of syntax. P⋆5 and P⋆6 ensure that revision is performed with minimal change to the AF F . For further discussion on the motivation of the postulates, see [Alchourr´on et al., 1985; G¨ardenfors, 1988; Katsuno and Mendelzon, 1991].

1 The restriction to consistent formulas is due to the fact that argumentation semantics usually are not capable of expressing the empty set of extensions. For semantics which can realize the empty set, such as the stable semantics, our results in this section apply even without this restriction.

Due to reasons pointed out in the introduction we require the result of the revision to be a single AF. For this reason we face a similar challenge to that encountered in Horn revision [Delgrande and Peppas, 2015]. Specifically, it may be the case that a set of extensions S that is the desired outcome of the revision under a semantics σ cannot be realized under σ. To overcome this problem we use Σσ to define the following restriction on pre-orders, which we will need to obtain our representation theorem:

Definition 4. A pre-order ⪯ is σ-compliant if for every consistent formula ϕ ∈ PA it holds that min([ϕ], ⪯) ∈ Σσ.

Example 1. Consider the pre-order ⪯ defined as {a, b, c} ≺ {a, b} ≈ {a, c} ≈ {b, c} ≺ {a} ≈ {b} ≈ {c} ≺ ∅. Now let ϕ = ¬(a ∧ b ∧ c) and observe that min([ϕ],⪯ ) = {{a, b}, {a, c}, {b, c}}. From the results in [Dunne et al., 2014] we know that for σ ∈ {stb, prf, stg, sem}, {{a, b}, {a, c}, {b, c}} /∈ Σσ, hence ⪯ is not σ-compliant.

On the other hand let ⪯′ be the pre-order defined as {a, b, c}≺′{a}≈′{b}≈′{c}≺′{a, b}≺′{a, c}≺′{b, c}≺′∅ followed by an arbitrary ≺′ -chain of the remaining elements of 2A . One can check that ⪯′ is σ-compliant. For instance, min([ϕ], ⪯′ ) = {{a}, {b}, {c}} ∈ Σσ.

Note that for semantics considered in [Dunne et al., 2014], their results imply that checking whether a given pre-order is σ-compliant can be done in polynomial time. Using the notion of σ-compliance enables us to extend the AGM approach to capture the revision of argumentation frameworks under proper I-maximal semantics by propositional formulas.

Theorem 1. Let σ be a proper I-maximal semantics, F ∈ AFA and ⪯F a σ-compliant and faithful ranking associated with F . Define an operator ⋆σ : AFA × PA ↦→ AFA by

Then ⋆σ satisfies postulates P⋆1 - P⋆6.

Proof. First of all, by the definition of fσ and due to the fact that ⪯F is σ-compliant, we have that σ(fσ(min([ϕ], ⪯F ))) = min([ϕ], ⪯F ), hence σ(F ⋆σ ϕ) = min([ϕ], ⪯F ). Therefore postulates P⋆1 and P⋆4 follow immediately.

If σ(F) ∩ [ϕ] ̸= ∅, it follows from⪯F being faithful that min([ϕ], ⪯F ) = σ(F ) ∩ [ϕ], satisfying P⋆2.

P⋆3 follows since ⪯F is transitive and A is finite and therefore if [ϕ] ̸= ∅ then [ϕ] has minimal elements, hence min([ϕ], ⪯F ) ̸= ∅.

P⋆5 and P⋆6 are trivially satisfied if σ(F ⋆σ ϕ) ∩ [ψ] = ∅. Assume σ(F ⋆σϕ)∩[ψ] ̸= ∅ and, towards a contradiction, that there is some E ∈ min([ϕ], ⪯F ) ∩ [ψ] with E /∈ min([ϕ ∧ ψ],⪯F ). Since E ∈ [ϕ ∧ ψ] there must be some E′ ∈ [ϕ ∧ ψ] with E′ ≺F E, a contradiction to E ∈ min([ϕ],⪯F ). Therefore σ(F ⋆σ ϕ) ∩ [ψ] ⊆ σ(F ⋆σ (ϕ ∧ ψ)). To show that also σ(F ⋆σ (ϕ∧ψ)) ⊆ σ(F ⋆σϕ)∩[ψ], assume E ∈ min([ϕ∧ ψ],⪯F ) and E /∈ min([ϕ],⪯F ) ∩ [ψ]. Since E ∈ [ψ], E /∈ min([ϕ],⪯F ). Let E′ ∈ min([ϕ],⪯F ) ∩ [ψ] (assumed to be nonempty). Then E′ ∈ [ϕ ∧ ψ] holds. As E ∈ min([ϕ ∧ ψ], ⪯F ) and ⪯F is total, E ⪯F E′ . Hence E ∈ min([ϕ], ⪯F ) follows from E′ ∈ min([ϕ], ⪯F ), a contradiction.

Theorem 2. Let ⋆σ : AFA×PA ↦→ AFA be an operator satisfying postulates P⋆1 - P⋆6 for a proper I-maximal semantics σ. Then, there exists a faithful assignment mapping every F ∈ AFA to a faithful ranking ⪯F on 2A such that ⪯F is σcompliant and σ(F ⋆σ ϕ) = min([ϕ], ⪯F ) for every ϕ ∈ PA.

Proof. For a set of interpretations S, we denote by φ(S) a formula with [φ(S)]=S. If the elements of S = {E1, . . . , En} are given explicitly we also write φ(E1, . . . , En) for φ(S).

We define the binary relation ⪯F on 2A as follows:

We begin by showing that ⪯F is a total pre-order. It follows from P⋆1 and P⋆3 that σ(F ⋆σφ(E, E′ )) is a non-empty subset of {E,E′}. Therefore ⪯F is total. Moreover, if E = E′ then σ(F ⋆σ φ(E)) = {E}. Hence E ⪯F E holds for each E ∈ 2A , i.e., ⪯F is reflexive.

In order to show transitivity of ⪯F , let E1,E2,E3 ∈ 2A and assume E1 ⪯F E2 and E2 ⪯F E3. By P⋆1 and P⋆3, σ(F ⋆σφ(E1, E2, E3)) is a non-empty subset of {E1, E2, E3}. First assume σ(F ⋆σ φ(E1, E2, E3)) ∩ {E1, E2} = ∅. Then σ(F ⋆σ φ(E1, E2, E3)) = {E3}. Knowing that φ(E2, E3) ≡ φ(E2, E3) ∧ φ(E1, E2, E3), we obtain from P⋆5 and P⋆6 that σ(F ⋆σ φ(E1,E2,E3)) ∩ {E2,E3} = σ(F ⋆σ φ(E2,E3)). But this implies σ(F ⋆σ φ(E2, E3)) = {E3}, a contradiction to E2 ⪯F E3.

On the other hand assume σ(F ⋆σ φ(E1,E2,E3)) ∩ {E1, E2} ̸= ∅. Since E1 ⪯F E2 we know that E1 ∈ σ(F ⋆σ φ(E1,E2)) holds. Considering the fact that φ(E1,E2) ≡ φ(E1, E2) ∧ φ(E1, E2, E3), we obtain from P⋆5 and P⋆6 that σ(F ⋆σ φ(E1,E2,E3)) ∩ {E1,E2} = σ(F ⋆σ φ(E1,E2)). Thus, E1 ∈ σ(F ⋆σ φ(E1, E2, E3)) ∩ {E1, E2}. Also E1 ∈ σ(F ⋆σ φ(E1, E2, E3)) ∩ {E1, E3} holds. By φ(E1, E3) ≡ φ(E1, E3) ∧ φ(E1, E2, E3), we obtain from P⋆5 and P⋆6 that σ(F ⋆σ φ(E1,E2,E3)) ∩ {E1,E3} = σ(F ⋆σ φ(E1,E3)). Therefore E1 ∈ σ(F ⋆σ φ(E1, E3)), meaning that E1 ⪯F E3.

Having shown that ⪯F is total, reflexive and transitive, it follows that ⪯F is a total pre-order. The following lemmata show that ⋆σ can indeed be simulated by ⪯F .

Lemma 1. Let E1,E2 ∈ 2A such that E1 ⪯F E2. Then for all formulas ϕ ∈ PA, if E1 ∈ [ϕ] and E2 ∈ σ(F ⋆σ ϕ) then E1 ∈ σ(F ⋆σ ϕ).

Proof. Let ϕ be a formula such that E1 ∈ [ϕ] and E2 ∈ σ(F ⋆σ ϕ). Then from P⋆5 and P⋆6 it follows that σ(F ⋆σ (ϕ ∧ φ(E1,E2))) = σ(F ⋆σ ϕ) ∩ [φ(E1,E2)]. Moreover, from E2 ∈ σ(F ⋆σ ϕ) and P⋆1 we derive that E2 ∈ [ϕ], hence [φ(E1, E2)] ⊆ [ϕ]. By P⋆4 we now get σ(F ⋆σ (ϕ ∧ φ(E1,E2))) = σ(F ⋆σ φ(E1,E2)). Therefore, by P⋆5 and P⋆6, σ(F ⋆σ φ(E1,E2)) = σ(F ⋆σ ϕ) ∩ [φ(E1,E2)]. This, together with the assumption that E1 ⪯F E2 (and therefore E1 ∈ σ(F ⋆σ φ(E1, E2))), entails E1 ∈ σ(F ⋆σ ϕ).

Proof. ⊆: Let ϕ ∈ PA. Towards a contradiction assume that there is some E1 ∈ min([ϕ], ⪯F ) such that E1 /∈ σ(F ⋆σ ϕ). Since [ϕ] ̸= ∅ it follows by P⋆3 that σ(F ⋆σ ϕ) ̸= ∅. Let E2 ∈ σ(F ⋆σ ϕ). Lemma 1 entails that E1 ̸⪯F E2. This also means, recalling that E1 ∈ min([ϕ],⪯F ), that E2 ̸⪯F E1. But this means by the definition of ⪯F that σ(F ⋆σ φ(E1, E2)) = ∅, a contradiction to ⋆σ satisfying P⋆3.

⊇: Let ϕ ∈ PA and E1 ∈ σ(F ⋆σ ϕ). We show that for all E2 ∈ [ϕ] it holds that E1 ⪯F E2. To this end let E2 ∈ [ϕ]. From E1 ∈ σ(F ⋆σ ϕ) we know that σ(F ⋆σ ϕ) ∩ [φ(E1, E2)] ̸= ∅. By P⋆5 and P⋆6 we get σ(F ⋆σ ϕ) ∩ [φ(E1, E2)] = σ(F ⋆σ (ϕ∧φ(E1, E2))). Since E1, E2 ∈ [ϕ] it follows by P⋆4 that σ(F ⋆σ (ϕ ∧ φ(E1,E2))) = σ(F ⋆σ φ(E1,E2)). Now as E1 ∈ σ(F ⋆σ ϕ) by assumption, also E1 ∈ σ(F ⋆σ φ(E1, E2)), meaning that E1 ⪯F E2. Since E2 was chosen arbitrarily, E1 ∈ min([ϕ], ⪯F ) follows.

From Lemma 2 it follows that ⪯F is σ-compliant. It remains to show that ⪯F is faithful wrt. F. If σ(F) = ∅ this is trivially the case. Therefore assume σ(F) ̸= ∅. By P⋆2 we get σ(F ⋆σ ⊤) = σ(F) (note that [⊤] = 2A ). Hence σ(F) = min([⊤],⪯F ) = min(2A,⪯F ), meaning that for E1,E2 ∈ 2A , E1 ≈F E2 if E1,E2 ∈ σ(F) and E1 ≺F E2 if E1 ∈ σ(F) and E2 /∈ σ(F). Therefore conditions (i) and (ii) from Definition 3 are fulfilled. Condition (iii) holds since ⪯F is defined with respect to the extensions of F, hence ⪯F is faithful wrt. F .

The attentive reader might have noticed that we did not make explicit use of the restriction to proper I-maximal semantics in the proofs above. It is rather used implicitely since, in general, rankings which are both faithful and σ-compliant only exist if σ fulfills property (ii) of proper I-maximality.

We can use the representation results obtained from Theorems 1 and 2 to define concrete operators via faithful and compliant rankings. For instance, the ranking ⪯F where the σ-extensions of F are the minimal elements and the remaining candidates in 2A are ordered as a ≺-chain leads to a simple but natural operator for any semantics σ. The concrete contents of Σσ will be the crucial aspect to consider when defining more refined operators under a certain semantics σ.

3.2 Revision by Argumentation Frameworks

In this section we investigate operators ∗σ : AFA × AFA ↦→ AFA. Such operators map an AF F and an AF G to an AF F ∗σ G. The underlying concept of a model is given by the argumentation semantics σ. As before, we show a correspondence between a set of postulates and a class of rankings on 2A . The revision postulates, in the manner of [Katsuno and Mendelzon, 1991], are formulated as follows:

(A∗3) If σ(G) ̸= ∅, then σ(F ∗σ G) ̸= ∅.

(A∗4) If σ(G) = σ(H), then σ(F ∗σ G) = σ(F ∗σ H).

(A∗5) σ(F ∗σ G) ∩ σ(H) ⊆ σ(F ∗σ fσ(σ(G) ∩ σ(H))).

(Acyc) If for 0 ≤ i ≤ n, σ(F ∗σ Gi+1) ∩ σ(Gi) ̸= ∅ and σ(F ∗σ G0)∩σ(Gn) ̸= ∅ then σ(F ∗σ Gn)∩σ(G0) ̸= ∅.

Postulate Acyc is borrowed from [Delgrande and Peppas, 2015]. Its addition to the set of postulates is motivated by the following problem. Suppose that for an AF F we have a ranking ≺F on 2A which behaves as in the following figure for the extensions {a}, {b, c}, {a, c} and {b}, and as a faithful ranking otherwise.

The arrow means that the relation is strict: thus {a} ⪯F {b, c} and {b, c} ⪯̸F {a}. The relation ≺F , then, contains a non-transitive cycle and is not a pre-order. However, quick inspection of the figure shows that for any non-empty subset S of extensions that can be represented by an AF under a proper I-maximal semantics σ, min(S, ≺F ) is still well defined and non-empty. Thus it is possible to define an operator ∗σ in the usual way: F ∗σ G = fσ(min(σ(G), ≺F )), and - crucially - the operator ∗σ satisfies postulates A∗1 - A∗6.

Additionally, there is no transitive ranking ⪯⋆F which is transitive and yields the same revision operator. To see this, notice that if ⪯⋆F existed, it would have to satisfy min({{a}, {b, c}},⪯⋆F ) = {{a}}, because we know that σ(F ∗σ fσ({{a}, {b, c}})) = {{a}}. Thus it would hold that {a} ≺∗F {b, c}. Similarly, we get that {b, c} ≺∗F {a, c} ≺∗F {b} ≺∗F {a}, and the cycle is reiterated.

Nonetheless, non-transitive cycles are something we want to avoid: since a natural reading of the rankings on 2A is as plausibility relations, we would like these rankings to be transitive, and it is thus undesirable to have revision operators that characterize non-transitive rankings. In order to prevent this situation we make use of Acyc.

The second detail that needs to be mentioned is our use of I-faithful assignments, motivated by the way in which proper I-maximal semantics work. Given a revision operator ∗σ and F ∈ AFA, the natural way to rank two extensions E1 and E2 is by appeal to F ∗σ fσ({E1,E2}): if E1 ∈ σ(F ∗σ fσ({E1,E2})), then E1 is considered 'more plausible' than E2 and it should hold that E1 ⪯F E2. However, by proper I-maximality of σ, fσ({E1,E2}) exists only if E1 and E2 are ⊆-incomparable. Thus if E1 and E2 are ⊆-comparable, ∗σ might not have any means to adjudicate between E1 and E2, hence it is natural to allow them to be incomparable with respect to ⪯F .

Given these preliminaries, we can now state our main representation results.

Theorem 3. Let σ be a proper I-maximal semantics, F ∈ AFA and ⪯F an I-faithful ranking associated with F . Define an operator ∗σ : AFA × AFA ↦→ AFA by:

Then ∗σ satisfies postulates A∗1 - A∗6 and Acyc.

Proof. Since σ is proper I-maximal, any non-empty subset of σ(G) (in particular, min(σ(G), ⪯F )) is realizable under σ. Thus ∗σ is well-defined and we do not need to add any extra condition on ⪯F , such as σ-compliance. Keeping this in mind, the proof that A∗1 - A∗6 hold is entirely similar to Theorem 1. In the following we show that Acyc also holds.

Let G0,G1, . . . ,Gn be a sequence of AFs such that for all i ∈ {1, . . . , n}, (F ∗σ Gi) ∩ σ(Gi-1) ̸= ∅ and (F ∗σ G0) ∩ σ(Gn) ̸= ∅ holds. From (F ∗σ G1) ∩ σ(G0) ̸= ∅ we derive by proper I-maximality of σ that min(σ(G1), ⪯F ) ∩σ(G0) ̸= ∅. Hence there is an extension E′0 ∈ σ(G0) such that E′0 ⪯F E1 for all E1 ∈ σ(G1). Likewise we get from (F ∗σ G2)∩σ(G1) ̸= ∅ that there is an extension E′1 ∈ σ(G1) such that E′1 ⪯F E2 for all E2 ∈ σ(G2), . . . , and from (F ∗ Gn) ∩ σ(Gn-1) ̸= ∅ that there is an extension E′n-1 ∈ σ(Gn-1) such that E′n-1 ⪯F En for all En ∈ σ(Gn). From transitivity of ⪯F we get E′0 ⪯F En for all En ∈ σ(Gn). Finally, from (F ∗σ G0) ∩ σ(Gn) ̸= ∅ it follows that there is some E′′ 0 ∈ σ(G0) with E′′ 0 ⪯F E0 for all E0 ∈ σ(G0) and E′′ 0 ∈ σ(Gn). Now from E′′ 0 ⪯F E′0 ⪯F En (for all En ∈ σ(Gn)) it follows that E′′ 0 ∈ min(σ(Gn),⪯F ). Hence σ(F ∗σ Gn) ∪ σ(G0) ̸= ∅.

Theorem 4. Let ∗σ : AFA ×AFA ↦→ AFA be an operator satisfying postulates A∗1 - A∗6 and Acyc for a proper I-maximal semantics σ. Then, there exists an I-faithful assignment mapping every F ∈ AFA to an I-faithful ranking ⪯F on 2A such that F ∗σ G = fσ(min(σ(G), ⪯F )) for any G ∈ AFA.

Proof. Assume there is ∗σ : AFA × AFA ↦→ AFA satisfying postulates A∗1-A∗6 and Acyc, and take an F ∈ AFA. We construct ⪯F in two steps. First we define a relation ⪯′F on 2A by saying that for any two ⊆-incomparable E, E′ ∈ 2A :

The relation ⪯′F is reflexive, as A∗1 and A∗3 imply that E ∈ σ(F ∗σ fσ({E})), but not necessarily total. In the next step we take ⪯F to be the transitive closure of ⪯′F . In other words:

The remainder of the proof shows that ⪯F is the desired I-faithful ranking. First, notice that if E1 ⪯′F E2 then E1 ⪯F E2. Hence ⪯F is reflexive and, by construction, it is transitive, which makes it a pre-order on 2A . Additionally, for any two ⊆-incomparable extensions E1, E2, proper I-maximality of σ guarantees that fσ({E1,E2}) exists. By A∗1 and A∗3, σ(F ∗σ fσ({E1,E2})) is a non-empty subset of {E1,E2}, thus E1 ⪯′F E2 or E2 ⪯′F E1 and ⪯′F is I-total. Next we argue that ⪯ is an I-faithful ranking.

Due to proper I-maximality of σ, a set {E1,E2} is realizable whenever E1 and E2 are ⊆-incomparable. Thus, we usually write simply {E1, E2} instead of σ(fσ({E1, E2})).

Proof. From A∗2 and proper I-maximality of σ, we get σ(F ∗ fσ({E1, E2})) = σ(F ) ∩ {E1, E2} = {E1, E2}. Thus E1 ⪯′F E2 and E2 ⪯′F E1, which implies E1 ≈F E2.

Lemma 3 shows that ⪯F satisfies property (i) of I-faithful assignments. For property (ii) we make use of the following lemmas. It is in this context that Acyc proves crucial.

Lemma 4. If E1, . . . ,En are pairwise distinct extensions with E1 ⪯′F E2 ⪯′F · · · ⪯′F En ⪯′F E1, then E1 ⪯′F En.

Proof. If n = 2 the conclusion follows immediately. In the following we assume that n > 2. From the hypothesis we have that Ei ∈ σ(F ∗σ fσ({Ei,Ei+1})), for i ∈ {1, n - 1}, and En ∈ σ(F ∗σ fσ({En,E1})). It follows that E1 ∈ σ(F ∗σ fσ({E1,E2})) ∩ {En,E1}, Ei ∈ σ(F ∗σ fσ({Ei, Ei+1}))∩{Ei-1, Ei}, for i ∈ {2, . . . , n-1}, and En ∈ σ(F ∗σ fσ({En, E1})) ∩ {En-1, En}. Applying Acyc, we get that σ(F ∗σ fσ({En,E1})) ∩ {E1,E2} ̸= ∅. From A∗5 and A∗6 it follows that σ(F ∗σ fσ({En, E1})) ∩ {E1,E2} = σ(F ∗σ fσ({En,E1} ∩ {E1,E2})). Since {En,E1} ∩ {E1,E2} = {E1} we get by A∗4 that σ(F ∗σ fσ({En, E1}∩{E1, E2})) = σ(F ∗σ fσ(E1)). Finally, using A∗1 and A∗3 we conclude that σ(F ∗σ fσ(E1)) = {E1}, and thus E1 ∈ σ(F ∗σ fσ({En, E1})), implying E1 ⪯′F En.

Lemma 5. For any extensions E and E′ , if E ≺′F E′ then E ≺F E′ .

Proof. Suppose, on the contrary, that E′ ⪯F E. Then there exist E1, . . . ,En such that E1 = E′ , En = E and E1 ⪯′F · · · ⪯′F En. Since we also have E ≺′F E′ , we can apply Lemma 4 to get E1 ⪯′F En, a contradiction.

Lemma 6. If E1 and E2 are ⊆-incomparable extensions and E1 ∈ σ(F), E2 /∈ σ(F), then E1 ≺F E2.

Proof. By proper I-maximality of σ and A∗2 we get σ(F ∗σ fσ({E1,E2})) = σ(F) ∩ {E1,E2} = {E1}. This implies that E1 ≺′F E2 and by Lemma 5 E1 ≺F E2.

Lemma 6 gives us property (ii). Property (iii) is true because ⪯F extends ⪯′F , which is defined solely with respect to the extensions of F .

Lastly, we show that the extensions of F ∗σ G, for any G ∈ AFA, are the minimal elements of σ(G) under ⪯F .

Lemma 7. For any two extensions E1, E2 and any G ∈ AFA, if E1 ∈ σ(G), E2 ∈ σ(F ∗σ G) and E1 ⪯′F E2, then E1 ∈ σ(F ∗σ G).

Proof. Since E2 ∈ σ(F ∗σG), by A∗1 we get that E2 ∈ σ(G). Thus E1 and E2 are both σ-extensions of G, and by proper I-maximality of σ, fσ({E1,E2}) exists. Given this, the rest of the proof is similar to the one for Lemma 1.

Proof. Keeping in mind that for any two σ-extensions E1, E2 of G, by proper I-maximality of σ), E1 ⪯′F E2 or E2 ⪯′F E1, the proof is similar to the one for Lemma 2.

Lemma 9. For any argumentation framework G ∈ AFA, it holds that min(σ(G), ⪯F ) = min(σ(G), ⪯′F ).

Proof. ⊆: Let E1 ∈ min(σ(G), ⪯F ) and suppose there exists E2 ∈ σ(G) with E2 ≺′F E1. By Lemma 5, this implies that E2 ≺F E1, a contradiction to E1 ∈ min(σ(G),⪯F ). It follows that E1 ⪯′F E2, thus E1 ∈ min(σ(G), ⪯′F ).

⊇: Take E1 ∈ min(σ(G),⪯′F ) and any E2 ∈ σ(G). If E2 = E1, it follows that E1 ⪯′F E2. If E2 ̸= E1, then by proper I-maximality of σ, E1 and E2 are ⊆-incomparable and thus E1 ⪯′F E2 or E2 ⪯′F E1. We cannot have that E2 ≺′F E1, since this would contradict the hypothesis that E1 ∈ min(σ(G), ⪯′F ), therefore E1 ⪯′F E2. In both cases it follows that E1 ⪯F E2, hence E1 ∈ min(σ(G), ⪯F ).

Finally, notice that any faithful assignment on 2A can be used, via Theorem 3, to construct a revision operator σ∗ : AFA × AFA → AFA. The reason why revision by argumentation frameworks is easier than revision by propositional formulas is the fact that any subset of σ(F) is realizable under σ, for any proper I-maximal semantics σ and F ∈ AFA. Also, any faithful assignment is an I-faithful assignment in our sense, which implies, by Theorem 3, that ∗σ satisfies A∗1 - A∗6 and Acyc. Thus, any model-based revision operator from the standard literature on belief change (e.g., Dalal's operator [Dalal, 1988]) can be used as a revision operator of AFs by AFs.

4 Discussion

RelatedWork As we already indicated in the introduction to this work, there has been a substantial amount of research in the dynamics of argumentation frameworks although the problems investigated and approaches that have been developed to tackle these differ considerably. We briefly discuss the most closely related work.

Booth et al. [2013] develop a general AGM-like framework for modelling the dynamics of AFs based on a labelling approach. Particularly relevant for their work is the notion of "fall back beliefs" which represent the most rational outcome of the input AF given a constraint. Their revision operator is defined in terms of conflict free labellings and their notion of "fall back beliefs" is developed only for complete semantics.

We have already mentioned the work presented in [CosteMarquis et al., 2014a] which is the starting point of our investigation. On the semantic side, their revision functions are defined following a two step process: first a counter-part to the notion of faithful assignment on the models of the revision operators is defined; secondly, a set of AFs that generate such extensions is constructed using different criteria, e.g. minimizing the changes in the attack relation of the input AF vs. minimizing the number of AFs generated. The main difference between the work presented in [Coste-Marquis et al., 2014a] to our work is that we consider the issue of revision of AFs as minimal change in the arguments statuses under the constraint that a single AF has to be produced. The price we pay is that in our solution the revised AF may have new arguments while in [Coste-Marquis et al., 2014a] only the attack relation can be modified. Recent work on realizability in compact AFs [Baumann et al., 2014] could pave the way for revision in the setting where, the result is a single AF, but no additional arguments are allowed to come into play.

Finally, in [Coste-Marquis et al., 2014b] the revision problem for AFs is translated into propositional logic thus enabling the use of classical AGM revision operators to carry out revision in the AF setting. On the other hand, the revision formulas are defined in terms of the skeptical acceptance of arguments. Nevertheless, the output of revision is still a set of AFs rather than a single AF.

Conclusion andOutlook We have presented a generic solution to the problem of revision for argumentation frameworks which applies to many prominent I-maximal argumentation semantics. The key to obtain our AGM-style representation theorems was the combination of recent advances from argumentation theory and belief change. We identify several directions for future work: (1) extend our results to semantics which are not proper I-maximal; (2) identify operators based on σ-compliant rankings for specific semantics σ; (3) analyze whether our insights can be extended to a broader theory of belief change within fragments; (4) apply our findings to other belief change operations. In particular, iterated belief revision seems to have natural applications in the argumentation domain and we believe that the understanding of revision yielding a single AF is fundamental for this purpose; (5) take the syntactic form of the AF into account. One possibility would be a two-step approach, where our abstract revision is the first step. Based on this result, a second step would revise the syntactic structure of the AF.