In this paper, we study the efect 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 efects 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 diferent classes of claim-augmented argumentation frameworks, and behave diferently 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.
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 [
The diference in argument strength and the resulting served in [
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 argumost 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.
Example 1. Consider two arguments , ′ with claim , and another argument having claim . Moreover, both and ′ attack , while attacks . Furthermore assume that we are given the additional information that is preferred over ′ (for example, if assumptions in the support of are stronger than assumptions made by ′). A common method to integrate such information on argument rankings is to delete attacks from arguments that attack preferred arguments. In this case, we delete the attack from ′ to .
Both frameworks are depicted below: represents the original situation while ′ is the CAF resulting from deleting the unsuccessful attack from ′ on the argument .
: ′ : ′ ′ tion 2) is {, ′} which translates to { } on the claim
since ′ does not attack . In ′, the argument-sets {, ′} and {, } are both acceptable w.r.t. to stable-semantics. In terms of claims this translates to { } and {, shows that I-maximality is violated on the claim-level. }, which
Although well-formedness can not be guaranteed in
view of preferences, this does not imply arbitrary
behavior of the resulting CAF: on the one hand, preferences
conform to a certain type of ordering (e.g., asymmetric,
strict, partial, or total orders) over the set of arguments;
on the other hand, it is evident that the deletion,
reversion, and other types of attack manipulation impose
certain restrictions on the structure of the resulting CAF.
Combining both aspects, we obtain that, assuming
wellformedness of the initial framework, it is unlikely that
preference incorporation results in arbitrary behavior.
preference-based argumentation frameworks (PAFs) [20]
into AFs but is also used in many structured
argumentation formalisms such as ASPIC+. This reduction has been
criticized due to several problematic side-efects, e.g., it
can be the case that two conflicting arguments are jointly
acceptable, and has been accordingly adapted in [21]; two
other reductions have been introduced in [
We show that for three of the four reductions, the verification problem drops by one level in the polynomial hierarchy for all except complete semantics and is thus not harder than for well-formed CAFs (which in turn has the same complexity as the corresponding AF problems). Complete semantics remain hard for all but one preference reduction. Moreover, it turns out that verification for the reduction which deletes attacks from weaker arguments remains as hard as for general CAFs. The key motivation of this paper is to identify and exOur results constitute a systematic study of the strucploit structural properties of preferential argumentation tural and computational efect of preferences on claim in the scope of claim acceptance. The aforementioned acceptance. Since we use CAFs as our base formalism, 5]. Complexity of CAFs (Δ ∈ {CAF , wfCAF }). Ver CAF
Ver wfCAF
in P NP-c NP-c in P NP-c NP-c Σ2P-c
trivial trivial
P-c coNP-c coNP-c Π2P-c Π2P-c
NP-c NP-c NP-c NP-c NP-c Σ2P-c Σ2P-c in P in P in P in P in P coNP-c coNP-c tion of AFs [14]. claim, and thus constitute a straightforward generaliza- all CAFs ∈ and all , ∈ ( ), ⊆ implies our investigations extend to large classes of formalisms that can be represented as CAFs, just like results on Dung AFs yield insights for formalisms that can be captured by AFs. naive x x stb x ✓ prf x ✓ sem x ✓ stg x ✓
We first define (abstract) argumentation frameworks [ denotes a countable infinite domain of arguments. Definition 1.
ple = (, ) where ⊆
is a finite set of arguments and ⊆ × is an attack relation between arguments. Let ⊆ some ∈ ; + = { ∈ | ∃ ∈ : (, ) ∈ } denotes the set of arguments attacked by . ⊕ = ∪ + . We say attacks (in ) if (, ) ∈ for (in ) by if ∈ + for each with (, ) ∈ . is the range of in . An argument ∈ is defended
Given an AF = (, ) it can be convenient to write ∈ for ∈ and (, ) ∈ for (, ) ∈ . Semantics for AFs are defined as functions which assign to each AF = (, ) a set ( ) ⊆ consider for the functions cf , adm, com, naive, stb, prf , sem, and stg which stand for conflict-free, admissible, complete, naive, stable, preferred, semi-stable, and 2 of extensions. We stage, respectively [22].
Definition 2. is conflict-free (in
Let = (, ) be an AF. A set ⊆ ), if there are no , ∈ , such that (, ) ∈ . cf ( ) denotes the collection of conflict-free sets of . For a conflict-free set ∈ cf ( ), it holds that defended by in is contained in ; • ∈ adm( ) if each ∈ is defended by in ; • ∈ com( ) if ∈ adm( ) and each ∈ • ∈ naive( ) if there is no ∈ cf ( ) with ⊂ ; in ; • ∈ stb( ) if each ∈ ∖ is attacked by • ∈ prf ( ) if ∈ adm( ) and there is no ∈ adm( ) with ⊂ ; ∈ adm( ) with ⊕ ⊂ ⊕ ; • ∈ sem( ) if ∈ adm( ) and there is no • ∈ stg ( ) if there is no ∈ cf ( ) with ⊕ ⊂
⊕ . stg }.
Example 2. Consider the AF = ({, ′, }, {(, ), (′, ), (, )}) from Example 1, ignoring claims and . Then cf ( ) = {∅, {}, {′}, {}, {, ′}}, adm( ) = and ( ) = {{, ′}} for {∅, {}, {′}, {, ′}}, naive( ) =
{{}, {, ′}}, ∈ {com, stb, prf , sem, CAFs are AFs in which each argument is assigned a
Definition 3.
work (CAF) is a triple (, , claim) where (, ) is an AF and claim : → Claims is a function that maps arguments to claims. The claim-function can be extended to sets of arguments, i.e., claim() = {claim() | ∈ }.
which all arguments with the same claim attack the same arguments, i.e., for all , ∈ with claim() = claim() we have { | (, ) ∈ } = { | (, ) ∈ }.
The semantics of CAFs are based on those of AFs. Definition 4.
Let = (, , claim) be a CAF.
( ) = {claim() | ∈ ((, ))}. stb( ) = {{ }}.
Example 3. Consider the CAF from Example 1. For{(, ), (′, ), (, )}, claim() = claim(′) mally, = (, , claim) with = {, ′, }, =
= , and claim() = . is well-formed and the underlying AF of was investigated in Example 2. From there we can infer that, e.g., cf( ) = {∅, { }, { }}, adm( ) = {∅, { }}, naive( ) = {{ }, { }}, and
cf( ) [
Well-known basic relations between diferent AF semantics also hold for : stb( ) ⊆
sem( ) ⊆ adm( ) as well as stb( ) ⊆ stg ( ) ⊆ Note that the semantics
∈ {naive, stb, prf , sem, ⊆ stg } employ argument maximization and result in incomparable extensions on regular AFs: for all , ∈ ( ),
implies = . This property is referred to as I-maximality, and is defined analogously for CAFs: Definition 5. is I-maximal for a class of CAFs if, for ℛ4()
Notice that preferences in PCAFs are not required to
be transitive. While transitivity of preferences is often
assumed in argumentation [
We furthermore consider these reasoning problems re- The literature describes four such reductions for
regustricted to wfCAFs and denote them by Cred wfCAF , lar AFs [
As discussed in the previous sections, wfCAFs are a natural 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 preferclaim-centric view we introduce preference-based CAFs. ence ordering while Reduction 2 reverts such attacks. ReThese 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 efect 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 • = 1: ∀, ∈ : (, ) ∈ ′ ⇔ (, ) ∈ ,
̸≻ • = 2: ∀, ∈ : (, ) ∈ ′ ⇔ ((, ) ∈ ,
̸≻ ) ∨ ((, ) ∈ , (, ) ∈/ , ≻ ) • = 3: ∀, ∈ : (, ) ∈ ′ ⇔ ((, ) ∈ ,
̸≻ ) ∨ ((, ) ∈ , (, ) ̸∈ ) • = 4: ∀, ∈ : (, ) ∈ ′ ⇔ ((, ) ∈ , ̸≻ ) ∨ ((, ) ∈ , (, ) ∈/ , ≻ ) ∨ ((, ) ∈ , (, ) ̸∈ ) 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 is applied to the given PCAF; then, CAF-semantics are applied to the resulting CAF.
Definition 8.
Let be a PCAF and let ∈ {1, 2, 3, 4}.
tive to Reduction is defined as ( ) = (ℛ( )). Example 4. Let = (, , claim, ≻ ) be the PCAF where = {, ′, }, = {(, ), (′, ), (, )}, claim() = claim(′) = , claim() = , and ≻
′.
Example 3. { }
, {, ℛ1( ) = (, ′, claim) with ′ = {(, ), (, )}, which is the same CAF as ′ in Example 1. It can be veriifed that, e.g., adm1( ) = adm(ℛ1( )) = {{∅, { }, }} and stb1( ) = {{ } , {, }}.
{ }}, and stb2( ) = {{ }, { }}. sions of a PCAF. For example, ℛ2( ) = (, ′′, claim) with ′′ = {(, ), (, ), (, )}, adm2( ) = {∅, { },
It is easy to see that basic relations between semantics carry over from CAFs, as, if we have ( ) ⊆ ( ) for two semantics , and all CAFs , then also ( ) ⊆ that for all ∈ prf ( ) ⊆ ( ) for all PCAFs . It thus holds {1, 2, 3, 4}, stb( ) ⊆ sem( ) ⊆ adm( ) as well as stb( ) ⊆ stg ( ) ⊆ naive( ) ⊆ cf ( ).
Remark 1. In this paper we require the underlying CAF of a PCAF to be well-formed. The reason for this is that we are interested in whether the benefits of well-formed CAFs are preserved when preferences have to be taken into account. Even from a technical perspective, admitting PCAFs with a non-well-formed underlying CAF is not very interesting with respect to the questions addressed in this paper. Indeed, any CAF could be obtained from such general
ing, by simply specifying the desired CAF and an empty preference relation. Thus, such general PCAFs have the same properties regarding I-maximality and complexity as general CAFs.
Our first step towards understanding the efect of preferences 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 obtained from applying the reductions of Definition 7 to PCAFs. ℛ4-CAF respectively. Solid arrows are attacks, dashed arrows indicate where attacks are missing for the CAF to be well-formed.
Definition 9.
ℛ-CAF denotes the set of CAFs that can be obtained by applying Reduction to PCAFs, i.e., ℛ-CAF = {ℛ( ) | is a PCAF}.
It is easy to see that ℛ-CAF, with ∈ {1, 2, 3, 4}, contains all wfCAFs (we can simply specify the desired wfCAF and an empty preference relation). However, not all CAFs are contained in ℛ-CAF. For example, = ({, }, {(, ), (, )}, claim) with claim() = claim() can not be obtained from a PCAF ′: such ′ would need to contain either (, ) or (, ). But then, since the underlying CAF of a PCAF must be well-formed, ′ would have to contain a self-attack which can not be removed by any of the reductions. This is enough to conclude1 that the four new classes are located in-between wfCAFs and general CAFs: it holds that wfCAF ⊂ ℛ -CAF ⊂ CAF.
wfCAF the set of all wfCAFs. For all ∈ {1, 2, 3, 4}
Furthermore, the new classes are all distinct from each other, i.e., we are indeed dealing with four new CAF classes: ℛ -CAF and ℛ3-CAF ⊂ ℛ -CAF.
Proposition 2. For all ∈
{1, 2, 4} and all ∈ {1, 2, 3, 4} such that ̸= it holds that ℛ-CAF ̸⊆ Proof sketch. Figure 2 shows CAFs that are in only one of ℛ1-CAF, ℛ2-CAF, and ℛ4-CAF. Consider the PCAF = ({, }, {(, ), (, )}, claim, ≻ ) with claim() = claim() = and ≻
. Then ℛ1( ), ℛ2( ), and ℛ4( ) are the CAFs of Figure 2. Since selfattacks are not removed or introduced by any reduction, and the underlying CAF must be well-formed, is the only PCAF from which ℛ1( ), ℛ2( ), and ℛ4( ) can be obtained. Note that ℛ3( ) is simply the underlying CAF of . ℛ3-CAF ⊂ ℛ -CAF follows by the fact that if an attack (, ) is removed by Reduction 3 from some PCAF , then (, ) ∈ . In this case, all reductions behave in the same way (cf. Definition 7 or 1Although many proof sketches are provided in this text, a preprint of this paper with full proofs in the appendix can be accessed at https://arxiv.org/abs/2204.13305.
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 Reducresults 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 ≻ if {(, ) | (, ) 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 argument for ℛ4-CAF is similar.
Intuitively, the wf-problematic part of a CAF consists of those attacks that are missing for to be wellformed (cf. Figure 2). Indeed, is a wfCAF if and only if wfp( ) = ∅. The four new classes can be characterized as follows:
The above characterizations give us some insights into the efect of the various reductions on wfCAFs. Indeed, the similarity between the characterizations of ℛ1-CAF and ℛ3-CAF, resp. ℛ2-CAF and ℛ4-CAF, can intuProposition 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 if (, ) ∈ wfp( ) implies introduce attacks. Furthermore, Proposition 3 allows us (, ) ̸∈ wfp( ); to decide in polynomial time whether a given CAF • ∈ ℛ2-CAF if 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 if (, ) ∈ wfp( ) implies duction to PCAFs with a transitive preference rela(, ) ∈ ; tion. It is clear that ℛ-CAFtr ⊆ ℛ -CAF for all • ∈ ℛ4-CAF if there are no arguments ∈ {1, 2, 3, 4}. Interestingly, the relationship be, ′, , ′ in with claim() = claim(′) tween the classes ℛ-CAFtr is diferent 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 ≻ if (, ) ∈ ′ ∖ . Observe that ≻ it holds that ℛ-CAFtr ̸⊆ ℛ -CAFtr . is asymmetric. Conversely, a CAF with arguments , such that (, ) ∈ wfp() and (, ) ∈ wfp() can not be obtained via Reduction 1 from a PCAF ′, since ′
We will not characterize all four classes ℛ-CAFtr .
However, capturing ℛ1-CAFtr will prove useful when analyzing the computational complexity of PCAFs using 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.
Proposition 5. ∈
ℛ1-CAFtr for a CAF if and that there is no path from to in wfp( ). only if (1) wfp( ) is acyclic and (2) (, ) ∈ implies Proof sketch. Assume there is a cycle (1, . . . , , 1) in we have (1, 2), . . . , (, 1) tacks, if there is a PCAF ′ such that ℛ1( ′) = , 1, i.e., ≻ ∈ ′.
This implies is not asymmet1 ≻ ≻
− 1 ≻ · · · ≻ ric. Similarly, if there is a path (1, . . . , ) in wfp( )
1 in ′. But then we have to define (1, ) ̸∈ ℛ1( ′).
≻ · · · ≻
If wfp( ) is acyclic and there is no path from to in wfp( ) such that (, ) ∈ , then we can construct a PCAF ′ such that ℛ1( ′) = in the same way as when ≻ is not transitive (cf. proof of Proposition 3).
From the high-level point of view, our characterization results yield insights into the expressiveness of argumentation formalisms that allow for preferences. Propositions 3 and 5 show which situations can be captured by formalisms which (i) constructs attacks based on the claim of the attacking argument (i.e., formalisms with well-formed attack relation) and (ii) incorporate asymmetric or transitive preference relations on arguments using one of the four reductions. 5. I-Maximality wfp( ). Then, since Reduction 1 can not introduce at- freeness. It is easy to see that this is not the case for ′ ′ ′
′′
Proposition 8 and 9). Dashed arrows are edges in wfp( ).
In other words, Reductions 2, 3, and 4 preserve conflictReduction 1. In fact, Reduction 1 has been deemed problematic for exactly this reason when applied to regular AFs [21], although it is still discussed and considered in the literature alongside the other reductions [6]. We ifrst consider Reduction
3, and show that it preserves I-maximality for some, but not all, semantics.
Proposition 7. prf 3, stb3, and sem3 are I-maximal for
Proof. By stb3( ) ⊆ sem3( ) ⊆
prf 3( ) it sufices to , ∈ prf 3( ). Then there are ′, ′ ⊆ consider prf 3. Towards a contradiction, assume there is a PCAF = (, , claim, ≻ ) such that ⊂ for some
such that ′ ∈ prf (ℛ3( )), claim(′) = , ′ ∈ prf (ℛ3( )), and claim( ′) = . ′ ̸⊆
′ since ′ ∈ prf (ℛ3( )).
There are two possibilities for why ̸∈ ′.
Thus, there is ∈ ′ such that ̸∈ ′. But claim() ∈ , i.e., there is ′ ∈ ′ with claim(′) = claim().
Case 1: ′ ∪ {} ̸∈ cf (ℛ3( )), i.e., there exists ∈ ′ such that ̸∈ ′ and either (, ) ∈ or (, ) ∈ . In fact, (, ) ̸∈ : otherwise, by the well-formedness of (, , claim), we have (′, ) ∈ and, by Lemma 6, ′ ̸∈ cf (ℛ3( )). Thus, (, ) ∈ . must defend in ℛ3( ), i.e., there exists ∈ ′ such that (, ) ∈ ℛ3( ). Then (, ) ∈ . Since ⊂ there exists ′ ∈ ′ such that claim(′) = claim().
≻ But then ′ ̸∈ cf (ℛ3( )). Contradiction.
Case 2: is not defended by ′, i.e., there exists ∈ that is not attacked by ′ and such that (, ) ∈ ℛ3( ).
By the same argument as above, there is ′ ∈ ′ with (′, ) ∈ . It cannot be that (′, ) ∈ ℛ3( ), i.e., ′. By the definition of Reduction
3, (, ′) ∈ and thus (, ′) ∈ ℛ3( ). But then ′ ̸∈ adm(ℛ3( )).
3, (, ) ∈ ℛ3( ). ′
Of course, positive results regarding the I-maximality of PCAFs with arbitrary preferences, such as in the above proposition, still hold for PCAFs with transitive preference orderings. Conversely, for negative results, it sufsitive orderings to obtain results for the more general One of the advantages of wfCAFs over general By the definition of Reduction CAFs is that they preserve I-maximality under most maximization-based semantics (cf. Table 1), which leads to more intuitive behavior of these semantics when congate whether these advantages are preserved when prefsidering extensions on the claim-level. We now investi- (′, ) ∈ by the well-formedness of (, , claim). erences are introduced. if, for all in and all , ∈ ( ), ⊆ implies
From known properties of wfCAFs (cf. Table 1) it folIt remains to investigate the I-maximality of prf , stb, sem, and stg for PCAFs. For convenience, given a lows directly that naive is not I-maximal for PCAFs. Contradiction.
CAF = (, , claim) and ⊆ write ∈ ( ) for ∈ ((, )).
, we sometimes cf ((, , claim)) for ∈ {2, 3, 4}. and ⊆ . ∈ cf (ℛ( )) if and only if ∈ case.
Lemma 6. Let = (, , claim, ≻ ) be a PCAF fices to show that I-maximality is not preserved on tran
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 arguments as , attacks {(, ), (, ), (, ), (′, ), (, ′)} and ≻ ′. Moreover, it can be verified that stg 3( ′) = {{ }, {, }, { }}.
In contrast to Reduction 3, under Reductions 1, 2, and 4 we lose I-maximality for all semantics.
Proposition 9. , with ∈ {prf , stb, sem, stg } and ∈ {1, 2, 4}, is not I-maximal for PCAFs, even when considering only transitive preferences.
Proof sketch. We only need to show this for stb since stb( ) ⊆ sem( ) ⊆ prf ( ) and stb( ) ⊆ stg ( ).
For ∈ {1, 4}, consider ′ from Example 1. ′ ∈ ℛ1-CAFtr by Proposition 5, and ′ ∈ ℛ4-CAFtr since ℛ4( ) = for = ({, ′, }, {(, )}, claim, ≻ ) with ≻ . It can be verified that stb( ′) = {{ }, {, }}.
For = 2, let be the CAF shown on the right in Figure 3. ∈ ℛ2-CAFtr since ℛ2(′) = for the PCAF ′ with attacks {(, ), (, ′), (′, ), (′, ′)} and preferences ≻ and ′ ≻ ′. stb() = {{ }, {, }}.
In this section, we investigate the impact of preferences on the computational complexity of claim-based reasoning. To this end, we adapt the decision problems introduced in Section 2 to PCAFs as follows: given a preference Reduction ∈ {1, 2, 3, 4}, we define Cred ,PCAF , Skept , PCAF analogously to
PCAF , and Ver , Cred CAF , Skept CAF , and Ver CAF , except that we take 1 1 2 2 3 3 1 1 2 2 4 4 3 3 4 4 a PCAF instead of a CAF as input and appeal to the semantics instead of the semantics. Membership results for PCAFs can be inferred from results for general CAFs (recall that the preference reductions from PCAFs to the respective CAF class can be done in polynomial time), and hardness results from results for wfCAFs. Thus, the complexity of credulous and skeptical acceptance follows immediately from known results for CAFs and wfCAFs: given ∈ {1, 2, 3, 4} and ∈ {cf , adm, com, naive, stb, prf , sem, stg }, the problems Cred ,PCAF and Skept ,
PCAF have the same complexity as Cred wfCAF and Skept wfCAF respectively (cf.
Table 2).
The computational complexity of the verification problem, on the other hand, is one level higher for general CAFs when compared to wfCAFs (cf. Table 2), i.e., the bounds that existing results yield for PCAFs are not tight.
PCAF In the following, we examine the complexity of Ver , for each of the considered reductions and semantics. Let us first consider Reduction 1.
PCAF is NP-complete for ∈ {cf , Proposition 10. Ver , 1 naive}, even for transitive preferences.
Proof sketch. NP-membership follows from known results for general CAFs. NP-hardness: let be an arbitrary instance of 3-Sat given as a set {1, . . . , } of clauses over variables . We construct a PCAF = (, , claim, ≻ ) and a set of claims = {1, . . . , } ∪ as follows: • = ∪ ∪ where = { | ∈ , 1 ≤ ≤ }, = { | ¬ ∈ , 1 ≤ ≤ }, and = { , | ∈ }; • = {( , ), ( , ) | ∈ } ∪
{( , ), ( , ) | ∈ }; • claim() = claim() = for , ∈ ∪ ,
claim( ) = claim( ) = for ∈ ; • ≻ for all ∈ and ≻ for all
∈ .
Note that the “trick” in above construction to guess an interpretation does not work for admissible-based semantics, since the occurrences of resp. in would remain undefended. Indeed, we need a more involved construction next.
PCAF is NP-complete for Proposition 11. Ver , 1 {stb, adm, com}, even for transitive preferences.
∈ Proof sketch. We show NP-hardness. Let be a 3-Satinstance given as a set {1, . . . , } of clauses over variables . For convenience, we directly construct a CAF = (, , claim) with ∈ ℛ1-CAFtr instead of providing a PCAF ′ such that ℛ1( ′) = . This is legitimate, as, by our characterization of ℛ1-CAFtr (see Proposition 5), we can obtain ′ by simply adding all edges in wfp( ) to and defining ≻ accordingly. , , ˆ, .
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 if ∈ 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 adone 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 conthe original CAF. lficts between arguments, we can construct such a maximal 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 obfor 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 Proposition 12. Ver ,PC1AF is Σ2P-complete for ∈ no*t(de)feisnodbetdaibnyedb1y(re)pienatℛedl(yre)muonvtiilnag fixaleldarpgouimnteinsts {prf , sem, stg }, even for transitive preferences. reached. Recall that + (,) = { | (, ) ∈ , ∈ } denotes the arguments attacked by in (, ). set of claims , and ∈ {2, 3, 4}, we define
Given a PCAF = (, , claim, ≻ ), a 0() ={ ∈ | claim() ∈ }; 1 () =0() ∖ 0()(+,); () ={ ∈ − 1() | is defended by − 1()
in ℛ( )} for ≥ 2; * () = for ≥ 2 such that () = − 1().
The above definition is based on [ 14, Definition 5], but with the crucial diferences that undefended arguments moved until a fixed point is reached. are (a) computed w.r.t. ℛ( ) and (b) are iteratively re
For conflict-free based semantics we observe that the conflicts are not afected by the reductions and thus one can use existing results for well-formed CAFs [14, Lemma 1] to obtain that 1 () is the unique candidate for the maximal conflict-free set of arguments that realizes the claim set .
such that claim() = . and ∈ {2, 3, 4}.
We have that ∈ cf ( ) if claim(1 ()) = . Moreover, if ∈ cf ( ) then 1 () is the unique maximal conflict-free set in ℛ( )
Regarding admissible semantics we are looking for a conflict-free set that defends all its arguments. Thus we start from the conflict-free set 1 (). Notice that arguments that are not in 1 () cannot be contained in any admissible set with claim() = . We can then obtain the maximal admissible set realizing in ℛ( ) by iteratively removing arguments that are not defended by the current set of arguments. Once we reach a fixed-point we have an admissible set, but need to check whether we still cover all the claims of . such that claim() = .
and ∈ {2, 3, 4}.
We have that ∈ adm( ) if claim(* ()) = . Moreover, if ∈ adm( ) then * () is the unique maximal admissible set in ℛ( )
By computing the maximal conflict-free (resp. admissible) extensions 1 () (resp. * ()) for a set of claims , the verification problem becomes easier for most semantics.
Proposition
16.
∈ ∈ transitive preferences.
{adm, stb}.
PCAF Ver , ∈{2,3,4} is in
P
for It is
coNP-complete for {prf , sem, stg }, even when considering only Proof sketch. Let = (, , claim, ≻ ) be a PCAF, let be a set of claims, and let ∈ {2, 3, 4}. We can compute ℛ( ), 1 (), and * () in polynomial time. ′ ′ ′ ′ 1 1 2 2 ′ ′ ′ ′ have been introduced by Reduction 4. ) ∧ (¬ ∨ ¬)). Symmetric attacks drawn in gray and thick
For adm, by Lemma 15, it sufices to test whether claim(* ()) = . For stb, we first check whether ∈ adm( ). If not, ̸∈ stb( ). If yes, then, by Lemma 15, claim(* ()) = . We can check in polynomial time if * () ∈ stb(ℛ( )). If yes, we are done. If no, then there is an argument that is not in () but is also not attacked by * () in ℛ( ). Moreover, there can be no other ∈ stb(ℛ( )) with claim() = * since for any such we would have ⊆ would imply that does not attack and that ̸∈ . * (), which The arguments for
∈ {prf , sem, stg } are similar, but some checks require coNP-time.
For complete semantics, only Reduction 3 retains the benefits of wfCAFs. Here, the fact that Reductions 2 and 4 can introduce new attacks leads to an increase in complexity.
Proposition 17. Ver cPoCmA,F3 is in P. Ver cPoCmA,F∈{2,4} is Proof sketch. P-membership for Ver cPoCmA,F3 is similar to the proof of Proposition 16.
We demonstrate NPhardness of Ver cPoCmA,F4 . Let be an arbitrary instance of 3-Sat given as a set of clauses over variables and let = { | ∈ }. We construct a PCAF = (, , claim, ≻ ) as well as a set of claims = ∪ { }: • = { } ∪ ∪ ∪ ∪ • = {(, ) | ∈ } ∪ {(, ) | ∈ } ∪ { | ∈ } ∪ {′ | ∈ ∪ }; {(, ) | ∈ , ∈ } ∪ {(, ) | ¬ ∈ , ∈ } ∪ {(′, ) | ∈ ∪ } ∪ {(′, ), (′, ) | ∈ }; claim() = otherwise; • claim() = claim() = for ∈ , • ≻ , ≻ ′ for all ∈ ∪ and all ∈ . Figure 6 illustrates the above construction. It can be verified that is satisfiable if ∈ com(ℛ4( )).
Many approaches to structured argumentation (i) assume that arguments with the same claims attack the same arguments and (ii) take preferences into account. Investigations on claim-augmented argumentation frameworks (CAFs) so far only consider (i), showing that the resulting 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 preferences are taken into account, since the incorporation of preferences can violate the syntactical restriction of wfCAFs.
To this end, we introduced preference-based claimaugmented argumentation frameworks (PCAFs) and investigated the impact of the four preference reductions commonly used in abstract argumentation when applied to PCAFs. We examined and characterized CAF-classes that result from applying these reductions to PCAFs, yielding insights into the expressiveness of argumentation formalisms that can be instantiated as CAF and allow for preference incorporation. Furthermore, we investigated the fundamental properties of I-maximality and computational complexity for PCAFs. Preserving Imaximality is desirable since it implies intuitive behavior of maximization-based semantics, while the complexity of the verification problem is crucial for the enumeration of claim-extensions. Insights in terms of both semantical and computational properties provide necessary foundations towards a practical realization of this particular argumentation paradigm (we refer to, e.g., [26, 27], for a similar research endeavor in terms of incomplete AFs).
Our results show that (1) Reduction 3, the most conservative of the four reductions, exhibits the same properties as wfCAFs regarding computational complexity while also preserving I-maximality for most of the semantics; (2) Reductions 2 and 4 retain the advantages of wfCAFs regarding complexity for all but complete semantics, but do not preserve I-maximality for any investigated semantics; (3) under Reduction 1, neither complexity properties nor I-maximality are preserved. The above results hold even if we restrict ourselves to transitive preferences. on regular AFs as well, fulfilling many principles for preference-based semantics laid out by Kaci et al. (2018).
A possible direction for future work is to lift the
preference ordering over arguments to sets of arguments and
for regular AFs in combination with Reduction 2 [21].
Another direction is to extend our studies to alternative
semantics for CAFs [
We thank the anonymous reviewers for their valuable feedback. This work was funded by the Austrian Science Fund (FWF) under grants Y698 and W1255-N23 and by the Vienna Science and Technology Fund (WWTF) under grant ICT19-065.
in: Proc. TAFA’11, volume 7132 of LNCS, Springer, 2011, pp. 1–16.
URL: https://doi.org/10.1007/978-3-642-29184-5_1.
doi:10.1007/978-3-642-29184-5\_1. [2] K. Atkinson, P. Baroni, M. Giacomin, A. Hunter,
H. Prakken, C. Reed, G. R. Simari, M. Thimm, S. Villata, Towards artificial argumentation, AI Magazine 38 (2017) 25–36. doi:10.1609/aimag.v38i3. and rather exhibits the full complexity as general CAFs. select extensions in this way. This has been investigated