Vol-3197/paper3
Jump to navigation
Jump to search
Paper
| Paper | |
|---|---|
 edit
| |
| description | scientific paper published in CEUR-WS Volume 3197 |
| id | Vol-3197/paper3 |
| wikidataid | Q117341398βQ117341398 |
| title | The Effect of Preferences in Abstract Argumentation Under a Claim-Centric View |
| pdfUrl | https://ceur-ws.org/Vol-3197/paper3.pdf |
| dblpUrl | https://dblp.org/rec/conf/nmr/BernreiterDRW22 |
| volume | Vol-3197βVol-3197 |
| session | β |
Freitext
The Effect of Preferences in Abstract Argumentation Under a Claim-Centric View
The Effect of Preferences in Abstract Argumentation Under
a Claim-Centric View
Michael Bernreiter* , Wolfgang DvoΕΓ‘k, Anna Rapberger and Stefan Woltran
Institute of Logic and Computation, TU Wien, Austria
Abstract
In this paper, we study the effect of preferences in abstract argumentation under a claim-centric perspective. Recent work has
revealed that semantical and computational properties can change when reasoning is performed on claim-level rather than
on the argument-level, while under certain natural restrictions (arguments with the same claims have the same outgoing
attacks) these properties are conserved. We now investigate these effects when, in addition, preferences have to be taken into
account and consider four prominent reductions to handle preferences between arguments. As we shall see, these reductions
give rise to different classes of claim-augmented argumentation frameworks, and behave differently in terms of semantic
properties and computational complexity. This strengthens the view that the actual choice for handling preferences has to
be taken with care.
1. Introduction by assigning to each argument a claim. Semantics for
CAFs can be obtained by evaluating the underlying AF
Arguments vary in their plausibility. Research in formal before inspecting the claims of the acceptable arguments
argumentation has taken up this aspect in both quanti- in the final step. CAFs serve as an ideal target formalism
tative and qualitative terms [1, 2]. Indeed, preferences for ASPIC+ [10] and other knowledge representation for-
are nowadays a standard feature of many structured ar- malisms which utilize abstract argumentation semantics
gumentation formalisms [3, 4]. At the same time, there whilst also considering the claims of the arguments in the
are numerous generalizations of abstract Argumentation evaluation. Thus, CAFs help to streamline the instantia-
Frameworks (AFs) [5] that consider the impact of pref- tion process by avoiding additional mappings to obtain
erences on the abstract level, be it in terms of argument semantical correspondence; e.g., in contrast to classi-
strength [6, 7] or preferences between values [8]. In cal AF-instantiations of logic programs [15] where ad-
Dung AFs in which conflicts are expressed as a binary ditional mappings are needed, claim-based semantics of
relation between arguments (attack relation), the incor- CAFs capture logic programming semantics without de-
poration of preferences typically results in the deletion tours [16]. In this way, we obtain a direct correspondence
or reversion of attacks between arguments of different between the claim-extensions in the CAF and conclusion-
strengthβdeciding acceptability of arguments via argu- extensions in the original formalism.
mentation semantics is thus reflected in terms of the Although the acceptance of claims is closely related to
modified attack relation [9]. argument-acceptance, there are subtle differences as ob-
The difference in argument strength and the resulting served in [14, 17, 10] stemming from the fact that claims
modification of the attack relation naturally influences can appear as conclusion of several different arguments.
the acceptability of the argumentsβ conclusion (the claim As a consequence, several properties of AF semantics
of the argument). Claim acceptance in argumentation such as I-maximality, i.e., β-maximality of extensions,
systems, i.e., the evaluation of commonly acceptable state- cannot be taken for granted when considered in terms of
ments while disregarding their particular justifications, the argumentsβ claims [18]. Furthermore, the additional
is an integral part of many structured argumentation for- level of claims causes a rise in the computational com-
malisms [10, 11] and has received increasing attention in plexity of standard decision problems (in particular, veri-
the literature [12, 13, 14]. A simple yet powerful general- fication is one level higher in the polynomial hierarchy as
ization of Dung AFs that allow for claim-based evaluation for standard AFs), see [14, 19]. Luckily, these drawbacks
are Claim-augmented AFs (CAFs) [14]. They extend AFs can be alleviated by taking fundamental properties of the
attack relation into account: the basic observation that
NMR 2022: 20th International Workshop on Non-Monotonic Reason- attacks typically depend on the claim of the attacking
ing, August 07β09, 2022, Haifa, Israel arguments gives rise to the central class of well-formed
*
Corresponding author.
mbernrei@dbai.tuwien.ac.at (M. Bernreiter);
CAFs. CAFs from this class require that arguments with
dvorak@dbai.tuwien.ac.at (W. DvoΕΓ‘k); the same claim attack the same arguments, thus model-
arapberg@dbai.tuwien.ac.at (A. Rapberger); ing β on the abstract level β a very natural behavior of
woltran@dbai.tuwien.ac.at (S. Woltran) arguments that is common to all leading structured argu-
Β© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License
CEUR
Attribution 4.0 International (CC BY 4.0). mentation formalisms and instantiations. Well-formed
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
27
οΏ½CAFs have the main advantage that most of the seman- restrictions suggest beneficial impact on both the compu-
tics behave βas expectedβ. For instance, they retain the tational complexity and on desired semantical properties
fundamental property of I-maximality, and their compu- such as I-maximality.
tational complexity is located at the same level of the In this paper, we tackle this issue by considering four
polynomial hierarchy as for Dung AFs. commonly used methods, so-called reductions, to inte-
Unfortunately, it turns out that well-formedness can- grate preference orderings into the attack relation: the
not be assumed if one deals with preferences in argu- most common modification is the deletion of attacks in
mentation, as arguments with the same claim are not case the attacking argument is less preferred than its
necessarily equally plausible. The following example target. This method is typically utilized to transform
demonstrates this. preference-based argumentation frameworks (PAFs) [20]
into AFs but is also used in many structured argumenta-
Example 1. Consider two arguments π, πβ² with claim πΌ,
tion formalisms such as ASPIC+. This reduction has been
and another argument π having claim π½. Moreover, both
criticized due to several problematic side-effects, e.g., it
π and π attack π, while π attacks π. Furthermore assume
β²
can be the case that two conflicting arguments are jointly
that we are given the additional information that π is pre-
acceptable, and has been accordingly adapted in [21]; two
ferred over πβ² (for example, if assumptions in the support
other reductions have been introduced in [9]. We apply
of π are stronger than assumptions made by π ). A com-
β²
these four preference reductions to well-formed CAFs
mon method to integrate such information on argument
with preferences. In particular, our main contributions
rankings is to delete attacks from arguments that attack
are as follows:
preferred arguments. In this case, we delete the attack from
π to π.
β²
β’ For each of the four reductions, we characterize
Both frameworks are depicted below: πΉ represents the the possible structure of CAFs that are obtained
original situation while πΉ β² is the CAF resulting from delet- by applying the reduction to a well-formed CAF
ing the unsuccessful attack from πβ² on the argument π. and a preference relation. This results in four
novel CAF classes, each of which constitutes a
πΌ π½ πΌ proper extension of well-formed CAFs but does
β²
πΉ : π π π not retain the full expressiveness of general CAFs.
We investigate the relationship between these
πΌ π½ πΌ classes.
β²
πΉ : π π πβ² β’ We study I-maximality of stable, preferred, semi-
stable, stage, and naive semantics of the novel
Note that πΉ is well-formed since all arguments with the CAF classes. Our results highlight a significant
same claims attack the same arguments. The unique ac- advantage of a particular reduction: we show that,
ceptable argument-set w.r.t. stable semantics (cf. Defini- for admissible-based semantics, this modification
tion 2) is {π, πβ² } which translates to {πΌ} on the claim- preserves I-maximality. The other reductions fail
level. to preserve I-maximality; moreover, for naive and
The CAF πΉ β² , on the other hand, is no longer well-formed stage semantics, I-maximality cannot be guaran-
since πβ² does not attack π. In πΉ β² , the argument-sets {π, πβ² } teed for any of the four reductions.
and {π, π} are both acceptable w.r.t. to stable-semantics. In β’ Finally, we investigate the complexity of reason-
terms of claims this translates to {πΌ} and {πΌ, π½}, which ing for CAFs with preferences with respect to
shows that I-maximality is violated on the claim-level. conflict-free, admissible, complete, and all of the
aforementioned semantics. We show that for
Although well-formedness can not be guaranteed in
three of the four reductions, the verification prob-
view of preferences, this does not imply arbitrary behav-
lem drops by one level in the polynomial hierar-
ior of the resulting CAF: on the one hand, preferences
chy for all except complete semantics and is thus
conform to a certain type of ordering (e.g., asymmetric,
not harder than for well-formed CAFs (which
strict, partial, or total orders) over the set of arguments;
in turn has the same complexity as the corre-
on the other hand, it is evident that the deletion, rever-
sponding AF problems). Complete semantics re-
sion, and other types of attack manipulation impose cer-
main hard for all but one preference reduction.
tain restrictions on the structure of the resulting CAF.
Moreover, it turns out that verification for the
Combining both aspects, we obtain that, assuming well-
reduction which deletes attacks from weaker ar-
formedness of the initial framework, it is unlikely that
guments remains as hard as for general CAFs.
preference incorporation results in arbitrary behavior.
The key motivation of this paper is to identify and ex- Our results constitute a systematic study of the struc-
ploit structural properties of preferential argumentation tural and computational effect of preferences on claim
in the scope of claim acceptance. The aforementioned acceptance. Since we use CAFs as our base formalism,
28
οΏ½our investigations extend to large classes of formalisms Table 1
that can be represented as CAFs, just like results on Dung I-maximality of CAFs.
AFs yield insights for formalisms that can be captured naiveπ stbπ prf π semπ stgπ
by AFs. CAF x x x x x
wfCAF x β β β β
2. Preliminaries
Table 2
We first define (abstract) argumentation frameworks [5]. Complexity of CAFs (Ξ β {CAF , wfCAF }).
π denotes a countable infinite domain of arguments. π Cred Ξ Skept Ξ Ver CAF Ver wfCAF
π
π π π
Definition 1. An argumentation framework (AF) is a tu- cf in P trivial NP-c in P
ple πΉ = (π΄, π
) where π΄ β π is a finite set of arguments adm NP-c trivial NP-c in P
and π
β π΄ Γ π΄ is an attack relation between arguments. com NP-c P-c NP-c in P
Let πΈ β π΄. We say πΈ attacks π (in πΉ ) if (π, π) β π
for naive in P coNP-c NP-c in P
some π β πΈ; πΈπΉ+ = {π β π΄ | βπ β πΈ : (π, π) β π
} de- stb NP-c coNP-c NP-c in P
notes the set of arguments attacked by πΈ. πΈπΉβ = πΈ βͺ πΈπΉ+ prf NP-c Ξ P2 -c Ξ£P
2 -c coNP-c
is the range of πΈ in πΉ . An argument π β π΄ is defended sem/stg Ξ£P2 -c Ξ P2 -c Ξ£P
2 -c coNP-c
(in πΉ ) by πΈ if π β πΈπΉ+ for each π with (π, π) β π
.
Given an AF πΉ = (π΄, π
) it can be convenient to write Definition 3. A claim-augmented argumentation frame-
π β πΉ for π β π΄ and (π, π) β πΉ for (π, π) β π
. Seman- work (CAF) is a triple (π΄, π
, claim) where (π΄, π
) is an
tics for AFs are defined as functions π which assign to AF and claim : π΄ β Claims is a function that maps ar-
each AF πΉ = (π΄, π
) a set π(πΉ ) β 2π΄ of extensions. We guments to claims. The claim-function can be extended to
consider for π the functions cf , adm, com, naive, stb, sets of arguments, i.e., claim(πΈ) = {claim(π) | π β πΈ}.
prf , sem, and stg which stand for conflict-free, admissi- A well-formed CAF (wfCAF) is a CAF (π΄, π
, claim) in
ble, complete, naive, stable, preferred, semi-stable, and which all arguments with the same claim attack the same
stage, respectively [22]. arguments, i.e., for all π, π β π΄ with claim(π) =
Definition 2. Let πΉ = (π΄, π
) be an AF. A set π β π΄ claim(π) we have {π | (π, π) β π
} = {π | (π, π) β π
}.
is conflict-free (in πΉ ), if there are no π, π β π, such that The semantics of CAFs are based on those of AFs.
(π, π) β π
. cf (πΉ ) denotes the collection of conflict-free
sets of πΉ . For a conflict-free set π β cf (πΉ ), it holds that Definition 4. Let πΉ = (π΄, π
, claim) be a CAF.
The claim-based variant of a semantics π is defined as
β’ π β adm(πΉ ) if each π β π is defended by π in πΉ ;
ππ (πΉ ) = {claim(π) | π β π((π΄, π
))}.
β’ π β com(πΉ ) if π β adm(πΉ ) and each π β π΄
defended by π in πΉ is contained in π; Example 3. Consider the CAF πΉ from Example 1. For-
β’ π β naive(πΉ ) if there is no π β cf (πΉ ) with mally, πΉ = (π΄, π
, claim) with π΄ = {π, πβ² , π}, π
=
π β π; {(π, π), (πβ² , π), (π, π)}, claim(π) = claim(πβ² ) = πΌ,
β’ π β stb(πΉ ) if each π β π΄ β π is attacked by π and claim(π) = π½. πΉ is well-formed and the under-
in πΉ ; lying AF of πΉ was investigated in Example 2. From
β’ π β prf (πΉ ) if π β adm(πΉ ) and there is no there we can infer that, e.g., cf π (πΉ ) = {β
, {πΌ}, {π½}},
π β adm(πΉ ) with π β π ; adm π (πΉ ) = {β
, {πΌ}}, naive π (πΉ ) = {{πΌ}, {π½}}, and
β’ π β sem(πΉ ) if π β adm(πΉ ) and there is no stbπ (πΉ ) = {{πΌ}}.
π β adm(πΉ ) with ππΉβ β ππΉβ ;
Well-known basic relations between different AF se-
β’ π β stg(πΉ ) if there is no π β cf (πΉ ) with
mantics π also hold for ππ : stb π (πΉ ) β sem π (πΉ ) β
ππΉ β ππΉ .
β β
prf π (πΉ ) β adm π (πΉ ) as well as stb π (πΉ ) β stg π (πΉ ) β
Example 2. Consider the AF πΉ = ({π, πβ² , π}, {(π, π), naive π (πΉ ) β cf π (πΉ ) [18].
(πβ² , π), (π, π)}) from Example 1, ignoring claims πΌ and π½. Note that the semantics π β {naive, stb, prf , sem,
Then cf (πΉ ) = {β
, {π}, {πβ² }, {π}, {π, πβ² }}, adm(πΉ ) = stg} employ argument maximization and result in incom-
{β
, {π}, {πβ² }, {π, πβ² }}, naive(πΉ ) = {{π}, {π, πβ² }}, parable extensions on regular AFs: for all π, π β π(πΉ ),
and π(πΉ ) = {{π, πβ² }} for π β {com, stb, prf , sem, π β π implies π = π . This property is referred to as
stg}. I-maximality, and is defined analogously for CAFs:
CAFs are AFs in which each argument is assigned a Definition 5. ππ is I-maximal for a class π of CAFs if, for
claim, and thus constitute a straightforward generaliza- all CAFs πΉ β π and all π, π β ππ (πΉ ), π β π implies
tion of AFs [14]. π = π.
29
οΏ½ π π πΉ, π β» π π π β1 (πΉ ) π π β2 (πΉ ) π π β3 (πΉ ) π π β4 (πΉ )
π π πΊ, π β» π π π β1 (πΊ) π π β2 (πΊ) π π β3 (πΊ) π π β4 (πΊ)
Figure 1: Effect of the four reductions on the attack relation between two arguments.
Table 1 shows I-maximality properties of CAFs [18], Definition 6. A preference-based claim-augmented ar-
revealing an important property of wfCAFs compared gumentation framework (PCAF) is a quadruple πΉ =
to general CAFs: I-maximality is preserved in all seman- (π΄, π
, claim, β») where (π΄, π
, claim) is a well-formed
tics except naive π , implying natural behavior of these CAF and β» is an asymmetric preference relation over π΄.
maximization-based semantics analogous to regular AFs;
see, e.g., [23] for a general discussion of such properties. Notice that preferences in PCAFs are not required to
Regarding computational complexity, we consider be transitive. While transitivity of preferences is often
the following decision problems pertaining to CAF- assumed in argumentation [21, 9], it cannot always be
semantics ππ : guaranteed in practice [6]. However, we will consider
the effect of transitive orderings when applicable.
β’ Credulous Acceptance (Cred CAF π ): Given a CAF If π and π are arguments and π β» π holds then we
πΉ and claim πΌ, is πΌ contained in some π β say that π is stronger than π. But what effect should this
ππ (πΉ )? ordering have? How should this influence, e.g., the set of
β’ Skeptical Acceptance (Skept CAF
π ): Given a CAF πΉ admissible arguments? One possibility is to remove all
and claim πΌ, is πΌ contained in each π β ππ (πΉ )? attacks from weaker to stronger arguments in our PCAF,
β’ Verification (Ver CAF
π ): Given a CAF πΉ and a set and to then determine the set of admissible arguments
of claims π, is π β ππ (πΉ )? in the resulting CAF. This altering of attacks in a PCAF
based on its preference-ordering is called a reduction.
We furthermore consider these reasoning problems re- The literature describes four such reductions for regu-
stricted to wfCAFs and denote them by Cred wfCAF π , lar AFs [9, 24, 21]. Following [9] we next recall these
Skept wfCAF
π , and Ver wfCAF
π . Table 2 shows the com- reductions.
plexity of these problems [14, 19]. Here we see that the
complexity of the verification problem drops by one level Definition 7. Given a PCAF πΉ = (π΄, π
, claim, β»),
in the polynomial hierarchy when comparing general a corresponding CAF βπ (πΉ ) = (π΄, π
, claim) is con-
β²
CAFs to wfCAFs. This is an important advantage of structed via Reduction π, where π β {1, 2, 3, 4}, as follows:
wfCAFs, as a lower complexity in the verification prob-
β’ π = 1: βπ, π β π΄ : (π, π) β π
β² β (π, π) β π
,
lem allows for a more efficient enumeration of claim-
π ΜΈβ» π
extensions (cf. [14]).
β’ π = 2: βπ, π β π΄ : (π, π) β π
β² β ((π, π) β π
,
π ΜΈβ» π) β¨ ((π, π) β π
, (π, π) β/ π
, π β» π)
3. Preference-based CAFs β’ π = 3: βπ, π β π΄ : (π, π) β π
β² β ((π, π) β π
,
π ΜΈβ» π) β¨ ((π, π) β π
, (π, π) ΜΈβ π
)
As discussed in the previous sections, wfCAFs are a natu- β’ π = 4: βπ, π β π΄ : (π, π) β π
β² β ((π, π) β π
,
ral subclass of CAFs with advantageous properties in π ΜΈβ» π) β¨ ((π, π) β π
, (π, π) β / π
, π β» π) β¨
terms of I-maximality and computational complexity. ((π, π) β π
, (π, π) ΜΈβ π
)
However, when resolving preferences among arguments
the resulting CAFs are typically no longer well-formed Figure 1 visualizes the above reductions. Intuitively,
(cf. Example 1). In order to study preferences under a Reduction 1 removes attacks that contradict the prefer-
claim-centric view we introduce preference-based CAFs. ence ordering while Reduction 2 reverts such attacks. Re-
These frameworks enrich the notion of wfCAFs with the duction 3 removes attacks that contradict the preference
concept of argument strength in terms of preferences. ordering, but only if the weaker argument is attacked by
Our main goals are then to understand the effect of re- the stronger argument also. Reduction 4 can be seen as a
solved preferences on the structure of the underlying combination of Reductions 2 and 3. Observe that all four
wfCAF on the one hand, and to determine whether the reductions are polynomial time computable with respect
advantages of wfCAFs are maintained on the other hand. to the input PCAF.
Given this motivation, it is reasonable to consider the Note that many structured argumentation formalisms
impact of preferences on well-formed CAFs only. make use of preference-reductions as well. For instance,
ABA+ [4] employs attack reversal similar to Reduction 2
30
οΏ½while some instances of ASPIC [3] delete attacks from
weaker arguments in the spirit of Reduction 1. πΌ π π πΌ πΌ π π πΌ πΌ π π πΌ
The semantics for PCAFs can now be defined in a
straightforward way: first, one of the four reductions Figure 2: CAFs contained only in β1 -CAF, β2 -CAF, and
is applied to the given PCAF; then, CAF-semantics are β4 -CAF respectively. Solid arrows are attacks, dashed ar-
applied to the resulting CAF. rows indicate where attacks are missing for the CAF to be
well-formed.
Definition 8. Let πΉ be a PCAF and let π β {1, 2, 3, 4}.
The preference-claim-based variant of a semantics π rela-
tive to Reduction π is defined as πππ (πΉ ) = ππ (βπ (πΉ )). Definition 9. βπ -CAF denotes the set of CAFs that
Example 4. Let πΉ = (π΄, π
, claim, β») be the PCAF can be obtained by applying Reduction π to PCAFs, i.e.,
where π΄ = {π, πβ² , π}, π
= {(π, π), (πβ² , π), (π, π)}, βπ -CAF = {βπ (πΉ ) | πΉ is a PCAF}.
claim(π) = claim(πβ² ) = πΌ, claim(π) = π½, and π β» πβ² . It is easy to see that βπ -CAF, with π β {1, 2, 3, 4},
The underlying CAF (π΄, π
, claim) of πΉ was examined in contains all wfCAFs (we can simply specify the desired
Example 3. wfCAF and an empty preference relation). However,
β1 (πΉ ) = (π΄, π
β² , claim) with π
β² = {(π, π), (π, π)}, not all CAFs are contained in βπ -CAF. For example,
which is the same CAF as πΉ β² in Example 1. It can be veri- πΉ = ({π, π}, {(π, π), (π, π)}, claim) with claim(π) =
fied that, e.g., adm 1π (πΉ ) = adm π (β1 (πΉ )) = {{β
, {πΌ}, claim(π) can not be obtained from a PCAF πΉ β² : such πΉ β²
{π½}, {πΌ, π½}} and stb 1π (πΉ ) = {{πΌ}, {πΌ, π½}}. would need to contain either (π, π) or (π, π). But then,
Indeed, the choice of reduction can influence the exten- since the underlying CAF of a PCAF must be well-formed,
sions of a PCAF. For example, β2 (πΉ ) = (π΄, π
β²β² , claim) πΉ β² would have to contain a self-attack which can not be
with π
β²β² = {(π, π), (π, π), (π, π)}, adm 2π (πΉ ) = {β
, {πΌ}, removed by any of the reductions. This is enough to con-
{π½}}, and stb 2π (πΉ ) = {{πΌ}, {π½}}. clude1 that the four new classes are located in-between
It is easy to see that basic relations between seman- wfCAFs and general CAFs:
tics carry over from CAFs, as, if we have ππ (πΉ ) β
Proposition 1. Let CAF be the set of all CAFs and
ππ (πΉ ) for two semantics π, π and all CAFs πΉ , then
π π wfCAF the set of all wfCAFs. For all π β {1, 2, 3, 4}
also ππ (πΉ ) β ππ (πΉ ) for all PCAFs πΉ . It thus holds
it holds that wfCAF β βπ -CAF β CAF.
that for all π β {1, 2, 3, 4}, stb ππ (πΉ ) β sem ππ (πΉ ) β
π π π π
prf π (πΉ ) β adm π (πΉ ) as well as stb π (πΉ ) β stg π (πΉ ) β Furthermore, the new classes are all distinct from each
naive ππ (πΉ ) β cf ππ (πΉ ). other, i.e., we are indeed dealing with four new CAF
classes:
Remark 1. In this paper we require the underlying CAF
of a PCAF to be well-formed. The reason for this is that we Proposition 2. For all π β {1, 2, 4} and all π β
are interested in whether the benefits of well-formed CAFs {1, 2, 3, 4} such that π ΜΈ= π it holds that βπ -CAF ΜΈβ
are preserved when preferences have to be taken into ac- βπ -CAF and β3 -CAF β βπ -CAF.
count. Even from a technical perspective, admitting PCAFs
with a non-well-formed underlying CAF is not very inter- Proof sketch. Figure 2 shows CAFs that are in only
esting with respect to the questions addressed in this pa- one of β1 -CAF, β2 -CAF, and β4 -CAF. Consider
per. Indeed, any CAF could be obtained from such general the PCAF πΉ = ({π, π}, {(π, π), (π, π)}, claim, β») with
PCAFs, regardless of which preference reduction we are us- claim(π) = claim(π) = πΌ and π β» π. Then β1 (πΉ ),
ing, by simply specifying the desired CAF and an empty β2 (πΉ ), and β4 (πΉ ) are the CAFs of Figure 2. Since self-
preference relation. Thus, such general PCAFs have the attacks are not removed or introduced by any reduction,
same properties regarding I-maximality and complexity as and the underlying CAF must be well-formed, πΉ is the
general CAFs. only PCAF from which β1 (πΉ ), β2 (πΉ ), and β4 (πΉ ) can
be obtained. Note that β3 (πΉ ) is simply the underly-
ing CAF of πΉ . β3 -CAF β βπ -CAF follows by the
4. Characterization & fact that if an attack (π, π) is removed by Reduction 3
Expressiveness from some PCAF πΊ, then (π, π) β πΊ. In this case, all
reductions behave in the same way (cf. Definition 7 or
Our first step towards understanding the effect of prefer- Figure 1).
ences on wfCAFs is to examine the impact of resolving
preferences on the structure of the underlying CAF. To
this end, we consider four new CAF classes which are 1 Although many proof sketches are provided in this text, a preprint
obtained from applying the reductions of Definition 7 to of this paper with full proofs in the appendix can be accessed at
PCAFs. https://arxiv.org/abs/2204.13305.
31
οΏ½ While the classes β1 -CAF, β2 -CAF, would have to contain both the attacks (π, π), (π, π) as
and β4 -CAF are incomparable we observe well as the preferences π β» π, π β» π. The argument for
β3 -CAF β βπ -CAF which reflects that Reduc- β3 -CAF is similar.
tion 3 is the most conservative of the four reductions, For β2 -CAF, suppose there are π, πβ² , π with
removing attacks only when there is a counter-attack claim(π) = claim(πβ² ), (π, π) β wfp(πΉ ), (π, π) ΜΈβ π
,
from the stronger argument. and (πβ² , π) β π
. Assume there is a PCAF πΉ β² =
We now know that applying preferences to wfCAFs (π΄, π
β² , claim, β») such that β2 (πΉ β² ) = πΉ . Since Reduc-
results in four distinct CAF-classes that lie in-between tion 2 can not completely remove conflicts, (π, π) ΜΈβ π
β²
wfCAFs and general CAFs. It is still unclear, however, and (π, π) ΜΈβ π
β² . If (π, πβ² ) β π
, then (πβ² , π) β π
β²
how to determine whether some CAF belongs to one and (π, πβ² ) β π
β² since Reduction 2 can not introduce
of these classes or not. Especially for β2 -CAF and symmetric attacks. But then (π΄, π
β² , claim) is not well-
β4 -CAF this is not straightforward, since Reductions 2 formed. Now suppose (π, πβ² ) ΜΈβ π
, but there is some
and 4 not only remove but also introduce attacks and πβ² with claim(π) = claim(πβ² ), (πβ² , πβ² ) ΜΈβ π
, and
therefore allow for many possibilities to obtain a particu- (πβ² , πβ² ) ΜΈβ π
. Then also (πβ² , πβ² ) ΜΈβ π
β² and (πβ² , πβ² ) ΜΈβ π
β² .
lar CAF as result. We tackle this problem by characteriz- But since (πβ² , π) β π
we have either (πβ² , π) β π
β²
ing the new classes via the so-called wf-problematic part or (π, πβ² ) β π
β² , which means that (π΄, π
β² , claim) is
of a CAF. not well-formed. In all other cases we can construct a
PCAF πΉ β²β² = (π΄, π
β²β² , claim, β») such that β2 (πΉ β²β² ) = πΉ :
Definition 10. A pair of arguments (π, π) is wf- first revert all attacks (πβ² , π) in πΉ for which there is
problematic in a CAF πΉ = (π΄, π
, claim) if π, π β π΄, some π with claim(π) = claim(πβ² ) and (π, π) ΜΈβ π
,
(π, π) ΜΈβ π
, and there is πβ² β π΄ with claim(πβ² ) = (π, π) ΜΈβ π
; then, add all remaining pairs (π, π) that
claim(π) and (πβ² , π) β π
. The set wfp(πΉ ) = are still wf-problematic as attacks. Define π β» π iff
{(π, π) | (π, π) is wf-problematic in πΉ } is called the wf- (π, π) β π
β²β² β π
. It can be verified that (π΄, π
β²β² , claim)
problematic part of πΉ . is well-formed, β» is asymmetric, and β2 (πΉ β²β² ) = πΉ . The
Intuitively, the wf-problematic part of a CAF πΉ con- argument for β4 -CAF is similar.
sists of those attacks that are missing for πΉ to be well-
The above characterizations give us some insights into
formed (cf. Figure 2). Indeed, πΉ is a wfCAF if and only if
the effect of the various reductions on wfCAFs. Indeed,
wfp(πΉ ) = β
. The four new classes can be characterized
the similarity between the characterizations of β1 -CAF
as follows:
and β3 -CAF, resp. β2 -CAF and β4 -CAF, can intu-
Proposition 3. Let πΉ = (π΄, π
, claim) be a CAF. Then itively be explained by the fact that Reductions 1 and 3
only remove attacks, while Reductions 2 and 4 can also
β’ πΉ β β1 -CAF iff (π, π) β wfp(πΉ ) implies introduce attacks. Furthermore, Proposition 3 allows us
(π, π) ΜΈβ wfp(πΉ ); to decide in polynomial time whether a given CAF πΉ
β’ πΉ β β2 -CAF iff there are no arguments can be obtained by applying one of the four preference
π, πβ² , π, πβ² in πΉ with claim(π) = claim(πβ² ) reductions to a PCAF.
and claim(π) = claim(πβ² ) such that (π, π) β But what happens if we restrict ourselves to transitive
wfp(πΉ ), (π, π) ΜΈβ π
, (πβ² , π) β π
, and either preferences? Analogously to βπ -CAF, by βπ -CAFtr
(π, πβ² ) β π
or ((πβ² , πβ² ) ΜΈβ π
and (πβ² , πβ² ) ΜΈβ π
); we denote the set of CAFs obtained by applying Re-
β’ πΉ β β3 -CAF iff (π, π) β wfp(πΉ ) implies duction π to PCAFs with a transitive preference rela-
(π, π) β π
; tion. It is clear that βπ -CAFtr β βπ -CAF for all
β’ πΉ β β4 -CAF iff there are no arguments π β {1, 2, 3, 4}. Interestingly, the relationship be-
π, πβ² , π, πβ² in πΉ with claim(π) = claim(πβ² ) tween the classes βπ -CAFtr is different to that between
and claim(π) = claim(πβ² ) such that (π, π) β βπ -CAF (Proposition 2). Specifically, β3 -CAFtr is
wfp(πΉ ), (π, π) ΜΈβ π
, (πβ² , π) β π
, and either not contained in the other classes. Intuitively, this is be-
(π, πβ² ) ΜΈβ π
or ((πβ² , πβ² ) ΜΈβ π
and (πβ² , πβ² ) ΜΈβ π
). cause, in certain PCAFs πΉ , transitivity can force π1 β» ππ
via π1 β» π2 β» . . . β» ππ such that (ππ , π1 ) β πΉ but
Proof sketch. Regarding β1 -CAF, observe that Reduc- (π1 , ππ ) ΜΈβ πΉ . In this case, only Reduction 3 leaves the
tion 1 can only delete but not introduce attacks. If attacks between π1 and ππ unchanged.
(π, π) β wfp(πΉ ) implies (π, π) ΜΈβ wfp(πΉ ) then we can
construct a PCAF πΉ β² with π
β² = π
βͺ {(π, π) | (π, π) β Proposition 4. For all π, π β {1, 2, 3, 4} such that π ΜΈ= π
wfp(πΉ )} and π β» π iff (π, π) β π
β² β π
. Observe that β» it holds that βπ -CAFtr ΜΈβ βπ -CAFtr .
is asymmetric. Conversely, a CAF πΊ with arguments π, π We will not characterize all four classes βπ -CAFtr .
such that (π, π) β wfp(πΊ) and (π, π) β wfp(πΊ) can not However, capturing β -CAF will prove useful when
1 tr
be obtained via Reduction 1 from a PCAF πΊβ² , since πΊβ² analyzing the computational complexity of PCAFs using
32
οΏ½Reduction 1 (see Section 6). Note that wfp(πΉ ) can be πΌ π
πΌ
πΌ π πβ² π½
seen as a directed graph, with an edge between vertices
π½ π πβ² πβ²β² πΌ
π and π whenever (π, π) β wfp(πΉ ). Thus, we may use
notions such as paths and cycles in the wf-problematic πΎ π π½ π πβ² πΌ
part of a CAF.
Figure 3: CAFs used as counter examples for I-maximality (cf.
Proposition 5. πΉ β β1 -CAFtr for a CAF πΉ if and Proposition 8 and 9). Dashed arrows are edges in wfp(πΉ ).
only if (1) wfp(πΉ ) is acyclic and (2) (π, π) β πΉ implies
that there is no path from π to π in wfp(πΉ ).
Proof sketch. Assume there is a cycle (π1 , . . . , ππ , π1 ) in In other words, Reductions 2, 3, and 4 preserve conflict-
wfp(πΉ ). Then, since Reduction 1 can not introduce at- freeness. It is easy to see that this is not the case for
tacks, if there is a PCAF πΉ β² such that β1 (πΉ β² ) = πΉ , Reduction 1. In fact, Reduction 1 has been deemed prob-
we have (π1 , π2 ), . . . , (ππ , π1 ) β πΉ β² . This implies lematic for exactly this reason when applied to regular
π1 β» ππ β» ππβ1 β» Β· Β· Β· β» π1 , i.e., β» is not asymmet- AFs [21], although it is still discussed and considered
ric. Similarly, if there is a path (π1 , . . . , ππ ) in wfp(πΉ ) in the literature alongside the other reductions [6]. We
we have to define ππ β» Β· Β· Β· β» π1 in πΉ β² . But then first consider Reduction 3, and show that it preserves
(π1 , ππ ) ΜΈβ β1 (πΉ β² ). I-maximality for some, but not all, semantics.
If wfp(πΉ ) is acyclic and there is no path from π to π Proposition 7. prf 3π , stb 3π , and sem 3π are I-maximal for
in wfp(πΉ ) such that (π, π) β πΉ , then we can construct PCAFs.
a PCAF πΉ β² such that β1 (πΉ β² ) = πΉ in the same way as
when β» is not transitive (cf. proof of Proposition 3). Proof. By stb 3π (πΉ ) β sem 3π (πΉ ) β prf 3π (πΉ ) it suffices to
consider prf 3π . Towards a contradiction, assume there is a
From the high-level point of view, our characterization
PCAF πΉ = (π΄, π
, claim, β») such that π β π for some
results yield insights into the expressiveness of argumen-
π, π β prf 3π (πΉ ). Then there are π β² , π β² β π΄ such that
tation formalisms that allow for preferences. Proposi-
π β² β prf (β3 (πΉ )), claim(π β² ) = π, π β² β prf (β3 (πΉ )),
tions 3 and 5 show which situations can be captured
and claim(π β² ) = π . π β² ΜΈβ π β² since π β² β prf (β3 (πΉ )).
by formalisms which (i) constructs attacks based on the
Thus, there is π₯ β π β² such that π₯ ΜΈβ π β² . But claim(π₯) β
claim of the attacking argument (i.e., formalisms with
π , i.e., there is π₯β² β π β² with claim(π₯β² ) = claim(π₯).
well-formed attack relation) and (ii) incorporate asym-
There are two possibilities for why π₯ ΜΈβ π β² .
metric or transitive preference relations on arguments
Case 1: π β² βͺ {π₯} ΜΈβ cf (β3 (πΉ )), i.e., there exists
using one of the four reductions.
π¦ β π β² such that π¦ ΜΈβ π β² and either (π₯, π¦) β πΉ or
(π¦, π₯) β πΉ . In fact, (π₯, π¦) ΜΈβ πΉ : otherwise, by the
5. I-Maximality well-formedness of (π΄, π
, claim), we have (π₯β² , π¦) β πΉ
and, by Lemma 6, π β² ΜΈβ cf (β3 (πΉ )). Thus, (π¦, π₯) β πΉ .
One of the advantages of wfCAFs over general By the definition of Reduction 3, (π¦, π₯) β β3 (πΉ ). π β²
CAFs is that they preserve I-maximality under most must defend π₯ in β3 (πΉ ), i.e., there exists π§ β π β² such
maximization-based semantics (cf. Table 1), which leads that (π§, π¦) β β3 (πΉ ). Then (π§, π¦) β πΉ . Since π β π
to more intuitive behavior of these semantics when con- there exists π§ β² β π β² such that claim(π§ β² ) = claim(π§).
sidering extensions on the claim-level. We now investi- (π§ β² , π¦) β πΉ by the well-formedness of (π΄, π
, claim).
gate whether these advantages are preserved when pref- But then π β² ΜΈβ cf (β3 (πΉ )). Contradiction.
erences are introduced. Case 2: π₯ is not defended by π β² , i.e., there exists π¦ β π΄
that is not attacked by π β² and such that (π¦, π₯) β β3 (πΉ ).
Definition 11. πππ is I-maximal for a class π of PCAFs
By the same argument as above, there is π§ β² β π β² with
if, for all πΉ in π and all π, π β πππ (πΉ ), π β π implies
(π§ β² , π¦) β πΉ . It cannot be that (π§ β² , π¦) β β3 (πΉ ), i.e.,
π = π.
π¦ β» π§ β² . By the definition of Reduction 3, (π¦, π§ β² ) β πΉ
From known properties of wfCAFs (cf. Table 1) it fol- and thus (π¦, π§ β² ) β β3 (πΉ ). But then π β² ΜΈβ adm(β3 (πΉ )).
lows directly that naive ππ is not I-maximal for PCAFs. Contradiction.
It remains to investigate the I-maximality of prf ππ , stb ππ ,
Of course, positive results regarding the I-maximality
sem ππ , and stg ππ for PCAFs. For convenience, given a
of PCAFs with arbitrary preferences, such as in the above
CAF πΉ = (π΄, π
, claim) and πΈ β π΄, we sometimes
proposition, still hold for PCAFs with transitive prefer-
write πΈ β π(πΉ ) for πΈ β π((π΄, π
)).
ence orderings. Conversely, for negative results, it suf-
Lemma 6. Let πΉ = (π΄, π
, claim, β») be a PCAF fices to show that I-maximality is not preserved on tran-
and πΈ β π΄. πΈ β cf (βπ (πΉ )) if and only if πΈ β sitive orderings to obtain results for the more general
cf ((π΄, π
, claim)) for π β {2, 3, 4}. case.
33
οΏ½Table 3 π π π π π π
I-maximality of PCAFs. Results also hold when considering ππΉ ππ ππΉ ππ ππΉ ππ
only PCAFs with transitive preferences.
naive ππ stb ππ prf ππ sem ππ stg ππ
π β {1, 2, 4} x x x x x π1 π2 π3 π1 π2 π4 π3 π4
π=3 x β β β x 1 2 3 1 2 4 3 4
Figure 4: Reduction of 3-Sat-instance πΆ1 = {π, π, π}, πΆ2 =
{Β¬π, Β¬π}, πΆ3 = {Β¬π, π}, πΆ4 = {π, Β¬π}, to an instance
Proposition 8. stg 3π is not I-maximal for PCAFs, even (πΉ, π) of Ver PCAF (cf. Proof of Proposition 10). Dashed ar-
cf ,1
when considering only transitive preferences. rows are attacks deleted in β1 (πΉ ), i.e., they are edges in
wfp(β1 (πΉ )).
Proof sketch. Let πΉ be the CAF shown on the left
in Figure 3. Observe that πΉ β β3 -CAFtr since
β3 (πΉ β² ) = πΉ for the PCAF πΉ β² with the same argu-
ments as πΉ , attacks {(π, π), (π, π), (π, π), (πβ² , π), (π, πβ² )} a PCAF instead of a CAF as input and appeal to the
π
and π β» πβ² . Moreover, it can be verified that stg 3π (πΉ β² ) = ππ semantics instead of the ππ semantics. Member-
{{πΌ}, {πΌ, πΎ}, {π½}}. ship results for PCAFs can be inferred from results
for general CAFs (recall that the preference reductions
In contrast to Reduction 3, under Reductions 1, 2, and 4 from PCAFs to the respective CAF class can be done
we lose I-maximality for all semantics. in polynomial time), and hardness results from results
for wfCAFs. Thus, the complexity of credulous and
Proposition 9. ππ , with π β {prf , stb, sem, stg} and skeptical acceptance follows immediately from known
π
π β {1, 2, 4}, is not I-maximal for PCAFs, even when con- results for CAFs and wfCAFs: given π β {1, 2, 3, 4}
sidering only transitive preferences. and π β {cf , adm, com, naive, stb, prf , sem, stg}, the
PCAF PCAF
Proof sketch. We only need to show this for stb ππ since problems Cred π,π and Skept π,π have the same com-
wfCAF
stb ππ (πΉ ) β sem ππ (πΉ ) β prf ππ (πΉ ) and stb ππ (πΉ ) β plexity as Cred π and Skept wfCAF
π respectively (cf.
π Table 2).
stg π (πΉ ).
For π β {1, 4}, consider πΉ β² from Example 1. πΉ β² β The computational complexity of the verification prob-
β1 -CAFtr by Proposition 5, and πΉ β² β β4 -CAFtr lem, on the other hand, is one level higher for general
since β4 (πΉ ) = πΉ for πΉ = ({π, πβ² , π}, {(π, π)}, CAFs when compared to wfCAFs (cf. Table 2), i.e., the
claim, β») with π β» π. It can be verified that stb π (πΉ β² ) = bounds that existing results yield for PCAFs are notPCAF tight.
{{πΌ}, {πΌ, π½}}. In the following, we examine the complexity of Ver π,π
For π = 2, let πΊ be the CAF shown on the right in for each of the considered reductions and semantics. Let
Figure 3. πΊ β β -CAF since β (πΊβ² ) = πΊ for the us first consider Reduction 1.
2 tr 2
PCAF πΊβ² with attacks {(π, π), (π, πβ² ), (πβ² , π), (πβ² , πβ² )} Proposition 10. Ver PCAF is NP-complete for π β {cf ,
π,1
and preferences π β» π and πβ² β» πβ² . stb π (πΊ) = naive}, even for transitive preferences.
{{πΌ}, {πΌ, π½}}.
Proof sketch. NP-membership follows from known re-
Table 3 summarizes our I-maximality results. Reduc- sults for general CAFs. NP-hardness: let π be an arbi-
tion 3 manages to preserve I-maximality in most cases. It trary instance of 3-Sat given as a set {πΆ1 , . . . , πΆπ } of
is also the most conservative of the reductions, preserving clauses over variables π. We construct a PCAF πΉ =
conflict-freeness and not adding new attacks. Interest- (π΄, π
, claim, β») and a set of claims π = {1, . . . , π} βͺ
ingly, the other three reductions lose I-maximality for all π as follows:
semantics.
β’ π΄ = π βͺ π βͺ π» where
π = {π₯π | π₯ β πΆπ , 1 β€ π β€ π},
6. Computational Complexity π = {π₯π | Β¬π₯ β πΆπ , 1 β€ π β€ π}, and
π» = {π₯π , π₯πΉ | π₯ β π};
In this section, we investigate the impact of preferences
on the computational complexity of claim-based rea- β’ π
= {(π₯π , π₯π ), (π₯πΉ , π₯π ) | π₯π β π } βͺ
soning. To this end, we adapt the decision problems {(π₯π , π₯π ), (π₯πΉ , π₯π ) | π₯π β π };
introduced in Section 2 to PCAFs as follows: given β’ claim(π₯π ) = claim(π₯π ) = π for π₯π , π₯π β π βͺ π ,
a preference Reduction π β {1, 2, 3, 4}, we define claim(π₯π ) = claim(π₯πΉ ) = π₯ for π₯ β π;
Cred PCAF
π,π , Skept PCAF
π,π , and Ver PCAF
π,π analogously to β’ π₯π β» π₯π for all π₯π β π and π₯π β» π₯πΉ for all
Cred π , Skept π , and Ver CAF
CAF CAF
, except that we take π₯π β π .
π
34
οΏ½Figure 4 illustrates the above construction. It can be π11,2 π21,2 ^11,2 π11,2
π
verified that π is satisfiable if and only if π β cf 1π (πΉ ). π 1
π 2
1,2 1,2
The same can be shown for naive 1π . Informally, the set ^41,2
π41,2 π 1 ^21,2 π21,2
π
π forces us to have, for each π₯ β π, π₯π or π₯πΉ in π π1 π41,2 π31,2 π2 2
thus simulating a guess for an interpretation. Due to the
removed attacks all corresponding occurrences π₯π (resp. ^31,2
π31,2 π π41,2 π31,2
π₯π ) can be added to π without conflict. Now it amounts
1
to check whether these occurrences cover all π, i.e., make π12,3 ^π2,3 π22,3 π12,3
all clauses true under the actual guess.
π22,3 π12,3
2 π3 π2 2
π22,3 ^π2,3 ^π4 π42,3
Note that the βtrickβ in above construction to guess 3 2,3
3 4
an interpretation does not work for admissible-based π 2,3 π 2,3
semantics, since the occurrences of π₯π resp. π₯π in π would π 3
π42,3 ^π3 π32,3
2,3 2,3
remain undefended. Indeed, we need a more involved π3 3
construction next.
Figure 5: Reduction of 3-Sat-instance πΆ1 = {π}, πΆ2 =
Proposition 11. Ver PCAF
π,1 is NP-complete for π β {Β¬π, π}, πΆ3 = {Β¬π, π}, to an instance (πΉ β² , π) of Ver PCAFstb,1
{stb, adm, com}, even for transitive preferences. (cf. Proof of Proposition 11). Dashed arrows are attacks
deleted from πΉ β² , i.e., they are edges in wfp(β1 (πΉ β² )).
Proof sketch. We show NP-hardness. Let π be a 3-Sat-
instance given as a set {πΆ1 , . . . , πΆπ } of clauses over
variables π. For convenience, we directly construct a
CAF πΉ = (π΄, π
, claim) with πΉ β β1 -CAFtr instead The proposition can be proven by adapting the stan-
of providing a PCAF πΉ β² such that β1 (πΉ β² ) = πΉ . This dard translation for skeptical acceptance of preferred-
is legitimate, as, by our characterization of β1 -CAFtr semantics [25, Reduction 3.7].
(see Proposition 5), we can obtain πΉ β² by simply adding We now turn our attention to Reductions 2, 3, and 4.
all edges in wfp(πΉ ) to π
and defining β» accordingly. Since these reductions do not remove conflicts between
arguments, it is easy to see that verification for conflict-
β’ π΄ = π βͺ π βͺ π» where free and naive semantics remains tractable.
π = {π₯π | π₯ β πΆπ , 1 β€ π β€ π},
π = {π₯π | Β¬π₯ β πΆπ , 1 β€ π β€ π}, and
Proposition 13. Ver PCAFπ,πβ{2,3,4} is in P for π β {cf ,
π π naive}.
π» = {π₯π,π , π₯ Λ π,π | 1 β€ π β€ 4, π₯π β π, π₯π β π };
β’ π
= {(π₯π , π₯1π,π ), (π₯1π,π , π₯2π,π ), (π₯2π,π , π₯π ), (π₯π , π₯3π,π ), Proof sketch. By Lemma 6, given a PCAF πΉ , it suffices to
(π₯3π,π , π₯4π,π ), (π₯4π,π , π₯π ) | π₯π β π, π₯π β π }; test if πΆ is conflict-free (resp. naive) in the underlying
β’ claim(π₯π ) = claim(π₯π ) = π for all π₯π , π₯π , CAF of πΉ . This problem is in P for wfCAFs (cf. Table 2).
claim(π₯ππ,π ) = claim(π₯ Λ ππ,π ) = π₯ππ,π for all
π₯ππ,π , π₯
Λ ππ,π .
As it turns out, with Reductions 2, 3, and 4 we retain
For verification consider the set π = {1, . . . , π} βͺ the benefits of wfCAFs over general CAFs for almost
{claim(π) | π β π»}. Figure 5 illustrates the above all investigated semantics with respect to computational
construction. It can be verified that (1) πΉ β β1 -CAFtr ; complexity. In short, verification for wfCAFs is easier
(2) π is satisfiable iff π β stb π (πΉ ). Likewise for adm π than on general CAFs because, given a wfCAF πΉ and a
and com π . Intuitively, for each π₯π , π₯π , the helper argu- set of claims πΆ, a set of arguments π can be constructed
ments π₯ππ,π and the corresponding cycle ensures that only in polynomial time such that π is the unique maximal ad-
one of π₯π , π₯π can be chosen. Note that π₯π and π₯π must not missible set in πΉ with claim claim(π) = πΆ [14]. Making
attack each other directly because of well-formedness in use of the fact that Reductions 2, 3, and 4 do not alter con-
the original CAF. flicts between arguments, we can construct such a max-
imal set of arguments also for PCAFs: given a PCAF πΉ
In fact, when applying Reduction 1, we lose the advan- and set πΆ of claims, we define the set πΈ0 (πΆ) containing
tages of wfCAFs for all investigated semantics, since also all arguments of πΉ with a claim in πΆ; the set πΈ1π (πΆ) is ob-
for the remaining semantics verification remains harder tained from πΈ0 (πΆ) by removing all arguments attacked
than in the case of wfCAFs. by πΈ0 (πΆ) in the underlying CAF of πΉ ; finally, the set
πΈ*π (πΆ) is obtained by repeatedly removing all arguments
Proposition 12. Ver π,1 PCAF
is Ξ£2 -complete for π β
P
not defended by πΈ1π (πΆ) in βπ (πΉ ) until a fixed point is
{prf , sem, stg}, even for transitive preferences. +
reached. Recall that π(π΄,π
) = {π | (π, π) β π
, π β π}
denotes the arguments attacked by π in (π΄, π
).
35
οΏ½Definition 12. Given a PCAF πΉ = (π΄, π
, claim, β»), a π π
set of claims πΆ, and π β {2, 3, 4}, we define πβ²π π1 π2 πβ²π
ππ ππ
πΈ0 (πΆ) ={π β π΄ | claim(π) β πΆ}; πβ²π π1 π2 πβ²π
ππ ππ
πΈ1π (πΆ) =πΈ0 (πΆ) β πΈ0 (πΆ)+
(π΄,π
) ; πβ²π πβ²
π
πΈππ (πΆ) ={π₯ β πΈπβ1
π
(πΆ) | π₯ is defended by πΈπβ1
π
(πΆ) πβ²π π π π π πβ²
π
in βπ (πΉ )} for π β₯ 2; π π π π
πΈ*π (πΆ) =πΈππ for π β₯ 2 such that πΈππ (πΆ) = πΈπβ1
π
(πΆ). Figure 6: β4 (πΉ ) from the proof of Proposition 17, π = ((πβ¨
π) β§ (Β¬π β¨ Β¬π)). Symmetric attacks drawn in gray and thick
The above definition is based on [14, Definition 5], but have been introduced by Reduction 4.
with the crucial differences that undefended arguments
are (a) computed w.r.t. βπ (πΉ ) and (b) are iteratively re-
moved until a fixed point is reached.
For conflict-free based semantics we observe that the For adm, by Lemma 15, it suffices to test whether
conflicts are not affected by the reductions and thus claim(πΈ*π (πΆ)) = πΆ. For stb, we first check whether
one can use existing results for well-formed CAFs [14, πΆ β adm ππ (πΉ ). If not, πΆ ΜΈβ stb ππ (πΉ ). If yes, then, by
Lemma 1] to obtain that πΈ1π (πΆ) is the unique candidate Lemma 15, claim(πΈ*π (πΆ)) = πΆ. We can check in poly-
for the maximal conflict-free set of arguments that real- nomial time if πΈ*π (πΆ) β stb(βπ (πΉ )). If yes, we are done.
izes the claim set πΆ. If no, then there is an argument π₯ that is not in πΈ*π (πΆ) but
is also not attacked by πΈ*π (πΆ) in βπ (πΉ ). Moreover, there
Lemma 14. Let πΉ be a PCAF, πΆ be a set of claims can be no other π β stb(βπ (πΉ )) with claim(π) = πΆ
and π β {2, 3, 4}. We have that πΆ β cf ππ (πΉ ) iff since for any such π we would have π β πΈ*π (πΆ), which
claim(πΈ1π (πΆ)) = πΆ. Moreover, if πΆ β cf ππ (πΉ ) then would imply that π does not attack π₯ and that π₯ ΜΈβ π.
πΈ1π (πΆ) is the unique maximal conflict-free set π in βπ (πΉ ) The arguments for π β {prf , sem, stg} are similar,
such that claim(π) = πΆ. but some checks require coNP-time.
Regarding admissible semantics we are looking for For complete semantics, only Reduction 3 retains the
a conflict-free set that defends all its arguments. Thus benefits of wfCAFs. Here, the fact that Reductions 2
we start from the conflict-free set πΈ1π (πΆ). Notice that and 4 can introduce new attacks leads to an increase in
arguments that are not in πΈ1π (πΆ) cannot be contained complexity.
in any admissible set π with claim(π) = πΆ. We can
com,3 is in P. Ver com,πβ{2,4} is
Proposition 17. Ver PCAF PCAF
then obtain the maximal admissible set realizing πΆ in
NP-complete, even for transitive preferences.
βπ (πΉ ) by iteratively removing arguments that are not
defended by the current set of arguments. Once we reach Proof sketch. P-membership for Ver PCAF
com,3 is similar to
a fixed-point we have an admissible set, but need to checkthe proof of Proposition 16. We demonstrate NP-
whether we still cover all the claims of πΆ. hardness of Ver PCAF
com,4 . Let π be an arbitrary instance
Lemma 15. Let πΉ be a PCAF, πΆ be a set of claims of 3-Sat given as a set πΆ of clauses over variables π
and π β {2, 3, 4}. We have that πΆ β adm ππ (πΉ ) iff and let π = {π₯ | π₯ β π}. We construct a PCAF πΉ =
claim(πΈ*π (πΆ)) = πΆ. Moreover, if πΆ β adm ππ (πΉ ) then (π΄, π
, claim, β») as well as a set of claims π = π βͺ {π}:
πΈ*π (πΆ) is the unique maximal admissible set π in βπ (πΉ ) β’ π΄ = {π} βͺ πΆ βͺ π βͺ π βͺ
such that claim(π) = πΆ. {π | π₯ β π} βͺ {πβ² | π₯ β π βͺ π};
π₯ π₯
By computing the maximal conflict-free (resp. admis- β’ π
= {(π, π) | π β πΆ} βͺ {(π, π) | π β πΆ} βͺ
sible) extensions πΈ1π (πΆ) (resp. πΈ*π (πΆ)) for a set of claims {(π, π₯) | π₯ β π, π β πΆ} βͺ
πΆ, the verification problem becomes easier for most se- {(π, π₯) | Β¬π₯ β π, π β πΆ} βͺ
mantics. {(πβ²π₯ , π₯) | π₯ β π βͺ π} βͺ
{(πβ²π₯ , ππ₯ ), (πβ²π₯ , ππ₯ ) | π₯ β π};
Proposition 16. Ver PCAFπ,πβ{2,3,4} is in P for β’ claim(π₯) = claim(π₯) = π₯ for π₯ β π,
π β {adm, stb}. It is coNP-complete for claim(π£) = π£ otherwise;
π β {prf , sem, stg}, even when considering only
β’ π₯ β» π, π₯ β» πβ²π₯ for all π₯ β π βͺ π and all π β πΆ.
transitive preferences.
Figure 6 illustrates the above construction. It can be
Proof sketch. Let πΉ = (π΄, π
, claim, β») be a PCAF, let verified that π is satisfiable iff π β com (β (πΉ )).
π 4
πΆ be a set of claims, and let π β {2, 3, 4}. We can com-
π π
pute βπ (πΉ ), πΈ1 (πΆ), and πΈ* (πΆ) in polynomial time.
36
οΏ½Table 4 vative of the four reductions, exhibits the same properties
Complexity of Ver PCAF
π,π . Results also hold when considering as wfCAFs regarding computational complexity while
only PCAFs with transitive preferences. also preserving I-maximality for most of the semantics;
π π=1 π β {2, 4} π=3 (2) Reductions 2 and 4 retain the advantages of wfCAFs
cf /adm/naive/stb NP-c in P in P regarding complexity for all but complete semantics, but
com NP-c NP-c in P do not preserve I-maximality for any investigated seman-
prf /sem/stg Ξ£P coNP-c coNP-c tics; (3) under Reduction 1, neither complexity properties
2 -c
nor I-maximality are preserved. The above results hold
even if we restrict ourselves to transitive preferences.
Table 4 summarizes our complexity results. Reduc- It is worth noting that Reduction 3 behaves favorably
tion 3 preserves the lower complexity of wfCAFs for on regular AFs as well, fulfilling many principles for
all investigated semantics, while Reductions 2 and 4 pre- preference-based semantics laid out by Kaci et al. (2018).
serve the lower complexity for all but complete semantics. A possible direction for future work is to lift the pref-
Reduction 1 does not preserve the advantages of wfCAFs, erence ordering over arguments to sets of arguments and
and rather exhibits the full complexity as general CAFs. select extensions in this way. This has been investigated
Notice that the lower complexity of the verification prob- for regular AFs in combination with Reduction 2 [21].
lem is crucial for enumerating extensions. In particular, Another direction is to extend our studies to alternative
the improved enumeration algorithm for wfCAFs [14] is semantics for CAFs [18, 19], where subset-maximization
based on the polynomial time verification of claim-sets is handled on the claim-level instead of on the argument-
and thus extends to PCAFs under Reductions 2β4. level.
7. Conclusion Acknowledgments
Many approaches to structured argumentation (i) assume We thank the anonymous reviewers for their valuable
that arguments with the same claims attack the same feedback. This work was funded by the Austrian Science
arguments and (ii) take preferences into account. Investi- Fund (FWF) under grants Y698 and W1255-N23 and by
gations on claim-augmented argumentation frameworks the Vienna Science and Technology Fund (WWTF) under
(CAFs) so far only consider (i), showing that the result- grant ICT19-065.
ing subclass of well-formed CAFs (wfCAFs) has several
desired properties. The research question of this paper
is to analyze whether these properties carry over when
References
preferences are taken into account, since the incorpora- [1] H. Li, N. Oren, T. J. Norman, Probabilistic ar-
tion of preferences can violate the syntactical restriction gumentation frameworks, in: Proc. TAFAβ11,
of wfCAFs. volume 7132 of LNCS, Springer, 2011, pp. 1β16.
To this end, we introduced preference-based claim- URL: https://doi.org/10.1007/978-3-642-29184-5_1.
augmented argumentation frameworks (PCAFs) and in- doi:10.1007/978-3-642-29184-5\_1.
vestigated the impact of the four preference reductions [2] K. Atkinson, P. Baroni, M. Giacomin, A. Hunter,
commonly used in abstract argumentation when applied H. Prakken, C. Reed, G. R. Simari, M. Thimm, S. Vil-
to PCAFs. We examined and characterized CAF-classes lata, Towards artificial argumentation, AI Maga-
that result from applying these reductions to PCAFs, zine 38 (2017) 25β36. doi:10.1609/aimag.v38i3.
yielding insights into the expressiveness of argumen- 2704.
tation formalisms that can be instantiated as CAF and [3] S. Modgil, H. Prakken, A general account of argu-
allow for preference incorporation. Furthermore, we in- mentation with preferences, Artif. Intell. 195 (2013)
vestigated the fundamental properties of I-maximality 361β397. URL: https://doi.org/10.1016/j.artint.2012.
and computational complexity for PCAFs. Preserving I- 10.008. doi:10.1016/j.artint.2012.10.008.
maximality is desirable since it implies intuitive behavior [4] K. Cyras, F. Toni, ABA+: assumption-based argu-
of maximization-based semantics, while the complexity mentation with preferences, in: Proc.KRβ16, AAAI
of the verification problem is crucial for the enumeration Press, 2016, pp. 553β556. URL: http://www.aaai.org/
of claim-extensions. Insights in terms of both semantical ocs/index.php/KR/KR16/paper/view/12877.
and computational properties provide necessary foun- [5] P. M. Dung, On the acceptability of arguments
dations towards a practical realization of this particular and its fundamental role in nonmonotonic rea-
argumentation paradigm (we refer to, e.g., [26, 27], for a soning, logic programming and n-person games,
similar research endeavor in terms of incomplete AFs). Artif. Intell. 77 (1995) 321β358. doi:10.1016/
Our results show that (1) Reduction 3, the most conser- 0004-3702(94)00041-X.
37
οΏ½ [6] S. Kaci, L. W. N. van der Torre, S. Vesic, S. Villata, [19] W. DvoΕΓ‘k, A. GreΓler, A. Rapberger, S. Woltran,
Preference in abstract argumentation, in: Hand- The complexity landscape of claim-augmented ar-
book of Formal Argumentation, Volume 2, College gumentation frameworks, in: Proc. AAAIβ21, AAAI
Publications, 2021, pp. 211β248. Press, 2021, pp. 6296β6303. URL: https://ojs.aaai.
[7] S. Modgil, Reasoning about preferences in argu- org/index.php/AAAI/article/view/16782.
mentation frameworks, Artificial Intelligence 173 [20] L. Amgoud, C. Cayrol, On the accept-
(2009) 901β934. ability of arguments in preference-based
[8] K. Atkinson, T. J. M. Bench-Capon, Value-based argumentation, in: Proc. UAIβ98, Mor-
argumentation, IfCoLog Journal of Logic and gan Kaufmann, 1998, pp. 1β7. URL: https:
its Applications 8 (2021) 1543β1588. URL: https: //dslpitt.org/uai/displayArticleDetails.jsp?mmnu=
//collegepublications.co.uk/ifcolog/?00048. 1&smnu=2&article_id=226&proceeding_id=14.
[9] S. Kaci, L. W. N. van der Torre, S. Vil- [21] L. Amgoud, S. Vesic, Rich preference-based ar-
lata, Preference in abstract argumentation, gumentation frameworks, Int. J. Approx. Reason.
in: Proc. COMMAβ18, volume 305 of FAIA, 55 (2014) 585β606. URL: https://doi.org/10.1016/j.
IOS Press, 2018, pp. 405β412. URL: https://doi. ijar.2013.10.010. doi:10.1016/j.ijar.2013.10.
org/10.3233/978-1-61499-906-5-405. doi:10.3233/ 010.
978-1-61499-906-5-405. [22] P. Baroni, M. Caminada, M. Giacomin, Abstract
[10] S. Modgil, H. Prakken, Abstract rule-based argu- argumentation frameworks and their semantics, in:
mentation, in: Handbook of Formal Argumentation, Handbook of Formal Argumentation, College Pub-
College Publications, 2018, pp. 287β364. lications, 2018, pp. 159β236.
[11] P. M. Dung, R. A. Kowalski, F. Toni, Assumption- [23] L. van der Torre, S. Vesic, The principle-based ap-
based argumentation, in: Argumentation in Ar- proach to abstract argumentation semantics, If-
tificial Intelligence, Springer, 2009, pp. 199β218. CoLog Journal of Logic and its Applications 4 (2017)
URL: https://doi.org/10.1007/978-0-387-98197-0_10. 2735β2778. URL: http://www.collegepublications.
doi:10.1007/978-0-387-98197-0\_10. co.uk/downloads/ifcolog00017.pdf.
[12] J. F. Horty, Skepticism and floating conclusions, [24] L. Amgoud, C. Cayrol, A reasoning model based
Artif. Intell. 135 (2002) 55β72. URL: https://doi. on the production of acceptable arguments, Ann.
org/10.1016/S0004-3702(01)00160-6. doi:10.1016/ Math. Artif. Intell. 34 (2002) 197β215.
S0004-3702(01)00160-6. [25] W. DvoΕΓ‘k, P. E. Dunne, Computational problems
[13] P. Baroni, R. Riveret, Enhancing statement evalua- in formal argumentation and their complexity, If-
tion in argumentation via multi-labelling systems, J. CoLog Journal of Logic and its Applications 4 (2017)
Artif. Intell. Res. 66 (2019) 793β860. doi:10.1613/ 2557β2622.
jair.1.11428. [26] D. Baumeister, M. JΓ€rvisalo, D. Neugebauer,
[14] W. DvoΕΓ‘k, S. Woltran, Complexity of abstract A. Niskanen, J. Rothe, Acceptance in incomplete
argumentation under a claim-centric view, Artif. argumentation frameworks, Artif. Intell. 295 (2021)
Intell. 285 (2020) 103290. doi:10.1016/j.artint. 103470. URL: https://doi.org/10.1016/j.artint.2021.
2020.103290. 103470. doi:10.1016/j.artint.2021.103470.
[15] M. Caminada, S. SΓ‘, J. AlcΓ’ntara, W. DvoΕΓ‘k, On [27] B. Fazzinga, S. Flesca, F. Furfaro, Revisiting the
the equivalence between logic programming se- notion of extension over incomplete abstract argu-
mantics and argumentation semantics, Int. J. Ap- mentation frameworks., in: Proc. IJCAIβ20, 2020,
prox. Reasoning 58 (2015) 87β111. doi:10.1016/j. pp. 1712β1718.
ijar.2014.12.004.
[16] A. Rapberger, Defining argumentation semantics
under a claim-centric view, in: Proc. STAIRSβ20,
volume 2655 of CEUR Workshop Proceedings, CEUR-
WS.org, 2020. URL: http://ceur-ws.org/Vol-2655/
paper2.pdf.
[17] H. Prakken, G. A. Vreeswijk, Logics for defeasi-
ble argumentation, in: Handbook of Philosophical
Logic, volume 4, Springer, 2002.
[18] W. DvoΕΓ‘k, A. Rapberger, S. Woltran, Argumenta-
tion semantics under a claim-centric view: Prop-
erties, expressiveness and relation to SETAFs, in:
Proc. KRβ20, IJCAI.org, 2020, pp. 341β350. doi:10.
24963/kr.2020/35.
38
οΏ½