--- title: "Two Sides of the Same Coin: Belief Revision and Enforcing Arguments" authors: - "Adrian Haret" - "Johannes P. Wallner" - "Stefan Woltran" doi: "10.24963/ijcai.2018/256" url: "https://ijcai.org/proceedings/2018/256" pdf: "https://ijcai.org/proceedings/2018/0256.pdf" venue: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence" year: 2018 pages: "1854-1860" track: "Main track" keywords: - "Knowledge Representation and Reasoning: Computational Models of Argument" - "Knowledge Representation and Reasoning: Belief Change" --- # Two Sides of the Same Coin: Belief Revision and Enforcing Arguments Adrian Haret, Johannes P. Wallner, Stefan Woltran *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence*, pages 1854-1860. DOI: [10.24963/ijcai.2018/256](https://doi.org/10.24963/ijcai.2018/256) ## Abstract We study a type of change on knowledge bases inspired by the dynamics of formal argumentation systems, where the goal is to enforce acceptance of certain arguments. We put forward that enforcing acceptance of arguments can be viewed as a member of the wider family of belief change operations, and that an axiomatic treatment of it is therefore desirable. In our case, laying down axioms enables a precise account of the close connection between enforcing arguments and belief revision. Our analysis of enforcing arguments proceeds by (i) axiomatizing it as an operation in propositional logic and providing a representation result in terms of rankings on sets of interpretations, (ii) showing that it stands in close relationship to belief revision, and (iii) using it as a gateway towards a principled treatment of enforcement in abstract argumentation. ## Full text ## 1 Introduction The axiomatic approach to belief change [Alchourr´on et al., 1985; G¨ardenfors, 1988; Katsuno and Mendelzon, 1992] is a powerful tool in the study of dynamically evolving knowledge. Its unified methodology has proven useful for the formalization and comparison of various change operations (e.g., revision or update), and has opened up an avenue for the foundational study of other change operations of relevance to the AI community. The present work looks at enforcing acceptance of arguments, an operation from the rapidly growing field of formal argumentation [Bench-Capon and Dunne, 2007], whose focus on formalized debates lends itself naturally to an analysis in terms of beliefs and their dynamics. Indeed, interest in connecting argumentation and belief change has steadily risen over the last few years (see [Falappa et al., 2011; Paglieri and Castelfranchi, 2004] for an overview, and the dedicated workshop [Ferm´e et al., 2013], which was held again in end of 2017). Enforcing arguments is a core operator in formal argumentation, whose aim is to force a reasoner to accept (a set of) arguments. Typically, this aim must be achieved through minimal modifications to the reasoner's current state of arguments [Baumann and Brewka, 2010; Baumann, 2012b; de Saint-Cyr et al., 2016], with the intuition that enforcing should be done in an "economic" manner. While several aspects of enforcing arguments have been investigated, a general axiomatic study of the semantic changes required by this operation (as carried out for operators in belief change) has so far received little attention. The multitude of formal models in argumentation, coupled with a plethora of semantics, means that such a general investigation is helpful for avoiding ad-hoc approaches focused on single formalisms. ∗This work has been supported by the Austrian Science Fund (FWF): P30168-N31, P25521, I2854, W1255-N23 and a Marietta Blau grant (OeAD-GmbH). In this paper we provide an axiomatization of enforcement with the novel feature of accommodation, or preservation, of current points of view. This comes in contrast to existing enforcement, which may disrupt beliefs arbitrarily. In line with our vision of a principled approach, we begin by providing an axiomatization of our enforcement operation in propositional logic, which (1) places enforcement on the map of generic belief change operations and highlights connections to other operations in this field, and (2) lays the groundwork for deriving foundational representation results. We argue that this provides a general framework for enforcement, and take first steps in applying it to the context of abstract argumentation. We find that viewing enforcement as a dual to revision provides a natural way for axiomatizing these requirements: while revising a knowledge base κ with µ returns a nonempty subset of the models of µ, a dual axiomatization of revision represents a family of operators that return a nontautological superset of the models of µ. In this way models of µ are enforced, while models of κ's are, if possible, included, all the while avoiding an uninformative tautology. Our main contributions are summarized below: - We provide an alternative representation result for revision that uses rankings on sets of interpretations, rather than the more usual rankings on interpretations, which are better suited for relating revision and enforcement. - We axiomatize enforcement as a natural dual to revision, prove the connection between revision and enforcement and show a representation result for enforcement based on ranking sets of interpretations. - Based on the formalization in propositional logic, we axiomatize our enforcement operation in the context of argumentation frameworks (AFs) [Dung, 1995], a major formalism in argumentation and their admissible semantics. We show that certain "idealized" axioms cannot be applied to AFs, yet our axiomatization in logic, aided by a characterization of the admissible semantics, leads to a principled approach to modify the axioms to suit AFs. - We show how distance-based revision operators (e.g., [Dalal, 1988]) can be adapted to propositional enforcement and to AFs under admissible semantics. - We argue that, when permitting only certain structural changes to an AF, axioms have to be adapted to such constraints, yet this endeavor requires semantical characterizations of the restrictions. ## 2 Belief Revision We assume a finite set P of propositional atoms and L is the set of formulas generated from P with the usual connectives. A knowledge base κ is a finite set of formulas, typically interpreted conjunctively (i.e., as ∧ϕ∈κ ϕ). The set of propositional knowledge bases is 2L. The universe U is the set of possible interpretations for formulas in L. The models of a propositional formula µ are the interpretations which satisfy it, and we write [µ] (respectively, [κ]) for the set of models of µ (respectively, for ⋂ϕ∈κ [ϕ]). We typically write models as words where letters are the atoms assigned to true, e.g., {{a, b}, {b, c}} is written as {ab, bc}. If µ1, µ2 ∈ L, we say that µ1 |= µ2, if [µ1] ⊆ [µ2], and that µ1 ≡ µ2, if [µ1] = [µ2]. A formula µ (a knowledge base κ) is consistent if [µ] ̸= ∅ ([κ] ̸= ∅). The set of consistent knowledge bases is 2Lc . The set of refutable (i.e., non-tautological) knowledge bases is 2Lr . A propositional revision operator ◦ maps a κ ∈ 2Lc and a µ ∈ L to κ ◦ µ ∈ L. The intention is that κ ◦ µ is the result of modifying existing beliefs κ such that new, trusted information µ is accepted. The following list of axioms is typically acknowledged as a basic core of rational properties for revision [Katsuno and Mendelzon, 1992]: - (R1) κ ◦ µ |= µ. - (R2) If κ ∧ µ is consistent, then κ ◦ µ ≡ κ ∧ µ. - (R3) If µ is consistent, then κ ◦ µ is consistent. - (R4) If κ1 ≡ κ2 and µ1 ≡ µ2, then κ1 ◦ µ1 ≡ κ2 ◦ µ2. - (R5) (κ ◦ µ) ∧ϕ |= κ ◦ (µ ∧ϕ). - (R6) If (κ ◦ µ) ∧ϕ is cons., then κ ◦ (µ ∧ϕ) |= (κ ◦ µ) ∧ϕ. Reflection on axioms R1-6 reveals that, if faced with inconsistency, an operator ◦ satisfying them has to give up information from κ and that, in doing so, ◦ behaves as if it has preferences over units of information. This is formalized using the following notions. A preorder ≤ on a set W is a reflexive, transitive binary relation on W. The set of transitive relations on W is denoted as T (W). We write < for the strict part of ≤, i.e., x < x′ if x ≤ x′ and x′ ̸≤ x. We write x ≈ x′ if x ≤ x′ and x′ ≤ x. The ≤-minimal elements of W with respect to ≤ are defined as min≤W = {x ∈ W | ∄x′ ∈ W such that x′ < x}. An assignment from W1 to W2 is a function α : W1 → T (W2). A useful result in belief revision connects axioms R1-6 to assignments from 2Lc to U, for which we may write ≤κ instead of α(κ) if there is no danger of ambiguity. We say that an assignment from 2Lc to U represents a revision operator ◦ (and that ◦ is represented by an assignment from 2Lc to U) if, for any κ ∈ 2Lc and µ ∈ L, it holds that [κ ◦ µ] = min≤κ [µ]. Given an assignment from 2Lc to U, κ, κ1, κ2 ∈ 2Lc and w1,w2 ∈ U, the following properties are of particular interest: (f1) if w1,w2 ∈ [κ], then w1 ≈κ w2; (f2) if w1 ∈ [κ] and w2 /∈ [κ], then w1 <κ w2; (f3) if κ1 ≡ κ2, then ≤κ1 =≤κ2 . A faithful assignment is an assignment from 2Lc to U such that ≤κ is a total preorder and properties f1-3 are satisfied. Faithful assignments provide the semantic counterpart to axioms R1-6, as shown by the following representation result. Theorem 1 ([Katsuno and Mendelzon, 1992]). A revision operator satisfies axioms R1-6 iff there exists a faithful assignment which represents it. Revision by ranking sets of interpretations. By Theorem 1, revision according to axioms R1-6 is equivalent to ranking interpretations in a way that depends on κ, and choosing the most plausible allowed interpretations. Alternatively, we show, revision can be seen as choosing one element from a set of formulas (in semantic terms, from a set of sets of interpretations). If M is a set, we write sub(M) = 2M \ {∅} for the set of non-empty subsets of M. We now switch to working with assignments from 2Lc to sub(U). Given such an assignment, κ, κ1, κ2 ∈ 2Lc , and W1,W2 ∈ sub(U), the following properties are of particular interest: - (r1) If W1 ̸= W2, there is W3 ∈ sub(U) such that W3 ⊆ W1 ∪W2 and min≤κ {W1,W2,W3} = {W3}. - (r2) If W1,W2 ∈ sub([κ]) andW1 ⊆W2, thenW2≤κW1. - (r3) If W1 ∈ sub([κ]) andW2 /∈ sub([κ]), thenW2 ≰κ W1. - (r4) If κ1 ≡ κ2, then ≤κ1 =≤κ2 . - (r5) If W1≤κW3≤κW2 andW3⊆W2, thenW1 ∩W2⊆W3. - (r6) If W1≤κW3 ≤W2, W3 ⊆W2 and W1 ∩W2 ̸= ∅, then W3 ⊆ W1 ∩ W2. An r-assignment is an assignment from 2Lc to sub(U) such that ≤κ is a partial transitive relation and r1-6 are satisfied. The intention is to use properties r1-6 to represent revision operators satisfying axioms R1-6: intuitively, sets of interpretations W1 and W2 stand for formulas, and W1 <κ W2 encodes the fact that W1 gets chosen over W2 if a choice is to be made among them. Property r1 says that, for any sets of interpretations W1 and W2, there is W3 ⊆ W1 ∪W2 strictly preferred among the three, i.e., W3 would get chosen if the choice were between W1, W2 and W3. This property is equivalent to min≤ sub([µ]) being a singleton, for any µ ∈ L: assuming two distinct ≤κ-minimal subsets of [µ] generates a contradiction with r1. Since we only consider assignments satisfying r1, we henceforth identify min≤ sub([µ]) with its unique element. Thus we can define a revision operator whose output is exactly this minimal element. For further intuitions, (r2) states that supersets are preferred (if models of κ), (r3) states that models of κ are preferred, (r4) denotes syntax independence, and (r5) and (r6) can be seen as semantic counterparts of axioms R5-6, We say that an assignment from 2Lc to sub(U) satisfying r1 represents a revision operator ◦ if, for any κ ∈ 2Lc and µ ∈ L, it holds that [κ◦µ] = min≤κ sub([µ]). Figure 1: Rankings associated to κ by a faithful assignment and an r-assignment; an arrow from x to y indicates that x≤κy. ![Image](https://ijcai.org/proceedings/2018/fulltext/256/image_000000_1e5c28c0a022f4a1e87ba8a7883260a9a92a915c4f88335572bd1aba53108804.png) Example 1. Consider the alphabet P = {a, b}, a knowledge base κ = {¬a} and an r-assignment that associates to κ the ranking ≤κ in Figure 1-(b). Revision of κ by µ = a yields min≤κ sub([µ]) = min≤κ {{a}, {ab}, {a, ab}} = {a, ab}. Finally, we convince ourselves that things are properly arranged with a representation result involving r-assignments. Theorem 2. A revision operator satisfies R1-6 iff there exists an r-assignment which represents it. Faithful assignments and r-assignments represent the same axioms, so one would expect there to be a correspondence between them. This correspondence can be made precise, as follows. If ≤g is a relation onM, the lifting of ≤g to sub(M) is a relation ≤l on sub(M) defined, for any W1,W2 ∈ sub(M), by taking W1≤lW2 iff (l1)min≤g W1 = W1, and either (l21) W2 ⊆ W1, or (l22) w1<gw2, for any w1 ∈ W1 and w2 ∈ W2 \ W1. Conversely, if ≤l is a relation on sub(M), the grounding of ≤l to M is a relation ≤g on M defined, for any w1,w2 ∈ M, by taking w1≤gw2 iff w1 ∈ min≤l sub({w1,w2}). Notably, lifting a faithful assignment results in an r-assignment, while grounding an rassignment results in a faithful assignment. Example 2. For κ = {¬a}, ≤rκ in Figure 1-(b) is obtained by lifting ≤fκ in Figure 1-(a): notice, e.g., that {∅, b}≤rκ {∅, b}, since ∅ ≈fκ b (giving us l1) and {∅, b} ⊆ {∅, b} (giving us l21); we also have {∅}<rκ {∅, a}, because ∅ ≈fκ ∅ (giving us l1) and ∅ <fκa (giving us l22). Conversely, ≤fκ is the grounding of ≤rκ , we get, e.g., that ∅ <fκa, because min≤rκ sub({∅, a}) = min≤rκ {{∅}, {a}, {∅, a}} = ∅. ## 3 Propositional Enforcement Axiomatization. Enforcement stems from abstract argumentation, where new information can be brought to a debate, requiring reconsideration of the acceptance status of certain arguments [de Saint-Cyr et al., 2016]. Concretely, an argumentation framework undergoes change such that its extensions (in this section, its models) include some distinguished elements. More broadly, daily life provides us with interactions where agents balance their positions in order to take into account differing points of view. Accommodation is achieved not necessarily through unconditional acceptance of one of the viewpoints (as in revision), but by finding a middle ground between the different sources. Such interactions often have a strategic flavor, and success consists in finding a position that allows the possibility of having one's preferred options, while avoiding an uninformative solution such as a tautology. Example 3. The prime-minister is weighing two responses to an economic downturn: a combination of increased taxes and spending cuts, i.e., austerity measures (a), and borrowing money (b). The prime-minister is privately in favor of implementing austerity (µ = a), but polling reveals that the public is in favor of borrowing (κ1 = {b}). The prime-minister wants to put forward a plan that leaves the option of austerity on the table, while at the same time appeasing the public. The most inclusive solution in this situation is κ1 ∨ µ ≡ a ∨ b. Suppose that further polling reveals the public to be opposed to austerity (κ2 = {¬a}). In this case we have κ2∨µ ≡ ¬a ∨ a, and the prime-minister would like to avoid putting forward a vacuous proposal. Nonetheless, the same considerations from before apply and we reason that the primeminister's options range as follows: she could put forward a, if she is confident she can override public opinion; b → a, for a compromise solution; or a∨b, for a non-committal position. We formalize these intuitions through an enforcement operator ▷, mapping a refutable (i.e., non-tautological) knowledge base κ ∈ 2Lr and a formula µ ∈ L to a knowledge base κ ▷ µ ∈ 2L. We restrict to refutable knowledge bases, since tautological formulas are a special case (no useful information and all interpretations are models). Following common belief change practice, we start by proposing a set of axioms: - (E P3 ) If µ is refutable, then κ ▷ µ is refutable. Axioms E P1-6 can be seen as dual to axioms R1-6 for revision, and their logic is as follows. Axiom E P1 formalizes the idea that the enforcement result takes µ into account, by requiring that µ implies it. Axiom E P2 says that unless κ ∨ µ is a tautology, in which case it would carry no useful information, we are to simply take the disjunction of κ and µ. Thus, ideally, enforcement shall accommodate (preserve) κ's models. Axioms E P3 and E P4 say that enforcement should yield an informative result when µ is informative, and that this result should not depend on the syntax of κ and µ. Finally, axioms E P5 and E P6 ensure that the enforcement operator has a stable behavior when the enforcement formula is allowed to vary. For an intuition, consider Example 3: if the policy proposal (κ1 ▷ µ) were to be augmented with a third option (c), then the axioms ensure equivalence to κ1 ▷(µ∨c) (the result is the same as if c was part of original proposal and public opinion needs to be accommodated either way). Relating revision and enforcement. It is intended that the enforcement axioms E P1-6 bear some resemblance to the revision axioms R1-6, which raises the question of what connection there is between the two operations. The following theorem makes this connection precise. Figure 2: Order associated with κ by an e-assignment. ![Image](https://ijcai.org/proceedings/2018/fulltext/256/image_000001_51a44991c94d6b401afff508ba22973c68e55746174661e24111cf706bc8ef06.png) Theorem 3. A propositional enforcement operator ▷ satisfies E P1-6 iff there is a propositional revision operator ◦ satisfying R1-6 s.t., for any κ ∈ 2Lr and µ ∈ L: κ ▷ µ = ¬(¬κ ◦ ¬µ). Theorem 3 reveals that enforcement is a dual to revision. Intuitively, in order to accommodate µ, an enforcement operator gives up possible worlds that do not satisfy µ, in a manner that shows some preference for preserving as much as possible of the information in κ. Thus enforcement operators act as choice functions, choosing the 'best' elements from feasible options: the menu of feasible options here is the set of refutable supersets of [µ], defined as sup([µ]) = {W ̸= U | [µ] ⊆ W}. Deciding which of these supersets is best requires an underlying ranking over sets of interpretations, and to this purpose we employ assignments from 2Lr to 2Ur , where 2Ur = 2U \ {U}. Given such an assignment, κ, κ1, κ2 ∈ 2Lr , and W1,W2 ∈ 2Ur , consider the following properties: - (e1) If W1 ̸= W2, there is W3 ∈ sup(U) such that W1 ∩ W2 ⊆ W3 and min≤κ {W1, W2, W3} = {W3}. - (e2) If W1,W2 ∈ sup([κ]) andW1 ⊆W2, thenW1≤κW2. - (e3) If W1 ∈ sup([κ]), W2 /∈ sup([κ]), thenW2 ≰κ W1. - (e4) If κ1 ≡ κ2, then ≤κ1 =≤κ2 . - (e5) If W1≤κW3≤κW2 andW2⊆W3, thenW3⊆W1 ∪W2. - (e6) If W1≤κW3≤κW2, W2 ⊆W3 andW1 ∪W2 ̸= U, then W1 ∪ W2 ⊆ W3. An e-assignment αe is an assignment from 2Lr to 2Ur such that ≤κ is a partial transitive relation and e1-6 are satisfied. An e-assignment αe represents an enforcement operator ▷ (alternatively, ▷ is represented by αe ) if, for any κ ∈ 2Lr and µ ∈ L, it holds that [κ ▷ µ] = min≤κ sup([µ]). Example 4. For the alphabet P = {a, b}, take a knowledge base κ = {a} and the ranking ≤κ in Figure 2. Enforcement by µ = ¬a yields [κ ▷ µ] = min≤κ sup([µ]) = min≤κ {{∅, b}, {∅, a, b}, {∅, b, ab}} = {∅, b}. To establish a representation result, we use the connection to revision presented in Theorem 3. We show a similar correspondence between r-assignments and e-assignments. Proposition 4. For any r-assignment αr there is an eassignment αe such that, for any κ ∈ 2Lr andW1,W2 ∈ 2Ur , it holds that W1≤eκW2 iff (U \W1)≤r¬κ (U \W2). Conversely, for any e-assignment αe there is an r-assignment αr such that W1≤rκW2 iff (U \W1)≤e¬κ (U \W2). This correspondence facilitates the following result. Theorem 5. A propositional enforcement operator satisfies axioms E P1-6 iff there is an e-assignment representing it. It is here that our representation of revision operators using rankings on sets of formulas pays off richly, as it highlights in a very clear manner the correspondence between revision and enforcement at the semantic level. A representation for enforcement using rankings on interpretations is unwieldy and lacks the intuitive appeal of an e-assignment. Concrete enforcement operators. The drastic enforcement operator ▷D , is defined, for any κ ∈ 2Lr and µ ∈ L, by: κ ▷D µ = κ ∨ µ if κ ∨ µ is refutable, and µ otherwise. A more fine-grained operator uses the Hamming distance between interpretations (i.e., the number of atoms on which they differ) to choose a set of interpretations situated between [µ] and [κ ∨ µ]. We call this Dalal's enforcement operator ▷H , as it uses the identity in Theorem 3 to adapt Dalal's revision operator [Dalal, 1988] into an enforcement operator. Define, first, the minimum cardinality of the symmetric difference of models of two formulas as |∆|min (ϕ, ψ) = min{|w∆w′ | | w ∈ [ϕ],w′ ∈ [ψ]}, for ϕ, ψ ∈ L. The operator ▷H is now defined by taking [κ ▷H µ] = {w ∈ U | ∄w′ ∈ [¬κ] such that |w∆w′ | = |∆|min (¬κ, ¬µ)}. Intuitively, [κ ▷H µ] is obtained by removing the interpretations from [¬µ] at minimum distance to [¬κ]. Example 5. For an alphabet P = {a, b}, take κ = {¬a∨¬b}, and suppose we want to enforce µ = a ∧ b. For ▷D we get κ ▷D µ = µ, since κ ∨ µ is a tautology. For ▷H , we have [¬κ] = {ab} and [¬µ] = {∅, a, b}. The models from ¬µ that have minimum distance to ¬κ are a and b. Therefore, [κ ▷H µ] = U \ {a, b} = {∅, ab} = [a ↔ b]. Drastic and Hamming enforcement operators satisfy E P1-6 (via Theorem 3, any revision operator satisfying R1-6 can be converted into an enforcement operator satisfying E P1-6 ). ## 4 Enforcement in Argumentation Existing forms of enforcement focus on the formal model of argumentation frameworks (AFs) [Dung, 1995], representable as directed graphs F = (A,R) with A a set of arguments and R a directed conflict relation (attacks) between arguments. The study of AFs is mainly concerned with defining subsets of arguments (extensions) that can be accepted together when taking into account the graph structure. As a result, the argumentation literature offers a wide range of criteria (AF semantics) for establishing jointly acceptable arguments. Enforcing a set S with respect to F typically amounts to changing F such that F's set of extensions includes S [Baumann and Brewka, 2010; Baumann, 2012b]. In this section we focus on the admissible semantics, whose definition requires the following notions. For an AF F = (A,R), a set E ⊆ A is conflict-free in F if there is no directed edge between any arguments in E; E is an admissible extension if E is conflict-free, and for each argument c attacking a ∈ E, there is an argument b ∈ E that attacks c (b counters c, and can be thought of as defending a). If F is an AF, then adm(F) is the set of its admissible extensions. Example 6. Let F = ({a, b, c}, {(b, c)}) be an AF. We have adm(F) = {∅, a, b, ab}. Enforcing {ac} requires finding an AF F ′ such that ac ∈ adm(F ′ ). Notice the similarity between the extensions of an AF and the models of a propositional formula: though syntactically different, formulas and AFs share a common semantic representation, and it is this insight that raises the prospect of modelling enforcement as a belief change operation. We wish to apply the axiomatic approach developed for propositional enforcement (see previous section) to AFs. In doing so, we will exploit the analogy between extensions and propositional models. However, we immediately run into a problem. In contrast to propositional logic, there are sets S of sets of arguments for which there is no AF F such that adm(F ) = S. A set S of sets of arguments is adm-realizable if there exists an AF F such that adm(F) = S [Dunne et al., 2015]. Fortunately, we know exactly what properties S has to satisfy in order for such an F to exist. The admissible closure of a set S of extensions [Dunne et al., 2015; Niskanen et al., 2016] characterizes all adm-realizable sets, and is defined by taking Cl (S) = {E | E = ⋃E′∈S′ E′ , S′ ⊆ S, ∀a, b ∈ E it holds that ∃E′′ ∈ S s.t. {a, b} ⊆ E′′ }. Intuitively, in the admissible closure of S, we add E, if E is the union of some sets in S, and each pair of arguments a, b from E is conflictfree, i.e., both occur together in some set in S. It holds that Cl (S) is the smallest superset of S that is adm-realizable, and that S is adm-realizable iff Cl (S) = S. The signature of the admissible semantics Σadm = {adm(F) | F is an AF} thus can be characterized by Σadm = {S | Cl (S) = S}. Example 7. If M = {∅, a, ab, ac, bc}, then Cl (M) = M ∪ {abc} and thus M is not adm-realizable. An adm-enforcement operator ▷adm is a function which, given an AF F and µ ∈ L, maps adm(F) and [µ] to a set of extensions adm(F ▷adm µ). The propositional formula µ encodes the extensions to be enforced, under the assumption that sets of arguments are identified with interpretations and admissible extensions with models. The notation makes it clear that the intention is to realize adm(F ▷adm µ) as an AF under the admissible semantics, and it is worth noting how the issue of realizability has a role to play: a set of extensions is adm-realizable as an AF only if it is in the signature Σadm of the admissible semantics; given our identification of extensions with interpretations, one can think of all adm-realizable sets as a subset of the semantics of propositional logic. In this way, enforcement on adm-realizable sets can be viewed as operating in a "fragment" of propositional logic. Going from propositional enforcement to admenforcement of AFs, we say a set S is refutable if it is a proper subset of 2A, with A the set of all arguments occurring in F and µ. We propose the following axioms: - (E A1 ) [µ] ⊆ adm(F ▷adm µ). - (E A2 ) adm(F ▷adm µ) ⊆ Cl (adm(F) ∪ [µ]). - (E A3 ) If Cl (adm(F) ∪ [µ]) is refutable, then adm(F)∪[µ] ⊆ adm(F ▷adm µ). - (E A4 ) If adm(F1) = adm(F2) and [µ1] = [µ2], then adm(F1 ▷adm µ1) = adm(F2 ▷adm µ2). - (E A5 ) adm(F ▷adm (µ ∨ ϕ)) ⊆Cl (adm(F ▷adm µ) ∪ [ϕ]). - (E A6 ) If adm(F ▷adm µ) ∪ [ϕ] is refutable, then adm(F ▷adm µ) ∪ [ϕ] ⊆ adm(F ▷adm (µ ∨ ϕ)). 1 1 Refutable refers here to arguments occurring in F , µ and ϕ. Comparison with axioms E P1-6 reveals differences, imposed by the particularities of AF semantics. One change concerns axiom E A2 , which reflects a no-effort case: a straight adaptation of the propositional case suggests adm(F) ∪ [µ] as default output, but this is not guaranteed to be adm-realizable. Example 8. Let A = {a, b, c}, adm(F) = {∅, a, ab} and [µ] = {ac, bc}, we have adm(F ) ∪ [µ] is not adm-realizable. Since adm(F ▷adm µ) includes [µ] (by E A1 ), and is admrealizable, we have Cl ([µ]) ⊆ adm(F ▷adm µ). What we need from E A2 is an adm-realizable set that acts as an approximation of adm(F ) ∪ [µ], and we suggest Cl (adm(F ) ∪ [µ]) as an upper bound. To justify the choice of axioms E A3 and E A5 , notice that straightforward adaptations of E P3 and E P5 , given by E A7 and E A8 below, clash with the other postulates: - (E A7 ) If Cl ([µ]) is refutable, adm(F ▷adm µ) is refutable. - (E A8 ) adm(F ▷adm µ) ⊆ adm(F ▷adm µ) ∪ [ϕ]. Proposition 6. There is no adm-enforcement operator satisfying axioms E A2-4,6-7 , or E A1-2,4,8 . Thus, we have to weaken E A7,8 . Axiom E A3 sets a lower bound for adm(F ▷adm µ) if Cl (adm(F ▷adm µ)) is refutable, and axiom E A5 replaces adm((F ▷adm µ) ∪ [ϕ]) with its closure. Next, we ask whether there exist adm-enforcement operators satisfying axioms E A1-6 . One natural idea is to use existing propositional enforcement operators, but this founders on the discovery that they typically do not guarantee an admrealizable result, as witnessed by Examples 8 and 9. Example 9. If A = {a, b, c}, adm(F) = {∅, b, c, ac, bc, abc}, and [µ] = {a, b, ab, ac}, then ▷H yields {a, b, c, ab, ac, bc}, which is not adm-closed, and thus not adm-realizable. To ensure that enforcement yields an adm-realizable result, we propose to use propositional operators and coerce their results into Σadm of the adm semantics via the adm-closure. Definition 1. Let F be the set of all AFs, α an assignment from F to 2U mapping every F ∈ F to a transitive order ≤F such that ≤F satisfies e1-6. Then the adm-refinement w.r.t. α is an adm-enforcement operator ▷ref adm and is defined as adm(F ▷ref adm µ)=Cl (min≤F sup(µ)) for any F∈F, µ∈L. By Theorem 5, properties e1-6 are used to represent axioms E P1-6 . Definition 1 can thus be seen as taking a propositional enforcement operator and refining its output such that it falls inside the signature Σadm. This is possible because of our semantic approach where we treat adm(F ) as the models of F , i.e., as a set of sets of atoms in the base alphabet. Interestingly, it turns out that refinements satisfy axioms E A1-6 . Proposition 7. If α is an assignment satisfying e1-6, the adm-refinement with respect to α satisfies axioms E A1-6 . An equivalent result does not hold if we now switch to the duals of axioms E A1-6 . This shows that the restriction to admissible sets makes revision and enforcement diverge: in this context they are no longer mirror images of each other. Structural constraints and existing enforcement. We argue that imposing structural constraints on how an AF may be modified, axiomatization of enforcement requires semantical characterizations of such constraints. To illustrate one such restriction, consider normal expansions [Baumann, 2012a]: given an AF F = (A,R), another AF F ′ = (A′ ,R′ ) is a normal expansion of F if A ⊆ A′ , R ⊆ R′ and for each new attack (a, b) ∈ R′ \ R we have that a or b is an added argument (in A′ \ A). (Attacks between existing arguments must stay untouched.) The signature of normal expansions is, for an AF F = (A, R) with expanded arguments A′ , ΣA′ F = {adm(F ′ ) | F ′ = (A′ ,R′ ) a normal expansion of F}. Example 10. Assume an AF F = ({b, c}, {(b, c)}) and the goal to enforce {ac} to be admissible under normal expansions that may add a (A′ = {a, b, c}). There are only two sets of sets of arguments that include {ac}, are adm-realizable, and realizable via normal expansions, namely W1 = {∅, a, ac} (adding (a, b)), and W2 = {∅, a, b, ac} (adding (a, b) and (b, a)): ΣA′ F ∩sup({ac}) = {W1,W2}. Note that adm(F) = {∅, b} and Cl adm(adm(F ) ∪ {ac}) = adm(F ) ∪ {ac}. As illustrated by the example, there are cases where operator ▷ref adm yields an adm-realizable set, yet not realizable via normal expansions. We now show axiom satisfaction when we define an operator that may choose arbitrarily from ΣA′ F as the outcome of enforcement, i.e., for an AF F = (A,R), we define adm(F ▷s µ) ∈ ΣA′ F , for pre-specified expanded arguments A′ ⊇ A, and only require that [µ] ⊆ adm(F ▷s µ) (enforcement is successful). The alphabet (arguments) and A (for defining refutability) for such operators is then equal to A′ . For instance, in Example 10, such an operator may either choose W1 or W2. We assume here that there always is a superset of [µ] in ΣAF . Let S be all such operators ▷s . Independently of the choice, two axioms cannot be satisfied. Proposition 8. If ▷s is an operator such that ▷s ∈ S, then ▷s satisfies axiom E A1 , but neither E A2 nor E A4 . In strict extension enforcement for normal expansions [Baumann and Brewka, 2010] for an AF F = (A, R) and S ⊆ 2A, the output is F ′ = (A′ ,R′ ) s.t. F ′ is a normal expansion of F , S ⊆ adm(F ′ ) and |R∆R′ | is minimal, breaking ties arbitrarily. We assume that F ′ is uniquely determined. Example 11. Continuing Ex. 10, enforcing {ac} under strict extension enforcement adds (a, b), corresponding to W1. This shows that axioms for enforcement under adm cannot be preserved under normal expansions. Generally, strict extension enforcement satisfies axiom E A1 , but not E A2-6 . Other variants of enforcement [Coste-Marquis et al., 2015], under minimal changes to attacks, can be shown to violate at least one axiom. Rather than a shortcoming of the axiomatic approach, this shows that semantical characterizations of structural constraints are needed: e.g., under normal expansions admissible extensions can be preserved (see Ex. 10). However, axiom E A2 is tailored to unrestricted enforcement under adm. What is needed to adapt a property such as adm(F ) ∪ [µ] ⊆ adm(F ▷s µ) ⊆ U to other types of enforcement is a new bound U. While semantic effects (e.g., adding an argument [Cayrol et al., 2010]), have been studied, characterizations for structural constraints are missing. Writing good axioms for enforcement, we find, goes hand in hand with understanding the semantic effects of changing an AF's structure, and the challenge for axiomatization is to take these effects into account while preserving the intuitions. ## 5 RelatedWork Theorem 3 makes it clear that propositional enforcement is closely related to revision, deserving to be treated as a member of the wider family of belief change operators. The idea that enforcement accommodates the two sources recalls the operation of non-prioritized revision [Hansson, 1999], though our axiomatization sets it apart from these proposals. Our choice of representing the operators using rankings on sets of interpretations is reminiscent of other similar approaches [Grove, 1988; G¨ardenfors and Makinson, 1988; Lindstr¨om and Rabinowicz, 1989; Rott, 1992; Meyer et al., 2000] and bears close similarity to the monoselective approach [Hansson, 2015]. The axioms for propositional enforcement are similar to axioms proposed for revising desires [Dubois et al., 2017], though used to different effect. Adapting propositional enforcement to an AF setting recalls work on revision in fragments of propositional logic, e.g., Horn logic [Delgrande and Peppas, 2015]; in our case, the fragment is characterized in terms of Σadm. Our approach is most similar to [Creignou et al., 2014] through the usage of a closure function that takes us into the fragment we are interested in, while the most striking contrast is our finding that a refined operator satisfies a set of intuitive axioms. In [de Saint-Cyr et al., 2016], enforcement is modeled as change on FO formulas, whose semantics are AFs. In [Doutre et al., 2014], enforcing arguments is encoded in a logic for dynamics. Axioms in [de Saint-Cyr et al., 2016] relate AFs encoded in the formulas, while Doutre et al. [2014] show that axioms can be defined via the logic. Booth et al. [2013] consider an agent that has beliefs and an AF. If inconsistent together, they study AF expansions to restore consistency. In [Moguillansky and Simari, 2016; Moguillansky et al., 2013], acceptance revision operators are defined that incorporate a new logic (rule)-based argument, and they give axioms ensuring the argument's acceptance. Further, studies on enforcement in AFs concern characterizations [Baumann and Brewka, 2010; Baumann, 2012b; Coste-Marquis et al., 2015] and computational results [Coste-Marquis et al., 2015; Wallner et al., 2017]. In contrast, we axiomatize the semantic change induced by our novel enforcement operator. ## 6 Conclusions In this paper we have axiomatized enforcement in the spirit of belief change operators, and showed its duality to revision. We have made the case that the connection to revision is best seen through the lens of a new type of representation result, using rankings on sets of interpretations. Moreover, we have modified the axioms to fit AFs, showing that operators satisfying the modified axioms can be obtained in a seamless way if no structural restrictions are present. For future work, we think that our results should be extended by considering further semantics and characterizations of structural changes. ## References 1. [Alchourrón et al., 1985] C. E. Alchourrón, P. Gärdenfors, and D. Makinson. On the logic of theory change: Partial meet contraction and revision functions. J. Symb. Log., 50(2):510-530, 1985. 2. [Baumann and Brewka, 2010] R. Baumann and G. Brewka. Expanding argumentation frameworks: Enforcing and monotonicity results. In Proc. COMMA, pages 75-86, 2010. 3. [Baumann, 2012a] R. Baumann. Normal and strong expan- sion equivalence for argumentation frameworks. Artif. In- tell., 193:18-44, 2012. 4. [Baumann, 2012b] R. Baumann. What does it take to enforce an argument? Minimal change in abstract argumentation. In Proc. ECAI, pages 127-132, 2012. 5. [Bench-Capon and Dunne, 2007] T. J. M. Bench-Capon and P. E. Dunne. Argumentation in artificial intelligence. Artif. Intell., 171(10-15):619-641, 2007. 6. [Booth et al., 2013] R. Booth, S. Kaci, T. Rienstra, and L. W. N. van der Torre. A logical theory about dynamics in abstract argumentation. In Proc. SUM, pages 148-161, 2013. 7. [Cayrol et al., 2010] C. Cayrol, F. Dupin de Saint-Cyr, and M.-C. Lagasquie-Schiex. Change in abstract argumenta- tion frameworks: Adding an argument. J. Artif. Intell. Res., 38:49-84, 2010. 8. [Coste-Marquis et al., 2015] S.Coste-Marquis, S.Konieczny, J.-G. Mailly, and P. Marquis. Extension enforcement in abstract argumentation as an optimization problem. In Proc. IJCAI, pages 2876-2882, 2015. 9. [Creignou et al., 2014] N. Creignou, O. Papini, R. Pichler, and S. Woltran. Belief revision within fragments of propo- sitional logic. J. Comput. Syst. Sci., 80(2):427-449, 2014. 10. [Dalal, 1988] M.Dalal. Investigations into a theory of knowl- edge base revision. In Proc. AAAI, pages 475-479, 1988. 11. [de Saint-Cyr et al., 2016] F. Dupin de Saint-Cyr, P. Bis- quert, C. Cayrol, and M.-C. Lagasquie-Schiex. Argumen- tation update in YALLA (Yet Another Logic Language for Argumentation). Int. J. Approx. Reasoning, 75:57-92, 2016. 12. [Delgrande and Peppas, 2015] J. P. Delgrande and P. Peppas. Belief revision in Horn theories. Artif. Intell., 218:1-22, 2015. 13. [Doutre et al., 2014] S. Doutre, A. Herzig, and L. Perrussel. A dynamic logic framework for abstract argumentation. In Proc. KR, pages 62-71, 2014. 14. [Dubois et al., 2017] D. Dubois, E. Lorini, and H. Prade. The strength of desires: A logical approach. Minds and Machines, 27(1):199-231, 2017. 15. [Dung, 1995] P. M. Dung. On the acceptability of argu- ments and its fundamental role in nonmonotonic reason- ing, logic programming and n-person games. Artif. Intell., 77(2):321-358, 1995. 16. [Dunne et al., 2015] P. E. Dunne, W. Dvořák, T. Linsbichler, and S. Woltran. Characteristics of multiple viewpoints in abstract argumentation. Artif. Intell., 228:153-178, 2015. 17. [Falappa et al., 2011] M. A. Falappa, A. J. García, G. Kern- Isberner, and G. R. Simari. On the evolving relation be- tween belief revision and argumentation. Knowledge Eng. Review, 26(1):35-43, 2011. 18. [Fermé et al., 2013] E. L. Fermé, D. M. Gabbay, and G. R. Simari, editors. Trends in Belief Revision and Argumenta- tion Dynamics. 2013. 19. [Gärdenfors and Makinson, 1988] P. Gärdenfors and D. Makinson. Revisions of Knowledge Systems Using Epis- temic Entrenchment. In Proc. TARK, pages 83-95, 1988. 20. [Gärdenfors, 1988] P. Gärdenfors. Knowledge in Flux: Mod- elling the Dynamics of Epistemic States. 1988. 21. [Grove, 1988] A. Grove. Two modellings for theory change. J. Philosophical Logic, 17(2):157-170, 1988. 22. [Hansson, 1999] S. O. Hansson. A survey of non-prioritized belief revision. Erkenntnis, 50(2):413-427, 1999. 23. [Hansson, 2015] S. O. Hansson. A monoselective presenta- tion of AGM revision. Studia Logica, 103(5):1019-1033, 2015. 24. [Katsuno and Mendelzon, 1992] H. Katsuno and A. O. Mendelzon. Propositional Knowledge Base Revision and Minimal Change. Artif. Intell., 52(3):263-294, 1992. 25. [Lindström and Rabinowicz, 1989] S. Lindström and W. Ra- binowicz. Epistemic entrenchment with incomparabili- ties and relational belief revision. In The Logic of Theory Change, pages 93-126, 1989. 26. [Meyer et al., 2000] T. A. Meyer, W. A. Labuschagne, and J. Heidema. Refined Epistemic Entrenchment. Journal of Logic, Language and Information, 9(2):237-259, 2000. 27. [Moguillansky and Simari, 2016] M. Moguillansky and G. R. Simari. A specialized set theoretic semantics for acceptability dynamics of arguments. In Proc. COMMA, pages 391-402, 2016. 28. [Moguillansky et al., 2013] M. O. Moguillansky, N. D. Rot- stein, M. A. Falappa, A. J. García, and G. R. Simari. Dy- namics of knowledge in DeLP through argument theory change. TPLP, 13(6):893-957, 2013. 29. [Niskanen et al., 2016] A. Niskanen, J. P. Wallner, and M. Järvisalo. Synthesizing argumentation frameworks from examples. In Proc. ECAI, pages 551-559, 2016. 30. [Paglieri and Castelfranchi, 2004] F. Paglieri and C. Castel- franchi. Revising beliefs through arguments: Bridging the gap between argumentation and belief revision in MAS. In Proc. ArgMAS, pages 78-94, 2004. 31. [Rott, 1992] H. Rott. Preferential belief change using gen- eralized epistemic entrenchment. Journal of Logic, Lan- guage and Information, 1(1):45-78, 1992. 32. [Wallner et al., 2017] J. P. Wallner, A. Niskanen, and M. Järvisalo. Complexity results and algorithms for ex- tension enforcement in abstract argumentation. J. Artif. Intell. Res., 60:1-40, 2017.