On Preferences and Priority Rules in Abstract Argumentation

1 Introduction

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 Ω ⊆ 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 tell 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, Ω〉 = 〈{a, b}, {(a, b), (b, a)}〉 having two arguments, a and b, attacking each other, there are two preferred/stable extensions, {a} and {b}, and neither argument a nor b is skeptically accepted. To cope with such situations, a possible solution is to provide means for preferring one argument to another, as shown in the following example.

Example 1 Consider AF Λ=〈{fish, meat, red, white}, {(fish, meat), (meat, fish), (meat, white), (white, red), (red, white)}〉, whose corresponding graph is shown in Figure 1. Intuitively, Λ 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. Λ has six complete extensions E0 = ∅, E1 = {fish, white}, E2 = {fish, red}, E3 = {meat, red}, E4 = {fish}, and E5 = {red}, which represent possible menus; E0 is the grounded extension, whereas E1,E2 and E3 are stable, preferred and semi-stable extensions. Assume now that person prefers to have meat instead of fish as main dish. Under such an assumption there is only one stable (and preferred) extension (namely E3) which in a sense satisfies the person's preference. ✷

Two main approaches have been proposed in the literature for Preference-based Argumentation Frameworks (PAFs).

The first approach defines the PAF semantics in terms of an underlying AF [Amgoud and Cayrol, 2002a; Amgoud and Vesic, 2014; Kaci et al., 2018]. Considering for instance the PAF of our previous example, where the preference is meat > fish (meat is better than fish), the underlying AF according to the approach proposed in [Amgoud and Cayrol, 2002a] consists of an AF where the attack (fish, meat) is deleted. Consequently, there is only one complete extension (namely E3) and both meat and red are skeptically accepted.

However, there are cases where this PAF semantics may give counterintuitive results as shown next.

Example 2 Consider a scenario where David wants to organize a party and would invite Anne, Bob and Cayrol, and he received the following answers: Bob will attend the party if Anne does not, Cayrol will attend if Bob does not, and Anne will attend if Cayrol does not attend. Regarding the contrast between Anne and Cayrol, David would prefer that Anne attends the party. This could be represented by the PAF ∆ = 〈{a, b, c}, {(a, b), (b, c), (c, a)}, {a > c}〉, where argument x states that "(the person whose names' initial is) x joins the party" and a > c encodes the preference. According to the previous PAF semantics, for any semantics σ ∈ {gr, co, pr, st, ss}, there is only one σ-extension {a, c} stating that is Anne and Cayrol will attend the party. ✷

Observe that, in Example 2, the resulting set {a, c} does not give the desired intuition as Anne and Cayrol should not attend the party together in any case (because of attack (c, a) the resulting set is not conflict-free). Herein, the problem is that preferences and attacks describe different pieces of knowledge and should be considered separately. This is carried out by the second approach defining the PAF semantics, that consists in comparing extensions w.r.t. preferences obtained from those between arguments [Amgoud and Vesic, 2014; Kaci et al., 2018].

In this paper we focus on the second PAF semantics, based on extension selection by means of preferences, and investigate AF with preferences from several standpoints including the complexity analysis of well-known reasoning problems as well as the introduction of a general framework for dealing with preferences in AF.

Contributions. Our main contributions are as follows.

• We study the complexity of the verification (Verσ) as well as credulous (CAσ) and skeptical acceptance (SAσ) problems for PAF under the democratic (d), elitist (e), and KTV (k) criteria for multi-status semantics σ ∈ {co, st, pr, ss} (Section 3). As shown in Table 1 that summarizes our results, it turns out that the complexity of these problems generally increases of one level in the polynomial hierarchy w.r.t. the corresponding problems for AF.
• In Section 4 we introduce cardinality based semantics for AF, namely cardinality preferred (c-pr) and cardinality semi-stable (c-ss), that refine the set-inclusion based semantics pr and ss by allowing to filter out extensions on the basis of the cardinality of the set of arguments belonging to an extension. Cardinality based semantics are meant to be complementary to set based semantics, providing the user with further preferential criteria to select among complete extensions. For these semantics, as well as for another cardinality based semantics that is shown to collapse to one of them, we investigate the relationships with classical AF semantics as well as the complexity of Verσ, CAσ and SAσ with σ ∈ {c-pr, c-ss}. Interestingly while the complexity of Verσ remains coNP-complete, as for the corresponding set-inclusion based semantics, CAσ and SAσ become easier (in ΘP2 and ∆P2 instead of ΣP2 and ΠP2 , respectively) under the cardinality based semantics c-pr and c-ss.
• We extend AF with sequences of priority rules allowing to reasoning about extensions (Section 5). We call the resulting framework AF with Priority rules (AFP). We show that AFP generalizes AF with the above discussed cardinality based semantics (c-pr and c-ss) as well as with the classical semantics (gr, co, pr, st, ss). That is, encoding such argumentation semantics in AFP means expressing priorities on the complete extensions of the underlying AF. Results concerning the complexity of the verification as well as

the credulous and skeptical acceptance problems in AFP are given in Section 5.3. Finally, in Section 5.4, PAF and AFP are combined by extending AFP with preferences between arguments that lead to preferences between extensions (with the same spirit of PAF). We show that the resulting framework, called AF with Priority rules and Preferences (AFP2 ), is able to capture existing and novel PAF semantics. The complexity of AFP2 is also investigated.

2 Preliminaries

We review the Dung's framework and its generalization with preferences (PAF), and recall some basic complexity classes.

2.1 Abstract Argumentation Framework

An abstract Argumentation Framework (AF) is a pair 〈A, Ω〉, where A is a (finite) set of arguments and Ω ⊆ A × A is a set of attacks (also called defeats). An AF can be seen as a directed graph, whose nodes represent arguments and edges represent attacks. 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, Ω〉 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) ∈ Ω; ii) acceptable w.r.t. E iff ∀b ∈ A with (b, a) ∈ Ω, ∃c ∈ E such that (c, b) ∈ Ω. The sets of defeated, acceptable and undecided arguments w.r.t. E are defined as follows (where Λ is understood): 1

• Def(E) = {a ∈ A | ∃b ∈ E . (b, a) ∈ Ω};
• Acc(E)={a ∈ A | ∀b∈A . (b, a) ∈ Ω ⇒ b ∈ Def(E)}.
• Undec(E)=A \ (E ∪ Def(E)). To simplify the notation, we will often use E+ and Eu to denote Def(E) and Undec(E), respectively.

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

• conflict-free iff E ∩ E+ = ∅;
• admissible iff it is conflict-free and E ⊆ Acc(E). Given an AF 〈A, Ω〉, a set E ⊆ A is an extension called:
• complete (co) iff it is conflict free and E = Acc(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 ∪ E+ = A or, equivalently, Eu = ∅;
• semi-stable (ss) iff it is a complete extension with a minimal set of undecided arguments, i.e., Eu 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(Λ)). With a little abuse of notation, in the following we also use gr(Λ) to denote the grounded extension. 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. For any AF Λ, st(Λ) ⊆ ss(Λ) ⊆ pr(Λ) ⊆ co(Λ) and gr(Λ) ∈ co(Λ). Note that stable (resp. semi-stable) extensions could be also defined as preferred extensions containing an empty (resp. minimal) set of undecided arguments.

1 For E ∈ co(Λ), Acc(E) (resp. Def(E), Undec(E)) is the set of arguments labelled as in (resp. out, undec) [Caminada, 2006].

Example 3 Let Λ = 〈A, Ω〉 be an AF where A = {a, b, c, d} and Ω = {(a, b), (b, a), (a, c), (b, c), (c, d), (d, c)}. The grounded extension is ∅ whereas the preferred extensions are {a, d} and {b, d}, which are also stable and semi-stable. ✷

Given an AF Λ = 〈A,Ω〉 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 Preference-based AFs

Several works generalizing Dung's AF to handle preferences over arguments have been proposed [Amgoud and Cayrol, 1998; 2002a; Amgoud and Vesic, 2011; 2014; Cyras, 2016; Silva et al., 2020].

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

For arguments a and b, a > b means that a is better than b. Two main approaches have been proposed to handle preferences in argumentation.

The first approach considers AF-based semantics and consists in first defining a defeat relation Ωi that combines attacks in Ω and preference relations, and then applying the usual semantics on the AF 〈A, Ωi〉. Here Ωi (with i ∈ [1, 4]) denotes one of the four mappings proposed in the literature [Amgoud and Cayrol, 2002a; Amgoud and Vesic, 2014; Kaci et al., 2018]. As discussed in the Introduction, in some cases these semantics fail to capture the expected meaning and, therefore, we will not further discuss them. We point out that the complexity of acceptance problems does not increase as the mapping to AF (i.e., building Ωi) is polynomial time.

The second approach to handle preferences considers extensions selection semantics for PAF [Amgoud and Vesic, 2014; Kaci et al., 2018]. Here, given a PAF 〈A,Ω,>〉, classical argumentation semantics are used to obtain extensions of the underlying AF 〈A, Ω〉, 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. There have been different proposals to define the best extensions, corresponding to different criteria to define ⪰.

Definition 2 Given a PAF 〈A,Ω,>〉, 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;

2 Equivalent definitions use as a primitive the partial preorder ≥ and then derive > [Amgoud and Vesic, 2014].

• 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 3 Given a PAF ∆ = 〈A, Ω, >〉, a semantics σ ∈ {gr, co, pr, st, ss}, and a criterion ∗ ∈ {d, e, k} for ⪰, the best σ-extensions of ∆ under criterion ∗ (denoted as σ∗(∆)) are the extensions E ∈ σ(〈A,Ω〉) such that there is no F ∈ σ(〈A, Ω〉) with F ≻ E.

Example 4 Consider the following three PAFs:

• ∆1 = 〈{a, b, c}, {(a, b), (b, a), (a, c)}, {a > b}〉,
• ∆2 = 〈{a, b, d}, {(a, b), (b, a), (b, d)}, {a > b}〉,
• ∆3 = 〈{a, b, c, d}, {(a, b), (b, a), (a, c), (b, d)}, {a > b}〉.

The preferred extensions for the underlying AFs Λi, ob-

tained from∆i by ignoring the preferences, are:

• pr(Λ1) = {E1 = {a}, E2 = {b, c}};
• pr(Λ2) = {E3 = {a, d}, E4 = {b}};
• pr(Λ3) = {E3 = {a, d}, E2 = {b, c}}.

The best preferred extensions are as follows:

• pre (∆1) = prk (∆1) = {E1}, prd (∆1) = {E1 , E2};
• prd (∆2) = prk (∆2) = {E3}, pre (∆2) = {E3 , E4};
• prk (∆3) = {E3}, pre (∆3) = prd (∆3) = {E3 , E2}. ✷

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,Ω,≥〉, 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 only deal with PAFs where relation ⪰ is not transitive as our proposal is intended to extend PAF, where ⪰ is not transitive for all the criteria of Definition 2 (e.g. KTV).

Observe that the preference relation makes sense only for multiple-status semantics, i.e. semantics prescribing more than one extension. In fact, for the unique-status grounded semantics, gr∗ (〈A, Ω, >〉) = gr(〈A, Ω〉) with ∗ ∈ {d, e, k}.

Verification and Credulous/Skeptical Acceptance Problems. The verification problem for PAF, denoted as Verσ with σ ∈ {co∗, pr∗, st∗, ss∗, gr∗} and ∗ ∈ {d, e, k}, extends that for AF by considering best extensions. Given a PAF ∆ = 〈A,Ω,>〉, Verσ consists in checking whether a set S ⊆ A belongs to σ(∆). Similarly, for a goal argument g ∈ A, the credulous (resp. skeptical) acceptance problem, denoted as CAσ (resp. SAσ), consists in deciding whether g belongs to any (resp. every) σ-extension in σ(∆).

2.3 Complexity Classes

We recall the main complexity classes used in the paper and, in particular, the definition of the classes ΣPh ,ΠPh and ∆Ph , with h ≥ 0 (see e.g. [Papadimitriou, 1994]):

• ΣP0 = ΠP0 =∆P0 = P; ΣP1 = NP and ΠP1 = coNP;
• ∆Ph =P ΣPh-1 , ΣPh =NP ΣPh-1 , and ΠPh =coΣPh , ∀h > 0.

Thus, P C (resp. NP C ) denotes the class of problems that can be solved in polynomial time using an oracle in the class C by a deterministic (resp. non-deterministic) Turing machine. The class ΘPh = ∆Ph [log n] denotes the subclass of ∆Ph containing the problems that can be solved in polynomial time by a deterministic Turing machine by performing a number of calls bounded by O(log n) to an oracle in the class ΣPh-1 . It holds that ΣPh ⊆ ΘPh+1 ⊆ ∆Ph+1 ⊆ ΣPh+1 ⊆ PSPACE and ΠPh ⊆ ΘPh+1 ⊆ ∆Ph+1 ⊆ ΠPh+1 ⊆ PSPACE.

3 Complexity of Acceptance Problems in PAF

We start with the following proposition showing that, irrespective of the preference relation >, best complete and grounded semantics for PAF coincide under elitist criterion, whereas best complete and best preferred semantics coincide under the democratic criterion; moreover, the grounded extension of the underlying AF is contained in the set of best complete extensions under KTV criterion.

Proposition 1 For any PAF ∆ = 〈A,Ω,>〉 it holds that i) coe(∆) = gr(〈A,Ω〉), ii) cod(∆) = prd (∆), and iii) gr(〈A, Ω〉) ∈ cok(∆).

We now characterize the complexity of the verification, credulous and skeptical acceptance problems for PAF. First, observe that the results of Proposition 1, and the fact that the grounded semantics prescribes exactly one extension, entail that Vercoe , CAcoe , and SAcoe are polynomial as these problems are equivalent to those for AF under the grounded semantics. Moreover, since cod(∆) = prd (∆) we will state the result for prd (∆) only.

Theorem 1 Verσ is coNP-complete for σ ∈ {cok, std, ste, stk, prd }, and ΠP2 -complete for σ ∈ {pre , prk , ssd, sse, ssk}.

The complexity of the verification problem helps in addressing the complexity of the credulous and skeptical acceptance problems, which is given in the following theorems.

Theorem 2 CAσ is i) ΣP2 -complete for σ ∈ {cok, std, ste, stk, prd }; ii) ΣP2 -hard and in ΣP3 for σ ∈ {pre , prk , ssd, sse, ssk}.

Theorem 3 SAσ is i) in P for σ ∈ {cok}; ii) ΠP2 -complete for σ ∈ {std, ste, stk, prd }; and iii) ΠP2 -hard and in ΠP3 for σ ∈ {pre , prk , ssd, sse, ssk}.

The results of the previous theorems, summarized in Table 1, show that the complexity of the three problems generally increases of one level in the polynomial hierarchy w.r.t that of AFs for multiple-status semantics (see [Dvor´ak and Dunne, 2017] for a survey on the complexity of AF).

4 Cardinality Based Semantics for AF

In this section we present new semantics for AF that are inspired by the criteria at the basis of preferred and semi-stable semantics, which refine complete semantics by selecting from the set of complete extensions, respectively, the ⊆-maximal sets and the sets having a ⊆-minimal set of undecided arguments. In particular, instead of comparing sets by set inclusion, we focus on a filtering mechanism based on the cardinality of complete extensions. As it will be clear in what follows, our proposals for AF semantics refine the well-known preferred and semi-stable semantics.

Before providing the formal definitions, we introduce a partial order on pairs of (natural) numbers. Given the numbers a, b, c, d, we say that i) (a, b) ≥ (c, d) iff a ≥ c and b ≥ d, and ii) (a, b) > (c, d) iff (a, b) ≥ (c, d) and either a > c or b > d. 3 Moreover, given two complete extensions E and F, we say that E ⪰ F (resp. E ≻ F) if (|E|, |E+|) ≥ (|F|, |F +|) (resp. (|E|, |E+|) > (|F|, |F +|)).

Definition 4 Given an AF Λ, a complete extension E ∈ co(Λ) is said to be:

• cardinality preferred (c-pr) iff there is no complete extension F of Λ such that F ≻ E;
• cardinality semi-stable (c-ss) iff there is no complete extension F of Λ such that |F u | < |Eu |;
• cardinality least-undecided (c-lu) iff it is a cardinality preferred extension with a minimum number of undecided elements, i.e., there is no cardinality preferred extension F of Λ such that |F u | < |Eu |.

Therefore, (i) c-pr semantics returns the complete extensions whose numbers of accepted and defeated arguments are pairwise maximum (instead of ⊆-maximal accepted arguments as for pr); (ii) c-ss returns the complete extensions whose number of undecided elements is minimum (instead of ⊆-minimal as for ss); and (iii) c-lu refines c-pr by minimizing the number of undecided arguments.

3 With a little abuse of notation, we use the same symbols ≤ and < to compare numbers and pairs of numbers, though ≤ defines a linear order on numbers and a partial order on pairs of numbers.

Cardinality based semantics are useful when the user would prefer "optimal" solutions. As as example, consider the AF obtained by adding argument sorbet and attack (meat, sorbet) to the AF of Example 1. There are three stable, preferred and semi-stable extensions, E1 = {fish, white, sorbet}, E2 = {fish, red, sorbet} and E3 = {meat, red}, representing possible menus. Assume now that the customer would like to have as many menu items as possible. Hence the best extensions according to the customer's criteria are E1 and E2. This is exactly what is obtained by using the cardinality preferred semantics (c-pr)- classical AF semantics are not able to express such kind of criteria.

The following proposition states the relationships between cardinality and classical semantics, summarized in Figure 2.

Proposition 2 For any AF Λ, it holds that:

i) c-lu(Λ) = c-ss(Λ); ii) st(Λ) ⊆ c-ss(Λ) ⊆ ss(Λ);

• iii) c-ss(Λ) ⊆ c-pr(Λ) ⊆ pr(Λ);
• iv) st(Λ) ̸= ∅ iff st(Λ) = c-ss(Λ) = ss(Λ).

As c-lu and c-ss semantics coincide, hereafter we do not explicitly deal with c-lu semantics.

Example 5 Continuing with Example 2, assume now that the party planner would like to invite 10 people (corresponding to arguments a, b, .., j) and that the conditions for attending the party are represented by the AF shown in Figure 2. Then, there are three complete extensions E1 = ∅, E2 = {a, g, i} and E3 = {b, d}, with E+ 1 = ∅, E+ 2 = {f, h, j} and E+ 3 = {c, e}. E2 and E3 are preferred and semi-stable extensions, but as E3 ≻ E2 only E3 is a c-pr and c-ss extension. ✷

For any AF Λ ss(Λ) ⊆ pr(Λ), and Proposition 2 tells us that c-pr(Λ) ⊆ pr(Λ). The next proposition shows that the sets ss(Λ), c-pr(Λ) and pr(Λ) are distinct.

Proposition 3

• There exists an AF Λ s.t. ss(Λ) ̸⊆ c-pr(Λ).
• There exists an AF Λ s.t. ss(Λ) ̸⊇ c-pr(Λ).
• There exists an AF Λ s.t. (ss(Λ) ∪ c-pr(Λ)) ⊂ pr(Λ).

Complexity of cardinality based semantics. The next theorem states the complexity of the verification and credulous and skeptical acceptance problems for AF under the two novel cardinality based semantics, i.e. c-pr and c-ss.

Theorem 4

• V erσ is coNP-complete for σ ∈ {c-pr, c-ss}.
• Both CAc-pr andSAc-pr are ΘP2 -hard and in ∆P2 .
• Both CAc-ss andSAc-ss are ΘP2 -complete.

It turns out that, under standard complexity assumptions, computing credulous and skeptical acceptance under the cardinality based semantics c-pr and c-ss is easier than under classical maximal-set semantics pr and ss.

5 AF with Priority Rules

In this section we extend AF with priority rules that allow us to express several kinds of desiderata among extensions, e.g. expressing the above-discussed cardinality based semantics as well as the classical AF semantics. Preferences between arguments are then considered in Subsection 5.4.

5.1 Syntax

Priority rules define a priority between two extensions on the base of the satisfaction of a first order formula. Our formulae are built by considering variables denoting sets of arguments and variables denoting single arguments, logical connectives ∧, ∨ and ¬, built-in predicates and functions operating on sets of arguments as described next.

The vocabulary consists of finite sets of (constant) arguments, argument variables, set variables, built-in predicates and functions and natural numbers in the interval [0, |A|], where A is the set of arguments. In the following, arguments, argument variables, and set variables are denoted by lowercase letters a, b, c, d, lowercase letters x, y, z, and uppercase letters E, F, G, respectively. Therefore, we have simple terms (constant arguments and variable arguments) and set terms (set variables). The built-in (binary, infix) predicates are:

• ∈ (predicate in): x ∈ E checks if x belongs to set term E;
• comparison predicates >, ≥, <, ≤, to compare natural numbers (got by cardinality function applied to sets, see below);
• comparison predicates = and ̸= to compare terms.

The built-in functions are Acc, Def and Undec defined earlier for AFs and the unary cardinality function |S| computing the number of elements in S.

Definition 5 For an AF Λ = 〈A, Ω〉, a priority rule is of the form E ⊒ F ← body, where E and F are two distinct set variables and body is a quantified first order formula using simple terms, set variables E and F, predicates and functions, where E and F range over co(Λ), and argument variables range over A.

Example 6 Some examples of priority rules are:

Recall that we use E+ and Eu as shorthand for Def(E) and Undec(E). We also use the shorthand ̸∈ since x ̸∈ E ≡ ¬(x ∈ E). Finally, we may use the predicates ⊂, ⊆ to compare set terms as shorthands for the corresponding quantified first order formulae, e.g. F ⊆ E ≡ ∀x . x ̸∈ F ∨ x ∈ E.

Definition 6 An AF with Priority rules (AFP) is a triple 〈A,Ω,Φ〉, where 〈A,Ω〉 is an AF and Φ = [ϕ1, ..., ϕn] is a linearly ordered set of priority rules (with n ≥ 0).

5.2 Semantics

The semantics of AFPs is given by extensions which are 'prioritized' w.r.t. partially ground instances of priority rules, as explained in what follows.

For any AFP ∆ = 〈A,Ω,Φ〉, let Λ = 〈A,Ω〉 be the AF associated with ∆, pgroundΛ(Φ) (or simply pground(Φ) whenever Λ is understood) denotes the set of partially grounded priority rules derived from Φ by replacing head set variables with constant set terms (i.e. complete extensions). Furthermore, groundΛ(Φ) denotes the set of ground rules derived from pgroundΛ(Φ) by making variable-free the body of priority rules, as illustrated in the following example.

Example 7 Consider the AFP ∆ = 〈A = {a, b, c}, Ω = {(a, b), (b, a)}, Φ = [E ⊒ F ← ∀x.(x ̸∈ F) ∨ (x ∈ E)]〉. Here, set variables E and F take values from co(〈A,Ω〉) = {{c}, {a, c}, {b, c}}. For the partially grounded priority rule {a, c} ⊒ {c} ← ∀x.(x ̸∈ {c}) ∨ (x ∈ {a, c}), the ground rule is as follows:

The body of the ground rule is true. Its intuitive meaning is that {a, c} is in some sense better than {c}. ✷

Before defining the semantics of an AFP, we introduce some notations. Let 〈A,Ω, [ϕ]〉 be an AFP, C = co(〈A,Ω〉), and E, F ∈ C two complete extensions. Then E ⪰ F w.r.t. ϕ if there exists a partially ground instantiation of ϕ of the form E ⊒ F ← body such that body evaluates to true. Moreover, E ≻ F (w.r.t. ϕ) if E ⪰ F and F ̸⪰ E; E ∈ C is a prioritized extension w.r.t. ϕ if there exists no extension F ∈ C such that F ≻ E. We use βϕ(C) to denote the set of prioritized extensions in C w.r.t. ϕ.

Definition 7 Given an AFP ∆ = 〈A, Ω, Φ = [ϕ1, ..., ϕn]〉, the set of prioritized extensions of ∆ w.r.t. Φ is given by βϕn (...βϕ1 (co(〈A, Ω〉)...) and is denoted by co(〈A, Ω, Φ〉).

We do not consider transitivity of relation ⊒ and focus on explicit prioritized rules stating e.g. E is as good as F. A transitive closure of ⊒ would require to (iteratively) adding a ground prioritized rule E ⊒ F ← body1, body2 for each pair of ground rules E ⊒ G ← body1 and G ⊒ F ← body2, which can yield an exponential blow-up in the number of prioritized rules. Nonetheless, if needed, transitivity can still be stated by explicitly including the transitive closure in Φ.

AF semantics can be easily expressed in AFP; the encoding for st, that may admit no extensions, is given separately.

Proposition 4 For any AF Λ = 〈A, Ω〉 and σ ∈ {gr, pr, ss, c-pr, c-ss}, it holds that σ(Λ) = co(〈A, Ω, [ϕσ]〉) with:

• ϕgr = E ⊒ F ←F ⊇ E;
• ϕpr = E ⊒ F ←F ⊆ E;
• ϕss = E ⊒ F ←Eu ⊆ F u ;
• ϕc-pr = E ⊒ F ← (|F | > |E| ∧ |F +| ≥ |E+|) ∨
• (|F | ≥ |E| ∧ |F +| > |E+|); · ϕc-ss = E ⊒ F ← |Eu | ≤ |F u |.

Proposition 5 For any AF Λ = 〈A, Ω〉, let A′ = A ∪ {α, α} and Ω′ = Ω ∪ {(α, α), (α, α)} ∪ {(α, a) | a ∈ A}. Let ϕst = E ⊒ F ← Eu ⊆ F u ∧ α ∈ E. It holds that st(Λ)= {∅, if {α} ∈ co(〈A′ ,Ω′ , [ϕst]〉); {E \ {α} | E ∈ co(〈A′ , Ω′ , [ϕst]〉)}, otherwise.

5.3 Acceptance and Verification Problems in AFP

Given an AFP ∆ and a set S of arguments, the prioritized verification problem, denoted as PV , is the problem of deciding whether S ∈ co(∆), i.e. S is a prioritized extension of ∆. Moreover, given an argument g, the prioritized credulous (resp. skeptical) acceptance problem, denoted as PCA (resp. PSA), is the problem of deciding whether g belongs to any (resp. all) prioritized extension in co(∆).

Theorem 5 For any AFP 〈A,Ω,Φ〉, PV (resp. PCA, PSA) is in ΠP|Φ| (resp. ΣP|Φ|+1 , ΠP|Φ|+1 ).

It is worth noting that in our complexity analysis the input consists of three sets and its size is |A| + |Ω| + |Φ|. That is, the number of variables in the body of a rule is considered bounded by a constant, i.e. not part of the input, thus grounding a rule as well as its evaluation is polynomial. Though this can be seen as a limitation, in practice, the number of variables needed in a rule can be reasonably bounded by a constant. As a matter of fact, at most two variables per rule are used in all our examples and in the semantics encodings in Propositions 4 and 5, as well as in Proposition 6 below.

Tighter complexity bounds can be obtained by using the result of Proposition 4 that entails that for any AFP 〈A,Ω,Φ〉, with |Φ| = 1, PV (resp. PCA, PSA) is coNP-complete (resp. ΣP2 -complete, ΠP2 -complete). Specifically, the hardness results can be shown by providing a reduction from Verss (resp. CAss, SAss) for AF [Dvor´ak and Dunne, 2017] to our problem with Φ = [ϕss].

5.4 Combining Preferences with Priorities

We extend AFP with preferences between pairs of arguments. Specifically, we allow the use of the predicate > introduced for PAF to compare arguments in the body of priority rules.

Definition 8 An AF with Priority rules and Preferences (AFP2 ) is a tuple 〈A,Ω,Φ,>〉, where 〈A,Ω,Φ〉 is an AFP and > is a strict partial order over A.

Example 8 The priority rule E ⊒ F ← ∃x, y . (x ∈ E) ∧ (y ∈ F )∧(x > y), which uses preferences among arguments, states that E is as good as F if there is an argument in E which is preferred to an argument in F . ✷

The following proposition states that PAF semantics can be encoded in AFP2 . Particularly, the set of best σ-extensions of a given PAF can be defined by filtering out from the set of complete extension of an AFP2 those that follow the priority rules (i) ϕσ encoding the chosen complete-based semantics σ (cf. Proposition 4), and (ii) ϕ∗ encoding one of the preference criteria (i.e. deterministic, elitist and KTV of Definition 2).

Proposition 6 For any PAF ∆ = 〈A,Ω,>〉, ∗ ∈ {d, e, k} and σ ∈ {co, gr, pr, ss}, it holds that σ∗(∆) = co(〈A,Ω, [ϕσ, ϕ∗],>〉) where ϕσ is empty for σ = co and as defined in Proposition 4 for σ ∈ {gr, pr, ss}, and:

• ϕd = E ⊒ F ← ∀y ∈ F \ E ∃x ∈ E \ F . x > y;
• ϕe = E ⊒ F ← ∀x ∈ E \ F ∃y ∈ F \ E . x > y;
• ϕk = E ⊒ F ← ¬(∃x ∈(F \ E) ∃y ∈(E\ F ) . x > y).

Moreover, st∗(∆) = ∅ if {α} ∈ co(〈A′ ,Ω′ , [ϕst]〉); otherwise st∗(∆) = {E \ {α} | E ∈ co(〈A′ ,Ω′ , [ϕst, ϕ∗]〉)}, where A′ , Ω′ , ϕst are as in Proposition 5.

The complexity of AFP2 does not increase w.r.t. that of AFP. Proposition 7 For any AFP2 〈A,Ω,Φ,>〉, PV (resp. PCA, PSA) is in ΠP|Φ| (resp. in ΣP|Φ|+1 , in ΠP|Φ|+1 ).

6 Conclusions and FutureWorks

We introduced a general argumentation framework (AFP2 ) where priorities between complete extensions as well as preferences between individual arguments can be expressed.

AFP2 extends the research generalizing the Dung's framework for allowing preferences over arguments [Amgoud and Cayrol, 2002a; 2002b; Kaci et al., 2018; Modgil, 2009; Amgoud and Vesic, 2011]. Priorities and preferences in AFP2 are handled as in logic programming, where in answer set and circumscription approaches they are exploited to filter out the best models [Brewka and Eiter, 1999; Delgrande et al., 2003; Eiter et al., 2003; Sakama and Inoue, 2000; Brewka et al., 2003; Greco et al., 2007] and in [Brewka et al., 2015] users may also extend the ASP system to define their own preference ordering through a set of primitives. Preferences can be also expressed in value-based AFs [Bench-Capon, 2003; Dunne and Bench-Capon, 2004], where each argument is associated with a numeric value, and a set of possible orders (preferences) among the values is defined. In [Dunne et al., 2011; Coste-Marquis et al., 2012] weights are associated with attacks, and new semantics extending the classical ones are proposed-we plan to investigate the connection between the above-mentioned frameworks and AFP2 in future work.

As for cardinality based semantics, cardinality-minimum sets of arguments have been considered in [Caminada and Dunne, 2020; Dvor´ak and Wallner, 2020] where the complexity of identifying strongly admissible sets with bounded or minimal size is investigated, and computational approaches are provided to minimize the steps of a discussion [Caminada et al., 2016]. Similarly to our language, YALLA [de SaintCyr et al., 2016] allows to write logic formulae useful for reasoning on extensions under AF semantics. However, while AFP2 is designed to compare complete extensions, YALLA is designed for more general purposes, such as describing AF graphs, structural semantics (i.e. semantics based on the attack relation), and also changes in argumentation systems.

We are interested in exploring the relationship between AFP2 and rich PAF [Amgoud and Vesic, 2014], an extension of PAF providing two separate sets of preferences: one containing preferences used to generate a "repaired" AF, and one containing preferences used to select the best extensions. Moreover, following [Mailly and Rossit, 2020] that recently investigates to what extent preferences can be blended with ranking semantics, it would be interesting to explore the relationship between AFP2 and ranking semantics [Bonzon et al., 2016]. Also, we believe that the idea behind AFP2 concerning priorities on extensions, i.e. preferences between solutions, could be explored for structured argumentation formalisms [Prakken and Sartor, 1997; Modgil and Prakken, 2013; Toni, 2014; Garcia et al., 2020; Heyninck and Strasser, 2021; Alfano et al., 2021a] where preferences are typically used to resolve attacks into defeats between arguments. As for implementations of our framework, given the connection between AF semantics and LP models [Caminada et al., 2015; Alfano et al., 2020b], ASP implementations such as DLV and potassco that support cardinality-based semantics can be used to define encodings for AFP semantics by extending those for AF [Dvor´ak et al., 2020]. Finally, we plan to investigate preferences in incomplete AF [Fazzinga et al., 2020; Alfano et al., 2022], probabilistic AF [Fazzinga et al., 2015; Alfano et al., 2020a], and AF with constraints [Alfano et al., 2021b].