Difference between revisions of "Vol-3197/paper3"
Jump to navigation
Jump to search
(modified through wikirestore by wf) |
|||
| Line 1: | Line 1: | ||
=Paper= | =Paper= | ||
| + | |||
{{Paper | {{Paper | ||
|id=Vol-3197/paper3 | |id=Vol-3197/paper3 | ||
| − | | | + | |wikidataid=Q117341398 |
|title=The Effect of Preferences in Abstract Argumentation Under a Claim-Centric View | |title=The Effect of Preferences in Abstract Argumentation Under a Claim-Centric View | ||
|pdfUrl=https://ceur-ws.org/Vol-3197/paper3.pdf | |pdfUrl=https://ceur-ws.org/Vol-3197/paper3.pdf | ||
| + | |dblpUrl=https://dblp.org/rec/conf/nmr/BernreiterDRW22 | ||
|volume=Vol-3197 | |volume=Vol-3197 | ||
| + | |storemode=property | ||
|authors=Michael Bernreiter,Wolfgang Dvořák,Anna Rapberger,Stefan Woltran | |authors=Michael Bernreiter,Wolfgang Dvořák,Anna Rapberger,Stefan Woltran | ||
| − | |||
}} | }} | ||
| + | =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== | ||
<pdf width="1500px">https://ceur-ws.org/Vol-3197/paper3.pdf</pdf> | <pdf width="1500px">https://ceur-ws.org/Vol-3197/paper3.pdf</pdf> | ||
Revision as of 16:06, 30 March 2023
Paper
| Paper | |
|---|---|
 edit
| |
| description | |
| 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
�