In recent years there has been an increasing interest in extending Dung's framework to facilitate the knowledge representation and reasoning process. In this paper, we discuss a recently proposed extension of abstract Argumentation Framework (AF) that allows for the representation of preferences over arguments' truth values (3-valued preferences) [1]. For instance, we can express a preference stating that extensions where argument is false (i.e. defeated) are preferred to extensions where argument is false. Interestingly, such a framework generalizes the well-known Preference-based AF with no additional cost in terms of computational complexity for most of the classical argumentation semantics. Then, AF is further extended by considering both (3-valued) preferences and 3-valued constraints, that is constraints of the form ⇒ or ⇒ , where is a logical formula and is a 3-valued truth value. We discuss the complexity of deciding acceptance of arguments in this context.
meat fish meat
fish beer Recent years have witnessed intensive formal study, devtaetlioopnmFernamt, aewndorakpp(AlicFa)tiionnvoafriDouusndgi’rseacbtisotrnasc[t2A].rgAunmAenF- white red white red consists of a set of arguments and an attack relation ℛ ⊆ × that specifies conflicts between arguments Figure 1: AF Λ1 (left) and AF Λ2 (right). (if argument attacks argument , then is acceptable only if is not). We can think of an AF as a directed graph whose nodes represent arguments and edges repre- white}, {(fish, meat), (meat, fish), (meat, white), sent attacks. The meaning of an AF is given in terms of (white, red), (red, white)}⟩, shown in Figure 1(left). argumentation semantics, e.g. the well-known grounded Intuitively, Λ 1 describes what a person is going to have (gr), complete (co), preferred (pr), stable (st), and semi- for lunch. (S)he will have either fish or meat, and will stable (ss) semantics. Intuitively, an argumentation se- drink either white wine or red wine. However, if (s)he mantics tells us the sets of arguments (called -extensions, will have meat, then (s)he will not drink white wine. Λ 1 with ∈ {gr, co, pr, st, ss}) that can collectively be has three preferred (stable and semi-stable) extensions accepted to support a point of view in a dispute. For 1 = {fish, white}, 2 = {fish, red}, and 3 = instance, for AF ⟨, ℛ⟩ = ⟨{a, b}, {(a, b), (b, a)}⟩ hav- {meat, red}, which represent alternative menus. ing two arguments, a and b, attacking each other, there Assume that there is a pescetarian customer and, as a are two preferred/stable extensions, {a} and {b}; neither consequence, (s)he wants to discard all menus with meat a nor b is certainly accepted. by putting the constraint meat ⇒ false, stating that
Several proposals have been made to extend the Dung’s argument meat must be rejected. Thus, feasible preferred
framework with the aim of better modeling the knowledge extensions are only those where meat is defeated, that is
to be represented. These extensions include AF with 1 and 2.
constraints (CAF) [
Considering the previous example, one could observe that the (pescetarian) user constraint could be modeled by modifying the AF through the addition of an (unattacked in {f , u, t}, denoting false, undefined , and true truth valmeta-) argument attacking meat. However, such kind of ues, and corresponding to the following statuses of argurewriting is not always easy to carry out, e.g. when con- ments: defeated, undecided, and accepted respectively. straints are defined by complex propositional formulae. For instance, considering the AF Λ 2 shown in FigIn some cases, it is even not possible (e.g. under the com- ure 1(right), a preference redt ≻ redu means that we plete semantics). In fact, the introduction of constraints prefer menus containing red wine w.r.t. menus where red and/or preferences is useful not only to separate the objec- wine is undecided, whereas a preference fisht ≻ redf tive knowledge represented by the AF from the subjective states that we prefer menus containing fish w.r.t. menus restrictions and preferences added by users but also be- where red is false (i.e. defeated). cause, as it will be clear from our complexity analysis, the rewriting is not always possible. Definition 2. An extended PAF (ePAF) is a triple
Regarding Preference-based AF (PAF), user prefer- ⟨, ℛ, ⟩≻ where ⟨, ℛ⟩ is an AF and ≻ is an extended ences are used to select a subset of extensions of the preference relation.
AF, called best extensions [
A limitation of the forms of preferences proposed in ∈ 1( ) ∖ 1(), ∈ 2() ∖ 2( ) holds (where the literature is that, as AF semantics may be 3-valued 1, 2 ∈ {f , u, t}). Moreover, ⊐ , if ⊒ and (arguments can be either accepted, defeated, or undecided) ̸⊒ . they do not allow expressing preferences referring to the status of arguments. For instance, continuing with our example, classical preferences do not allow us to express a preference for menus (i.e. extensions) containing fish w.r.t. menus not containing fish (i.e. extensions where fish is defeated or undecided) or to express a preference for menus surely not containing fish (i.e. with fish being defeated) w.r.t. menus surely not containing meat (i.e. with meat being defeated).
As most of the AF semantics are 3-valued, in this
paper we discuss AF with extended preferences [
We assume the reader is familiar with AF, CAF and
PAF semantics. We refer the interested reader to [
Let (⟨, ℛ⟩) be the set of -extensions for AF ⟨, ℛ⟩. Given an ePAF ∆ = ⟨, ℛ, ≻⟩ and ∈ {co, pr, st, ss}, an extension ∈ (⟨, ℛ⟩) is a best extension for ∆ if there is no extension ∈ (⟨, ℛ⟩) such that ⊐ . The set of best -extensions for an ePAF ∆ under KTV criterion is denoted by (∆) .
Considering the AF Λ 1, there are six complete extensions: 0 = ∅, 1 = {fish, white}, 2 = {fish, red}, 3 = {meat, red}, 4 = {fish} (with white and red undecided), and 5 = {red} (with fish and meat undecided). When assuming the following preferences: t ≻ u and t ≻ f , for every argument , the best complete extensions are 1, 2 and 3 (which are the preferred ones). If we also have the preference fisht ≻ meatt, then the best complete extensions are 1 and 2.
Notice that ePAF generalizes PAF with KTV criterion. Indeed, let ∆ = ⟨, ℛ, ≻⟩ be an ePAF and ∆ ′ = ⟨, ℛ, >⟩ be a PAF such that ≻ = {t ≻ t | > ∆ ′} and > = { > | t ≻ t in ∆ }, where > is a strict partial order over arguments, then it holds that (∆) = (∆ ′) for ∈ {co, pr, st, ss}.
In this section we introduce a new form of preference for AF and extend the PAF under the KTV criterion [14].
Definition 1. Let be a set of arguments, an (extended) preference relation, denoted as ≻ , is a strict partial order (i.e. an irreflexive, asymmetric, and transitive relation) over = { | ∈ ∧ ∈ {f , u, t}} of the form 1 ≻ 2 .
Intuitively, it is allowed to define preference between pairs, where each pair consists of an argument and a truth value Combining Preferences with Constraints Extended preferences and constraints have been combined so that the resulting framework, called extended Preference-based Constrained Argumentation Framework, other than offering a compact and easier representation of both preferences and constraints, is also more expressive than both CAF and PAF and allows to express several kinds of desiderata among extensions.
Definition 4. An extended Preference-based Constrained
Argumentation Framework (ePCAF) is a tuple ∆ = co st pr ss (co), stable (st), preferred (pr), and semi-stable (ss) semantics. For any complexity class , -c (resp., -h) means -complete (resp., -hard). An interval -h, ′ means -hard and in ′.
Given an eP(C)AF ∆
and a set of arguments, the verification
problem under KTV criterion (denoted as ) is deciding whether belongs to the set of best -extensions of ∆ . Moreover, given an argument , the credulous and skeptical acceptance problems (denoted as and ) are the problems of deciding whether belongs to any/every -extension of ∆ , respectively.
As stated by the complexity results reported in Table 1, 23, 24, 25, 26, 27, 28, 29], as well as other forms of that also summarizes known results for AF, CAF and PAF, constraints such as weak and epistemic constraints [5, 30, the complexity bounds of verification, credulous acceptance and skeptical acceptance for ePAF do not increase (extended) preference relation (cf. Definition 1). ⟨, ℛ, , ≻⟩ , where ⟨, ℛ, ⟩ is a CAF and ≻ is an
Definition 5. a semantics ⊐ . ⟨, ℛ, ⟩ is a best -extension for ∆ rion if there is no -extension for ⟨, ℛ, ⟩ such that ∈ {co, pr, st, ss}, a -extension for Given an ePCAF ∆ = ⟨, ℛ, , ≻⟩ and
Continuing with our running example, consider the ePCAF ∆ 1 = ⟨1, ℛ1, {white ⇒ f }, {meatt ≻ fisht}⟩, The preferred extensions for AF Λ 1 ⟨1, ℛ1⟩ are 1 = {fish, white}, 2 = {fish, red} and 3 = {meat, red}. As white must be false, there are only two preferred extensions satisfying the constraint: = 2 and 3. Then, the only best preferred extension is 3.
been different if the ePCAF ∆ = defined as an ePAF Indeed, in such a case, the -extensions for ∆ been as the best -extensions of ⟨, ℛ, ≻⟩ would have satisfying constraints , that is constraints would have been applied ⟨, ℛ, ≻⟩
with a set of constraints . after preferences.
Complexity ⟨, ℛ, , ≻⟩ has been
observed for ePAF. under KTV crite- in Figure 1 (right). The PAF preference red > white w.r.t. those of PAF under KTV semantics, except for skeptical acceptance under complete semantics that becomes Π 2-complete. Although the form of preference introduced is more flexible than that of PAF, the complexity does not increase in most of the cases.
We observe that ePAF is used to express preferences not allowed in PAF. As an example, consider the AF Λ 2 shown does not allow to restrict the set of extensions and all complete (resp. preferred) extensions are also the best ones. However, the ePAF preference redt ≻ us to select as best complete (resp. preferred) extension redu allow 2 only.
particularly if we consider the verification problem whose complexities increase of one level in the polynomial hierarchy for all considered semantics. Also, it turns out that ePCAF has the same complexity bounds as PAF, except for the co problem, similarly to what we have
Extended preferences and (3-valued) constraints as well as the complexity results for the novel frameworks (ePAF and ePCAF) can carry over to other AF-based frameworks [15, 16, 17, 18, 19]. Indeed, as these frameworks can be rewritten into AF [20], their extended Preferencebased Constrained forms could be rewritten in ePCAF, obtaining upper bounds on their complexity from ePCAF results. Lower bounds also follow if those frameworks generalize ePCAF.