Assumption-Based Approaches to Reasoning with Priorities ? Jesse Heyninck, Pere Pardo, and Christian Straßer {jesse.heyninck, pere.pardoventura, christian.strasser}@rub.de Institute of Philosophy II, Ruhr Universität Bochum Abstract. This paper maps out the relation between different approaches for handling preferences in argumentation with strict rules and defea- sible assumptions by offering translations between them. The systems we compare are: non-prioritized defeats, preference-based defeats, and preference-based defeats extended with reverse defeat. We prove that these translations preserve the consequences of the respective systems under different semantics. 1 Introduction The aim of this paper is to map out the relation between different approaches for handling preferences in assumption-based argumentation (in short, ABA) [2]. The orthodox approach in ABA, that we call direct, defines defeats (among sets of assumptions) as attacks from assumptions that are at least as preferred as the assumption under attack. The fact that ABA admits asymmetric contrariness relations, though, makes preference-handling more difficult: this asymmetry is preserved on the level of attacks and then defeats, possibly leading to inconsis- tencies. In order to re-establish consistency, the framework ABA+ was recently proposed in [5] to handle preferences in ABA. ABA+ adds reverse defeats as passive counterparts to direct defeats: if an assumption is attacked from less preferred assumptions a reverse attack is initiated. Therefore, it seems fruitful to investigate the exact relation between systems that are equipped with a re- verse defeat and systems that only make use of direct defeats. In this paper, we contribute to this line of research by studying two questions. First, we investi- gate under which conditions ABA equipped with direct but not reverse defeat satisfies the consistency postulate. Thereafter, we investigate the relationship between these two frameworks by providing translations. Outline of the paper: In Section 2 we review the different versions for ABA defined by: non-prioritized defeats —i.e. attacks (ABAf ), preference-based de- feats (ABAd ), and preference-based defeats extended with reverse defeat (ABAr ). In Section 3 we motivate the translations by showing first that ABAd is well- behaved and secondly that ABAd and ABAr give rise to incomparable outcomes. ? The research of the authors was supported by a Sofja Kovalevkaja award of the Alexander von Humboldt-Foundation, funded by the German Ministry for Education and Research. The authors thank two anonymous reviewers for helpful comments. Then in Section 4, we provide first a translation from ABAd to ABAf . In Section 5 we show ABAr and ABAd are conservative extensions of ABAf . This result also extends the translation from Section 4 into ABAr . In Section 6, we complete the cycle by providing a direct translation from ABAr to ABAd . The contributions of this paper can be summarized in the following diagram: Sec. 6 Sec. 4 ABAf ABAd ABAr Sec. 4+Sec. 5 Sec. 5 2 Assumption-Based Argumentation ABA, thoroughly described in [2], is a formal model on the use of plausible assumptions used “to extend a given theory” [2, p.70] unless and until there are good arguments for not using (some of) these assumptions. Inferences are implemented in ABA by means of rules formulated over a formal language. Furthermore, defeasible assumptions are introduced, together with a contrariness operator to express argumentative attacks. We adapt the definition from [5] for an ABA+ assumption-based framework as follows: Definition 1 (Assumption-based framework). An assumption-based frame- work is a tuple of the form ABF = (L, R, Ab, , V, ≤, υ), where: – L is a formal language (consisting of countably many sentences). – R is a set of inference rules of the form A1 , . . . , An → A or → A, where A, A1 . . . , An ∈ L. – Ab ⊆ L is a non-empty set of candidate assumptions. – : Ab → ℘(L) is a contrariness operator. – The members of V are called values and we require that V 6= ∅ and V∩L = ∅. – ≤ ⊆ V × V is a preorder over the values. – υ : Ab → V is a function assigning values to the assumptions1 . As usual, we define ≥ as the inverse of ≤, and define α < β iff α ≤ β and β 6≤ α. An ABF without priorities is simply defined as a tuple ABF = (L, R, Ab, ).2 Remark 1. In many publications (e.g. [2, 11, 6, 7]), attention is restricted to so- called flat ABFs, i.e. ABFs that contain no rules A1 , . . . , An → A such that A ∈ Ab. We do not make this assumption but will point to simplifications allowed by it. 1 In [6], a preference order ≤ ⊆ Ab × Ab is defined directly over the assumptions. It will, however, greatly increase readability to use values to express priorities in this paper. Clearly, these modes of expression are equivalent. 2 If needed, one can identify an ABF without priorities (L, R, Ab, ) with a trivial prioritized ABF = (L, R, Ab, , V, ≤, υ) given by υ(A) = υ(B) for all A, B ∈ Ab. In some presentations of ABA, deductions are obtained from a set of strict premises Γ ⊆ L, a set of plausible assumptions Ab ⊆ L and a set of rules R. Here we follow [5], by rewritting each strict premise A ∈ Γ as an empty-bodied rule → A (contained in the set of rules R). The previous definition generalizes the contrariness function : Ab → L in [5], from a single contrary A = B, to a set of contraries Bi ∈ A = {B0 , . . . , Bk }. (Although in our examples, for the sake of simplicity, A will denote an arbitrary member of A.) The reason for this generalization is to avoid clutter for the translations presented. 3 Definition 2 (R-deduction). Given ABF = (L, R, Ab, , V, ≤, υ) and a set ∆ ⊆ Ab, an R-deduction from ∆ of A, written ∆ `R A, is a finite tree where 1. the root is A, 2. the leaves are either of the form B, where → B ∈ R, or elements from ∆, 3. the children of non-leaf nodes are the conclusions of rules in R whose an- tecedents correspond to their own parents, 4. ∆ is the set of all B ∈ Ab that occur as nodes in the tree. Remark 2. Note that for flat ABFs, if ∆ `R A then ∆ will be the set of all B ∈ Ab occurring as leaves in the tree. The following example shows that for non-flat ABFs we also have to consider non-leaf nodes. Example 1. Let ABF = (L, R, Ab, , V, ≤, υ) be given by: Ab = {p, q, r} and the set of rules R = {p → r, p → q, q → r}. Note that there is no deduction {p} `R r since r appears as a node in any derivation of r. We have both {r} `R r, whose tree only consists of the root r, and {p, r} `R r with root r and unique leaf p. Deductions are neither monotonic in the antecedent, e.g. we do not have {p, r, q} `R r in Ex. 1; nor need the antecedent be a closed set of assumptions, e.g., {p} `R p although p → r ∈ R in Ex. 1. We define various ways to lift ≤ to sets of assumptions. Definition 3 (≤-minimal set). Given an assumption-based framework ABF = (L, R, Ab, , V, ≤, υ) and ∆ ⊆ Ab, we define υ(∆) = {υ(A) : A ∈ ∆} and:  min(∆) = α ∈ υ(∆) : @β ∈ υ(∆) such that β < α  min(∆) = α ∈ υ(∆) : ∃β ∈ min(∆) such that β 6< α . The intuition behind min(·) is to close min under incomparable elements: min(∆) includes all the elements that are incomparable to at least one element of min(∆). Definition 4 (Lifting of ≤). Given an assumption-based framework ABF = (L, R, Ab, , V, ≤, υ), ∆ ∪ {A} ⊆ Ab, we define 4 3 If one is interested in reducing a set of contraries B = {A1 , . . . , An } to a single contrary {A1 }, one can simply add the rule Ai → A1 for every 1 < i ≤ n, cf. [11, p. 109]. 4 It is not necessary to consider the lifting: ∆ α3 ). We have the following: α1 α5 {A2 , A3 } ∆00   In the context of ABA without priorities, attack coincides with d-defeat, so we will sometimes write f-defeat instead of attack to avoid confusion. From here on, ABAf , ABAd and ABAr denote assumption-based argumentation using, respectively f-, d- and r-defeats. Definition 6 (S-closure). Given an ABF = (L, R, Ab, , V, ≤, υ), where ∆ ⊆ Ab and S ⊆ R, we define: 5 We follow [6] in letting A reverse defeat ∆00 only if A > ∆00 . However, we do not see any conclusive reason why we should not let A reverse defeat ∆00 only if A ≤ ∆00 . We leave the investigation of this alternative form of r-<-defeat for future work. A ∈ ClS (∆) iff there is a sequence A1 , . . . , An with A = An , and for 1 ≤ i ≤ n Ai ∈ ∆ or Ai is obtained by an application of a rule Ai1 , . . . , Aim → Ai where i1 , . . . , im < i S 0 0 0 ℘ (∆) = {∆ ⊆ ∆ : ∆ = ClS (∆ )} (S-closed sets within ∆). Finally, we say that ∆ is S-closed iff ∆ ∈ ℘S (Ab). The consequences of a given ABF are determined by the argumentation se- mantics. On the basis of argumentative attacks, the semantics determine when a set of assumptions ∆ is acceptable. Informally, an acceptable set ∆ should at least not attack itself, and it should be able to defend itself against attacks from other sets of assumptions. Argumentation semantics, originally defined for abstract frameworks in [8], have been reformulated for ABA in e.g. [2]. Definition 7 (Argumentation semantics [2]). Given a framework ABF = 0 (L, R, Ab, , V, ≤, υ), a lifting < ∈ { v(q)). Consequently, the translation from Def. 9 is not adequate for non-flat frameworks. Translation for ABAd under {A1 , . . . , An }. It would perhaps be more elegant to have contraposition on the level of the rules rather than to base it on the derivability relation `R . Such a proposal, however, runs into additional complications. The following Vn example demonstrates why we cannot just replace R∧¬ \ R∧ by {A → ( i=1 Ai )¬ : A1 , . . . , An → A ∈ R}: Example 10. Let Ab = {p, q} and R = {p → s, s → q}. Note that we can’t add q → s¬ to R since s¬ is not defined (since s 6∈ Ab). Of course one could extend the language with A¬ for A ∈ L \ Ab. However, we leave the investigation of this proposal for future research. 7 Related Work In [2, 10] ways of expressing priorities in the object language of ABA were pro- posed. In our contribution we demonstrated how this idea can be utilised to express the ways priorities are handled in ABAd and ABAr in the basic (non- prioritized) ABA framework of [2]. In [7] it was shown that (a special case of) ABAr conservatively extends ABA from [2]. We have generalized this result to ABAd and by translating both to ABA we have shown that the expressive power of the three frameworks (w.r.t. the standard semantics) is the same. On the relation between ABA+ and ABAr . The idea of reverse-defeat was first introduced in [6] in the context of ABA+ . In this subsection we will discuss the various versions of ABA+ and their relation to ABAr as defined in this paper. In [6] we find the following definition of defence and a corresponding notion of admissibility (for flat assumption-based frameworks): Definition 14 (Defence, admissibility in ABA+ ). Define, for ∆∪{A} ⊆ Ab, ∆ defends+ A iff ∆ r-