# on_structured_argumentation_with_conditional_preferences__89fe865c.pdf The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19) On Structured Argumentation with Conditional Preferences Phan Minh Dung Department of Computer Science Asian Institute of Technology Thailand Phan Minh Thang BUUIC College of Burapha University Thailand Tran Cao Son Department of Computer Science New Mexico State University Las Cruces, NM, USA We study defeasible knowledge bases with conditional preferences (DKB). A DKB consists of a set of undisputed facts and a rule-based system that contains different types of rules: strict, defeasible, and preference. A major challenge in defining the semantics of DKB lies in determining how conditional preferences interact with the attack relations represented by rebuts and undercuts, between arguments. We introduce the notions of preference attack relations as sets of attacks between preference arguments and the rebuts or undercuts among arguments as well as of preference attack relation assignments which map knowledge bases to preference attack relations. We present five rational properties (referred to as regular properties), the inconsistency-resolving, effective rebuts, context-independence, attack monotonicity and link-orientation properties generalizing the properties of the same names for the case of unconditional preferences. Preference attack relation assignment are defined as regular if they satisfy all regular properties. We show that the set of regular assignments forms a complete lower semilattice whose least element is referred to as the canonical preference attack relation assignment. Canonical attack relation assignment represents the semantics of preferences in defeasible knowledge bases as intuitively, it could be viewed as being uniquely identified by the regular properties together with the principle of minimal removal of undesired attacks. We also present the normal preference attack relation assignment as an approximation of the canonical attack relation assignment. Keywords: Conditional preferences, regular properties, minimal removal principle, preference attack relation assignments, canonical and normal preference attack relation assignments. Introduction There are extensive research on rule-based systems with prioritized rules (see, e.g., Modgil and Prakken (2014); Amgoud and Cayrol (2002); Brewka (1989); Delgrande, Schaub, and Tompits (2003); Schaub and Wang (2001); Brewka and Eiter (1999)). Prakken and Sartor (1997) is arguably the first attempt to study the application of priorities of defeasible rules to define a preference order between ar- The lead and corresponding author Copyright c 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. guments and then using this preference order to remove undesired attacks. Amgoud and Cayrol (2002) has studied different ways to define preference order between arguments. Prakken (2010) and Modgil and Prakken (2013; 2014) have proposed ASPIC+, a rich framework for structured argumentation with prioritized rules with several distinct systems of preference orders between arguments. The rich diversity of proposed attack relations poses a serious challenge for any potential user of structured argumentation as such a user would have to decide which attack relation should be selected and implemented for her/his domain. To address this problem, general principles for the characterization and evaluation of alternative attack relations for rulebased systems are needed. Caminada and Amgoud (2007) have introduced the postulates of consistency and closure for argument-based systems. A subargument closure postulate stating that any extension should contain all subarguments of its arguments has been studied by Martinez, Garcia, and Simari (2006), Amgoud (2014), Modgil and Prakken (2013). The three proposed postulates give important insights into the characteristics of attack relations in structured argumentation. But they are not sufficient to guarantee intuitive semantics, as they do not take into account the preferences among defeasible rules. Dung (2016) has proposed a set of simple and intuitive properties, referred to as regular properties, to study the attack relations. Dung and Thang (2018) have showed that these properties coupled with the minimal removal principle stating that the removal of attacks should be kept to a minimum, uniquely identify the canonical attack relations that could be viewed as representing the intended attack relations for structured argumentation with prioritized rules. Until now, axiomatic analysis of attack relations has been carried out mostly for systems with unconditional preferences. In the next example, an extended version of the Sherlock Holmes example from Dung (2016); Dung and Thang (2018), we can see that conditional preferences could be a natural part of many defeasible knowledge bases. Example 1 (Adapted from Dung (2016)). Sherlock Holmes is investigating a case involving three persons P1, P2 and S together with the dead body of a big man. Furthermore S is a small child who cannot kill a big man and P1 is a beneficiary from the dead of the big man. The case could be represented by the following knowledge 1. The knowledge that one of the persons is the murderer is represented by three strict rules: r1 : Inno(P1), Inno(S) Inno(P2)1 r2 : Inno(P2), Inno(S) Inno(P1) r3 : Inno(P1), Inno(P2) Inno(S) 2. The legal principle that people are considered innocent until proven otherwise could be represented by three defeasible rules di : Inno(Pi) for i = 1, 2 together with d : Inno(S) 3. A rule-of-thumb for the investigation is to find out whether the possible suspects have any motives and to focus the investigation on the one with strong motive to commit the crime. Such rule-of-thumb can be represented by two conditional preferences: π1:Have Motive(P1), Have Motive(P2) d1 d2. π2: Have Motive(P1), Have Motive(P2) d2 d1. The rules state that if Pi has a motive and Pj (i = j) does not have a motive then the default dj is more preferred than di. 4. A good reason for having a motive to kill is to be a beneficiary from the dead of the deceased. r4 : Beneficiary(P1) Have Motive(P1) r5 : Beneficiary(P2) Have Motive(P2) 5. Peoples are normally assumed not to have motives to kill. d3: Have Motive(P1) d4: Have Motive(P2). 6. The facts that S is a small child and P1 is a beneficiary from the dead of the big man are represented by atoms Inno(S), Beneficiary(P1). The considered knowledge base is represented by Ksh=(RSsh, RDsh, RPsh, BEsh) with RSsh={r1, r2, r3, r4, r5} containing of the strict rules, RDsh = {d1, d2, d, d3, d4} consisting of the defeasible rules and RPsh = {π1, π2} consisting of the preference rules while BEsh = {Inno(S), Beneficiary(P1)} represents the set of facts. Relevant arguments are given in figures 1. Among these, X1 is a preference argument (formal definition a bit later) whose conclusion is d1 d2. It is easy to see that X1 is defeasible since d4 is defeasible. In this paper, we develop a framework for dealing with conditional preferences in structured argumentation. We define defeasible knowledge bases with conditional preferences (DKB) over a rule-based system. The semantics of a DKB is defined by a preference-based argumentation framework whose set of arguments consists of the arguments of the DKB and its direct undercuts and rebuts and whose set of attacks consists of the set of attacks created from the rebuts and undercuts of the DKB and a preference attack relation a set of attacks between preference arguments and the rebuts or undercuts among arguments. We prove that this semantics is a conservative generalization of the semantics of basic knowledge bases when restricted to knowledge bases without preferences. 1 Inno stands for Innocent . A1: Inno(P1) C1: Inno(P2) A2: Inno(P2) C2: Inno(P1) A1: Inno(P1) As: Inno(S) A2: Inno(P2) A1: Inno(P1) N1: Inno(P2) r1 As: Inno(S) A2: Inno(P2) N2: Inno(P1) r2 As: Inno(S) A2: Inno(P2) Ns: Inno(S) r3 A1: Inno(P1) B2: Have_Motive(P2) X1: d1 < d2 M1: Have_Motive(P1) Beneficiary(P1) B1: Have_Motive(P1) B2: Have_Motive(P2) M1: Have_Motive(P1) Beneficiary(P1) Figure 1: Sherlock Holmes Arguments To analyze attack relations, we present the notion of a preference attack relation assignment which maps knowledge bases to preference attack relations and discuss five regular properties, the context-independence, effective rebuts, inconsistency-resolving, attack monotonicity, and linkorientation properties of preference attack relations generalizing properties of the same names in the unconditional cases in Dung (2016) and Dung and Thang (2018). We say an assignment is regular if it satisfies all regular properties and show that the set of regular assignments forms a complete lower semilattice whose least element is referred to as the canonical preference attack relation assignment. Canonical attack relation assignment could be viewed as representing the semantics of preferences in defeasible knowledge bases as intuitively, it is uniquely identified by the regular properties together with the principle of minimal removal of undesired attacks. We also define a notion of a normal preference attack relation assignment that satisfies all regular properties and discuss sufficient conditions under which canonical and normal preference attack relation assignments coincide. Preliminary: Abstract Argumentation An abstract argumentation framework Dung (1995) is a pair AF=(AR, At) where AR is a set of arguments and att AR AR. (A, B) At means that A attacks B. A set of arguments S attacks (or is attacked by) an argument A (or a set of arguments R) if some argument in S attacks (or is attacked by) A (or some argument in R); S is conflict- free if it does not attack itself. A set of arguments S defends an argument A if S attacks every argument that attacks A. S is admissible if S is conflict-free and defends each argument in it. A preferred extension is a maximal admissible set of arguments. A complete extension is an admissible set of arguments containing each argument it defends. A stable extension is a conflict-free set of arguments that attacks every argument not belonging to it. We introduce the concept of semilattice. A partial order2 on a set S is a complete lower-semilattice (Davey and Priestley (2002)) iff each non-empty subset of S has a infimum w.r.t. . It follows immediately that each non-empty complete lower semilattice S has an unique least element. Defeasible KBs with Conditional Preferences We assume a non-empty set L of ground atoms. We distinguish between domain atoms representing propositions about the concerned domains; non-applicability atoms (or undercut atoms) of the form abd representing the non-applicability of a defeasible rule d even if its premises hold; and preference atoms (or p-atom for short) of the form d d (also d d) where d, d are distinct defeasible rules, representing the preference of d over d. A domain atom a (resp. its negation a) is called a positive (resp. negative) domain literal. a and a are said to be the complementary of each other. is a strict partial order. We write (d d ) for d d and say that d d and d d are complementary of each other. A set of literals is said to be contradictory iff it contains an atom and its complement. We distinguish between strict and defeasible rules as often done in the literature (e.g., Modgil and Prakken (2013, 2014); Garcia and Simari (2004)). Definition 1. A defeasible (resp. strict) domain rule r is of the form b1, . . . , bn h (resp. b1, . . . , bn h) where b1, . . . , bn are domain literals, and h is a domain literal, or a non-applicability atom abd (and r is also often called an undercut rule). A preference rule (or p-rule for short) r is a strict rule of the form b1, . . . , bn d0 d1 where b1, . . . , bn are domain literals and d0, d1 are distinct defeasible domain rules. The set {b1, . . . , bn} (resp. the literal h or the preference atom d0 d1) is referred to as the body (resp. head) of r and denoted by bd(r) (resp. hd(r)). When the body of a preference rule r is empty, we say that r represents an unconditional preference. Definition 2. A rule-based system with conditional preferences (or simply a rule-based system) is a quadruple R = (RS, RD, RP, RT) where RS is a set of strict domain rules, and RD is a set of defeasible domain rules, and RP is a set of p-rules, and 2A reflexive, transitive and antisymmetric relation RT is the set of all transitive preference rules that are ground instances of the transitive rule x y, y z x z where x, y, z range over RD and x, y, z are pairwise distinct. A defeasible knowledge base with conditional preferences (DKB) (or a knowledge base) over R is a pair K = (R, BE) consisting of a rule-based system R, and a set of ground domain literals BE, the base of evidence of K, representing unchallenged facts, observations. A DKB K is basic if it contains no precedence rules. A DKB K is often written directly as a tuple (RS, RD, RP, RT, BE). For simplicity, we sometimes omit the set RT in the description of a rule-based system. Arguments of a knowledge base are defined as follows. Definition 3. Let K = (RS, RD, RP, RT, BE) be a KB. An argument w.r.t. K is a proof tree defined as follows: 1. For each α BE, [α] is an argument with conclusion α. 2. Let r be a rule of the forms α1, . . . , αn ( ) α, n 0 from RS RD RP RT and A1, . . . , An be arguments with conclusions αi, 1 i n, respectively. Then A = [A1, . . . , An, r] is an argument. α and r are called the conclusion and the last rule of A and are denoted by cnl(A) and last(A), respectively. If α is a domain (undercut) atom then A is called a domain (undercut) argument. 3. Let A1, . . . , An be arguments with p-atoms αi as conclusions, 1 i n, respectively. Then A = [A1, . . . , An] is a preference argument with the conclusion cnl(A) = {α1, . . . , αn}. 4. Each argument w.r.t. K is obtained by applying the above steps finitely many times. In the following, a preference argument [A1, . . . , An] is identified with any argument obtained from reordering of its components or removal of duplicates among its arguments. The set of all arguments (resp. preference arguments) w.r.t. K is denoted by ARK (resp. ARp,K). For S ARK, cnl(S)={l | A S, l appears in cnl(A)}. An argument B is a subargument of an argument A iff (i) B = A; or (ii) A = [A1, . . . , An, r] or A = [A1, . . . , An] and B is a subargument of some Ai. B is a proper subargument of A if B is a subargument of A and B = A. A rule r is said to appear in an argument A if A = [A1, . . . , An, r] or r appears in some proper subargument A. The set of defeasible rules appearing in an argument A is denoted by dr(A). A is strict if no defeasible rule appears in it. It is defeasible otherwise. A is called basic defeasible iff last(A) is defeasible. The set of last defeasible rules in A, denoted by ldr(A), is {last(A)} if A is basic defeasible, otherwise it is equal ldr(A1) . . . ldr(An) where A = [A1, . . . , An, r] or A = [A1, . . . , An]. A undercuts B (at B ) if B is basic defeasible subargument of B and cnl(A) = ablast(B ). A rebuts B (at B ) if B is a basic defeasible subargument of B, both A, B are domain arguments and the conclusions of A and B are contradictory. A directly rebuts or undercuts B iff A rebuts or undercuts B (at B) respectively. We often simply say A re- buts or undercuts B if it is not relevant to specify the exact place at which A rebuts or undercuts B. For a knowledge base K, let rbut K = {(A, B) | A rebuts B} and ucut K = {(A, B) | A undercuts B}. Furthermore, dbut K = { (A, B) | A directly rebuts B} and dcut K = { (A, B) | A directly undercuts B}. Example 2. Let us revisit Ex. 1.3 Most relevant arguments w.r.t. Ksh are given in Figure 1: (i) all arguments except M1 are defeasible; (ii) A1, A2, As, B1, and B2 are basic defeasible; and (iii) X1 is a preference argument. As we interpret the strict rules and the facts in the base of evidences of a knowledge base as representing the unchallenged knowledge and observation of the concerned domain, it is therefore natural to expect that they are consistent as defined in the following definition.4 Definition 4. Let R be a rule-based system. 1. The closure of a set of literals X over L w.r.t. a rulebased system R, denoted by CNR(X), is the union of X and the set of conclusions of all strict arguments w.r.t. the knowledge base (R, Xdom) where Xdom is the set of domain literals in X. X is said to be closed w.r.t. R iff X=CNR(X). We write X R l iff l CNR(X). X is said to be inconsistent w.r.t. R iff its closure CNR(X) is contradictory. X is consistent w.r.t. R iff it is not inconsistent. 2. A knowledge base K is said to be consistent iff its base of evidence BE is consistent w.r.t. R. 3. R is said to be consistent iff the knowledge base (R, ) is consistent. 4. CR denotes the set of all consistent KBs over R. Assumption: From now on, whenever we refer to rule-based systems, we always mean consistent ones. Preference-based Argumentation Framework of Defeasible KB with Conditional Preferences The previous section defines different types of arguments and different types of attacks (like rebuts or undercuts) among them. However, the discussion thus far does not yet specify the semantics of a knowledge base. This is because it does not yet take into consideration preference arguments. In this section, we will address this problem. Example 3. Consider Ksh from Ex. 2. Let us consider the arguments C1, A2, and X1 (Fig. 2). By definition, C1 directly rebuts A2 (i.e. (C1, A2) dbut Ksh). The presence of X1 indicates that d2 is preferred to d1. This means that the direct rebut (C1, A2) could be removed from consideration whenever X1 is acceptable. In other words, we can say that X1 attacks the rebuttal of A2 by C1 and represent this attack in the form (X1, (C1, A2)). 3Note that transitive rules are not mentioned explicitly in the representation of the knowledge base. 4Note that if the evidences together with the strict rules are not consistent then they in fact represent defeasible knowledge. As such they should be represented by the defeasible rules, not by strict rules and facts. B2: Have_Motive(P2) X1: d1 < d2 M1: Have_Motive(P1) Beneficiary(P1) 훑1 A1: Inno(P1) C1: Inno(P2) A2: Inno(P2) Figure 2: C1 and A2 and the preference argument X1 The above example shows that preference arguments introduce a new type of attacks, i.e., attacks against direct rebuttals among arguments. We will refer to an attack of this new type as an attack by preference arguments. Formally, a set of attacks by preference arguments could be represented by a binary relation in ARp,K dbut K. Clearly, the choice of the set defining the attacks by preference arguments will determine which arguments will be accepted. The next example illustrates this problem. Example 4. Consider again Ksh from Ex. 1. It is not difficult to see: dbut Ksh = {(N1, A2), (N2, A1), (C1, A2), (C2, A1), (M1, B1)}. Furthermore, dcut Ksh = and the only preference argument w.r.t. Ksh is X1, i.e., ARp,Ksh = {X1}. We consider two situations with respect to the choice of the set of attacks by preference arguments: Assume that we select {(X1, (N1, A2)), (X1, (C1, A2))} as the set of attacks by preference arguments. Then, because X1 is not attacked by any argument w.r.t. Ksh, we can conclude that X1 is always acceptable, and hence, we should remove the attacks (N1, A2) and (C1, A2) from consideration when determining the acceptability of arguments w.r.t. Ksh. Hence there is no attack against A2 which shows that P2 is innocent and P1 is not. Assume that we select the empty set as the set of attacks by preference arguments. Then argument X1 plays no role in the attack relations between A1, A2, N1, N2, C1, C2. There are then two acceptable scenarios: One in which P1 is innocent and the other in which P2 is innocent. Ex. 4 shows that the key question in dealing with preference arguments is what is the intuitively expected set of attacks by preference arguments? More formally, given a knowledge base K, which subset of ARp,K dbut K should be selected as the set of attacks by preference arguments. In the rest of this paper, we will propose a solution for this question. Observe that we only consider attacks by preference arguments against rebuttals but not against undercuts. This is because, in our view, undercuts are preference independent, which is also in agreement with the view expressed by many others (e.g., by Modgil and Prakken (2013)). At this point, it is instructive to recall that we are dealing with conditional preferences. Consequently, an attack against a rebuttal by a preference argument does not yet mean that the rebuttal should be eliminated from consideration. Let us consider again the argument X1 in Ex. 4. As we have argued, X1 attacks the rebuttal of A2 by C1. But this attack is effective only if X1 itself is accepted. In other words, whether the rebut (C1, A2) is accepted or not depends on the acceptance of X1. This insight suggests that rebuts also need to be defended like arguments. We formal- ize this insight by viewing direct rebuts like (C1, A2) as arguments. A question, that arises immediately, is that how are the rebut-arguments attacked? Clearly, a rebut argument like (C1, A2) could be attacked in two ways: Attacking the rebutting connection like the way X1 attacks (C1, A2) or attacking the source C1. As direct rebuttals are considered as arguments, it is convenient to also consider direct undercuts as arguments. But in contrast to rebut arguments, there is only one way to attack undercut arguments, namely attacking their source. We can now introduce a novel notion of preference argumentation framework capturing the key conceptual ideas discussed above. Definition 5. (Preference-Based AF) Given a knowledge base K, a preference-based argumentation framework (PAF) of K is an abstract argumentation framework FK = (ARPK, att F) where ARPK = ARK dbut K dcut K, and att F = datt K patt where (a) datt K (dbut K dcut K) ARPK such that ((A, B), X) datt K iff X ARK and B is a subargument of X, or X=(C, D) (dbut K dcut K) and B is a subargument of C. (b) patt ARp,K dbut K where patt is often referred to as the preference attack relation (or just p-attack relation) of F. For ease of reference, we often refer to a PAF of K by the triple (ARPK, datt K, patt). As FK is an abstract argumentation framework, its semantics is fully defined. As such, we can define the semantics of K by its PAFs. Intuitively, FK contains arguments w.r.t. K together with the direct attacks and direct rebuts w.r.t K and the attacks in FK are of two types: attacks agains arguments (type (a)) and attacks against attacks (type (b)). In this sense, PAF is similar to extended argumentation frameworks (see, e.g., Gabbay (2009); Baroni et al. (2011); Modgil (2009); Hanh et al. (2011); Young et al. (2018)) in which attacks against attacks are allowed or metalevel arguments are considered. The key difference between PAFs and extended argumentation frameworks is that since PAF are abstract argumentation frameworks, we do not need to define new semantics for PAFs. The next theorem shows that the concept of PAF is a conservative generalization of the semantics of basic knowledge bases, i.e., when restricted to basic knowledge bases, our new concept of PAF delivers the same semantics captured in the traditional view of undercuts and rebuts as attacks. Theorem 1. Let R be a basic rule-based system and K CR. Let F0 be the argumentation framework (ARK, rbut K ucut K) and F = (ARPK, datt K) be an PAF of K.5 Then, (i) if E is a complete extension of F then E ARK is a complete extension of F0; and (ii) if G is a complete extension of F0 then G { (X, Y ) | X 5Since there is no preference argument, the preference attack relation component is empty. G and (X, Y ) dbut K dcut K } is a complete extension of F. Definition 5 precisely defines datt K but leaves the set patt unspecified. As we have alluded to above, the choice of patt will affect the semantics of K as it is specified by FK = (ARPK, datt K, patt). The next example discusses this issue in more detail. Example 5. Reconsider Ex. 4, we can easily check: (i) F1=(ARPKsh, datt Ksh, patt1), where patt1={(X1, (N1, A2)), (X1, (C1, A2))}, has a unique stable (complete, preferred) extension that delivers the conclusion that P2 is innocent in accordance with the 1st choice in Ex. 4; (ii) F2 = (ARPKsh, datt Ksh, patt2) where patt2 = . F2 has two stable extensions that deliver the two scenarios in the 2nd choice in Ex. 4. F2 in Example 5 shows that not every p-attack relation yields the expected and intuitive semantics for a DKB. The extreme case of patt2 = is equivalent to not considering any preference in the DKB at all. Nevertheless, all PAFs as defined in Definition 5satisfies both the closure and subargument closure postulates introduced in Caminada and Amgoud (2007); Modgil and Prakken (2013); Martinez, Garcia, and Simari (2006); Amgoud (2014). We adapt these postulates to our notation below. Note that for any set S ARPK, we define cnl(S) = cnl(S ARK). patt satisfies the consistency postulate (resp. closure postulate) iff for each complete extension E of FK, cnl(E) is consistent (resp. closed); patt satisfies the subargument closure postulate iff for each complete extension E of FK, E contains all subarguments of its arguments. Before continuing, we introduce some additional notions. An argument A is said to be generated by a set of arguments S ARK if and only if all basic defeasible subarguments of A are subarguments of arguments in S. A is said to be generated by a set of arguments from ARPK if it is generated by the arguments from ARK in this set. The next theorem shows the closure and subargument closure postulates are satisfied with any patt. Theorem 2. Let R be a rule based-system, K CR, and F= (ARPK, datt K, patt) a PAF of K. If E is a complete extension of F then E contains all arguments generated by E. Theorems 1-2 show that PAFs present a reasonable generalization of the semantics of basic DKBs and can satisfy two of the basic postulates proposed for characterizing attack relations in structured argumentation. Definition 5 indicates that there are distinct preference attack relations for the same knowledge base. Example 5 shows that it is important to correctly identify this relation. The key question is then given K, what should be selected as the intuitive p-attack relation? We next addresses this question. Regular Properties Attack relations have been studied in Dung (2016) and Dung and Thang (2018) for dealing with unconditional preferences. They introduced the regular properties for attack relations and proved that under reasonable conditions on the KBs, these properties guarantee the intuitively expected behavior of the atack relations including the satisfaction of the basic postulates introduced in Caminada and Amgoud (2007); Amgoud (2014); Modgil and Prakken (2013); Martinez, Garcia, and Simari (2006). To save space, from now until the end of this section, we assume an arbitrary but fixed consistent rule-based system R = (RS, RD, RP, RT), K CR, and F = (ARPK, datt K, patt) a PAF of K. Even though the consistency postulate is very intuitive, it does not give any insight into the structure of the attack relations. We next adapt the inconsistency-resolving property from Dung (2016) and Dung and Thang (2018) to conditional preferences to shed light on the structure of attack relations underlining the consistency postulate. Definition 6. patt satisfies the inconsistency-resolving property (IR) for K iff for each finite set of arguments S ARK, if cnl(S) is inconsistent then there is some (A, B) dbut K dcut K s.t. both A, B are generated by S and there is no P ARp,K s.t. (P, (A, B)) patt. Intuitively, the IR property states that the inconsistency between arguments is rooted in the conflict between them w.r.t. rebutting or undercutting relations. Theorem 3. If patt satisfies (IR) and E is a complete extension of F then cnl(E) is consistent.6 The next property focuses on a minimal interpretation of preferences. Specifically, in situations when d0 d1 holds and both d0 and d1 are applicable but accepting both d0, d1 is not possible, then d1 should be preferred. Definition 7. patt satisfies the effective rebut property (ER) iff for each P ARp,K and (A0, A1) dbut K such that each Ai, i = 0, 1 contains exactly one defeasible rule di, it holds that (P, (A0, A1)) patt iff (d0 d1) cnl(P). Preference attacks propagate from stronger to weaker rebuts. For illustration, let consider the rebuts (N1, A2) and (C1, A2) in Ex. 1. As C1 is based on a fact Inno(S) while N1 is based on a defeasible conclusion about Inno(S), it is clear that C1 is stronger an argument then N1. Hence the rebuttal of A2 by C1 is stronger than the rebuttal of A2 by N1. We say that N1 is a weakening of C1. Let A, B ARK and AS be a set of domain arguments. B is said to be a weakening of A by AS iff A = [α] for α BE, and (B = [α] or B AS with cnl(B) = α), or A = [A1, . . . , An, r] and B = [B1, . . . , Bn, r], n 0 where each Bi is a weakening of Ai by AS, or A = [A1, . . . , An] and B = [B1, . . . , Bn], n 1 where each Bi is a weakening of Ai by AS. By A AS we denote the set of all weakenings of A by AS. For simplicity, we often say that A is a strengthening of B (by AS) if B is a weakening of A (by AS). For illustration, consider the arguments in Example 1. For AS={As}, we have C1 AS = {C1, N1}. Suppose A is a weakening of A and A directly rebuts B. Hence A also directly rebuts B. Since A is a strengthening of 6Note that cnl(E) = cnl(E ARK). A , a rebut from A against B should be stronger than a rebut from A against B. Therefore, if a preference-argument P attacks (A, B), it should also attack (A , B). Similarly if A directly rebuts B then A also represents a stronger rebuttal against any weakening B of B than against B. Therefore, if a preference argument P attacks (A, B ), it should also attack (A, B). Definition 8. patt satisfies the property of attack monotonicity (AM) iff for all A, B, P ARK, and for each weakening A of A, for each weakening B of B, the following assertions hold: If (P, (A, B)) patt then (P, (A , B)) patt. If (P, (A, B )) patt then (P, (A, B)) patt. Let us look at Example 1 again for illustration. Suppose patt satisfies both (ER) and (AM) properties. (ER) implies that X1 attacks (C1, A2), i.e., (X1, (C1, A2)) patt. Since N1 is a weakening of C1, (AM) dictates that X1 also attacks (N1, A2) (i.e. (X1, (N1, A2)) patt). The next property extends the link-oriented property, which focuses on identifying the culprit links within arguments and directs the attacks against these culprits. Definition 9. patt satisfies the link-oriented property (LO) iff for all arguments A, B, B , P ARK such that (i) B B BS for some BS ARK, (ii) (P, (A, B)) patt, and (iii) A does not rebut any argument in BS, it holds that (P, (A, B ) ) patt. A key property for attack relations is that the attacks depend only on the structure of the arguments involved. This property holds obviously for attack relations datt K that are based on the rebut and undercut relations. We will introduce shortly the context-independence (CI) property that relates the p-attack relations among different DKBs of a rule-based system and states that the attacks depend only on the structure of the arguments involved. But we first need to define the notion of attack relation assignments. Definition 10. A preference-attack relation assignment w.r.t. a rule-based system R is a mapping Π assigning to each knowledge base K CR a preference-attack relation Π(K) ARp,K dbut K. Definition 11. (Context-Independence (CI)) A preferenceattack relation assignment Π for a rule-based system R is said to satisfy the property of context-independence (CI) iff for any two knowledge bases K, K CR and for any three arguments A, B, P from ARK ARK , it holds that (P, (A, B) ) Π(K) iff (P, (A, B) ) Π(K ). We can now present the concept of the regular preferenceattack relation assignments. For simplicity, we refer to the properties of contextindependence, effective rebuts, inconsistency-resolving, attack monotonicity and link-orientation as regular properties. Let π be one of the regular properties except the contextindependent one. For ease of reference, we say that a preference attack relation assignment Π satisfies π if for each knowledge base K CR, Π(K) satisfies π. Definition 12. (Regular Preference-Attack Relation Assignments) A preference-attack relation assignment Π for a Figure 3: patt and consistency postulate rule-based system R is said to be regular iff it satisfies all regular properties. The set of all regular preference-attack relation assignments for R is denoted by RPAAR. Semilattice Structure of Regular Assignments of Preference-Attack Relations Let R = (RS, RD, RP, RT) be a rule-based system. For Π, Π RPAAR, define Π Π iff K CR : Π(K) Π (K). It is obvious that (RPAAR, ) is a partial order. Definition 13. Let A be a non-empty set of assignments of preference-attack relations. Define A by: K CR : ( A)(K) = \ { Π(K) | Π A } The following simple lemma and theorem present a deep insight into the structure of regular attack assignments. Lemma 1. Let A be a non-empty set of assignments of preference-attack relations. 1. Suppose P is a regular property and every preferenceattack relation assignment Π A satisfies P. Then A also satisfies P. 2. If the preference-attack relations assignments in A are regular then A is also regular. Because of the second item in Lemma 1, we have that A is the infimum of A w.r.t. (RPAAR, ). It follows immediately Theorem 4. (RPAAR, ) is a complete lower semilattice. The following example adapted from example 8 in Dung and Thang (2018) illustrates that the set RPAAR of regular assignments of preference attack relations could be empty. Example 6. Consider the DKB K with empty base of evidence where all strict and defeasible rules of K appearing in Fig. 3 and K contains an unique unconditional preference rule π : d0 d1. We can check that ARK consists of A and B (Fig. 3), C = [d0], and a preference argument X = [π]. dbut K = {(A, B)}. By definition, datt K = {((A, B), B)}. It is not difficult to see that patt = {(X, (A, B))} is the unique preference attack relation satisfying the effective rebut property. Therefore the corresponding PAF has an unique stable extension E = {A, B, C, X}. However, cnl(E) is inconsistent. Canonical preference-attack relation assignment is defined next. Definition 14. Suppose the set RPAAR of all regular attack relation assignments for R is not empty. The canonical assignment of preference-attack relations of R denoted by CPR is defined by: CPR = RPAAR. In other words, we could say that the canonical attack relation assignment is uniquely characterized by the regular properties coupled with the minimal removal principle. It turns out that even though in general regular attack relation assignments do not exist, their existence is guaranteed under fairly general and sensible conditions. We will discuss these conditions in the next section. Normal Preference Attack Relation Assignment Definition 15. A preference attack relation patt w.r.t. K is said to be normal iff for any arguments A, B, X ARK, (X, (A, B)) patt if and only if there exists d ldr(A) such that (d last(B)) cnl(X). A preference-attack relation assignment Π w.r.t. a rulebased system R is normal iff for any knowledge base K CR, Π(K) is normal. We denote the normal assignment of preference attack relations by Πnr. It is easy to check that patt1 in Ex. 5 is indeed normal. Lemma 2. The normal preference-attack relation assignment Πnr satisfies in general all regular properties except the inconsistency-resolving one. Furthermore, the following holds. Lemma 3. If the canonical preference attack relation assignment CPR exists then CPR Πnr. In general, the canonical and normal assignments of preference attack relations are distinct (see Ex. 7 below adapted from Dung and Thang (2018)). Example 7. Let R = (RS, RD, RP, RT) such that RS RP consists of the strict and defeasible rules appearing in Fig. 4 (where a bar on an arrow indicates that the conclusion of the rule is negated) and RP contains an unique preference rule π : d2 d3. Let be an assignment of preference attack relations assigning to each K CR, the empty preference attack relation. We show that is also the canonical assignment of preference attack relations of R. It is easy to check that satisfies the properties of attack monotonicity, link orientation, and context independence. Since the set {a, b} is inconsistent, there is no knowledge base K CR such that {a, b} BEK. Therefore arguments [[a], d2] and [[b], d3] never coexist w.r.t. Figure 4: Rebut Redundance the same knowledge base. Hence the effective rebut property is always satisfied. We show that satisfies the inconsistency-resolving property. Let S ARK, K CR, be finite such that cnl(S) is inconsistent. Therefore there are two contradictory arguments X, Y generated by S. Since BEK is consistent, at least one of them (say X) is defeasible. We show that at least one of X, Y is basic defeasible. Suppose none of X, Y are basic defeasible. Therefore X is defeasible but not basic defeasible. Since r0, r1 are the only strict rules in R, X must be of one of the following two forms: X = B0 = [[d0], r0] or X = B1 = [[d1], r1]. Let X = B0 = [[d0], r0]. Hence cnl(Y ) = b. Because Y is not basic defeasible, and there is no strict rule in R whose conclusion is b, Y = [b]. Therefore d rank(d ). The rule-based system in Ex. 8 is obviously not preference-stratified. The rule based system in Ex. 1 is p- stratified where defeasible rules d1, d2 are given rank 1 and the rest is given rank 0. Furthermore, rule-based systems with unconditional preferences are p-stratified. The second property on R is on the strict rules of R adapted from Dung (2016) and Dung and Thang (2018). Definition 18. R is said to satisfy the self-contradiction property iff for each minimal inconsistent set of domain literals S L, for each l S, it holds: S RS l. The next theorem relates (IR) and the self-contradiction property. Theorem 5. If R is p-stratified and satisfies the selfcontradictory property then Πnr also satisfies (IR) and hence is regular. An interesting question arisen immediately is under which conditions the canonical and normal preference attack relation assignments coincide. Such a result has been given for the case of unconditional preferences in Dung and Thang (2018). As the regular properties for preference attack relation assignments generalize the properties with the same names for unconditional preferences, it is expected that similar result also holds w.r.t. the framework of preference attack relation assignments. We show below that it is indeed the case. Let R = (RS, RD, RP) be a consistent unconditional rule-based system. Since R is consistent, it is obvious that the transitive closure of RP is a strict partial order. For simplicity, we assume that RP coincides with its transitive closure and hence is a strict partial order. We say a domain literal λ directly depends on a domain literal β iff there is a rule r RS RD such that λ = hd(r) and β bd(r). λ depends on β iff λ = β or λ depends on α that directly depends on β. The set of all sentences in L on which λ depends is denoted by (λ). For a set S L, (S) is the union of (λ) for λ S. Theorem 6. Let R be an unconditional rule-based system satisfying the self-contradiction property. Furthermore for each defeasible rule d RD, if there exists d d in RP then the set (bd(d)) ( hd(d)) is consistent. Then the canonical attack relation assignment CPR and the normal attack relation assignment Πnr coincide. Discussion and Conclusion We study defeasible knowledge bases with conditional preferences between defaults (DKB). We introduce the notion of a preference-based argumentation frameworks (PAF), which views direct rebut and undercut attacks among arguments as arguments and contains a preference-attack relation between preference arguments and direct rebuts and undercuts. We show that PAF generalizes the semantics of basic knowledge bases to DKBs. We propose the notion of a preference attack relation assignment, which maps each knowledge base to a preference attach relation, and discuss five regular properties, of such an assignment: the context-independence, effective rebuts, inconsistency-resolving, attack monotonicity, and linkorientation properties. We prove that the set of all regular preference attack relation assignments forms a complete lower-semilattice under the relation. We also define the notion of a normal preference attack relation assignment that in general satisfies all but the inconsistency-resolving property and specify conditions under which normal preference attack relation assignments coincide with regular assignments. Prakken and Sartor (1997) has studied conditional preferences of defeasible rules. As pointed out in Caminada and Amgoud (2007), the proposed system does not satisfy the consistency postulate. Further, conditional preferences are not used to define attacks against attacks. Antoniou (2004) has studied the use of conditional preferences in the context of defeasible logics. Delgrande, Schaub, and Tompits (2003) viewed preferences as specifying application orders of rules. In Dung (2016), we show for unconditional preferences that this view is more conservative than our approach in the sense that extensions following DST concept are also extensions in our approach but not vice versa. It turns out that this result also holds for the general case of conditional preferences. Our approach to dealing with conditional preferences generalizes the approach in Dung and Thang (2018) where the regular properties of preference attack relation assignments generalize the properties with the same names for attack relation assignments for unconditional preferences. References Amgoud, L., and Cayrol, C. 2002. Infering from inconsistency in preference-based argumentation framework. Int J. Automated Reasoning 29(2):197 215. Amgoud, L. 2014. Postulates for logic-based argumentation systems. Int J. Approximate Reasoning 55(9):2028 2048. Antoniou, G. 2004. Defeasible logic with dynamic priorities. International Journal of Intelligent Systems 19. Baroni, P.; Cerutti, F.; Giacomin, M.; and Guida, G. 2011. AFRA: argumentation framework with recursive attacks. Int. J. Approx. Reasoning 52(1):19 37. Brewka, G., and Eiter, T. 1999. Preferred answer sets for extended logic programs. Artificial Intelligence 109:297 356. Brewka, G. 1989. Preferred subtheories: An extended logical framework for default reasoning. In Proc of IJCAI 89, 1043 1048. Morgan Kaufmann. Caminada, M., and Amgoud, L. 2007. On the evaluation of argumentation formalisms. Artificial Intelligence 171:286 310. Davey, B. A., and Priestley, H. A. 2002. Introduction to Lattices and Order. Cambridge University Press. Delgrande, J.; Schaub, T.; and Tompits, H. 2003. A framework for compiling preferences in logic programs. Theory and Practice of Logic Programming 129 187. Dung, P. M., and Thang, P. M. 2018. Fundamental properties of attack relations in structured argumentation with priorities. Artificial Intelligence 255:1 42. Dung, P. 1995. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell. 77(2):321 358. Dung, P. M. 2016. An axiomatic analysis of structured argumentation with priorities. Artificial Intelligence 231:107 150. Gabbay, D. M. 2009. Semantics for higher level attacks in extended argumentation frames part 1: Overview. Studia Logica 93(2-3):357 381. Garcia, A., and Simari, G. 2004. Defeasible logic programming: An argumentative approach. TPLP 4(1-2):95 138. Hanh, D.; Dung, P.; Hung, N.; and Thang, P. M. 2011. Inductive defence for skeptixcal semantics of extended argumentation. J of Logic and Computation 21(2):307 349. Martinez, D. C.; Garcia, A. J.; and Simari, G. R. 2006. On acceptability in abstract argumentation frameworks with an extended defeat relation. In P.E. Dunne, T. J. M. B.-C., ed., Proc. of Int. Conf. on Computational models of arguments. IOS Press. Modgil, S., and Prakken, H. 2013. A general account of argumentation with preferences. Artificial Intelligence 197:361 397. Modgil, S., and Prakken, H. 2014. The aspic+ framework for structured argumenttion: a tutorial. J. Arguments and Computation 5:31 62. Modgil, S. 2009. Reasoning about preferences in argumentation frameworks. Artif. Intell. 173(9-10):901 934. Prakken, H., and Sartor, G. 1997. Argument-based extended logic programming with defeasible priorities. Journal of Applied Non-Classical Logics (1997) 7(1):25 75. Prakken, H. 2010. An abstract framework for argumentation with structured arguments. J. Arguments and Computation 1. Schaub, T., and Wang, K. 2001. A comparative study of logic programs with preferences. In Proc of IJCAI, 2001. Morgan kaufmann. Young, A. P.; Kokciyan, N.; Sassoon, I. K.; Modgil, S.; and Parsons, S. 2018. Instantiating metalevel argumentation frameworks. In 7th International Conference on Computational Models of Argument, Warsaw.