=Paper=
{{Paper
|id=Vol-3419/paper4
|storemode=property
|title=Abstract Argumentation Framework with Priority Rules and Preferences
|pdfUrl=https://ceur-ws.org/Vol-3419/paper4.pdf
|volume=Vol-3419
|authors=Gianvincenzo Alfano,Sergio Greco,Francesco Parisi,Irina Trubitsyna
|dblpUrl=https://dblp.org/rec/conf/aiia/AlfanoGPT22a
}}
==Abstract Argumentation Framework with Priority Rules and Preferences==
<pdf width="1500px">https://ceur-ws.org/Vol-3419/paper4.pdf</pdf>
<pre>
Abstract Argumentation Framework with
Priority Rules and Preferences
Gianvincenzo Alfano, Sergio Greco, Francesco Parisi and Irina Trubitsyna
Department of Informatics, Modeling, Electronics and System Engineering (DIMES),
University of Calabria, Rende, Italy


                                      Abstract
                                      Dung’s abstract Argumentation Framework (AF) has emerged as a central formalism for argumentation in
                                      AI. In this paper, we discuss a recently proposed framework called AF with Priority rules (AFP) [1] that
                                      extends AF with sequences of priority rules which are able to express several kinds of desiderata among
                                      AF extensions. Using AFP, AF semantics can be viewed as ways to express priorities among extensions.
                                      We extend AFP by presenting AF with Priority rules and Preferences (AFP2 ), where also preferences
                                      over arguments can be used to define priority rules. We study the complexity of the verification as well as
                                      credulous and skeptical acceptance problems for AFP and AFP2 .

                                      Keywords
                                      Abstract Argumentation, Priorities, Preferences, Computational Complexity.




1. Introduction
Abstract argumentation has emerged as one of the major fields in AI [2]. In particular, recent
years have witnessed intensive formal study, development and application of Dung’s abstract
Argumentation Framework (AF) in various directions [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]. Dung’s
framework is recognized as a simple, yet powerful formalism for modelling disputes between
two or more agents. An AF consists of a set 𝐴 of arguments and an attack relation Ω ⊆ 𝐴 × 𝐴
that specifies conflicts between arguments (if argument 𝑎 attacks argument 𝑏, then 𝑏 is acceptable
only if 𝑎 is not). We can think of an AF as a directed graph whose nodes represent arguments
and edges 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, 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.


Discussion Papers - 21st International Conference of the Italian Association for Artificial Intelligence (AIxIA 2022),
November 28- December 2, 2022, Udine, Italy
$ g.alfano@dimes.unical.it (G. Alfano); greco@dimes.unical.it (S. Greco); fparisi@dimes.unical.it (F. Parisi);
i.trubitsyna@dimes.unical.it (I. Trubitsyna)
                                    © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
 CEUR
 Workshop
 Proceedings
               http://ceur-ws.org
               ISSN 1613-0073
                                    CEUR Workshop Proceedings (CEUR-WS.org)
          fish    meat    white   red     white   red     beer      white   red    beer


Figure 1: AF Λ1 of Example 1 (left), AFs Λ2 (center) and Λ2 (right) of Example 2.

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 [13, 14, 15]. However, there are cases where this semantics may
give counterintuitive results as shown next.

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 [14, 15]. Following
this approach, we introduce a general framework for dealing with preferences and priority rules
in AF.

Contribution. We first discuss AF with Priority rules (AFP) [1] which extends AF with
sequences of priority rules allowing to reasoning about extensions. We show that AFP generalizes
AF with the classical semantics (i.e., gr, co, pr, st, ss). Encoding such argumentation semantics
in AFP means expressing priorities on the complete extensions of the underlying AF. Next, results
concerning the complexity of the verification as well as the credulous and skeptical acceptance
problems in AFP are given in Section 3.3.
   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.


2. Preliminaries
We review the Dung’s framework and its generalization with preferences (PAF).

2.1. Abstract Argumentation Framework
An abstract Argumentation Framework (AF) is a pair ⟨𝐴, Ω⟩, where 𝐴 is a (finite) set of argu-
ments 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 [16].
  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.

2.2. Preference-based AFs
Several works generalizing Dung’s AF to handle preferences over arguments have been proposed
[17, 13, 18, 14, 19, 20].

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 𝑖 ∈ [1, 4]) denotes one of the four mappings proposed in the
literature [13, 14, 15]. 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 Ω𝑖 )
is polynomial time.
   The second approach to handle preferences considers extensions selection semantics for
PAF [14, 15]. Here, given a PAF ⟨𝐴, Ω, >⟩, classical argumentation semantics are used to obtain
extensions of the underlying AF ⟨𝐴, Ω⟩, 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 ⟨𝐴, Ω, >⟩, for 𝐸, 𝐹 ⊆ 𝐴 with 𝐸 ̸= 𝐹 , we have that under
∙ democratic (𝑑) criterion [14]: 𝐸 ⪰ 𝐹 if ∀𝑏 ∈ 𝐹 ∖ 𝐸 ∃𝑎 ∈ 𝐸 ∖ 𝐹 such that 𝑎 > 𝑏;
∙ elitist (𝑒) criterion [14]: 𝐸 ⪰ 𝐹 if ∀𝑎 ∈ 𝐸 ∖ 𝐹 ∃𝑏 ∈ 𝐹 ∖ 𝐸 such that 𝑎 > 𝑏;
∙ KTV (𝑘) criterion [15]: 𝐸 ⪰ 𝐹 if ∀𝑎, 𝑏 ∈ 𝐴 the relation 𝑎 > 𝑏 with 𝑎 ∈ 𝐹 ∖ 𝐸 and 𝑏 ∈ 𝐸 ∖ 𝐹
 does not hold.
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 Λ𝑖 , ob-
tained 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 * ∈ {𝑑, 𝑒, 𝑘}.

Verification and Credulous/Skeptical Acceptance Problems. The verification problem
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 [1]. 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.


3. 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 classical AF semantics. Preferences between arguments are
then considered in Subsection 3.4.

3.1. Syntax
A priority rule defines 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, |𝐴|], 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).


3.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 Δ = ⟨𝐴, Ω, Φ⟩, 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} ← ∀x.(x ̸∈ {c}) ∨ (x ∈ {a, c}), the ground rule is as follows:
{a, c} ⊒ {c} ← ((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 [1],
AFP also encodes several cardinality-based semantics for AF.

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 ]⟩)}.

3.3. Acceptance and Verification Problems in AFP
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 ].

3.4. Combining Preferences with Priorities
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 complete-
based 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 Proposi-
tion 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 [1]. We have that,
for any AFP2 ⟨𝐴, Ω, Φ, >⟩, 𝑃𝑉 (resp. 𝑃𝐶𝐴, 𝑃𝑆𝐴) is in Π𝑝|Φ| (resp. in Σ𝑝|Φ|+1 , in Π𝑝|Φ|+1 ).
   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 [10, 37],
probabilistic AF [38, 39, 40, 41], and AF with constraints [9].
References
 [1] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On preferences and priority rules in abstract
     argumentation, in: Proc. of IJCAI, 2022, pp. 2517–2524.
 [2] D. Gabbay, M. Giacomin, G. R. Simari, M. Thimm (Eds.), Handbook of Formal Argumen-
     tation, volume 2, College Public., 2021.
 [3] D. Baumeister, M. Järvisalo, D. Neugebauer, A. Niskanen, J. Rothe, Acceptance in
     incomplete argumentation frameworks, Artif. Intell. (2021) 103470.
 [4] G. Alfano, S. Greco, F. Parisi, A meta-argumentation approach for the efficient compu-
     tation of stable and preferred extensions in dynamic bipolar argumentation frameworks,
     Intelligenza Artificiale 12 (2018) 193–211.
 [5] G. Alfano, S. Greco, F. Parisi, On scaling the enumeration of the preferred extensions of
     abstract argumentation frameworks, in: Proc. of ACM SAC, 2019, pp. 1147–1153.
 [6] G. Alfano, A. Cohen, S. Gottifredi, S. Greco, F. Parisi, G. R. Simari, Dynamics in abstract
     argumentation frameworks with recursive attack and support relations, in: Proc. of ECAI,
     2020, pp. 577–584.
 [7] G. Alfano, S. Greco, F. Parisi, Incremental computation in dynamic argumentation frame-
     works, IEEE Intell. Syst. 36 (2021) 80–86.
 [8] G. Alfano, S. Greco, Incremental skeptical preferred acceptance in dynamic argumentation
     frameworks, IEEE Intell. Syst. 36 (2021) 6–12.
 [9] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, Argumentation frameworks with strong and
     weak constraints: Semantics and complexity, in: Proc. of AAAI, 2021, pp. 6175–6184.
[10] B. Fazzinga, S. Flesca, F. Furfaro, Revisiting the notion of extension over incomplete
     abstract argumentation frameworks, in: Proc. of IJCAI, 2020, pp. 1712–1718.
[11] B. Fazzinga, S. Flesca, F. Furfaro, Abstract argumentation frameworks with marginal
     probabilities, in: Proc. of IJCAI, 2022, pp. 2613–2619.
[12] B. Fazzinga, S. Flesca, F. Furfaro, L. Pontieri, Process mining meets argumentation:
     Explainable interpretations of low-level event logs via abstract argumentation, Inf. Syst.
     107 (2022) 101987.
[13] L. Amgoud, C. Cayrol, Inferring from inconsistency in preference-based argumentation
     frameworks, J. Autom. Reason. 29 (2002) 125–169.
[14] L. Amgoud, S. Vesic, Rich preference-based argumentation frameworks, Int. J. Approx.
     Reason. 55 (2014) 585–606.
[15] S. Kaci, L. W. N. van der Torre, S. Villata, Preference in abstract argumentation, in: Proc.
     COMMA, 2018, pp. 405–412.
[16] P. M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic
     reasoning, logic programming and n-person games, Artif. Intell. 77 (1995) 321–358.
[17] L. Amgoud, C. Cayrol, On the acceptability of arguments in preference-based argumentation,
     in: Proc. of UAI, 1998, pp. 1–7.
[18] L. Amgoud, S. Vesic, A new approach for preference-based argumentation fra-meworks,
     Ann. Math. Artif. Intell. 63 (2011) 149–183.
[19] K. Cyras, Argumentation-based reasoning with preferences, in: PAAMS, 2016, pp. 199–
     210.
[20] R. Silva, S. Sá, J. F. L. Alcântara, Semantics hierarchy in preference-based argumentation
     frameworks, in: COMMA, 2020, pp. 339–346.
[21] C. Sakama, K. Inoue, Prioritized logic programming and its application to commonsense
     reasoning, Artif. Intell. 123 (2000).
[22] T. Wakaki, Preference-based argumentation built from prioritized logic programming, J.
     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 ap-
     proaches 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.

</pre>