# on_undisputed_sets_in_abstract_argumentation__a5bb0835.pdf

On Undisputed Sets in Abstract Argumentation

Matthias Thimm

Artificial Intelligence Group, University of Hagen, Germany matthias.thimm@fernuni-hagen.de

We introduce the notion of an undisputed set for abstract argumentation frameworks, which is a conflict-free set of arguments, such that its reduct contains no non-empty admissible sets. We show that undisputed sets, and the stronger notion of strongly undisputed sets, provide a meaningful approach to weaken admissibility and deal with the problem of attacks from self-attacking arguments, in a similar manner as the recently introduced notion of weak admissibility. We investigate the properties of our new semantical notions and show certain relationships to classical semantics, in particular that undisputed sets are a generalisation of preferred extensions and strongly undisputed sets are a generalisation of stable extensions. We also investigate the computational complexity of standard reasoning tasks with these new notions and show that they lie on the second and third level of the polynomial hierarchy, respectively.

1 Introduction Computational models of argumentation (Baroni et al. 2018; Gabbay et al. 2021) are formal approaches to knowledge representation and reasoning that focus on the representation of arguments and their interaction with each other. In particular, abstract argumentation frameworks (AFs) model argumentative scenarios as a directed graph where arguments are identified as vertices and a directed edge from one argument to another is interpreted as an attack (Dung 1995). Formal semantics for abstract argumentation (Baroni, Caminada, and Giacomin 2018) capture conditions that should be imposed on a set of arguments in order to deem this set a plausible outcome of the argumentation (also called an extension). Many different semantics have been proposed over the years, many based on this notion of an extension, but also based on different concepts such as rankings (Amgoud and Ben-Naim 2013; Skiba et al. 2021), weights (Dunne et al. 2011; Bistarelli and Santini 2021), or probabilities (Li, Oren, and Norman 2011; Hunter et al. 2021). This work continues the investigation on primal reasons why arguments should be deemed acceptable and what should form an extension. We are particularly interested in the family of non-admissible semantics (Kakas and Mancarella 2013; Baumann, Brewka, and Ulbricht 2020b; Dauphin,

Copyright 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Rienstra, and van der Torre 2020; Dondio and Longo 2019). The notion of admissibility (Dung 1995) refers to the property of a set of arguments to defend itself against all attacks: for every argument that is attacking an argument of the set, there must be an argument in the set that attacks back (we will provide formal definitions in Section 2). Semantics based on notions such as weak admissibility (Baumann, Brewka, and Ulbricht 2020b; Dauphin, Rienstra, and van der Torre 2020) see also (Kakas and Mancarella 2013) for an earlier treatment of the same idea or undecidedness blocking (Dondio and Longo 2019) take a more relaxed stand on this constraint, insofar only attacks from relevant arguments must be defended. How this aspect of relevance is defined, differs in the aforementioned works. However, a particular example (where all these approaches also agree on) is that an attack from a self-attacking argument is deemed irrelevant. While we will provide a deeper discussion of the pros and cons of these approaches in Section 3, let us just note that the formal definition of those semantics can be quite involved and opaque, in contradiction to the general aim of having explainable models in AI. In addition to that, the semantical notion of weak admissibility (Baumann, Brewka, and Ulbricht 2020b) also comes with the additional caveat of being computationally very hard, (Dvoˇr ak, Ulbricht, and Woltran 2021) shows that all interesting reasoning problems for weak admissibility are PSPACE-complete.

Our aim is to define a new notion of a non-admissible semantics that captures the intuition of the works above but is conceptually simple and enjoys better computational complexity (in particular better than PSPACE-completeness). Our core concept to this aim is that of an undisputed set, which is a conflict-free set of arguments, such that its reduct i. e., the part of the argumentation framework that remains when we remove the set and all arguments attacked by it contains no non-empty admissible sets anymore. We show that this notion is actually a generalisation of preferred extensions (Dung 1995), which are subset-maximal admissible sets, and we show that it enjoys further desirable properties. We then investigate a special case of undisputed sets, namely strongly undisputed sets that additionally demand that their reduct does not contain a non-empty undisputed set as well. We show that the strongly undisputed semantics behaves identical on all examples from (Baumann, Brewka, and Ulbricht 2020b) and therefore poses a conceptually sim-

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

pler alternative. In addition, we show that the computational complexity of standard reasoning tasks with undisputed sets and strongly undisputed sets lie (only) on the second and third level of the polynomial hierarchy, respectively. In summary, the contributions of this paper are as follows. 1. We revisit the foundations of non-admissible semantics and discuss their properties (Section 3), 2. We present and analyse the notion of undisputed sets, particularly showing that they naturally derive from established notions such as preferred semantics (Section 4). 3. We present and analyse the notion of strongly undisputed sets and show they satisfy similar properties as weak admissibility-based semantics (Section 5). 4. We analyse the computational complexity of reasoning with (strongly) undisputed sets (Section 6). Section 2 gives the necessary background on abstract argumentation and Section 7 concludes the paper.

2 Preliminaries An abstract argumentation framework (AF) F is a tuple F = (A,R) where A is a finite set of arguments and R is a relation R A A (Dung 1995). For two arguments a,b A the relation a Rb means that argument a attacks argument b. For a set S A we define

S+ F = {a A | b S : b Ra} S F = {a A | b S : a Rb}

If S is a singleton set, we omit brackets for readability, i. e., we write a F (a+ F ) instead of {a} F ({a}+ F ). For two sets S and S we write SRS iff S S+ F = /0. For a set S A, we denote by F|S = (S,R (S S)) the projection of F on S and by FS = F|A\(S S+ F ) the reduct (Baumann, Brewka, and Ulbricht 2020b) of F wrt. S. We say that a set S A is conflict-free if for all a,b S it is not the case that a Rb. A set S defends an argument b A if for all a with a Rb there is c S with c Ra. A conflict-free set S is called admissible if S defends all a S. Let cf(F) and adm(F) denote the set of conflict-free and admissible sets of F, respectively. Different semantics can be defined by imposing constraints on admissible sets (Baroni, Caminada, and Giacomin 2018). An admissible set E is a complete (co) extension iff for all a A, if E defends a then a E, grounded (gr) extension iff E is complete and minimal, stable (st) extension iff E E+ F = A, preferred (pr) extension iff E is maximal. All statements on minimality/maximality are meant to be with respect to set inclusion. For σ {co,gr,st,pr} let σ(F) denote the set of σ-extensions of F.

3 Related Works and Motivation Consider the AFs F0 and F1 depicted in Figure 1. Both model the core issue of admissible-based semantics and they have been used as the motivating examples for semantics aiming at weakening admissibility (Kakas and Mancarella 2013;

Figure 1: The AFs F0 (left) and F1 (right).

Baumann, Brewka, and Ulbricht 2020b; Dauphin, Rienstra, and van der Torre 2020; Dondio and Longo 2019). For all semantics σ {adm,co,gr,st}1, we have that both F0 and F1 possess no non-empty extension and stable semantics is even undefined. However, consider the set {b} (for both frameworks). In F0, {b} is only attacked by a and one may argue why {b} should actually defend itself against a. The argument a is self-attacking and therefore provides sufficient reasons for its own unacceptability. Since a is nonsensical and can never be in an acceptable position, we can admit the set {b} to not need to defend against a. In F1, the situation is similar: the set {b} is only attacked by a1 and a1 is part of a non-sensical sub-framework itself. The arguments a1,a2,a3 form an odd cycle that cannot be resolved (if a1 would be acceptable, then a3 would be defeated, and a2 therefore acceptable, defeating a1 in turn, and so on). So a1,a2,a3 are non-sensical as a whole and there is reason to neglect attacks from any of them. Dung points to this issue in his seminal paper on abstract argumentation (Dung 1995, p. 351):

An interesting topic of research is the problem of selfdefeating arguments as illustrated in the following example. Consider the argumentation framework < {A,B},{(A,A),(A,B)} >. The only preferred extension here is empty though one can argue that since A defeats itself, B should be acceptable.

The above quote is also used as a motivation of (Baumann, Brewka, and Ulbricht 2020b), but instead of directly working on the notion of preferred semantics (as hinted by the quote), Baumann et al. provide an alternative definition of admissibility.

Definition 1. Let F = (A,R) be an AF. A set S A is weakly admissible (S wadm(F)) iff

1. S cf(F) and 2. for every a S F , a / Swadm(FS).

In other words, a set S of arguments is weakly admissible if for every attacker a of this set, S either attacks a (then a is not in FS anymore) or S does not need to defend against a, which is the case if a itself is not a member of a weakly admissible set of the reduct FS. Note that {b} is a weakly admissible set for both frameworks F0 and F1 from above. The definition of weak admissibility is recursive and in order to show that an argument a is or is not a member of a weakly admissible set one has to consider further reducts of the initial reduct, and so on. This recursive definition is

1In the remainder of the paper, we treat adm and also cf as semantics as well for simplicity of presentation.

also the main culprit for the complexity of weak admissibility. In particular, deciding whether an argument is contained in a weakly admissible set is PSPACE-complete (Dvoˇr ak, Ulbricht, and Woltran 2021). Other approaches (Kakas and Mancarella 2013; Dauphin, Rienstra, and van der Torre 2020; Dondio and Longo 2019) to weaken admissibility in order to solve the issues of frameworks F0 and F1 use different formalisations and sometimes even more involved constructions. For example, the families of (semi-)qualified semantics from (Dauphin, Rienstra, and van der Torre 2020) are based on the decomposition of an AF into strongly connected components (SCCs) and use the SCC-decomposition schema from (Baroni et al. 2014) to define their semantics. In the remainder of this paper we present another alternative for addressing the issues in frameworks F0 and F1 (and similar ones) by relying on a conceptually simpler approach.

4 Undisputed Sets Let us recall that in the quote of Dung before, he explicitly mentioned that the issue with F0 is wrt. to preferred semantics (and not necessarily with the notion of admissibility). Therefore, in this section, we will present a generalised version of preferred semantics directly. We will do this by first presenting a new characterisation of preferred semantics that relies on the notion of vacuity.

Definition 2. Let σ be a semantics. An AF F is σ-vacuous iff σ(F) {/0}.

The notion of σ-vacuity models a relaxed concept of inconsistency for AF semantics and can be used to identify non-sensical situations such as the ones in F0 and F1 from above. We use this notion here to define what we call a vacuous reduct semantics.

Definition 3. Let σ, τ be two semantics and F = (A,R) an AF. A set S A is a στ-extension iff S is a σ-extension and FS is τ-vacuous.

In other words, a set S is a στ-extension iff it is a σextension and the remaining framework is non-sensical wrt. τ. Let στ(F) denote the set of all στ-extensions of F. The definition of vacuous reduct semantics provides a template for defining completely new semantics, but we leave a further investigation of this concept for future work. Here, we are only interested in some special cases of this template. In particular, we can observe that preferred semantics is actually a very specific instance (note that the following result has essentially already been shown in (Baumann, Brewka, and Ulbricht 2020a), Proposition 3.2 items 2 and 3, but since we use different notation and concepts, we give a complete proof).

Proposition 1. pr = admadm.

: Let S be preferred (and therefore admissible). Assume that FS = (A,R) is not adm-vacuous. Then there is non-empty admissible S A. Define S = S S and observe that S is conflict-free: no argument in S attacks an

Figure 2: The AF F2 from Example 1.

argument in S as all arguments attacked by S are not in A; furthermore, no argument in S attacks an argument in S as S was admissible in F and would have defended the attack. Furthermore, S is admissible: this follows inductively from Dung s fundamental lemma (Dung 1995). It follows that S is not preferred since S is admissible and a proper superset of S, contradicting the assumption. : Let S be admissible and FS is adm-vacuous. Assume that S is not preferred, so there is S with S S and S is preferred. Let S = S \S. With the converse argumentation as above, it can be seen that S is admissible in FS, contradicting the assumption that FS is admvacuous.

One interesting aspect of this above characterisation of preferred semantics is that it does not explicitly mention any form of maximisation (recall that preferred extensions are defined as subset-maximal admissible sets). It states that a preferred extension is an admissible set such that the remaining framework does not possess any non-empty admissible set. We now come to our aim of defining a generalised version of preferred semantics that allows us address the issues discussed in Section 3. We do so by relaxing the requirement of admissibility to conflict-freeness on the base of the characterisation from Proposition 1. We call these sets undisputed. Definition 4. Let F = (A,R) be an AF. A set S A is undisputed iff it is a cfadm-extension. Let ud(F) denote the set of all undisputed sets of F. Example 1. Consider the AF F2 in Figure 2. There are 3 undisputed sets in F2: ud(F2) = {{a},{a,c},{a, f}}. For example, consider {a, f}. Clearly, {a, f} is conflict-free. Furthermore, the reduct F{a, f} 2 is depicted in Figure 3 and it can be clearly seen that F{a, f} 2 is adm-vacuous, showing that {a, f} is an undisputed set. For symmetry reasons, {a,c} is also undisputed. Finally, {a} is also undisputed as F{a} 2 consists of the arguments c,d,e, f,g and their corresponding attacks and there is also no non-empty admissible sets of that framework as well. Example 2. Recall the AFs F0 and F1 from Figure 1. Here we have ud(F0) = {/0,{b}} and ud(F1) = {/0,{b}} In particular, note that the reduct F{b} 0 consists only of the selfattacking argument a and /0 is its only admissible set. Also, F{b} 1 consists of the cycle with the arguments a1,a2,a3, which also has /0 as its only admissible set. Furthermore, /0 is also undisputed in both frameworks since both are admvacuous as well. Note also that no superset of {b} in F1

Figure 3: The reduct F{a, f} 2 (only black arguments and attacks) from Example 1.

can be undisputed since it either becomes conflicting or the reduct will not be adm-vacuous. For example, the reduct of the set {b,a2} consists of the single argument a3 and no attacks. Clearly, {a3} is a non-empty admissible set in F{b,a2}. As can be seen in the above examples, undisputed sets are a quite general concept that captures sets of arguments that do not necessarily defend themselves from all attacks (as motivated in the previous section), but also the classical admissible point of view (as, e. g., the empty set is also undisputed in F0 and F1). The reason for this is also clear, since undisputed sets are a generalisation of preferred extensions, so every preferred extension is also an undisputed set. We can actually exactly characterise preferred extensions as a specific subclass of undisputed sets as follows. Define

udmin(F) = {S ud(F)| S ud(F) : S S}

udmax(F) = {S ud(F)| S ud(F) : S S}

In other words, udmin(F) is the set of subset-minimal undisputed sets of F and udmax(F) is the set of subset-maximal undisputed sets of F. Our next result shows preferred extensions are exactly those undisputed sets that are also admissible, which in turn are exactly those minimal undisputed sets that are also admissible. Theorem 1. For all F, pr(F) = ud(F) adm(F) = udmin(F) adm(F).

Proof. We show the claim by showing pr(F) udmin(F) adm(F), udmin(F) adm(F) ud(F) adm(F), and ud(F) adm(F) pr(F).

pr(F) udmin(F) adm(F): Let S pr(F). Since S is clearly admissible, it remains to show that S udmin(F). By Proposition 1 it follows that S is undisputed, i. e., S ud(F). Assume that S / udmin(F), which means there is S S with S udmin(F). Consider S = S \ S in FS = (A,R). Clearly, S is conflict-free as it is a subset of the conflict-free S. Furthermore, let a S and b A with (b,a) R. Since S is admissible, there is c S that attacks b in F. If c S

then b / A as it would have been removed in FS . It follows c S and therefore a is defended by S . It follows that S is admissible, contradicting S udmin(F). It follows S udmin(F). udmin(F) adm(F) ud(F) adm(F): As udmin(F) ud(F) by definition, udmin(F) adm(F) ud(F) adm(F) follows directly. ud(F) adm(F) pr(F): This follows directly from Proposition 1.

Figure 4: The AF F3 from Example 3.

The above theorem shows that our new notion is generally compatible with classical semantics, insofar that preferred extensions are a special case of undisputed sets. A simple corollary of the above observation is that the notion of an undisputed set is always defined.

Corollary 1. For all F, ud(F) = /0.

Proof. Follows directly from F having at least one preferred extension and pr(F) ud(F), cf. Theorem 1.

Before we continue with analysing the behaviour of undisputed sets in more detail, let us first dwell a bit more on their relationship to preferred extensions. The works mentioned in Section 3 and we as well already motivated the need for relaxing the notion of admissibility when it comes to attackers that should be deemed irrelevant. So one can ask what happens to our new semantical notion if such attackers do not exist? In fact, if we consider odd-cycle-free AFs2 then undisputed sets coincide with preferred extensions.

Proposition 2. If F is odd-cycle-free, pr(F) = ud(F).

Proof. Let F = (A,R) be an argumentation framework. Observe that for every set S A, if F is odd-cycle-free then FS is also odd-cycle-free. Furthermore, recall that for oddcycle free F, preferred and stable semantics coincide (Dung 1995). So assume that there is an undisputed set E which is not a preferred/stable extension. As E is undisputed, it follows that FE = (A ,R ) has no non-empty admissible sets. But as E is not stable, it follows A = /0 and since FE is oddcycle-free, it must possess a (non-empty) stable extension (which is also admissible).

Note that odd-cycle-free argumentation frameworks also subsume acyclic and bipartite argumentation frameworks, so undisputed sets and preferred extensions also coincide in these settings. The previous result (or more specifically, its proof strategy) may lead to the hypothesis that undisputed sets coincide with preferred extensions whenever the framework is coherent (Dung 1995), i. e., whenever preferred and stable extensions coincide (odd-cycle-free frameworks are coherent). This is not the case as the following example shows.

Example 3. Consider the AF F3 in Figure 4. Here we have

pr(F3) = st(F3) = {{a}}

so F3 is coherent. However we have ud(F3) = {{a},{b}}.

2An AF F = (A,R) is odd-cycle free if there are no arguments a1,...,ak A with k being odd and ai Rai+1 for all i = 1,...,k 1 and ak Ra1.

There is another subclass of AFs where preferred extensions and undisputed sets coincide, namely the set of symmetric AFs (an AF F = (A,R) is symmetric, if a Rb implies b Ra, for all a,b A).

Proposition 3. If F is symmetric, pr(F) = ud(F).

Proof. pr(F) ud(F) follows from Theorem 1. Let E ud(F). Since E is conflict-free, no a E attacks itself. Since F is symmetric, E is also admissible (in fact, every argument a E defends itself). Due to Theorem 1, E pr(F).

Let us now turn to some more general properties of undisputed sets. The next observation is about the inclusion of defended arguments. Theorem 3.11 of (Baumann, Brewka, and Ulbricht 2020b) extended Dung s fundamental lemma (Dung 1995) by showing that adding defended arguments to a weakly admissible set yields again a weakly admissible set. For undisputed sets, inclusion of defended arguments is already built into the definition.

Proposition 4. Let F = (A,R) be an AF, S A be an undisputed set, and a A some argument. If S defends a then a S.

Proof. Let S be an undisputed set and let a S+. Assume that a / S. Since S does not attack a (otherwise S would not be conflict-free since it defends a) and S attacks all arguments attacking a, it follows that a is an isolated argument in FS. It follows that {a} is admissible in FS, contradicting the fact that S is undisputed. It follows that a S.

The above proposition shows that arguments defended by an undisputed set, are always included in that set. This property is also called reinstatement (van der Torre and Vesic 2018). Our final result of this section shows that undisputed sets can be decomposed along the reduct.

Proposition 5. Let F = (A,R) be an AF, E ud(F), and E E with E ud(F). Then E \E ud(FE ).

Proof. Let E ud(F) and E E with E ud(F). Since E is conflict-free in F, E \ E is also conflict-free in FE . Furthermore, (FE )E\E = FE (E\E ) = FE and adm(FE) {/0} as E is undisputed. It follows that E \E ud(FE ).

Note that the above property is an inverse version of the property of modularization (Baumann, Brewka, and Ulbricht 2020a). So far we have seen that the notion of undisputed sets provides an elegant concept that both extends classical semantical notions and can be used to analyse matters related to irrelevant attacks. However, there are also certain drawbacks of this notion, one of them being its failure to satisfy I-maximality (van der Torre and Vesic 2018), i. e., undisputed sets may be in a subset relation with each other (see, e. g., Example 1 where both {a} and {a, f} are undisputed), and satisfaction of I-maximality is usually desired. Another drawback is shown in the next example, which is also exhibited by the approach of (Dondio and Longo 2019).

Figure 5: The AF F4 from Example 4.

Example 4. Consider the AF F4 in Figure 5. Here we have ud(F4) = {/0,{b},{c}} In particular, {c} is undisputed. Whether {c} is an acceptable extension is debatable, since we already argued strongly for {b} being an acceptable extension due to its only attack being the self-attacking argument a. However, if {b} is an acceptable extension then {c} should probably not be an acceptable extension, as b attacks c (and {c} does not defend itself from this relevant attacker). In the next section we present a stronger notion of undisputed sets that solves both issues mentioned above.

5 Strongly Undisputed Sets The reason for {c} being an undisputed set in Example 4 is that the corresponding reduct is adm-vacuous and therefore b is not recognised as a relevant attacker that must be defended against. However, we recover this aspect if we additionally require that the reduct is also ud-vacuous. Definition 5. Let F = (A,R) be an AF. S A is strongly undisputed in F if it is undisputed and FS is ud-vacuous. In other words, a strongly undisputed set S is a conflictfree set such that FS possesses no non-empty admissible or undisputed sets. Let sud(F) denote the set of strongly undisputed sets of F. Since it can easily be seen that non-existence of non-empty undisputed sets implies non-existence of nonempty admissible sets, we obtain the following simpler characterisation. Proposition 6. sud = cfud.

: Let S be a strongly undisputed set. As S is undisputed it is also conflict-free. As FS is (by definition) also udvacuous it follows that S is a cfud-extension. : Let S be a cfud-extension. By definition FS is ud-vacuous and S is conflict-free. So it remains to show that FS is adm-vacuous. Assume that FS is not adm-vacuous, then there exists a non-empty set S that is admissible in FS. Then it also follows that there is a non-empty preferred extension S with S S in FS. Since preferred extensions are also undisputed sets, it follows that FS has the non-empty undisputed set S , in contradiction to the assumption that FS is ud-vacuous.

Let us now consider the examples from before. Example 5. Consider again F0 and F1 from Figure 1, see also Example 2. We have sud(F0) = sud(F1) = {{b}} as desired. In particular, note that /0 is not strongly undisputed in both F0 and F1 since the corresponding reducts contain non-empty undisputed sets (see Example 2).

Example 6. Consider again F2 from Figure 2, see also Example 1. We have sud(F2) = {{a,c},{a, f}}.

Example 7. Consider again F4 from Figure 5, see also Example 4. We have sud(F3) = {{b}}. In particular, note that {c} is not strongly undisputed since its reduct F{c} 3 is the same as the AF F0 (see Figure 1), which has the non-empty undisputed set {b}.

The above examples show that strongly undisputed semantics behaves well with the considered examples. In particular, Example 7 showed that we solved one of the two issues we raised at the end of the previous section. The other issue will be shown to have been solved below (in fact as a corollary of the very next result).

Theorem 2. For all F, sud(F) = udud(F) = udud max(F).

Proof. The equality sud(F) = udud(F) follows directly from Definition 5. The subset relation udud max(F) udud(F) follows also directly from udmax(F) ud(F). It remains to show udud(F) udud max(F). Let S udud(F) and assume S / udud max(F). Then there is S with S S and S udud max(F). From S udud max(F) it follows S ud(F). From S udud(F) it follows S ud(F). With S S and Proposition 5 it follows S \ S ud(FS), contradicting the fact that S udud(F) and FS being ud-vacuous.

The above theorem paints a nice symmetric picture in light of Theorem 1. There, preferred extensions could be characterised by combining admissibility with minimal undisputed sets (where combination was implemented through intersection). Above, strongly undisputed sets are characterised by combining ud-vacuity with maximal undisputed sets (where combination was implemented through vacuous reduct construction). Theorem 2 gives us the following nice properties of strongly undisputed sets.

Corollary 2. sud satisfies I-maximality, i. e., for all AFs F = (A,R), S,S sud(F) with S = S , we have S S and S S.

Proof. Theorem 2 showed that strongly undisputed sets are maximal undisputed sets. By definition, no two maximal undisputed sets can be in any subset relation.

Corollary 3. For all F = (A,R), st(F) sud(F).

Proof. Any stable extension S is preferred and therefore undisputed, see Theorem 1. Since S attacks all arguments it does not contain, FS is empty and therefore ud-vacuous. The claim follows then from Theorem 2.

Taken together Theorem 1, Corollary 3, as well as established relationships (Dung 1995), and the definitions of our new semantical notions, we obtain the picture in Figure 6. It shows that the relationships between strongly undisputed sets, undisputed sets, and conflict-free sets mirror the relationships between stable extensions, preferred extensions,

Figure 6: Relationships between our new semantics ud and sud and the existing notions of stability (st), preferredness (pr), admissibility (adm), and conflict-freeness (cf). An arrow from σ1 to σ2 implies σ1(F) σ2(F) for all F.

Figure 7: The AF F5 from Example 8.

and admissible sets. In particular, note that for odd-cyclefree F, pr(F) = st(F) = ud(F) = sud(F), cf. Proposition 2.

The relationship between stable and strongly undisputed semantics comes with one caveat, namely that strongly undisputed semantics can also be undefined for certain AFs. Example 8. Consider AF F5 in Figure 7 with ud(F5) = {/0,{a},{b},{c}}. In particular, note that adm(F5) = {/0} and that, e. g., F{a} 5 consists of the self-attacking d that attacks c (which is isomorphic to F0 from Figure 1). The undisputed sets {a}, {b}, and {c} are maximal (and therefore the only candidates for strongly undisputed sets). However, ud(F{a} 5 ) = {/0,{c}} and, likewise, F{b} 5 and F{c} 5 are also not ud-vacuous. It follows sud(F5) = /0. Weak admissibility behaves a little different in the previous example, where it classifies /0 as the only weakly admissible set (in contrast to strongly undisputed semantics that states that there is no strongly undisputed set, not even /0). However, both weakly admissible semantics as well as strongly undisputed semantics agree that there is no acceptable argument in F5 (i. e., an argument that is contained in at least one acceptable set). Note that due to Proposition 4, strongly undisputed semantics also satisfies the reinstatement property (i. e., defended arguments are always contained in a strongly undisputed set). Dauphin et al. (Dauphin, Rienstra, and van der Torre 2020) introduced the principle of reduct admissibility as a weaker form of admissibility that generalises the issue observed in the AFs F0 and F1 from Section 3. In general, a semantics σ satisfies reduct admissibility if for every AF

F = (A,R), every E σ(F), and every a E, if b Ra then b / Sσ(FE). In other words, every attacker of an extension of σ(F) is not acceptable in the reduct FE.

Proposition 7. sud satisfies reduct admissibility.

Proof. For F = (A,R) and E sud(F), we have ud(FE) {/0} and therefore sud(FE) {/0}. So Ssud(FE) = /0 and for every b with b Ra with a E, b / /0.

The following observation is a variant of Proposition 5 and shows that strongly undisputed sets can also be decomposed along the reduct.

Proposition 8. Let F = (A,R) be an AF, E sud(F), and E E with E ud(F). Then E \E sud(FE ).

Proof. Let E sud(F) and E E with E ud(F). Since E is conflict-free in F, E \E is also conflict-free in FE . Furthermore, (FE )E\E = FE E\E = FE and adm(FE) {/0} and ud(FE) {/0} as E is strongly undisputed. It follows that E \E sud(FE ).

In this section, we showed that strongly undisputed semantics is a conceptually simple approach to model a weaker form of admissibility that complies with the intuition behind the AFs F0 and F1 discussed in Section 3. Moreover, (strongly) undisputed sets nicely fit into the general classification of classical semantics due to their mirrored relationships wrt. preferred and stable semantics, cf. Figure 6. In the next section, we will analyse the computational complexity of reasoning with (strongly) undisputed sets.

6 Computational Complexity

We assume familiarity with basic concepts of computational complexity and basic complexity classes such as P, NP, co NP, see (Papadimitriou 1994) for an introduction. For two complexity classes C and D, the class C D is the class of decision problems solvable by an algorithm in class C that has access to an oracle of class D (which means that the algorithm can obtain the answer of any problem in class D within one step). We also consider complexity classes of the polynomial hierarchy, which are defined via ΠP 0 = ΣP 0 = P and ΣP i = NPΣP i 1, ΠP i = co NPΣP i 1 for i > 0. We consider the following computational tasks for σ {ud,sud}, cf. (Dvoˇr ak and Dunne 2018):

Verσ Given F = (A,R) and E A, decide whether E σ(F). Existsσ Given F = (A,R), decide whether σ(F) = /0. Exists /0 σ Given F = (A,R), decide whether there is an E σ(F) with E = /0. Credσ Given F = (A,R) and a A, decide whether there is E σ(F) with a E. Skeptσ Given F = (A,R) and a A, decide whether for all E σ(F), a E.

The following theorems summarise our results regarding the computational complexity of the above tasks for (strongly)

undisputed sets. The proofs are omitted due to space restrictions, but can be found in an online appendix.3

Theorem 3. Verud is co NP-complete, Existsud is trivial, Exists /0 ud is ΣP 2-complete, Credud is ΣP 2-complete, and Skeptud is ΠP 2-complete. Theorem 4. Versud is ΠP 2-complete, Existssud is ΣP 3complete, Exists /0 sud is ΣP 3-complete, Credsud is ΣP 3-complete, and Skeptsud is ΠP 3-complete. It can be observed that the computational complexity of reasoning with (strongly) undisputed sets is relatively high, in particular compared to classical admissibility-based semantics (Dvoˇr ak and Dunne 2018). However, it should be noted that skeptical reasoning with undisputed sets is of the exact same complexity as skeptical reasoning with preferred semantics, which is insofar interesting as undisputed sets were defined as a generalisation of preferred extensions. Moreover, compared to weak admissibility-based semantics, where all reasoning problems are PSPACE-complete (Dvoˇr ak, Ulbricht, and Woltran 2021), our new semantical notions are significantly easier (under standard complexitytheoretic assumptions). As with regards to subclasses of abstract argumentation frameworks where the above tasks become tractable (or just easier), we can exploit the observations from Propositions 2 and 3, which showed that (strongly) undisputed semantics coincides with preferred (and stable) semantics in certain subclasses. For example, for odd-cycle-free argumentation frameworks, skeptical reasoning with strongly undisputed sets is only co NP-complete (since it is equivalent to skeptical reasoning with stable semantics).

7 Summary and Conclusion We introduced the notions of undisputed sets and strongly undisputed sets as an approach to define a weaker version of admissibility that deals with the issue of irrelevant attacks. Our notions rely on the property of σ-vacuity, i. e., the property of an AF to have no non-empty σ-extension. Then an undisputed set is any conflict-free set such that its reduct is adm-vacuous and a strongly undisputed set is any conflictfree set such that its reduct is ud-vacuous. We analysed both notions in-depth and showed that they comply with desirable properties of weak versions of admissibility. In addition, they are founded on a conceptually simple idea and mirror classical relationships between stable, preferred, and admissible sets. We analysed the computational complexity and showed that most problems lie on the second and third level of the polynomial hierarchy. Part of future work is to analyse the properties of (strongly) undisputed sets in more detail, in particular wrt. argumentation principles discussed in, e. g., (van der Torre and Vesic 2018). We will also investigate vacuous reduct semantics in more detail. In particular, it would be interesting to investigate whether further semantics can be characterised in the same way as preferred extensions have been characterised as admadm-extensions. For example, it is also quite easy to see that co = admgr.

3http://mthimm.de/misc/aaai23 appendix.pdf

References Amgoud, L.; and Ben-Naim, J. 2013. Ranking-based Semantics for Argumentation Frameworks. In Liu, W.; Subrahmanian, V. S.; and Wijsen, J., eds., Proceedings of the 7th International Conference on Scalable Uncertainty Management (SUM 2013), volume 8078 of Lecture Notes In Artificial Intelligence. Washington, DC, USA. Baroni, P.; Boella, G.; Cerutti, F.; Giacomin, M.; van der Torre, L.; and Villata, S. 2014. On the Input/Output behavior of argumentation frameworks. Artificial Intelligence, 217: 144 197. Baroni, P.; Caminada, M.; and Giacomin, M. 2018. Abstract Argumentation Frameworks and Their Semantics. In Baroni, P.; Gabbay, D.; Giacomin, M.; and van der Torre, L., eds., Handbook of Formal Argumentation, 159 236. College Publications. Baroni, P.; Gabbay, D.; Giacomin, M.; and van der Torre, L., eds. 2018. Handbook of Formal Argumentation, volume 1. College Publications. Baumann, R.; Brewka, G.; and Ulbricht, M. 2020a. Comparing Weak Admissibility Semantics to their Dung-style Counterparts - Reduct, Modularization, and Strong Equivalence in Abstract Argumentation. In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 20). Baumann, R.; Brewka, G.; and Ulbricht, M. 2020b. Revisiting the Foundations of Abstract Argumentation - Semantics Based on Weak Admissibility and Weak Defense. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 20). Bistarelli, S.; and Santini, F. 2021. Weighted Argumentation. In Gabbay, D.; Giacomin, M.; Simari, G. R.; and Thimm, M., eds., Handbook of Formal Argumentation, volume 2, chapter 6. College Publications. Dauphin, J.; Rienstra, T.; and van der Torre, L. 2020. A Principle-Based Analysis of Weakly Admissible Semantics. In Prakken, H.; Bistarelli, S.; Santini, F.; and Taticchi, C., eds., Computational Models of Argument - Proceedings of COMMA 2020, Perugia, Italy, September 4-11, 2020, volume 326 of Frontiers in Artificial Intelligence and Applications, 167 178. IOS Press. Dondio, P.; and Longo, L. 2019. Beyond reasonable doubt: A proposal for undecidedness blocking in abstract argumentation. Intelligenza Artificiale, 13(2): 123 135. Dung, P. M. 1995. On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. Artificial Intelligence, 77(2): 321 358. Dunne, P. E.; Hunter, A.; Mc Burney, P.; Parsons, S.; and Wooldridge, M. 2011. Weighted argument systems: Basic definitions, algorithms, and complexity results. Artificial Intelligence, 175(2): 457 486. Dvoˇr ak, W.; and Dunne, P. E. 2018. Computational Problems in Formal Argumentation and their Complexity. In Baroni, P.; Gabbay, D.; Giacomin, M.; and van der Torre, L., eds., Handbook of Formal Argumentation, chapter 14. College Publications.

Dvoˇr ak, W.; Ulbricht, M.; and Woltran, S. 2021. Recursion in Abstract Argumentation is Hard - On the Complexity of Semantics Based on Weak Admissibility. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 21). Gabbay, D.; Giacomin, M.; Simari, G. R.; and Thimm, M., eds. 2021. Handbook of Formal Argumentation, volume 2. College Publications. Hunter, A.; Polberg, S.; Potyka, N.; Rienstra, T.; and Thimm, M. 2021. Probabilistic Argumentation: A Survey. In Gabbay, D.; Giacomin, M.; Simari, G. R.; and Thimm, M., eds., Handbook of Formal Argumentation, volume 2, chapter 7. College Publications. Kakas, A.; and Mancarella, P. 2013. On the semantics of abstract argumentation. Journal of Logic and Computation, 23(5): 991 1015. Li, H.; Oren, N.; and Norman, T. J. 2011. Probabilistic Argumentation Frameworks. In Proceedings of the First International Workshop on the Theory and Applications of Formal Argumentation (TAFA 11). Papadimitriou, C. 1994. Computational Complexity. Addison-Wesley. Skiba, K.; Rienstra, T.; Thimm, M.; Heyninck, J.; and Kern Isberner, G. 2021. Ranking Extensions in Abstract Argumentation. In Zhou, Z.-H., ed., Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 21), 2047 2053. van der Torre, L.; and Vesic, S. 2018. The Principle-Based Approach to Abstract Argumentation Semantics. In Baroni, P.; Gabbay, D.; Giacomin, M.; and van der Torre, L., eds., Handbook of Formal Argumentation. College Publications.