meat white red white red beer white red beer Example 1. Consider the AF Λ1 = ⟨{fish, meat, red, white}, {(fish, meat), (meat, fish), (meat, white), (white, red), (red, white)}⟩, whose corresponding graph is shown in Figure 1(left-hand side). 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 six complete extensions 0 = ∅, 1 = {fish, white}, 2 = {fish, red}, 3 = {meat, red}, 4 = {fish}, and 5 = {red}, which represent possible menus; 0 is the grounded extension, whereas 1, 2 and 3 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 3, which in a sense satisfies the person’s preference. □
AF has been extended to Preference-based Argumentation Framework (PAF) where preferences
stating that an argument is better than another are considered. Two main approaches have been
proposed in the literature to define PAF semantics. The first approach defines PAF semantics in
terms of that of an auxiliary AF [
Example 2. Consider a PAF consisting of the AF Λ2 = ⟨{white, red, beer}, {(white, red), (red, beer), (beer, white)}⟩ shown in Figure 1(center), and the preference white > beer that intuitively states that white is better than beer. According to the first approach for defining PAF semantics, for the auxiliary AF Λ2 shown in Figure 1(right-hand side), obtained from Λ2 by removing attack (beer, white) conflicting with preference white > beer, there is only one complete extension, that is {white, beer}. However, this is not an extension for the underlying AF Λ2 as it is not conflict-free w.r.t. Λ2 (since beer attacks white). □
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 for defining PAF
semantics that compares extensions w.r.t. preferences defined over arguments [
Contribution. We first discuss AF with Priority rules (AFP) [
Then, in Section 3.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). The resulting framework, called AF with Priority rules and Preferences (AFP2), is able to capture existing and novel PAF semantics. Finally, the complexity of the above-mentioned problems for the case of AFP2 framework is studied. Notably, the complexity of AFP2 does not increase w.r.t. that of AFP.
We assume the reader is familiar with the complexity classes used in the paper.
We review the Dung’s framework and its generalization with preferences (PAF).
An abstract Argumentation Framework (AF) is a pair ⟨, Ω⟩, where is a (finite) set of
arguments and Ω ⊆ × 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 [
Given an AF Λ = ⟨, Ω⟩ and a set ⊆ of arguments, an argument ∈ is said to be i) defeated w.r.t. iff ∃ ∈ such that (, ) ∈ Ω; ii) acceptable w.r.t. iff ∀ ∈ with (, ) ∈ Ω, ∃ ∈ such that (, ) ∈ Ω. The sets of defeated, acceptable and undecided arguments w.r.t. are defined as follows (where Λ is understood): ∙ Def() = { ∈ | ∃ ∈ . (, ) ∈ Ω}; ∙ Acc() = { ∈ | ∀ ∈ . (, ) ∈ Ω ⇒ ∈ Def()}. ∙ Undec() = ∖ ( ∪ Def()).
To simplify the notation, we will often use + and to denote Def() and Undec(), respectively.
Given an AF ⟨, Ω⟩, a set ⊆ of arguments is said to be conflict-free iff ∩ + = ∅; admissible iff it is conflict-free and ⊆ (). Given an AF ⟨, Ω⟩, a set ⊆ is an extension called: • complete (co) iff it is conflict free and = (); • preferred (pr) iff it is a ⊆ -maximal complete extension; • stable (st) iff it is a total complete extension, i.e., a complete extension such that ∪ + = or, equivalently, = ∅; • semi-stable (ss) iff it is a complete extension with a minimal set of undecided arguments, i.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(Λ)). 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.
Example 3. Let Λ3 = ⟨3, Ω3⟩ be an AF where 3 = {a, b, c, d} and Ω3 = {(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 Λ = ⟨, Ω⟩ and a semantics ∈ {co, pr, st, ss, gr}, the verification problem, denoted as , is deciding whether a set ⊆ is a -extension of Λ. Moreover, for a goal argument ∈ , the credulous (resp. skeptical) acceptance problem, denoted as (resp. ), is deciding whether belongs to any (resp. every) -extension of Λ. Clearly, gr and gr are identical problems.
Several works generalizing Dung’s AF to handle preferences over arguments have been proposed
[
Definition 1. A Preference-based Argumentation Framework (PAF) is a triple ⟨,Ω,>⟩ such that ⟨, Ω⟩ is an AF and > is a strict partial order (i.e. an irreflexive, asymmetric and transitive relation) over , called preference relation.
For arguments and , > means that is better than . 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
Ω that combines attacks in Ω and preference relations, and then applying the usual semantics
on the AF ⟨, Ω⟩. Here Ω (with ∈ [
The second approach to handle preferences considers extensions selection semantics for
PAF [
Definition 2.
Given a PAF ⟨, Ω, >⟩, for , ⊆ with ̸= , we have that under
∙ democratic () criterion [
Moreover, ≻ , if ⪰ and ̸⪰ .
Definition 3. Given a PAF Δ = ⟨, Ω, >⟩, a semantics ∈ {gr, co, pr, st, ss}, and a criterion * ∈ { , , } for ⪰ , the best -extensions of Δ under criterion * (denoted as * (Δ)) are the extensions ∈ (⟨, Ω⟩) such that there is no ∈ (⟨, Ω⟩) with ≻ .
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 Λ, obtained from Δ 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: pr(Δ1) = pr(Δ1) = {E1 }, pr(Δ1) = {E1 , E2 }; pr(Δ2) = pr(Δ2) = {E3 }, pr(Δ2) = {E3 , E4 }; pr(Δ3) = {E3 }, pr(Δ3) = pr(Δ3) = {E3 , E2 }. □
An alternative definition for PAF, based on that defined in [ 21] for logic programs with preferences, has been proposed in [22]. In this context a PAF is a triple ⟨, Ω, ≥⟩ , where ≥ is a reflexive and transitive relation and > if ≥ and ̸≥ . Moreover, the preference relation ⪰ over extensions is reflexive ( ⪰ ), transitive ( ⪰ and ⪰ implies ⪰ ) and satisfies the condition ⪰ if ∃ ∈ ∖ , ∃ ∈ ∖ such that ≥ and ∄ ∈ ∖ such that > . 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* (⟨, Ω, >⟩) = gr(⟨, Ω⟩) with * ∈ { , , }.
for PAF, denoted as with ∈ {co* , pr* , st* , ss* , gr* } and * ∈ { , , }, extends that for AF by considering best extensions. Given a PAF Δ = ⟨, Ω, >⟩, consists in checking whether a set ⊆ belongs to (Δ), where (Δ) is the set of best -extensions of PAF Δ. Similarly, for a goal argument ∈ , the credulous (resp. skeptical) acceptance problem, denoted as (resp. ), consists in deciding whether belongs to any (resp. every) -extension in (Δ).
The complexity of the verification as well as credulous and skeptical acceptance problems for
PAF under the democratic, elitist, and KTV criteria for multi-status semantics ∈ {co, pr, st, ss}
is presented in [
In this section we extend AF with priority rules that allow us to express several kinds of desiderata among extensions, e.g. expressing classical AF semantics. Preferences between arguments are then considered in Subsection 3.4.
A priority rule defines a priority between two extensions on the base of the satisfaction of a ifrst 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, ||], where is the set of arguments. In the following, arguments, argument variables, and set variables are denoted by lowercase letters , , , , lowercase letters , , , and uppercase letters , , , 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): ∈ checks if belongs to set term ; ∙ 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 || computing the number of elements in .
Definition 4. For an AF Λ = ⟨, Ω⟩, a priority rule is an expression of the form ⊒ ← , where and are two distinct set variables and is a quantified first order formula using simple terms, set variables and , predicates and functions, where and range over co(Λ), and argument variables range over .
Example 5. Examples of priority rules are: 1 = ⊒ ← ∀ . ¬( ∈ ) ∨ ( ∈ ); 2 = ⊒ ← ∀ . ¬( ∈ +) ∨ ( ∈ +); and 3 = ⊒ ← | | ≥ | |. □
We use + and as shorthand for Def() and Undec(). We also use the shorthand ̸∈ since ̸∈ ≡ ¬ ( ∈ ). Finally, we may use the predicates ⊂ , ⊆ to compare set terms as shorthands for the corresponding quantified first order formulae, e.g. ⊆ ≡ ∀ . ̸∈ ∨ ∈ . Definition 5. An AF with Priority rules (AFP) is a triple ⟨, Ω, Φ⟩, where ⟨, Ω⟩ is an AF and Φ = [ 1, ..., ] is a linearly ordered set of priority rules (with ≥ 0).
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 Δ = ⟨, Ω, Φ⟩, let Λ = ⟨, Ω⟩ be the AF associated with Δ, Λ(Φ) (or simply (Φ) 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, Λ(Φ) denotes the set of ground rules derived from Λ(Φ) by making variable-free the body of priority rules, as illustrated in the following example. Example 6. Consider the AFP Δ6 = ⟨6, Ω6, Φ6⟩ with 6 = {a, b, c}, Ω6 = {(a, b), (b, a)}, and Φ6 = [ ⊒ ← ∀ .( ̸∈ ) ∨ ( ∈ )]⟩. Here, set variables and take values from co(⟨6, Ω6⟩) = {{c}, {a, c}, {b, c}}. For the partially grounded priority rule: {a, c} ⊒ {c} ← ∀ {a, c} ⊒ {c} ←
x.(x ̸∈ {c}) ∨ (x ∈ {a, c}), the ground rule is as follows: ((a ̸∈ {c}) ∨ (a ∈ {a, c})) ∧ ((b ̸∈ {c}) ∨ (b ∈ {a, c})) ∧ ((c ̸∈ { }
c ) ∨ (c ∈ {a, c})).
The body of the ground rule is true. Its intuitive meaning is that {a, c} is “better” than {c}. □ Before defining the semantics of an AFP, we introduce some notations. Let ⟨, Ω, [ ]⟩ be an AFP, = co(⟨, Ω⟩), and , ∈ two complete extensions. Then ⪰ w.r.t. if there exists a partially ground instantiation of of the form ⊒ ← such that evaluates to true. Moreover, ≻ (w.r.t. ) if ⪰ and ̸⪰ ; ∈ is a prioritized extension w.r.t. if there exists no extension ∈ such that ≻ . We use () to denote the set of prioritized extensions in w.r.t. .
Definition 6. Given an AFP Δ = ⟨, Ω, Φ = [ 1, ..., ]⟩, the set of prioritized extensions of Δ w.r.t. Φ is given by (... 1 (co(⟨, Ω⟩)...) and is denoted by co(⟨, Ω, Φ⟩).
We do not consider transitivity of relation ⊒ and focus on explicit prioritized rules stating
e.g. is as good as . A transitive closure of ⊒ would require to (iteratively) adding a ground
prioritized rule ⊒ ← 1, 2 for each pair of ground rules ⊒ ← 1 and
⊒ ← 2, which can yield an exponential blow-up in the number of prioritized rules.
Nonetheless, if needed, transitivity can still be stated by including the transitive closure in Φ.
Encoding AF semantics in AFP. As shown below, AF semantics can be easily expressed
in AFP; the encoding for st, that may admit no extensions, is given separately. As shown in [
Proposition 1. For AF Λ = ⟨, Ω⟩ and ∈ {gr, pr, ss}, it holds that (Λ) = co(⟨, Ω, [ ]⟩) with: gr = ⊒ ← ⊇ ; pr = ⊒ ← ⊆ ; ss = ⊒ ← ⊆ . Proposition 2. For any AF Λ = ⟨, Ω⟩, let ′ = ∪ {, } and Ω′ = Ω ∪ {(, ), (, )} ∪ {(, ) | ∈ }. Let st = ⊒ ← ⊆ ∧ ∈ . It holds that st(Λ) = ∅ if { } ∈ co(⟨′, Ω′, [ st]⟩); otherwise st(Λ) = { ∖ { } | ∈ co(⟨′, Ω′, [ st]⟩)}.
Given an AFP Δ and a set of arguments, the prioritized verification problem, denoted as , is the problem of deciding whether ∈ co(Δ), i.e. is a prioritized extension of Δ. Moreover, given an argument , the prioritized credulous (resp. skeptical) acceptance problem, denoted as (resp. ), is the problem of deciding whether belongs to any (resp. all) prioritized extension in co(Δ).
Theorem 1. For any AFP ⟨, Ω, Φ⟩, (resp. , ) is in Π|Φ| (resp. Σ|Φ|+1, Π|Φ|+1).
In our complexity analysis the input consists of three sets and its size is || + |Ω| + |Φ|. 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 1 and 2, as well as in Proposition 3 below.
Tighter complexity bounds can be obtained by using the result of Proposition 1 that entails that for any AFP ⟨, Ω, Φ⟩, with |Φ| = 1, (resp. , ) is coNP-complete (resp. Σ2-complete, Π2-complete). Specifically, the hardness results can be shown by providing a reduction from ss (resp. ss, ss) for AF [23] to our problem with Φ = [ ss].
We extend AFP with preferences between arguments. Specifically, we allow the use of the predicate > introduced for PAF to compare arguments in the body of priority rules. Definition 7. An AF with Priority rules and Preferences (AFP2) is a tuple ⟨, Ω, Φ, >⟩, where ⟨, Ω, Φ⟩ is an AFP and > is a strict partial order over .
Example 7. The priority rule ⊒ ← ∃ , . ( ∈ ) ∧ ( ∈ ) ∧ ( > ), which uses preferences among arguments, states that is as good as if there is an argument in which is preferred to an argument in . □
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 completebased semantics (cf. Proposition 1), and (ii) * encoding one of the preference criteria (i.e. deterministic, elitist and KTV of Definition 2).
Proposition 3. For any PAF Δ = ⟨, Ω, >⟩, * ∈ { , , } and ∈ {co, gr, pr, ss}, it holds that * (Δ) = co(⟨, Ω, [ , * ], >⟩) where is empty for = co and as defined in Proposition 1 for ∈ {gr, pr, ss}, and: ∙ = ⊒ ← ∀ ∈ ∖ ∃ ∈ ∖ . > ; ∙ = ⊒ ← ∀ ∈ ∖ ∃ ∈ ∖ . > ; ∙ = ⊒ ← ¬ (∃ ∈ ( ∖ ) ∃ ∈ ( ∖ ) . > ).
Moreover, st* (Δ) = ∅ if { } ∈ co(⟨′, Ω′, [ st]⟩); otherwise st* (Δ) = { ∖ { } | ∈ co(⟨′, Ω′, [ st, * ]⟩)}, where ′, Ω′, st are as in Proposition 2.
Interestingly, the complexity of AFP2 does not increase w.r.t. that of AFP [
We believe that the idea behind AFP2 concerning priorities on extensions, i.e. preferences
between solutions, could be explored for structured argumentation formalisms [24, 25, 26, 27, 28,
29, 30] 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 [31, 32], ASP systems such as DLV and potassco that support cardinality-based semantics
can be used to define encodings for AFP semantics by extending those for AF [ 33]. Finally, we
plan to investigate preferences (possibly conditioned ones [34, 35, 36]) in incomplete AF [
Log. Comput. 25 (2015) 251–301. [23] W. Dvorák, P. E. Dunne, Computational problems in formal argumentation and their complexity, FLAP 4 (2017). [24] H. Prakken, G. Sartor, Argument-based extended logic programming with defeasible priorities, J. Appl. Non Class. Logics 7 (1997) 25–75. [25] S. Modgil, H. Prakken, A general account of argumentation with preferences, Artif. Intell.
195 (2013) 361–397. [26] F. Toni, A tutorial on assumption-based argumentation, Arg. & Comp. 5 (2014) 89–117. [27] G. Alfano, S. Greco, F. Parisi, G. I. Simari, G. R. Simari, Incremental computation of warranted arguments in dynamic defeasible argumentation: the rule addition case, in: Proc. of ACM SAC, 2018, pp. 911–917. [28] A. J. Garcia, H. Prakken, G. R. Simari, A comparative study of some central notions of
ASPIC+ and DeLP, Theory Pract. Log. Program. 20 (2020) 358–390. [29] J. Heyninck, C. Strasser, A comparative study of assumption-based argumentative approaches to reasoning with priorities, FLAP 8 (2021) 737–808. [30] G. Alfano, S. Greco, F. Parisi, G. I. Simari, G. R. Simari, Incremental computation for structured argumentation over dynamic DeLP knowledge bases, AI 300 (2021) 103553. [31] M. Caminada, S. Sá, J. F. L. Alcântara, W. Dvorák, On the equivalence between logic programming semantics and argumentation semantics, IJAR 58 (2015) 87–111. [32] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On the semantics of abstract argumentation frameworks: A logic programming approach, TPLP 20 (2020) 703–718. [33] W. Dvorák, S. A. Gaggl, A. Rapberger, J. P. Wallner, S. Woltran, The ASPARTIX system suite, in: Proc. of COMMA, 2020, pp. 461–462. [34] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, Abstract argumentation framework with conditional preferences, in: Proc. of AAAI, 2023, p. (to appear). [35] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)cp-nets:
Pareto and majority voting, Artif. Intell. 272 (2019) 101–142. [36] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)cp-nets:
Max and rank voting, Artif. Intell. 303 (2022) 103636. [37] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, Incomplete argumentation frameworks:
Properties and complexity, in: Proc. of AAAI, 2022, pp. 5451–5460. [38] B. Fazzinga, S. Flesca, F. Parisi, On the complexity of probabilistic abstract argumentation frameworks, ACM Trans. Comput. Log. 16 (2015) 22:1–22:39. [39] B. Fazzinga, S. Flesca, F. Furfaro, Complexity of fundamental problems in probabilistic abstract argumentation: Beyond independence, Artif. Intell. 268 (2019) 1–29. [40] B. Fazzinga, S. Flesca, F. Furfaro, Probabilistic bipolar abstract argumentation frameworks: complexity results, in: Proc. of IJCAI, 2018, pp. 1803–1809. [41] G. Alfano, M. Calautti, S. Greco, F. Parisi, I. Trubitsyna, Explainable acceptance in probabilistic abstract argumentation: Complexity and approximation, in: Proc. of KR, 2020, pp. 33–43.