Preferences and Constraints in Abstract Argumentation

1 Introduction

Reasoning about preferences over a set of alternatives is central to rational decision-making. Preferences have been investigated in many contexts including e.g. decision theory, social choice, knowledge bases, and AI [Rossi et al., 2011; Manlove, 2013; Santhanam et al., 2016; Domshlak et al., 2011; Pigozzi et al., 2016; Conitzer, 2019; Brewka et al., 2003; Staworko et al., 2012]. Preferences are often modeled by means of an irreflexive, asymmetric, and transitive binary relation (expressing the preference of one element w.r.t. another one) and can be represented by an acyclic graph.

Recent years have witnessed intensive formal study, development, and application of Dung's abstract Argumentation Framework (AF) in various directions [Gabbay et al., 2021]. An AF consists of a set A of arguments and an attack relation R ⊆ A×A that specifies conflicts between arguments (if argument a attacks argument b, then b is acceptable only if a is not). We can think of an AF as a directed graph whose nodes represent arguments and edges represent attacks. The meaning of an AF is given in terms of argumentation semantics, e.g. the well-known grounded (gr), complete (co), preferred (pr), stable (st), and semi-stable (ss) semantics, which intuitively tells us the sets of arguments (called σ-extensions, with σ ∈ {gr, co, pr, st, ss}) that can collectively be accepted to support a point of view in a dispute. For instance, for AF 〈A, R〉 = 〈{a, b}, {(a, b), (b, a)}〉 having two arguments, a and b, attacking each other, there are two preferred/stable extensions, {a} and {b}; neither a nor b is certainly accepted.

Several proposals have been made to extend the Dung's framework with the aim of better modeling the knowledge to be represented. These extensions include Bipolar AF [Nouioua and Risch, 2011], AF with recursive attacks and supports [Cohen et al., 2015; Cayrol et al., 2018], Dialectical framework [Brewka et al., 2013], AF with preferences [Amgoud and Cayrol, 1998; Modgil and Prakken, 2013; Alfano et al., 2022b; 2023a] and AF with constraints [Coste-Marquis et al., 2006; Arieli, 2015; Alfano et al., 2021b], as well as extensions for representing uncertain information [Fazzinga et al., 2020; 2015; Li et al., 2011]. In this paper, we focus on AF with constraints and preferences.

Example 1 Consider AF Λ1 = 〈{fish, meat, red, white}, {(fish, meat), (meat, fish), (meat, white), (white, red), (red, white)}〉, shown in Figure 1(left). Intuitively, Λ1 describes what a person is going to have for lunch. (S)he will have either fish or meat, and will drink either white wine or red wine. However, if (s)he will have meat, then (s)he will not drink white wine. Λ1 has three preferred (stable and semi-stable) extensions E1 = {fish, white}, E2 = {fish, red}, and E3 = {meat, red}, which represent alternative menus.

Assume that there is a pescetarian customer and, as a consequence, (s)he wants to discard all menus with meat by putting the constraint meat ⇒ false, stating that argument meat must be rejected. Thus, feasible preferred extensions are only those where meat is defeated, that is E1 and E2.

Assume now that there is another customer which would express the preference on menus having meat instead of fish as main dish; the preference meat > fish can be used to encode such a desideratum. In this case no extension is discarded. Among the three above-mentioned extensions representing the alternative menus, the best one for the considered customer is selected, that is, extension E3. ✷

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 meta-) argument attacking meat. However, such kind of rewriting is not always easy to carry out, e.g. when constraints are defined by complex propositional formulae. In some cases, it is even not possible (e.g. under the complete semantics). In fact, the introduction of constraints and/or preferences is useful not only to separate the objective knowledge represented by the AF from the subjective restrictions and preferences added by users but also because, as it will be clear from our complexity analysis, the rewriting is not always possible.

The extension of AF with constraints, called Constrained AF (CAF), has been studied in [Coste-Marquis et al., 2006; Arieli, 2015; Alfano et al., 2021b], while for AF with preferences different semantics have been proposed in [Amgoud and Cayrol, 1998; 2002; Amgoud and Vesic, 2011; 2014; Cyras, 2016; Silva et al., 2020].

Regarding Preference-based AF (PAF), two main approaches have been proposed in the literature. A first approach defines the PAF semantics in terms of an underlying AF [Amgoud and Cayrol, 2002; Amgoud and Vesic, 2014; Kaci et al., 2018], whereas a second approach uses preferences to select a subset of extensions of the AF, called best extensions [Amgoud and Cayrol, 1998; 2002; Amgoud and Vesic, 2011; 2014; Cyras, 2016; Silva et al., 2020]. Considering the first approach, there are cases where the semantics may give counterintuitive results (e.g. the extensions of the rewritten AF are not conflict-free w.r.t. the initial AF). Thus, in the rest of the paper, we focus on the second approach.

A limitation of the forms of preferences proposed in the literature is that, as AF semantics may be 3-valued (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 study AF with extended preferences, that is preferences of the form av ≻ bw , where a and b are arguments and v and w are truth values (true, false, and undefined) denoting the status of associated arguments (accepted, defeated, and undecided, respectively). We also study the combination of extended preferences with 3-valued constraints and propose a framework with multiple agents sharing the same AF while expressing different constraints and preferences.

Contributions. Our main contributions are as follows.

• We introduce the extended Preference-based AF (ePAF), an extension of AF where preferences are 3-valued, in the sense that they also refer to the status of arguments (Section 3). We show that ePAF is in general more expressive than PAF (under the so-called KTV interpretation) and that AF semantics can be emulated by ePAF under completesemantics (cf. Proposition 2). We study the complexity of the verification (Verσ) as well as credulous (CAσ) and skeptical (SAσ) acceptance problems, and show that in most of the cases (i) it increases by one level in the polynomial hierarchy w.r.t. that of AF, and (ii) is the same as that of PAF under KTV criterion (see Table 1).
• We combine the features of CAF and ePAF to define the extended Preference-based Constrained AF (ePCAF), and investigate the complexity of the verification and credulous and skeptical acceptance problems for ePCAF for multistatus semantics σ ∈ {co, st, pr, ss}. As shown in Table 1, it turns out that ePCAF is more expressive than both CAF and PAF, though the complexity bounds do not increase w.r.t. that of ePAF (Section 4).
• To establish the above-mentioned complexity relationships, i) we study the complexity of the verification problem for CAF, showing that it does not increase w.r.t. that of AF; ii) we show that CAF is more expressive than AF under preferred semantics by closing the complexity gap (NP-hard, in Σp2 ) for the credulous acceptance problem (cf. Table 1).
• We further extend our framework by considering a multiple agents scenario. Here the objective knowledge is modeled through an AF, whereas, the agents' subjective knowledge is modeled by means of constraints and (extended) preferences. Also in this context, we study the computational complexity and show that there is no increase w.r.t. ePCAF.

2 Preliminaries

We next review the Dung's framework and its generalizations with constraints (CAF) and preferences (PAF).

2.1 Abstract Argumentation Framework

An abstract Argumentation Framework (AF) is a pair 〈A, R〉, where A is a (finite) set of arguments and R ⊆ A×A is a set of attacks (also called defeats). Different semantics have been defined for AF, leading to the characterization of collectively acceptable sets of arguments, called extensions [Dung, 1995].

Given an AF Λ = 〈A, R〉 and a set E ⊆ A of arguments, an argument a ∈ A is said to be i) defeated w.r.t. E iff ∃b ∈ E such that (b, a) ∈ R; ii) acceptable w.r.t. E iff ∀b ∈ A with (b, a) ∈ R, ∃c ∈ E such that (c, b) ∈ R. Given an extension E, the sets of defeated (f(E)), acceptable (t(E)), and undecided (u(E)) arguments w.r.t. E are defined as follows (where Λ is understood):

• f (E) = {a ∈ A | ∃b ∈ E . (b, a) ∈ R};
• t(E)={a ∈ A | ∀b∈A . (b, a) ∈ R ⇒ b ∈ f (E)};
• u(E)=A \ (t(E) ∪ f (E)).

Given an AF 〈A, R〉, a set E ⊆ A of arguments is said to be:

• conflict-free iff E ∩ f (E) = ∅;
• admissible iff it is conflict-free and E ⊆ t(E).

Given an AF 〈A, R〉, a set E ⊆ A is an extension called:

• complete (co) iff it is conflict free and E = t(E);
• preferred (pr) iff it is a ⊆-maximal complete extension;
• stable (st) iff it is a total complete extension, i.e. a complete extension s.t. E∪f (E)=A or, equivalently, u(E)=∅;
• semi-stable (ss) iff it is a complete extension with a minimal set of undecided arguments, i.e. f(E) is ⊆-minimal;
• grounded (gr) iff it is the ⊆-smallest complete extension.

The set of complete (resp. preferred, stable, semi-stable, grounded) extensions of an AF Λ will be denoted by co(Λ) (resp. pr(Λ), st(Λ), ss(Λ), gr(Λ)). It is well-known that the set of complete extensions forms a complete semilattice w.r.t. ⊆, where gr(Λ) is the meet element, whereas the greatest elements are the preferred extensions. All the above-mentioned semantics except the stable admit at least one extension. The grounded semantics, that admits exactly one extension, is said to be a unique status semantics, while the others are multiple status semantics. With a little abuse of notation, we also use gr(Λ) to denote the grounded extension. For any AF Λ, st(Λ) ⊆ ss(Λ) ⊆ pr(Λ) ⊆ co(Λ), gr(Λ) ∈ co(Λ) and st(Λ) ̸= ∅ ⇒ st(Λ) = ss(Λ).

Example 2 Consider the AF Λ2 shown in Figure 1 (centerleft). Λ2 has three complete extensions: E0 = ∅, E1 = {fish} (where f(E1) = {meat}), and E2 = {meat, red} (where f(E2) = {fish, white, beer}. E0 is the grounded extension, whereas E1 and E2 are preferred (semi-stable and stable) extensions. ✷

Given an AF Λ = 〈A,R〉 and a semantics σ ∈ {co, pr, st, ss, gr}, the verification problem, denoted as Verσ, is deciding whether a set S ⊆ A is a σ-extension of Λ. Moreover, for g ∈ A, the credulous (resp. skeptical) acceptance problem, denoted as CAσ (resp. SAσ), is deciding whether g belongs to any (resp. every) σ-extension of Λ. Clearly, CAgr and SAgr are identical problems.

2.2 Constrained AF

We briefly recall the Constrained Argumentation Framework (CAF) extending AF with constraints expressed by means of propositional formulae [Arieli, 2015; Alfano et al., 2021b].

We use LA to denote the propositional language defined from a set of arguments A and the connectives ∧, ∨, ⇒, ¬.

Definition 1 A constraint is a formula of one of the following forms: (i) ϕ ⇒ v, or (ii) v ⇒ ϕ, where ϕ is a propositional formula in LA and v ∈ {f , u, t}.

The 3-valued semantics of a formula γ, denoted by tv(γ) (truth value of γ), assuming ¬u = u and the truth value ordering f < u < t, is defined as follows: (i) tv(v) = v, for v ∈ {f, u, t}, (ii) tv(ϕ ∧ ψ) = min(tv(ϕ), tv(ψ)), (iii) tv(ϕ ∨ ψ) = max(tv(ϕ), tv(ψ)), (iv) tv(¬ϕ) = ¬tv(ϕ). Regarding the implication operator ⇒, different semantics have been defined. For instance, under Kleene's logic tv(ϕ ⇒ ψ) = ¬tv(ϕ) ∨ tv(ψ), whereas under Lukasiewicz's logic tv(ϕ ⇒ ψ) = (¬tv(ϕ) ∨ tv(ψ)) ∨ (tv(ϕ) = tv(ψ))). For boolean constraints (that is, with v ∈ {f, t}) Kleene and Lukasiewicz's logics coincide. A nice property of both Kleene and Lukasiewicz's logics is that literals can be moved from the head to the body (after negating them), and vice versa, analogously to the case of 2-valued semantics. For formulae defining constraints, Lukasiewicz's logic seems to be more appropriate as, for instance, it allows to distinguish ϕ⇒ f fromϕ⇒u.

In the following, we refer to the Lukasiewicz's logic and assume that the set of constraints is satisfiable, that is there is an assignment of truth values to arguments which makes all constraints true.

Example 3 The constraint a ∧ b ∧ c ⇒ f states that at least one of the arguments a, b and c must be false, whereas a ∧ b ∧ c ⇒u states that a, b and c cannot be all true. ✷

Clearly, constraints of the forms f ⇒ ϕ and ϕ ⇒ t are useless because always satisfied. Regarding the stable semantics, which is 2-valued, only the symbols f and t can be used and all interpretations of the implication operator coincide with the classical 2-valued interpretation. Thus, a constraint ϕ ⇒ u is interpreted as ϕ ⇒ f , whereas a constraint u ⇒ ψ is interpreted as t ⇒ ψ.

Definition 2 A Constrained Argumentation Framework (CAF) is a triple 〈A, R, C〉 where 〈A, R〉 is an AF and C is a set of constraints built from LA.

Definition 3 Given a CAF 〈A,R, C〉 and a semantics σ ∈ {co, gr, pr, st, ss}, a set S ⊆ A is a σ-extension for 〈A,R, C〉 if S is a σ-extension for 〈A,R〉 and S |= C.

Note that, given a CAF 〈A, R, C〉, if we consider the corresponding AF Λ = 〈A, R〉, then the set of complete extensions of Λ that satisfy C does not always form a complete meetsemilattice. Roughly speaking, the constraints may break the lattice by making unfeasible some extensions. Therefore, even the grounded extension is not guaranteed to exist.

Example 4 Consider the CAF 〈A4 = {a}, R4 = {(a, a), C4 = {t ⇒ a}〉. AF 〈A4, R4〉 has only one complete extension, E1 = ∅, but it does not satisfy the constraint stating that "a must be accepted". Thus, the CAF 〈A4,R4, C4〉 has no complete extensions, and thus no grounded extension. ✷

2.3 Preference-based AF

Several extensions of Dung's framework for handling preferences over arguments have been proposed [Amgoud and Cayrol, 1998; 2002; Amgoud and Vesic, 2011; 2014; Cyras, 2016; Silva et al., 2020].

Definition 4 A Preference-based Argumentation Framework (PAF) is a triple 〈A,R,>〉 such that 〈A,R〉 is an AF and > is a strict partial order (i.e. an irreflexive, asymmetric and transitive relation) over A, called preference relation.

For arguments a and b, a > b means that a is better than b. To handle preferences, a "best extensions" semantics approach for PAF has been proposed in [Amgoud and Vesic, 2014; Kaci et al., 2018]. Given a PAF 〈A,R,>〉, classical argumentation semantics are used to obtain extensions of the underlying AF 〈A,R〉, and then the preference relation > is used to obtain a preference relation ⊒ over such extensions, so that the best extensions w.r.t. ⊒ are eventually selected.

Clearly, ⊒ is not trivial for multiple-status semantics only (for the grounded semantics, its extension is trivially the best one).

There have been different proposals to define the best extensions, corresponding to different criteria to define ⊒.

Definition 5 Given a PAF 〈A,R,>〉, for E, F ⊆ A with E ̸= F , we have that under

• democratic (d) criterion [Amgoud and Vesic, 2014]: E ⊒ F if ∀b ∈ F \ E ∃a ∈ E \ F such that a > b;
• elitist (e) criterion [Amgoud and Vesic, 2014]: E ⊒ F if ∀a ∈ E \ F ∃b ∈ F \ E such that a > b;
• KTV (k) criterion [Kaci et al., 2018]: E ⊒ F if ∀a, b ∈ A the relation a > b with a ∈ F \ E and b ∈ E \ F does not hold.

Moreover, E ⊐ F , if E ⊒ F and F ̸⊒ E.

Definition 6 Given a PAF ∆ = 〈A, R, >〉, a semantics σ ∈ {co, pr, st, ss}, and a criterion ∗ ∈ {d, e, k} for ⊒, the best σ-extensions of ∆ under criterion ∗ (denoted as σ∗(∆)) are the extensions E ∈ σ(〈A,R〉) such that there is no F ∈ σ(〈A, R〉) with F ⊐ E.

Example 5 Consider the AF Λ5 = 〈A5,R5〉 shown in Figure 1 (center-right) whose preferred extensions are {a, b}, {c, d}, and {e}. For PAF ∆5 = 〈A5,R5, {a > c, b>c, d>e}〉, the best preferred extensions are: prd (∆5) = {{a, b}, {c, d}}, pre (∆5) = {{a, b}, {e}}, and prk (∆5) = {{a, b}}. ✷

It is worth noting that, in some situations, the democratic and elitist criteria may lead to counterintuitive solutions. Consider, for instance, the AF of Example 1 with the preference meat > fish. As discussed in the Introduction, it is expected that the best preferred extension is E3 = {meat, red}. However, under both democratic and elitist criteria also E1 = {fish, white} is a best extension, because white and red are not compared with other arguments. In our opinion, democratic and elitist criteria are too restrictive and, for large AFs, may require a huge number of preferences to be effective. Moreover, for any PAF ∆= 〈A, R, >〉, (i) cod(∆) = prd (∆), and (ii) coe(∆) = gr(〈A,R〉) [Alfano et al., 2022b]. This means that under democratic and elitist interpretation, PAF semantics does not extend AF semantics, as for any PAF 〈A,R, ∅〉, co∗(∆) may be different from co(〈A, R〉), for ∗ ∈ {d, e}.

Thus, in this paper we will introduce and study a preference-based AF which extends PAF with KTV criterion.

Complexity of PAF. The verification, credulous and skeptical acceptance problems for PAF under KTV criterion (denoted as Verσk , CAσk and SAσk , respectively) naturally extend those for AF by considering the best σ-extensions (instead of all extensions of the underlying AF). As shown in Table 1, the complexity of Verσk increases by one level in the polynomial hierarchy, and also the complexity of CAσk and SAσk may increase by one level w.r.t. the corresponding problems for AF [Alfano et al., 2022b].

3 Extended Preference-based AF

In this section we introduce a new form of preference for AF and extend the PAF under the KTV criterion.

Definition 7 Let A 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 AV = {av | a ∈ A ∧ v ∈ {f , u, t}} of the form av1 ≻ bv2 .

Intuitively, we allow defining preference between pairs, where each pair consists of an argument and a truth value in {f, u, t}, denoting false, undefined, and true truth values, and corresponding to the following statuses of arguments: defeated, undecided, and accepted respectively. 1

For instance, considering the AF of Example 2, a preference redt ≻ redu means that we prefer menus containing red wine w.r.t. menus where red wine is undecided, whereas a preference fisht ≻ redf states that we prefer menus containing fish w.r.t. menus where red is false (i.e. defeated).

Definition 8 An extended PAF (ePAF) is a triple 〈A,R,≻〉 where 〈A, R〉 is an AF and ≻ is an extended preference relation.

The following definition introduces the semantics of ePAF. Definition 9 Given an ePAF ∆ = 〈A, R, ≻〉 and two distinct sets of arguments E, F ⊆ A, we have that E ⊒ F under KTV (k) criterion if ∄ av1 ≻ bv2 such that a ∈ v1(F) \ v1(E), b ∈ v2(E) \ v2(F) holds (where v1, v2 ∈ {f , u, t}). Moreover, E ⊐ F , if E ⊒ F and F ̸⊒ E.

Thus best extensions (under KTV (k) criterion) are defined as for PAF but using the criterion of Definition 9 to compare extensions. That is, given an ePAF ∆ = 〈A,R,≻〉 and σ ∈ {co, pr, st, ss}, an extension E ∈ σ(〈A,R〉) is a best extension for ∆ if there is no extension F ∈ σ(〈A,R〉) such that F ⊐ E. The set of best σ-extensions for an ePAF ∆ under KTV criterion is denoted by σk(∆).

Example 6 Consider the AF of Example 1 under the complete semantics. There are six complete extensions: E0 = ∅, E1 = {fish, white}, E2 = {fish, red}, E3 = {meat, red}, E4 = {fish} (with white and red undecided), and E5 = {red} (with fish and meat undecided).

Assume that there are the following preferences: xt ≻ xu and xt ≻ xf , for every argument x. Then, the best complete extensions are E1, E2 and E3 (which are the preferred ones).

If we also have the preference fisht ≻ meatt , then the best complete extensions are E1 and E2. ✷

As stated next, ePAF generalizes PAF with KTV criterion. Proposition 1 Let ∆ = 〈A,R,≻〉 be an ePAF and ∆′ = 〈A, R, >〉 be a PAF such that ≻ = {at ≻ bt | a > b in ∆′ } and > = {a > b | at ≻ bt in ∆}. Then, σk(∆) = σk(∆′ ) for σ ∈ {co, pr, st, ss}.

Moreover, AF semantics can be easily expressed in ePAF in terms of best complete extensions.

Proposition 2 Let 〈A,R〉 be an AF, σ ∈ {gr, co, pr, ss} a semantics, and the ePAF

1 Instead of notation at (resp. af , au ), we could have used the labelling notation in(a) (resp. out(a), undec(a)) [Caminada, 2006].

An encoding for the stable semantics, that may admit no extensions, is given in Section 4 where we characterize the stable semantics in a simple way by using constraints.

3.1 Complexity of ePAF

The verification, credulous and skeptical acceptance problems for ePAF under KTV criterion (denoted as Verσk , CAσk and SAσk , respectively) are defined as for PAF but considering the best extensions for ePAF (i.e. according Definition 9). The next theorem states the complexity of these problems.

Theorem 1 For ePAF, the problem:

· Verσk is i) coNP-complete for σ ∈ {co, st}; ii) Πp2 -complete for σ ∈ {pr, ss}; · CAσk is i) Σp2 -complete for σ ∈ {co, st}; ii) Σp2 -hard and in Σp3 for σ ∈ {pr, ss}; · SAσk is i) Πp2 -complete for σ ∈ {co, st};

• ii) Πp2 -hard and in Πp3 for σ ∈ {pr, ss}.

Thus, the complexity bounds of verification, credulous acceptance and skeptical acceptance for ePAF do not increase w.r.t. those of PAF under KTV semantics, except for skeptical acceptance under complete semantics that becomes Πp2 - complete (cf. Table 1). Although the form of preference introduced is more flexible than that of PAF, the complexity in most of the cases does not increase.

The following example shows a case where ePAF is used to express preferences not allowed in PAF.

Example 7 Consider the AF Λ2 of Example 2 shown in Figure 1 (center-left). The PAF preference red > white 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 ≻ redu allow us to select as best complete (resp. preferred) extension E2 only. ✷

Next, we combine extended preferences and constraints and show that the resulting framework, other than offering a compact and easier representation of both preferences and constraints, is also more expressive than both CAF and PAF.

4 Combining Preferences with Constraints

We now extend CAF with (extended) preferences to express several kinds of desiderata among extensions, and propose a novel framework called extended Preference-based Constrained Argumentation Framework.

Definition 10 An extended Preference-based Constrained Argumentation Framework (ePCAF) is a tuple ∆ = 〈A,R, C,≻〉, where 〈A,R, C〉 is a CAF and ≻ is an (extended) preference relation (cf. Definition 7).

The semantics of an ePCAF is given by the best extensions selected among those that satisfy the constraints.

Definition 11 Given an ePCAF ∆ = 〈A, R, C, ≻〉 and a semantics σ ∈ {co, pr, st, ss}, a σ-extension E for 〈A, R, C〉 is a best σ-extension for ∆ under KTV criterion if there is no σ-extension F for 〈A,R, C〉 such that F ⊐ E.

Example 8 Continuing with Example 1, consider the ePCAF ∆8 = 〈A8,R8, {white ⇒ f}, {meatt ≻ fisht }〉, where 〈A8,R8〉 is the AF in Figure 1 (left). The preferred extensions for AF Λ8 are E1 = {fish, white}, E2 = {fish, red} and E3 = {meat, red}. As white must be false, there are only two preferred extensions satisfying the constraint: E2 and E3. Then, the only best preferred extension is E3. ✷

It is worth noting that, the best extensions would have been different if we had defined the ePCAF ∆ = 〈A,R, C,≻〉 as an ePAF 〈A,R,≻〉 with a set of constraints C. Indeed, in such a case, the σ-extensions for ∆ would have been as the best σ-extensions of 〈A,R,≻〉 satisfying constraints C, that is constraints would have been applied after preferences.

We now extend the set of relationships provided in Proposition 2 by showing that the stable semantics of an ePAF can be expressed as the best complete extensions of an ePCAF.

Proposition 3 For any ePAF 〈A,R,≻〉, it holds that stk(〈A, R, ≻〉) = cok(〈A, R, {a ∧ ¬a ⇒ f | a ∈ A}, ≻〉).

Observe that if in the proposition the set of preferences ≻ is empty, then the ePAF is an AF and the ePCAF is a CAF.

4.1 Complexity of ePCAF

Before characterizing the complexity of ePCAF, we provide new results concerning the complexity of CAF. Although these results are of independent interest, they are also useful to provide lower bounds on the complexity of ePCAF and to compare the two frameworks from a complexity standpoint.

As observed after Definition 3, the presence of constraints in CAF breaks the meet-semilattice of complete extensions. This entails that the credulous and skeptical acceptance of an argument w.r.t a CAF 〈A,R, C〉 may differ from that of the associated AF 〈A,R〉. For instance, the fact that complete extensions may not exist for CAF (cf. Example 4) impacts on the complexity of the skeptical acceptance problem under complete semantics, which cannot be longer decided by simply looking at the grounded extension as for the case of AF (where an argument is skeptically accepted under complete semantics if and only if it is in the grounded extension).

A summary of known results for the complexity of CAF is reported in Table 1 (see cells with white background). The complexity of the verification problem has not been addressed so far. Moreover, an open question is whether credulous acceptance under preferred semantics for CAFs is harder than for AF (where it can be decided by checking credulous acceptance under complete semantics). Indeed, it is known that the complexity of CApr is NP-hard and in Σp2 [Alfano et al., 2021b]. In all the other cases the complexity of credulous and skeptical reasoning for CAFs and AFs coincides.

As stated next, the complexity of the verification problem for CAF remains the same as that for AF.

Proposition 4 For CAF, the problem Verσ is in P for any semantics σ ∈ {co, st} and coNP-complete for σ ∈ {pr, ss}.

We now provide a tight characterization of the complexity of CApr for CAF, showing that it is harder than for AF. The result follows from the fact we can write some constraints enabling a reduction to our problem from the complement of deciding coherence [Dunne and Bench-Capon, 2002].

We are now ready to address the complexity of ePCAF.

Given an ePCAF ∆ and a set S of arguments, the verification problem under KTV criterion (denoted as Verσk ) is deciding whether S ∈ σk(∆). Moreover, given an argument g, the credulous and skeptical acceptance problems (denoted as CAσk and SAσk ) are the problems of deciding whether g belongs to any/every σk-extension of ∆, respectively.

Theorem 3 For ePCAF, the problem:

· Verσk is i) coNP-complete for σ ∈ {co, st}; ii) Πp2 -complete for σ ∈ {pr, ss}; · CAσk is i) Σp2 -complete for σ ∈ {co, st}; ii) Σp2 -hard and in Σp3 for σ ∈ {pr, ss}; · SAσk is i) Πp2 -complete for σ ∈ {co, st};

• ii) Πp2 -hard and in Πp3 for σ ∈ {pr, ss}.

Thus ePCAF is generally more expressive than CAF, 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 SAcok problem, similarly to what we have observed for ePAF.

5 Dealing withMultiple Agents

Often in knowledge representation and reasoning using argumentation-based frameworks it is assumed that the AF represents the objective knowledge, while constraints and preferences are subjective knowledge of users/agents that are used for collective decision-making. We now extend our framework by considering the case of multiple agents sharing the same AF and having different constraints and preferences (represented by different ePCAFs) that are taken into account to decide for instance the acceptance of a given argument.

Definition 12 A multi-agent ePCAF (mPCAF) is a set of ePCAFs {〈A,R, C1,≻1〉, 〈A,R, C2,≻2〉, ..., 〈A,R, Cn,≻n〉}, one for each agent i ∈ [1, n].

Thus, we assume to have n (distinct) agents and that each agent i has a set of constraints Ci and a preference relation ≻i. For each agent i we have ePCAF ∆i = 〈A,R, Ci,≻i〉, and the best σ-extensions for agent i are those in σ(∆i).

Definition 13 Let ∆ = {∆1 = 〈A,R, C1,≻1〉, ...,∆n = 〈A, R, Cn, ≻n〉} be an mPCAF and σ ∈ {co, st, pr, ss} a semantics. Then, a set of arguments S ⊆ A is said to be a possible (resp. necessary) best σ-extension of ∆ (under KTV criterion) iff S ∈ σk(∆i) for some (resp. every) i ∈ [1, n].

Example 9 Consider the AF Λ9 =〈A9,R9〉 shown in Figure 1 (right) that extends that of Example 1. It has four preferred extensions: E1 = {fish, white, icec}, E2 = {fish, white, cake}, E3 = {fish, red, cake}, and E4 = {meat, red, cake}, where icec denotes ice cream. Assume to have 2 agents α and β whose constraints and preferences are as follows: (Cα = {t ⇒ fish}, ≻α= {white ≻ red}); (Cβ = {t ⇒ cake},≻β= {fish ≻ meat}). Thus, for agent α the best preferred extensions are E1 and E2, whereas for agent β the best preferred extensions are E2 and E3. Hence, E1, E2 and E3 are possibly best preferred extensions of the mPCAF ∆9 = {∆α = 〈A9, R9, Cα, ≻α〉, ∆β = 〈A9,R9, Cβ,≻β〉} while only E2 is a necessary best preferred extension of mPCAF ∆. ✷

We have two variants of the verification problem for mPCAF. Given an mPCAF ∆ = {∆1 = 〈A,R, C1,≻1〉, . . . , ∆n = 〈A,R, Cn,≻n〉} and a set S ⊆ A of arguments, the possible (resp. necessary) verification problem, denoted as Ver∃ σk (resp. Ver∀ σk ), is the problem of deciding whether S is possible (resp. necessary) best σ-extension of ∆.

Analogously, two variants of the credulous and skeptical acceptance problems are defined in what follows.

Definition 14 Let ∆ = {∆1 = 〈A,R, C1,≻1〉, . . . ,∆n = 〈A, R, Cn, ≻n〉} be an mPCAF, k the KTV criterion, and σ ∈ {co, st, pr, ss} a semantics. Then, g ∈ A is said to be:

• possibly credulously accepted under σk, denoted as CA∃σk (∆, g), iff ∃i ∈ [1, n], ∃E ∈ σk(∆i) such that g ∈ E;
• possibly skeptically accepted under σk, denoted as SA∃σk (∆, g), iff ∃i ∈ [1, n] s.t. g ∈ E for all E ∈ σk(∆i);
• necessarily credulously accepted under σk, denoted as CA∀σk (∆, g), iff ∀i ∈ [1, n], ∃E ∈ σk(∆i) such that g ∈ E;
• necessarily skeptically accepted under σk, denoted as SA∀σk (∆, g), iff ∀i∈ [1, n], g ∈ E for all E ∈ σk(∆i).

We now investigate the complexity of the verification and credulous and skeptical acceptance problems in mPCAF. It is worth noting that we are assuming that the number of agents is an arbitrary but fixed number n.

Interestingly, the verification problem in mPCAF is not harder than in PAF, ePAF, and ePCAF. Moreover, an analogous result also holds for the credulous and skeptical acceptance problems, that is, the complexity bounds for mPCAF

acceptance problems do not increase w.r.t. those of ePCAF (which coincide with those for ePAF, cf. Table 1).

Theorem 4 For mPCAF, the problems

• Ver∃ σk and Ver∀ σk are i) coNP-complete for σ ∈ {co, st}; ii) Πp2 -complete for σ ∈ {pr, ss};
• CA∃σk and CA∀σk are i) Σp2 -complete for σ ∈ {co, st}; ii) Σp2 -hard and in Σp3 for σ ∈ {pr, ss};
• SA∃σk and SA∀σk are i) Πp2 -complete for σ ∈ {co, st}; ii) Πp2 -hard and in Πp3 for σ ∈ {pr, ss}.

We conclude this section by observing that reasoning in a context of distributed and conflicting pieces of information underlies many questions related to the field of collective/multi-criteria decisions that are not in the scope of this paper. We have shown that the complexity in the multiple-agent scenarios considered does not increase w.r.t. that of the single-agent one. Our results may be useful for more refined approaches to be explored in future work.

6 RelatedWork

Different approaches have been proposed to handle preferences in argumentation. A first approach considers AFbased semantics and consists in first defining a defeat relation Ri that combines original attacks in R and preference relations, and then apply the usual semantics to the resulting AF 〈A,Ri〉. Here Ri (with i ∈ [1, 4]) denotes one of the four mappings proposed in the literature [Amgoud and Cayrol, 2002; Amgoud and Vesic, 2014; Kaci et al., 2018]. As mentioned in the Introduction, in some cases these semantics may give counterintuitive results, as for instance the extensions of the rewritten AF are not conflictfree w.r.t. the initial AF. We point out that, in this setting, the complexity of the verification and acceptance problems does not increase as the mapping to AF (i.e. building Ri) is polynomial time. As discussed in Section 2.3, a second approach to handle preferences considers a "best extensions" semantics for PAF [Amgoud and Vesic, 2014; Kaci et al., 2018],

An alternative definition for PAF, based on that defined in [Sakama and Inoue, 2000] for logic programs with preferences, has been proposed in [Wakaki, 2015]. In this context a PAF is a triple 〈A,R,≥〉, where ≥ is a reflexive and transitive relation and a > b if a ≥ b and b ̸≥ a. Moreover, the preference relation ⊒ over extensions is reflexive (E ⊒ E), transitive (E ⊒ F and F ⊒ G implies E ⊒ G) and satisfies the condition E ⊒ F if ∃a ∈ E \ F, ∃b ∈ F \ E such that a ≥ b and ∄c ∈ F \ E such that c > a. In this paper we have only dealt with preferences relation ⊒ that is not transitive as our proposal is intended to extend PAF, where ⊒ is not transitive for all the criteria of Definition 5 (e.g. KTV).

Constrained AF has been firstly proposed in [CosteMarquis et al., 2006] and then further investigated in [Arieli, 2015; Alfano et al., 2021b]. A drawback of the semantics proposed in [Coste-Marquis et al., 2006] is that, in checking whether an extension satisfies a set of constraints, it does not distinguish between false and undecided arguments. Thus, a constraint of the form a ∧ ¬a ⇒ f is always satisfied, even when a is undecided. The main difference between the approaches in [Arieli, 2015] and [Alfano et al., 2021b] is in the underlying logic. Indeed, while the approach in [Arieli, 2015] is based on Slupecki's logic, interpreting the implication as tv(ϕ ⇒ ψ) = (tv(ϕ) ̸= t) ∨ tv(ϕ ∧ ψ), the approach in [Alfano et al., 2021b] is based on Lucasiewitcz's logic. A drawback of Arieli's semantics is that it does not distinguish between constraints of the form ϕ ⇒ f and ϕ ⇒ u, though it distinguishes between constraints t ⇒ ϕ and u ⇒ ϕ.

It is worth mentioning that 3-valued logics [Lukasiewicz, 1920; Kleene, 2009; Berry, 1952] has found application in various research areas, such as in 3-state logical circuits, databases (e.g. well-founded semantics for Datalog [Gelder et al., 1991] and the so-called contension inconsistency measure for databases [Parisi and Grant, 2023]), logic programming (e.g. partial stable models and defeasible logic programming [Alfano et al., 2018; 2021a]), as well as in interpreting null values in SQL [Libkin, 2016].

In value-based argumentation framework (VAF) an argument a defeats b only if the value promoted for b is not preferred to that promoted for a (according to a total ordering on values given by an audience) [Bench-Capon et al., 2005]. Moreover, VAF has been extended by incorporating constraints expressed by propositional formulas on arguments' values or arguments, resulting in the constrained VAF [Sedki and Yahi, 2016]. Finally, with the aim of generating more skeptically accepted arguments, the idea of comparing extensions and choosing the best ones has been explored in [Konieczny et al., 2015; Bonzon et al., 2018]. Recently, comparing sets of arguments is studied in [Skiba et al., 2021] to identify sets "closed" to become an extension.

To the best of our knowledge, this is the first paper combining both 3-valued constraints and 3-valued preferences (i.e. extended preferences) in AF and providing a thorough investigation of the complexity of the resulting framework.

7 Conclusions and FutureWork

Extended preferences and (3-valued) constraints as well as the complexity results for the novel frameworks (ePAF, ePCAF and mPCAF) can carry over to other AF-based frameworks such as (Bipolar) Argumentation Frameworks with necessities (AFN) [Nouioua and Risch, 2011], Argumentation Framework with recursive attacks (AFRA) [Baroni et al., 2011], Recursive Attacks and Supports in Argumentation Framework (ASAF) [Gottifredi et al., 2018], and Recursive Argumentation Framework with Necessity Supports (RAFN) [Cayrol et al., 2018] without collective attacks and supports. Indeed, as these frameworks can be rewritten into AF [Alfano et al., 2020], their extended Preference-based Constrained forms could be rewritten in ePCAF, obtaining upper bounds on their complexity from our results. Lower bounds also follow if those frameworks generalize ePCAF.

As future work, we plan to investigate preferences and constraints in other frameworks extending AF [Baumeister et al., 2021; Alfano et al., 2022a; Fazzinga et al., 2015; 2022; 2023; Alfano et al., 2023c], as well as other forms of constraints such as weak and epistemic constraints [Alfano et al., 2021b; 2023b; Sakama and Son, 2020].

Acknowledgments

We acknowledge financial support from PNRR MUR project PE0000013-FAIR.