In abstract argumentation, arguments jointly attacking single arguments is a well-understood concept, captured by the established notion of SETAFs-argumentation frameworks with collective attacks. In contrast, the idea of sets attacking other sets of arguments has not received much attention so far. In this work, we contribute to the development of set-to-set defeat in formal argumentation. To this end, we introduce so called hyper argumentation frameworks (HYPAFs), a new formalism that extends SETAFs by allowing for set-to-set attacks. We investigate this notion by interpreting these novel attacks in terms of universal, indeterministic, and collective defeat. We will see that universal defeat can be naturally captured by the already existing SETAFs. While this is not the case for indeterministic defeat, we show a close connection to attack-incomplete argumentation frameworks. To formalize our interpretation of collective defeat, we develop novel semantics yielding a natural generalization of attacks between arguments to set-to-set attacks. We investigate fundamental properties and identify several surprising obstacles; for instance, the well-known fundamental lemma is violated, and the grounded extension might not exist. Finally, we investigate the computational complexity of the thereby arising problems.
ied. However, some preliminary considerations were performed, e.g. in [5] where defeat is modeled not based Formal argumentation is a major research area in knowl- on directed graphs but using rule-like statements; in [6] edge representation and reasoning, with applications in with the aim of formalizing global conflicts; Nielsen and various fields in the realm of Artificial Intelligence. The Parsons [2] reduce these phenomena to SETAFs; and by most popular formalism in the abstract setting are Ar- Gabbay and Gabbay [7] who investigate (among other nogumentation Frameworks (AFs) due to Dung [1], where tions) cases where the attacking set applies conjunctively arguments are modeled as the nodes of a directed graph and the attacked set is understood disjunctively. while the edges are interpreted as attacks. As oftentimes In this work, we provide the first thorough analysis of the use of sets instead of singular attackers comes handy, this setting. Naturally, the question arises of how to intergeneralizations have been proposed—most notably, col- pret an attack from a set of arguments to another set lective attacks [2]. These frameworks (referred to as of arguments? We investigate three natural notions that SETAFs) have recently been in the focus of researchers, capture diferent motivations: (i) universal defeat, i.e., acsee e.g., [3, 4]. SETAFs, however, are restricted in the cepting each ∈ defeats all ∈ : we argue that this sense that a set of arguments can attack only a single amounts to merely a simplification of the representation argument. of SETAFs. (ii) indeterministic defeat, i.e., we model the
The natural counter-part, namely allowing attacks be- situation where it is unknown which subset of is
attween sets of arguments, has not yet been widely stud- tacked by . Hence, the main motivation for this concept
is to model incomplete information of an agent’s
knowl2S1epstteImntberenra2t–io4n,a20l2W3,oRrkhsohdoeps,oGnrNeeocnemonotonic Reasoning, edge base. Consequently, we show a close connection to
* Corresponding author. attack-incomplete frameworks [
After briefly recalling the basic notions of SETAFs and formally introducing our HYPAFs (Section 2) we discuss the three defeat-modes, namely the simple case of universal defeat (Section 3), indeterministic defeat (Section 4), and collective defeat (Section 5). Finally, we conclude in Section 7.
In this section we briefly recall the definitions relevant to SETAFs (argumentation frameworks with collective attacks) and introduce our hyperframeworks (HYPAFs).
Argumentation Frameworks with Collective Attacks (SETAFs) were introduced by Nielsen and Parsons [2] as a generalization of Dung’s AFs [1].
Definition 2 (SETAFs). A SETAF is a pair SF = (, ) where is a finite set of arguments, and ⊆ 2 × is the attack relation1. • ∈ adm(SF ), if defends itself in SF , • ∈ com(SF ), if ∈ adm(SF ) and ∈ for all ∈ defended by , • ∈ grd(SF ), if = ⋂︀ ∈com(SF ) , • ∈ pref(SF ), if ∈ adm(SF ) and ∄ ∈ adm(SF ) s.t. ⊃ , and • ∈ stb(SF ), if attacks for all ∈ ∖ .
SF 4: adm(SF 4) = {∅, {, }, {}, {, }} com(SF 4) = {∅, {, }, {, }} grd(SF 4) = {∅} pref(SF 4) = {{, }, {, }} stb(SF 4) = {{, }, {, }}
We proceed by defining HYPAFs as the faithful generalization of SETAFs where we allow sets of arguments in the second position of the attack relation.
Definition 5 (HYPAFs). A HYPAF is a pair HF = (, ) where is a finite set of arguments, and ⊆ 2× (2∖∅) is the attack relation.
For an illustration see Example 6. HYPAFs (, ), where for all ( , ) ∈ it holds that || = 1, amount to SETAFs. Note that we allow for the empty set in the ifrst position of an attack (i.e., (∅, )), as to be in line with our notion of SETAFs. The empty set in the second position of an attack however (i.e., ( , ∅)) we exclude. This is due to the fact that an attack towards an empty set of arguments is nonsensical and has no corresponding counter-part in any argumentation scenario.
let us consider a situation in which three agents, Alice, Bob, and Carol, plan a tandem-trip. At most two of them can join the tandem, but not all of them at once. It could either be that Alice rides tandem (a), Bob rides tandem (b), or
is a two-person tandem (t). Utilizing collective defeat, we can depict the conflict between these statements as follows: Definition 3. Let SF = (, ) be a SETAF and ⊆ a set of arguments. Then is conflict-free if for all ( , ℎ) ∈ it holds ⊆ ⇒ ℎ ∈/ . An argument ∈ is defended (in SF ) by a set ⊆ if for each ⊆ , such that attacks , also some ′ ⊆ attacks some ∈ . A set ⊆ is defended (in SF ) by if each ∈ is defended by (in SF ). Let be conflict-free in
SETAFs SF = (, ), where for all ( , ℎ) ∈ it holds that | | = 1, amount to (standard Dung) AFs. We usually write (, ℎ) to denote the set-attack ({}, ℎ).
An attack ({1, . . . , }, ) is interpreted as follows: {} attack {, }, which we will illustrate as follows. Example 6. Let the set {, } attack the set {, } and if we accept all of 1, . . . , then is defeated. In order to defend against this attack, it thus sufices to defeat one of 1, . . . , . Based on this intuition, the classical Dungsemantics generalize as follows (for a recent overview, see e.g. [3, 12]). 1While the original definition of SETAFs from Nielsen and Parsons [2] does not allow attacks of the form (∅, ), these attacks are often included for convenience.
HF 6:
Intuition. In this section we interpret an attack to Example 8. In the construction from [2], the HYPAF HF8 in the way that defeats each element in individually. corresponds to the SETAF SF8.
In accordance with [5] we will call this notion universal defeat. Given a HYPAF HF = (, ) and an attack ( , ) ∈ , this interpretation of a hyper-attack would ℎ1 ℎ1 be captured if the following implication holds: 1 1 for each 1 ≤ ≤ . Let us illustrate this approach.
If all arguments in are accepted, then each ℎ ∈ is defeated.
However, as already observed by Nielsen and Parsons [2]2, this is mere syntactic sugar compared to usual SETAFs: Since a collective attack ( , ℎ) from to a single argument ℎ encodes that ℎ is defeated whenever all arguments in are accepted, the above requirement can be captured by introducing the set
{( , ℎ) | ( , ) ∈ , ℎ ∈ } of collective attacks. In the following definition we formalize this reduction of [2] in our terminology.
Definition 7. Let HF = (, ) be a HYPAF and ⊆ a set of arguments. Then we say that is a -extension of HF if is a -extension of the SETAF SF = (, {( , ℎ) | ( , ) ∈ , ℎ ∈ }).
attacks in the mode of universal defeat, the hyperframework HF 6 is equivalent to the SETAF SF 4 from Example 4.
Intuition. This section aims at formalizing the intuition that for an attack ( , ) ∈ it is not clear (i.e. “non-deterministic”) which of the arguments in are actually attacked by . That is, sets attacking sets are interpreted as a form of incomplete information. Formally, if we accept , then for each ′ ⊆ there shall be a possible world where ′ is the precise set of arguments which is defeated due to this attack.
Indeterministic attack has been discussed by Nielsen and Parsons [2]. Here the underlying idea is as follows. If ( , ) is an attack, then the set ∪ is certainly not conflict-free. Since it is not clear how to draw more information when interpreting ( , ) as an indeterministic attack towards , [2] refrain from encoding more than the definite conflicts we can be sure of. Thus they propose the following3: an attack ({1, . . . , }, {ℎ1, . . . , ℎ}) is mapped to the collective attacks
({1, . . . , , ℎ1, . . . , ℎ− 1, ℎ+1, . . . , ℎ}, ℎ) 2Note that in [2] this mode is called “collective defeat”. 3While [2] only explicitly mentions the attack ({1, . . . , , ℎ2, . . . , ℎ}, ℎ1), we assume the whole construction includes the symmetric cases towards each ℎ. 22–31 ℎ2 ℎ3 HF8: 2 ℎ2 ℎ3
SF8: 2 While we indeed note that (I) {1, 2}∪{ℎ1, ℎ2, ℎ3} is now conflicting, we want to point out some issues regarding this reduction, violating the intuition of indeterministic attacks.
(II) In order to accept any argument ℎ, either an argument or ℎ with ̸= has to be defeated. Thus whether or not ℎ is defended depends on the other ℎ, but their connection is an in-coming set-attack, not an internal conflict.
(III) Any admissible set that contains 1 and 2 and at least one ℎ argument has to contain exactly 2 arguments ℎ, ℎ . However, why should adding ℎ2 to {1, 2, ℎ1} render the set admissible, although the only attack involving ℎ2 is an in-coming one?
(IV) The arguments are necessarily involved in attacks towards each ℎ, although by our interpretation of indeterminism there should be a possible scenario where the arguments are not part of any attack towards a single argument ℎ.
From this illustrating example, we can extract the following desired properties for indeterministic HYPAFs corresponding to the observations (I)-(IV) from Example 8.
Property I Whenever we have an attack ( , ) and a jointly acceptable set of arguments , we have ⊆ ⇒ ⊈ .
Property II Given an attack ( , ) and two arguments ℎ1, ℎ2 ∈ , ℎ1 ̸= ℎ2, whether ℎ1 is defended against the attack ( , ) does not depend on whether ℎ2 is accepted or not.
Property III For an attack ( , ) for each ′ s.t. ∅ ⊆ ′ ⊊ we model a situation where ( , ) does not cause a conflict in ∪ ′.
Property IV An attack ( , ) should not be interpreted as an attack where for two ℎ1, ℎ2 ∈ the argument ℎ1 is part of an attack towards ℎ2.
In the following section, we will introduce a diferent notion of indeterministic defeat that indeed satisfies all desired properties (I)-(IV).
this as: either {, } defeats only , {, } defeats only , or {, } defeats both and . We do not know which is actually true, but we want to consider each possible scenario.
Likewise, {} could defeat , , or both and . Each combination of these scenarios corresponds to a SETAF as illustrated below.
The underlying idea for our approach is to interpret the ({,},{,}) = {({, }, ), ({, }, )} set-attacks of the form ( , ) ∈ as a blueprint to construct several SETAFs which represent possible worlds. ({},{,}) = {(, )} Given a SETAF, we can rely on the rich body of research Next, we turn to the semantics of HYPAFs when interon this matter in order to assess acceptance of arguments. preting attacks indeterministically. We define argument The following example shall illustrate our proposal. acceptance in hyper-argumentation frameworks with the following intuition: a set of arguments is possibly accepted (w.r.t. semantics ) if it is accepted in at least one of the “instantiated” SETAFs. This leads us to the following definition of extensions in indeterministic HYPAFs.
Definition 11. Let HF = (, ) be a HYPAF. A set ⊆ is a (possible) -extension of HF if is an extension for some interpretation of HF .
SF 9 SF 9 SF 9
SF 9 SF 9 SF 9ℎ
SF 9 SF 9 SF 9
We omit “possible” and simply speak of extensions if there is no risk of confusion.
Example 9 (ctd). In Example 9 we have that {, } is a stable extension; this is witnessed by the SETAF SF 9ℎ.
We will now illustrate the adequacy of this definition by showing that our indeterministic HYPAFs indeed satisfy the desired properties (I)-(IV). Again, let HF = (, ) be a HYPAF with ( , ) ∈ .
1. This is satisfied by the definition of conflict
freeness. 2. As desired, the attack ( , ) never maps to any scenario where two arguments ℎ, ℎ ∈ appear in the same collective attack (nor is ℎ relevant for the defense of ℎ ). 3. In the interpretation where defeats ′ ⊆ ,
the attack causes no conflict in ∪ ( ∖ ′). 4. In the interpretation where defeats ′ ⊆ , there is no (partial) conflict between and ∖ ′.
In order to define semantics for indeterministic defeat we first introduce interpretations of HYPAFs in order the capture the possible worlds. Note that our HYPAFs with indeterministic defeat semantically coincide with conjunctive-disjunctive argumentation networks [7]. Our approach extends this notion by defining all standard (Dung-style) extension-based semantics, and that our approach is syntactically close to the established SETAFs.
It is clear however that our properties (I)-(IV) can only serve to cover a small subset of conceivable desiderata.
Hence, to better put our proposal in context and demonstrate how it can be naturally captured by concepts from Definition 10. Let HF = (, ) be a HYPAF. For each the literature, in the following section we characterize attack ( , ) ∈ we choose a set of interpreted collec- indeterministic HYPAFs by showing a semantic relation to attack-incomplete frameworks with correlations. tive attacks (,) s.t.
∅ ⊂ (,) ⊆ { ( , ℎ) | ℎ ∈ }.
An interpretation of HF is any SETAF SF = (, ) s.t.
=
⋃︁ (,)∈
(,).
above correspond to the interpretations of HF 6 from Example 6. Each of these SETAFs realizes a possible world underlying the HYPAF HF 6 in question.
As due to their similar construction, our indeterministic interpretation of HYPAFs is close to attack-incomplete frameworks (iAFs) [8]. In iAFs a subset of the attack relation is uncertain, i.e., the reasoning agent is not sure whether this attack exists or not. For their semantics each possible scenario of taking or omitting an uncertain attack is considered. In our setting, an attack ( , {ℎ1, . . . , ℎ}) can be seen as the set of uncertain OR-constraint, and all attacks that appear in an ORattacks {( , ℎ1), . . . , ( , ℎ)}. However, indetermin- constraint together have the same tail, i.e., the following istic HYPAFs face an additional constraint, namely we properties hold: require at least one of these attacks to be present in each scenario. [13] generalized iAFs by the addition of corre- ⋃︁ = ? (1) lations. OR-Correlations pose the additional constraint ∈Δ that of a set ′ ⊆ , at least one attack of ′ is present, {(1, ℎ1), . . . , (, ℎ)} ∈ ∆ ⇒ 1 = · · · = (2) albeit unknown which one. The semantics are defined in terms of completions, which correspond to our interpretations. We can straightforwardly generalize iAFs with OR-correlations to feature set attacks.
Clearly, the construction in Theorem 13 maps precisely to those iSETAFs that satisfy both (1) and (2). Conversely, we show next that every iSETAF adhering to (1) and (2) can be seen as an equivalent HYPAF, i.e., the mapping is bijective.
Definition 12. A iSETAF with correlations is a tuple SF = (, , ?, ∆) , where is a finite set of arguments, , ? ⊆ 2 × are sets of certain/uncertain attacks, and ∆ ⊆ 2? ∖ ∅ is a set of OR-correlations.
A valid completion of SF is a SETAF SF = (, ′), where ⊆ ′ ⊆ ? such that for each ∈ ∆ it holds ′ ∩ ̸= ∅. A set ⊆ is a possible -extension of SF if for at least one completion of SF the set is a -extension.
The following equivalence follows directly from the respective definitions (cf. Definition 10, 12).
Theorem 13. Let HF = (, ) be a HYPAF. ⊆ is a -extension of HF if is a possible -extension of the iSETAF SF = (, ∅, ?, ∆) with ? = {( , ℎ) | ( , ) ∈ , ℎ ∈ }, ∆ = {{( , ℎ) | ℎ ∈ } | ( , ) ∈ }.
({1, . . . , }, {1, . . . , }) corresponds to the attacks
({1, . . . , }, 1), . . . , ({1, . . . , }, ), together with a corresponding OR-correlation that includes all of these attacks.
Theorem 14. Let SF = (, ∅, ?, ∆) be a iSETAF adhering to (1), (2). A set ⊆ is a possible -extension of SF if is a -extension of the HYPAF HF given as the tuple (, {( , {ℎ1, . . . , ℎ}) | {( , ℎ1), . . . , ( , ℎ)} ∈ ∆ }).
Proof. As in Theorem 13, there is a 1-to-1 correspondence between the interpretations of HF and the valid completions of SF that satisfies properties (1), (2). An OR-correlation
{({1, . . . , }, 1), . . . , ({1, . . . , }, )} corresponds to the indeterministic attack
({1, . . . , }, {1, . . . , }).
HF6
with Δ : ({, }, ) (, )
OR OR ({, }, ) (, ) SFHF6 Proof. The statement follows from Definition 10 and Def- Example 6 (ctd). Let us revisit HF 6 (left). The correinition 12: there is a 1-to-1 correspondence between the sponding iSETAF with OR-correlations is depicted below interpretations of HF and the valid completions of SF . (right). Note that its valid completions coincide with the An indeterministic attack interpretations of our HYPAF (see Example 9).
Even though the iSETAFs we construct in Theorem 13 have no certain attacks, they are still efectively present as an attack ( , ℎ) ∈ ? where {( , ℎ)} ∈ ∆ is semantically equivalent to ( , ℎ) ∈ . This is not surprising, as 5. Collective Defeat these attacks correspond to ( , ) with || = 1 in the original HYPAF. Intuition. In this section, we interpret a set-attack
For the reverse direction, i.e., mapping iSETAFs as ( , ) as a collective attack in the sense that whenever HYPAFs, we have to pose a restriction on the iSETAFs, is acceptable, then the set of arguments (and thus, namely that all uncertain attacks appear in at least one each superset of ) is not. As demonstrated in our introductory Tandem Example 15, we want to formalize the situation in which the set of arguments is attacked as
Theorems 13 and 14 provide an exact characterization of the relation between indeterministic HYPAFs and iSETAFs with OR-correlations. a whole but the attack does not afect any proper subset of . We will see that with this new notion, the preferred extensions of the HYPAF in Example 1 are {, , }, {, , }, {, , } and thereby correspond to the intuitive outcome. We emphasize that we do not aim to reduce this attack to any conceivable notion of an attack towards (some of) the individual arguments in .
HF 15: i) Our first observation here is that the attack ({, }, {, , }) should be redundant as it states that , , cannot be collectively accepted since {, } are (they are unattacked). However, the attack ({, }, {, }) states already that , cannot be collectively accepted, which is a strictly stronger condition. ii) Secondly, both {, , } and {, , } should be acceptable because the attack ({, }, {, }) only forbids collective acceptance of and . iii) Moreover, should be acceptable w.r.t. {, } because in order to defeat , {, } are required which in turn should be interpreted defeated. iv) Finally, defending is harder than defending since defeating {, } collectively is easier than defeating specifically.
Let us now define the standard concept required to generalize the usual AF semantics to capture the interaction of sets of arguments.
Definition 16. Let HF = (, ) be a HYPAF and let , ⊆ . We say that • attacks if there are ′ ⊆ and ′ ⊆ such that (′, ′) ∈ ; we call an attacker of ; • is conflict-free, ∈ cf(HF ), if it does not attack itself; • defends if attacks all attacker of , i.e. for all (, ′) ∈ with ′ ⊆ , there are ′ ⊆ and ′ ⊆ such that (′, ′) ∈ .
We observe that if a set is defended by some set , then all individual arguments of are defended as well. Lemma 17. Let (, ) be a HYPAF and let , ⊆ . If defends then defends {} for each ∈ . Proof. The statement follows from the observation that each subset of a defended set is defended. Let ⊆ defend , let ′ ⊆ , and consider some attacker of ′. By definition of attacks, attacks as well. By assumption, attacks and therefore also defends ′ against . Since was an arbitrary attacker, the claim follows.
Using these underlying notions, the definitions of the semantics naturally generalize to hyperframeworks. Definition 18. Let HF = (, ) be a HYPAF and let ∈ cf(HF ). Then • is admissible, ∈ adm(), if defends itself; • is complete, ∈ com(), if ∈ adm(HF ) and contains every set ⊆ it defends; • is grounded, ∈ grd(HF ), if is ⊆ -minimal in com(); • is preferred, ∈ pref(HF ), if is ⊆ -maximal in adm(); • is stable, ∈ stb(HF ), if attacks each ⊆ ∖ .
= {, , } is admissible ({, } defends ). It is not maximal though since ′ = {, , , , } ∈ adm(HF ) as well. The latter is preferred. Note that is not in any admissible set since defending would require defeating ; no set of arguments is capable though.
Interestingly, we can simplify our definitions for complete and stable semantics.
Lemma 19. Let HF = (, ) be a HYPAF. Then • ∈ stb() if ∈ cf(HF ) and attacks each set {} for all ∈ ∖ ; • ∈ com() if ∈ adm(HF ) and contains each argument it defends.
1 = {, , } and 2 = {, , } are conflict-free since {, } only attacks {, }, but none of them individually.
Moreover, {, } defends , but it does not defend . We also want to mention that the conflict-free and defended sets in HF 15 do not alter after removing ({, }, {, , }), i.e. the attack is indeed redundant.
Proof. A stable set attacks each singleton not contained
We abuse notation and write defends whenever in by definition. In case each singleton is attacked, then we mean that defends {}. each superset is attacked as well.
First assume is complete. Then it is admissible and contains each set it defends. Hence it contains each singleton it defends. Now assume is admissible and contains each defended argument. Let be defended by . By Lemma 17, each argument ∈ is defended by as well. Hence ⊆ , as desired.
Having defined our HYPAF semantics formally, we What are the complete extensions of the HYPAF? Coming are now interested in their properties. Thereby, we pay from the well-behaving SETAFs, we would expect that the special attention to the behavior of Dung’s semantics in two preferred sets {, , } and {, , } are complete as AFs, because they are well-behaved w.r.t. several aspects. well. However, it turns out that our HYPAF HF 22 has no We mention here the most common ones. complete extension at all. Let us consider the set {, , }:
While stable extensions do not necessarily exist, we By definition, the set is admissible, moreover, the arguexpect each HYPAF to possess admissible, complete, ment is unattacked, hence {} is defended by {, , }. grounded, and preferred extensions. Moreover, the However, we cannot extend {, , } with {} since the grounded extension should be unique since it intuitively resulting set {, , , } is not conflict-free anymore. formalizes the set of arguments one is willing to ac- This shows not only that com(HF 22) = ∅, but also the cept, even if the reasoning is cautious. The most im- fact that the fundamental lemma is violated. portant technical tool in order to ensure these properties From com(HF 22) = ∅ we also deduce grd(HF 22) = ∅. is Dung’s fundamental lemma [1].
Lemma 20 (Fundamental Lemma). Let = (, ) be an AF, ∈ adm( ) and , ′ ⊆ be sets of arguments that are defended by . Then 1. ′ = ∪ is admissible, and 2. ′ is defended by ′.
Moreover, we typically expect preferred extensions (i.e. maximal admissible sets) to be complete. In summary, we get the following properties which are typically desirable for any generalization of Dung’s setting.
We therefore conclude that the natural generalization of the semantics admits unexpected behavior. In summary, the previous example illustrates the following observation regarding our HYPAF semantics.
exist;
Let us first discuss the positive news: 1. (Some version of) the fundamental lemma holds. 5.2. HYPAF Properties 2. There is always at least one admissible, complete, In this section, we discuss complete and grounded semangrounded, and preferred extension. tics in more depth. For this, we define the characteristic 3. Every preferred extension is complete, and every function for HYPAFs as it is defined for (SET)AFs: Γ HF stable extension is preferred. applied to some set of arguments returns all arguments which are defended by . Due to Lemma 17 this also captures our intuition of defending sets of arguments.
Definition 24. Let HF = (, ) be a HYPAF and let 1. admissible and preferred extensions always exist; ⊆ . We define the characteristic function as and
Γ HF () = { ∈ | defends {}}.
Both follows directly from the definitions: indeed, the Example 22 (ctd). We revisit HF 22. Then Γ HF 22 (∅) = empty set as well as each stable extension defends itself, Γ HF 22 ({, }) = {, , , } as each singleton is moreover, each stable extension is ⊆ -maximal admissible. unattacked.
However, the following simple example already illustrates that the semantics we defined so far violate all of We mention that our characteristic function is monothe remaining properties. tonic.
in which the set {, } attacks the set {, }.
Lemma 25. Let HF = (, ) be a HYPAF and let ⊆ ⊆ . Then Γ HF () ⊆ Γ HF ( ).
HF 22: 5.2.1. Complete Semantics As for AFs and SETAFs, complete semantics can be alternatively defined via the characteristic function. By definition, the complete extensions are the conflict-free ifxed points of Γ HF .
In HF 22, both sets {, , } and {, , } are conflict-free.
selves (in fact, no subset of them is attacked). Moreover, Lemma 26. Let HF = (, ) be a HYPAF. Then ∈ they are preferred as {, , , } ∈/ cf(HF 22). com(HF ) if ∈ cf(HF ) and = Γ HF ().
However, in contrast to Dung AFs and SETAFs, the We do however obtain the following positive result. characteristic function might have no conflict-free fixed While on the one hand we cannot guarantee that Γ H∞F (∅) points, as Example 22 demonstrates: {, , , } is the is conflict-free, we can on the other hand be certain that only fixed point of Γ HF 22 . We can attribute the non- it is the only candidate for the grounded extension. existence of complete extensions to set-attacks in the following sense: If the head of each attack contains at Proposition 29. Let HF = (, ) be a HYPAF and let least two arguments, then complete extensions do not ⊆ . It holds that exist.
Lemma 27. Let HF = (, ) be a HYPAF, ̸= ∅. If || > 1 for all ( , ) ∈ then com(HF ) = ∅.
Proof. Let ∈ . We show that the singleton {} is not attacked by any set of arguments. Suppose attacks . Then there is a subset ′ ⊆ { } s.t. (′, ′) ∈ for some ′ ⊆ . This contradicts our assumption || > 1 for each ( , ) ∈ .
Hence, Γ HF behaves as expected in case it admits a conflict-free fixed point. As an immediate corollary, we obtain that the grounded extension is unique whenever
This result formalizes that our notion of attacks be- it exists. tween sets is not suitably tailored to assess the status of a single argument, but focuses on sets of arguments Corollary 30. For any HYPAF HF , |grd(HF )| ≤ 1. instead.
Even in the special (somewhat well-behaving) case Since there are never two grounded extensions, we where we do have fixed points for the characteristic func- sometimes abuse notation and write grd(HF ) to denote tion (i.e., there are complete extensions), we are not guar- the unique grounded extension of HF . Another corollary anteed to have the usual relations between the semantics of Proposition 29 is that grd(HF ) is a subset of each comthat we know from Dung’s notions. plete extension; i.e. grd(HF ) is the least set in com(HF ). 1. grd(HF ) = {Γ H∞F (∅)} if Γ H∞F (∅) ∈ cf(HF ); 2. grd(HF ) = ∅ if Γ H∞F (∅) ∈/ cf(HF ).
Proof. By monotonicity of the characteristic function, it holds that Γ H∞F (∅) is conflicting if Γ HF has no conflictfree fixed points. By definition of grounded semantics, we obtain the desired results.
Example 28. Note that even in case com(HF ) ̸= ∅ holds, it is still not ensured that pref(HF ) ⊆ com(HF ) holds, as HF 28 illustrates: the set {, } is preferred, but not complete (because {, } defends , but {, , } is not conflictfree). However, the empty set of arguments is complete in HF 28.
HF 28:
5.2.2. Grounded Semantics Now let us turn our attention towards the grounded extension. In AFs and SETAFs, the grounded extension is the least fixed point of the characteristic function. As is folklore in the argumentation community, the grounded extension can be computed by applying the characteristic function to the empty set until a fixed point is attained, i.e. we have grd( ) = {Γ ∞( )
∅ } whenever is a Dung-AF. An analogous result holds true in SETAFs.
Since a HYPAF might have no conflict-free fixed points (cf. Example 22), this does not hold for our HYPAFs, i.e, grd(HF ) = {Γ H∞F (∅)} is not true anymore (in Example 22, Γ HF22 (∅) contains all arguments and is not conflict-free).
Corollary 31. If com(HF ) ̸= ∅, then grd(HF ) is the least complete set.
We want to point out that with our new notion of collective attack it is possible to model undirected conflicts natively within our framework.
from the introduction, but this time, we use only the arguments , , and to model the conflict. Again, we have a conflict if we accept all of them but no conflict if we only accept a subset. In SETAFs we would model this scenario with symmetric attacks towards each argument (see SF 32).
in this case for example a singleton set cannot be accepted. Our collective defeat allows for the attack (∅, {, , }) (see
gives the desired behavior.
SF 32:
HF 32:
The following result illustrates that if we omit the direction of attacks of a HYPAF, we retain the admissible sets. Proposition 33. Let HF = (, ) be a HYPAF and ⊆ a set of arguments. If ∈ adm(HF ), then ∈ adm(HF ′) where HF ′ = (, {(∅, ∪ ) | ( , ) ∈ }).
Proof. First note that every conflict-free set in HF ′ is admissible. Moreover, every conflict-free set in HF is also conflict-free in HF ′, as an attack (∅, ∪ ) in could only cause a conflict in a set if ∪ ⊆ , which also causes a conflict in HF .
Note however that a version of Proposition 33 where instead of admissible sets we consider semantics that maximize the extensions (like grd, com, pref, and stb) does not necessarily hold, as Example 34 illustrates.
HF3′4. While ∅ is the only extension of HF 34 we have grd(HF3′4) = com(HF ′34) = pref(HF ′34) = {{}}. HF 34:
HF ′34:
attack of argument , the set {} is stable, but in the corresponding undirected pendant there is no stable extension. The idea is to iteratively remove conflicting attacks and attacks that it is impossible to defend against. Finally, for collective defeat we obtain the same computational properties as for SETAFs. The lower bound for preferred semantics carries over directly from the SETAF case, upper bounds can straightforwardly be obtained by the fact that conflict-freeness, defense, and the closure function can be computed in polynomial time.
Theorem 35. Let HF = (, ) be a HYPAF and ⊆ a set of arguments. For the problem of verifying whether is a -extension of HF w.r.t. universal/indeterministic/collective defeat, the complexity results in Table 1 hold.
grd adm com in P in P in P
pref stb coNP-c in P NP-c in P NP-c Σ2P-c
in P in P in P in P
coNP-c in P
In this paper, we provided three diferent defeat-modes
6. Computational Complexity for hyperattacks: universal, indeterministic, and
collective. It turns out that universal defeat simply amounts to
In this section, we briefly investigate the computational SETAF semantics. Our indeterministic defeat on the other
complexity of decision problems regarding our diferent hand generalizes attack-incomplete SETAFs, which in
notions of HYPAFs. We assume the reader to be familiar turn conservatively generalize attack-incomplete AFs [
We focus on verifying extensions, however other com- arguments. However, we observe undesirable behavior of putational problems are closely related and in most cases the characteristic function, i.e., the known well-behaved the complexity can be obtained as a corollary. properties of Dung’s framework are not preserved. In fu
First we have that HYPAFs with universal defeat can ture work, we want to address these issues. HYPAFs with
be directly reduced to SETAFs (and vice versa). Thus collective defeat resemble the semantics of ABA+ [