On the Conditional Preference-based Argumentation Framework(Extended Abstract)0Gianvincenzo Alfano0Sergio Greco0Francesco Parisi0Irina Trubitsyna0DIMES Department, University of Calabria
,
Rende
,
Italy115119
Dung's abstract Argumentation Framework (AF) has emerged as a central formalism in the area of knowledge representation and reasoning. Preferences in AF allow to represent the comparative strength of arguments in a simple yet expressive way. Preference-based AF (PAF) has been proposed to extend AF with preferences of the form > , whose intuitive meaning is that argument is better than . In this paper we discuss the recently proposed Conditional Preference-based Argumentation Framework (CPAF) [1] that extends PAF by introducing conditional preferences of the form > ← informally stating that is better than whenever the condition expressed by is true. We discuss CPAF properties and complexity results of the well-known verification and acceptance problems under multiple-status argumentation semantics.
The first approach defines the PAF semantics in terms of
that of an auxiliary AF [
3, 4, 5
]. However, there are cases
Recent years have witnessed intensive formal study, de- where this semantics may give counterintuitive results (see
velopment and application of Dung’s abstract Argumen- e.g. Example 3 in [
1
]). The problem is that preferences
tation Framework (AF) in various directions [
2
]. An AF and attacks, in our opinion, describe different pieces of
consists of a set A of arguments and an attack relation knowledge and should be considered separately. This is
Ω ⊆ A × A that specifies conflicts over arguments (if carried out by the second approach comparing extensions
argument attacks argument , then is acceptable only w.r.t. preferences defined over arguments [
3, 4, 5
].
if is not). Thus, an AF can be viewed as a directed Following this approach, the Conditional
Preferencegraph whose nodes represent arguments and edges repre- based AF (CPAF), an extension of AF (and PAF) with a set
sent attacks. The meaning of an AF is given in terms of of conditional preferences (CPs), has been recently
introargumentation semantics, e.g. the well-known grounded duced in [
1
]. Intuitively, the CPAF semantics prescribes as
(gr), complete (co), preferred (pr), stable (st), and semi- best -extensions (with ∈ {gr, co, pr, st, ss}) a
substable (ss) semantics. Intuitively, an argumentation se- set of the -extensions of the underlying AF that better
mantics tells us the sets of arguments (called -extensions, satisfy the conditional preferences.
with ∈ {gr, co, pr, st, ss}) that can collectively be As an example, consider the AF Λ 1 = ⟨{fish,
accepted to support a point of view in a dispute. For in- meat, white, red}, {(fish, meat), (meat, fish),
stance, for AF ⟨A, Ω ⟩ = ⟨{a, b}, {(a, b), (b, a)}⟩ having (white, red), (red, white)}⟩, describing what a
two arguments, a and b, attacking each other, there are two customer is going to have for lunch. (S)he will have
stable extensions, st(⟨A, Ω ⟩) = {{a}, {b}}, and neither either fish or meat, and will drink either white wine or
argument a nor b is skeptically accepted. To cope with red wine. Assume now that the customer expresses some
such situations, a possible solution is to provide means preferences about the menus: if (s)he will have meat
for preferring one argument to another. then would prefer to have red wine, whereas if (s)he
As an example, consider the AF Λ 2 = ⟨A2, Ω 2⟩ shown
in Figure 1 and the set Γ 2 consisting of the following CPs:
not feasible in general as we have a situation where the fish meat white red pie fruit
best stable extensions are not contained in the best
preferred extensions—this contradicts a well-known result Figure 1: AF Λ2 at the basis of the CPAF Δ2.
for AF stating that every stable extension is a preferred
extension [
7
]. This is also backed by our complexity
analysis entailing that CPAF cannot be reduced to AF. As
mentioned earlier, AF and preferences represent different fish > meat ← fruit | white > red ← fish.
pieces of knowledge, such as objective evidences and sub- Λ 2 has four preferred (and stable/semi-stable) extensions:
jective beliefs, which should be clearly distinguishable. 1 = {fish, white, pie}, 2 = {fish, white,
In fact, an AF represents a set of arguments and conflicts fruit}, 3 = {fish, red, fruit}, and 4 = {meat,
among them that leads to a set of consistent sets of ar- red, fruit} representing possible menus. Intuitively, we
guments that can be collectively accepted (i.e. the set of expect that the best preferred extensions according to the
extensions under a given argumentation semantics) as, for conditional preferences in Γ 2 are 1 and 2.
instance, the alternative menus of a restaurant. In contrast, The meaning of a CPAF ⟨, Ω , Γ ⟩ w.r.t. a given
argua set of preferences delivers the best extensions, e.g. best mentation semantics ∈ {gr,co, pr, st, ss} is given by
menus according to the customer’s preferences. considering the extensions that better satisfy Γ among the
We assume the reader is familiar with AF and PAF -extensions of the underlying AF ⟨, Ω ⟩. This is carried
semantics. We refer the interested reader to [
2
] for a out by extending the PAF comparison criteria between
comprehensive overview of abstract argumentation. extensions (i.e. democratic, elitist and KTV) according to
two different interpretations of the preference rules, that
are flat and closed interpretations. As discussed in what
AF with Conditional Preferences follows, differently from the flat interpretation, the closed
interpretation deals with the (transitive) closure of Γ .
Hereafter, we say that a (conflict-free) set of arguments
satisfies the body of a conditional preference (and
write |= ( )) iff the arguments that positively
(resp. negatively) occur in the body of belong to
(resp. are attacked by arguments in ).
A conditional preference (also called preference rule) in
tuitively represents the fact that an argument is better than
another whenever a condition expressed by a conjunction
of argument literals (i.e. an argument or its negation
¬) is satisfied. More formally, given an AF ⟨A, Ω ⟩, a
conditional preference (CP) is an expression of the form:
Definition 2. Given a CPAF ⟨A, Ω , Γ ⟩, for , ⊆ A
where1>1,22,← 1,.1..∧,· ··∧, 1,....,∧¬ a1re∧di·· s·∧tin¬ct arguments with ̸= , we have that ⪰ under
in A and , ≥ 0. 1 > 2 is said to be the • democratic () criterion:
head of the rule, whereas the conjunction of literals if ∀ ∈ ∖ ∃ ∈ ∖ and ∃ > ← ∈ Γ
1 ∧ · · · ∧ ∧ ¬1 ∧ · · · ∧ ¬ is called body. such that |= and |= ;
A (polynomial time verifiable) condition is imposed • elitist () criterion:
to avoid expressing CPs that can give counterintuitive if ∀ ∈ ∖ ∃ ∈ ∖ and ∃ > ← ∈ Γ
results. That is, a set of CPs is said to be well-formed if such that |= and |= ;
there exists a function : → N such that for each CP • KTV () criterion:
> ← in the set it holds that () () = () if ∀ , ∈ A ∄ > ← ∈ Γ such that ∈ ∖,
and () () ̸= () for each (or ¬) occurring in ∈ ∖ , |= , and |= .
. Intuitively, conditions () and () entail a form Moreover, ≻ if ⪰ and ̸⪰ .
of stratification of CPs. For instance, consider a CPAF
where the underlying AF has extensions {a, b} and {a, c}
and the (not well-formed) preferences c > b ← b and
c > b ← c. In this situation, one would expect that {a, c}
is preferred to {a, b}. However, as it will be clear after
introducing the semantics of CPAF, both extensions are
best-extensions. On the other hand, using the well-formed
preference c > b ← we obtain the expected solution.
For any CPAF ∆ = ⟨, Ω , Γ ⟩, best -extensions
under flat interpretation and criterion ∈ {, , } are
the extensions ∈ (⟨, Ω ⟩) such that there is no
∈ (⟨, Ω ⟩) with ≻ (under criterion ).
As an example, for the CPAF ∆ 2 = ⟨2, Ω 2, Γ 2⟩, we
have that 2 ≻ 3 and 3 ≻ 4 under democratic, elitist
and KTV criteria, whereas 1 ≻ 3 and 2 ≻ 4 under
KTV criterion. Thus, 1 and 2 are the best preferred
Definition 1. A Conditional Preference-based AF (CPAF) (and stable/semi-stable) extensions under any criteria.
is a triple ⟨, Ω , Γ ⟩, where ⟨, Ω ⟩ is an AF and Γ is a set
of (well-formed) conditional preferences.
Closed interpretation. The CPAF with flat interpre
tation does not generalize the PAF, in the sense that the
semantics of a CPAF ⟨, Ω , Γ ⟩ where Γ consists of
unconditional preferences (i.e. preference rules with empty
a CP, if ⊆ and |= , then |= .
co coNP-c Σ2-c Π2-c Several relationships arise between CPAF semantics.
co P P P Irrespective of the flat or closed interpretation, best
comco coNP-c Σ2-c P plete and grounded semantics for CPAF coincide under
st, st, st coNP-c Σ2-c Π2-c elitist criterion, whereas best complete and best preferred
sspr,psr,spr,ss coΠΠN22P--cc-c ΣΣ22Σ--hh2,,-cΣΣ33 ΠΠ22Π-- hh2,,-cΠΠ33 isdseitmciooannnattalilciyns,ectdhoeiinngcrtiohdueenusdenetddoeerfxtbtheeenstsdiceoomnmoopcfrlteahtteeicuecnxrdtieteenrrsliyiooinnn.gs
AAudnF-Table 1 der KTV criterion. Analogously to what holds for AF,
Complexity of verification and acceptance in CPAF. The the existence of at least one best-stable extension ensures
results under flat and closed interpretations coincide. that best-stable and best-semi-stable extensions coincide.
However, differently from AF semantics, the set of the
best stable (resp. semi-stable) extensions of a CPAF is not
body) may be not equivalent to considering a strict par- a proper subset of the set of the best preferred extensions
tial order over arguments as in PAF. In the following, we in general. This hold irrespective of the interpretation and
introduce a different semantics for CPAF, called closed preference criterion, suggesting that preferences cannot
interpretation, that generalizes that of PAF. be represented in (classical) AF in general, as there are
sit
The closed interpretation assumes that Γ denotes all uations where the best stable extensions are not contained
dependencies logically implied by it, that are elements in the best preferred extensions.
contained in the (transitive) closure of Γ , defined as: The complexity results reported in Table 1 show that
Γ * = Γ ∪ {1 > 3 ← 1 ∧ 2 | the verification and credulous/skeptical acceptance
prob{1 > 2 ← 1; 2 > 3 ← 2} ⊆ Γ * }. lems for CPAF are generally harder than those for AF.
Thus, the best extensions under closed interpretation, Verification and acceptance for CPAF are defined as for
denoted as * (∆ = ⟨, Ω , Γ ⟩), are obtained by using Γ * AF except that best extensions are considered instead of
instead of Γ , that is * (⟨, Ω , Γ ⟩) = (⟨, Ω , Γ * ⟩). regular ones. That is, given a CPAF ∆ = ⟨A, Ω , Γ ⟩,
un
It can be shown that CPAF semantics under closed in- der flat/closed interpretation i) the verification problem is
terpretation extend PAF semantics, and this holds under deciding whether a set of arguments ⊆ A belongs to
lfat interpretation if unconditional preferences represent- (∆) / * (∆) ; ii) the credulous (resp. skeptical)
acceping the closure of the PAF preferences are considered (i.e. tance problem is deciding whether an argument ∈ A
(⟨, Ω , >⟩) = * (⟨, Ω , Γ = { ←| ∈ > }⟩). belongs to any (resp. every) extension in (∆) / * (∆) .
When deciding between the flat or closed interpretation, Interestingly, the complexity of the vericfiation problem
it is crucial to consider the specific context in which the for CPAF does not depend on the flat or closed
interpreuser is operating and their level of familiarity with pref- tation. Moreover, the complexity bounds of the three
erence usage. The choice may vary depending on these considered problems for CPAF generally increases of one
factors. The closed interpretation offers a more concise level in the polynomial hierarchy w.r.t that of AF and
coinrepresentation of preferences, including (transitive) pref- cide with those known for PAF [
8
], though more general
erences that may not be immediately apparent to the user. preferences can be expressed in CPAF.
This results in a more comprehensive consideration of
preferences during the process. On the other hand, the
lfat interpretation gives the user direct control over the set Conclusion
of preferences to be taken into account. However,
transitive preferences must be explicitly provided by the user;
otherwise, they will be disregarded.
We have discussed the CPAF framework that extends PAF
with conditional preferences between arguments. In
addition to exploring the connections between CPAF and rich
PAF [
4
], as well as ranking semantics for AF [
9, 10
], an
Properties and Complexity interesting direction for future work is investigating
alterSeveral properties have been investigated for CPAF in [
1
]. native preference criteria for comparing extensions,
simi
A first property states that any conditional preference lar to those defined for comparing ASP models [ 11, 12].
having an head argument occurring in the body does Furthermore, we plan to examine conditional preferences
not play any role (under flat or closed interpretation). in other argumentation frameworks (including structured
Note that this kind of conditional preferences is not well- ones, as done in [13]) that share a semantic relationship
formed. That is, well-formed condition avoids using use- with AF [14, 15, 16, 17, 18, 19, 20, 21] as well as in a
less CPs. Moreover, the satisfaction of CPs are related dynamic setting [
22, 23, 24, 25, 26, 27, 28, 29, 30, 31
],
by subset inclusion, that is let and be two complete where objective evidence (underlying AF) and subjective
extensions of the same AF and = 1 > 2 ← be beliefs (conditional preferences) may change over time.
Acknowledgments We acknowledge the support tation
,
in: Proceedings of the 17th International(PE00000013)
, Spoke 9 -
Green-awareAI
,
under the tation and Reasoning
,
2020
, pp.
647
-
651
.
NRRPMUR program funded by the NextGenerationEU
. [11]
C.Sakama
,
K.Inoue
, Prioritized logic programming
ItalianNRRP
, Mission 4,
Component2
, Investment 1.5,
Intell
.
123
(
2000
).
call for the creation
and strengthening of 'Innovation [12]
G.Brewka
, I. Niemelä,
M.Truszczynski
, Answer
torial Decree n.
2021
/3277)
- project Tech4You - Tech-
International Joint Conference on Artificial Intelli-
nologies for climate change adaptation and quality of life gence
,
2003
, pp.
867
-
872
.
improvement, n.
ECS0000009
. This work reflects only [13]
P. M. Dung
,
P. M.Thang
,
T. C.Son
, On structured
can be considered responsible for them
.
Artificial Intelligence
,
2019
, pp.
2792
-
2800
. [14]
G.Alfano
,
S.Greco
,
F.Parisi
,
I. Trubitsyna
,
On the semantics of abstract argumentation frameworks: AReferences logic programming approach
,
Theory Pract. Log. Program
.
20
(
2020
)
703
-
718
.
[1]
G.Alfano
,
S.Greco
,
F.Parisi
,
I. Trubitsyna
, Ab- [15]
G.Alfano
,
S.Greco
,
F.Parisi
,
I. Trubitsyna
,
On acstract argumentation framework with conditional ceptance conditions in abstract argumentation framepreferences
,
in: Proc. of AAAI
,
2023
, pp.
6218
-
works
,
Information Sciences 625
(
2023
)
757
-
779
.
6227
. [16]
B.Fazzinga
,
S.Flesca
,
F.Furfaro
, Revisiting the
[2]
D.Gabbay
,
M.Giacomin
,
G. R.Simari
,
M.Thimm notion of extension over incomplete abstract argu
(Eds.),
Handbook of Formal Argumentation
, vol
- mentation frameworks
,
in: Proc. of IJCAI
,
2020
, pp.
ume 2
,
CollegePublications
,
2021
.
1712
-
1718
.
[3]
L.Amgoud
,
C.Cayrol
, Inferring from inconsistency [17]
G.Alfano
,
S.Greco
,
F.Parisi
,
I. Trubitsyna
,
Incomin preference-based argumentation frameworks
,
J. plete argumentation frameworks: Properties and Autom. Reason
.
29
(
2002
)
125
-
169
. complexity,
in: Proceedings of the Thirty-Sixth
[4]
L.Amgoud
, S. Vesic,
Rich preference-based argu- AAAI Conference on Artificial Intelligence
,
2022
, mentation frameworks,
Int. J. Approx. Reason
.
55
pp.
5451
-
5460
. (
2014
)
585
-
606
. [18]
B.Fazzinga
,
S.Flesca
,
F.Parisi
, On the complexity
[5]
S.Kaci
,
L. W. N. van derTorre
, S. Vesic, S. Villata,
of probabilistic abstract argumentation frameworks, Preference in abstract argumentation
,
in: Hand- ACM Trans. Comput. Log
.
16
(
2015
)
22
:
1
-
22
:
39
. book of Formal Argumentation, volume
2
, College [19]
G.Alfano
,
M.Calautti
,
S.Greco
,
F.Parisi
,
I. TruPublications
,
2021
. bitsyna, Explainable acceptance in probabilistic
[6]
M.Bernreiter
,
W.Dvorák
,
S.Woltran
,
Abstract ar- abstract argumentation: Complexity and approxigumentation with conditional preferences
,
in: Proc. mation, in: Proceedings of the 17th International of COMMA
,
2022
, pp.
92
-
103
. Conference on Principles of Knowledge Represen-
[7]
P. M.Dung
,
On the acceptability of arguments and tation and Reasoning
,
2020
, pp.
33
-
43
.
its fundamental role in nonmonotonic reasoning
, [20]
G.Alfano
,
M.Calautti
,
S.Greco
,
F.Parisi
,
I.Trulogic programming and n-person games, Artif
. Intell. bitsyna,
Explainable acceptance in probabilistic 77
(
1995
)
321
-
358
.
and incomplete abstract argumentation frameworks,
[8]
G.Alfano
,
S.Greco
,
F.Parisi
,
I. Trubitsyna
, On Artif. Intell. (
2023
)
103967. preferences and priority rules in abstract argumen-
[21]
G.Alfano
,
S.Greco
,
F.Parisi
,
I. Trubitsyna
, Argutation, in
: Proceedings of the Thirty-First Interna- mentation frameworks with strong and weak contional Joint Conference on Artificial Intelligence
,
straints: Semantics and complexity
,
in: Proceedings2022
, pp.
2517
-
2524
. of the Thirty-Fifth AAAI Conference on Artificial
[9]
E.Bonzon
,
J.Delobelle
,
S.Konieczny
,
N.Maudet
, Intelligence,
2021
, pp.
6175
-
6184
.
A comparative study of ranking-based semantics for
[22]
G.Alfano
,
S.Greco
,
F.Parisi
,
Computing stable and abstract argumentation
,
in: Proceedings of the Thir- preferred extensions of dynamic bipolar argumentieth AAAI Conference on Artificial Intelligence
, tation frameworks,
in: Proc. of the 1st Workshop2016
, pp.
914
-
920
. on Advances In Argumentation In Artificial Intelli-
[10]
J.Mailly
,
J.Rossit
, Argument, I choose you! pref- gence
AI3
,
2017
, pp.
28
-
42
.
erences and ranking semantics in abstract argumen-
[23]
G.Alfano
,
S.Greco
,
F.Parisi
,
A meta- meration of the preferred extensions of abstract arguargumentation approach for the efficient computa- mentation frameworks, in: Proceedings of ACM/SItion of stable and preferred extensions in dynamic GAPP Symposium on Applied Computing (SAC), bipolar argumentation frameworks
,
Intelligenza Ar- 2019
, pp.
1147
-
1153
. tificiale 12 (
2018
)
193
-
211
. [28]
G.Alfano
,
S.Greco
, Incremental skeptical preferred
[24]
G.Alfano
,
S.Greco
,
F.Parisi
,
G. I.Simari
,
G. R.acceptance in dynamic argumentation frameworks, Simari, An incremental approach to structured ar- IEEE Intell
.
Syst
.
36
(
2021
)
6
-
12
.
gumentation over dynamic knowledge bases
, in: [29]
G.Alfano
,
A.Cohen
,
S.Gottifredi
,
S.Greco
, Proceedings of International Conference on Princi- F. Parisi, G. Simari,
Dynamics in abstract argumenples of Knowledge Representation and Reasoning tation frameworks with recursive attack and support (KR
),
2018
, pp.
78
-
87
. relations,
in: Proceedings of the 24th European
[25]
G.Alfano
,
S.Greco
,
F.Parisi
,
G. I.Simari
, G. R. Conference
on Artificial Intelligence (ECAI)
,
2020
,
Simari, Incremental computation for structured ar
- pp.
577
-
584
.
gumentation over dynamic DeLP knowledge bases
, [30]
A.Niskanen
,
M.Järvisalo
, Algorithms for dyArtif.
Intell
.
300
(
2021
)
103553. namic argumentation frameworks: An incremental
[26]
G.Alfano
,
S.Greco
,
F.Parisi
,
Computing ex- sat-based approach
,
in: Proceedings of the 24th Eutensions of dynamic abstract argumentation frame- ropean Conference on Artificial Intelligence (ECAI)
,
works with second-order attacks
,
in: Proc. of the 2020
, pp.
849
-
856
. 22nd International Database Engineering & Appli- [31]
G.Alfano
,
S.Greco
,
F.Parisi
,
Incremental compucations Symposium (IDEAS)
,
2018
, pp.
183
-
192
.
tation in dynamic argumentation frameworks
, IEEE
[27]
G.Alfano
,
S.Greco
,
F.Parisi
,
On scaling the enu- Intell
. Syst.
36
(
2021
)
80
-
86
.