Optimisation and Approximation in Abstract Argumentation: The Case of Stable Semantics

1 Introduction

Abstract argumentation frameworks (AAFs) [Dung, 1995] are an approach for modelling argumentative scenarios that represents arguments as nodes in a directed graph, where a directed edge represents an attack from one argument to another. Reasoning in AAFs consists of identifying sets of arguments (extensions) that form a plausible outcome of the argumentation. Several different semantical approaches for formalising plausibility in this context have been proposed, see e. g. [Dung, 1995; Baroni et al., 2018]. In this work, we focus on stable semantics. A stable extension is a conflict-free set of arguments (no argument in the set attacks some other argument in the set) that attacks all arguments not contained in the set. Stable semantics is a very strong semantical notion and stable extensions are not guaranteed to exist [Dung, 1995].

In this work, we consider two soft notions of stable semantics that weaken the requirements of stable semantics by allowing to consider sets that do not necessarily attack all other arguments or are not necessarily conflict-free. While qualitative approaches for this motivation have been investigated with the stage [Verheij, 1996] and semi-stable semantics [Caminada, 2006] before, we consider here a quantitative treatment. In particular, a set of arguments is called a k-stable extension (with k ∈ N) iff is conflict-free and the number of arguments contained in the set and attacked by the set is at least k. Therefore, k-stable extensions with larger values of k are "closer" of being a stable extension. The other variant we consider is the k-stable* extension, which attacks all arguments it does not contain and "respects" at least k attacks (meaning that for at least k attacks, it is not the case that both arguments involved in the attack are in the extension). These notions have several applications. For one, they allow to rank sets of arguments in terms of their closeness of being stable extensions, see e. g. [Skiba et al., 2021] for a general treatment of this problem area. This allows to derive a graded notion of the acceptability of arguments and therefore judge their strength in a more fine-grained manner, as in ranking-based semantics [Amgoud and Ben-Naim, 2013; Bonzon et al., 2016]. Another application is in enforcement [Baumann et al., 2021], which addresses the problem of how to change an AAF in order to enforce arguments to become acceptable. Here, a set of arguments that is already "close" of being stable is likely to be easier to enforced than a set of arguments that are not "close" of being stable. The approaches considered in this work can therefore be used to guide practical approaches to enforcement.

Our analysis of the above two notions in this paper focusses on computational issues and, in particular, on the problem of approximation. The term approximation has received quite some attention in the context of AAFs in recent years [Kuhlmann and Thimm, 2019; Craandijk and Bex, 2020; Malmqvist et al., 2020; Malmqvist, 2022; Delobelle et al., 2023; Thimm, 2021] and the International Competition on Computational Models of Argumentation (ICCMA) 1 even featured approximation tracks in 2021 and 2023. However, these tracks and the aforementioned works are actually about heuristic algorithms for solving decision problems (such as the acceptability of arguments wrt. certain semantics) by relying, e. g., on heuristics informed by machine learning models [Kuhlmann and Thimm, 2019; Craandijk and Bex, 2020; Malmqvist et al., 2020; Malmqvist, 2022]. But in theoretical computer science the term approximation [Vazirani, 2003] actually refers to algorithms that feature a theoretically guaranteed approximation quality when solving optimisation problems. We consider this definition as well in the present work. In particular, we consider the optimisation problems of finding the maximal value k, such that a given argument is in a k-stable or k-stable* extension, which thus represent graded variants of the classical credulous reasoning problem for stable semantics. We study the computational complexity of these optimisation problems from two perspectives. First, we determine the complexity for solving these optimisation problems exactly and show that they are FP NP[log] - complete. Moreover, we analyse the hardness of approximation and show that the problem is Poly-APX-complete for k-stable semantics and Log-APX-hard for k-stable* semantics (both under PTAS-reductions). So both problems are, in general, very hard to approximate. Nonetheless, we present several simple polynomial-time approximation algorithms for these problems and show experimentally that their average approximation quality is rather good.

1 http://argumentationcompetition.org/

To summarise, the contributions of the paper are as follows.

1. We present two soft notions of stable semantics for abstract argumentation and analyse their general properties (Section 3).
2. We consider the two corresponding optimisation problems and show that they are both FP NP[log] -complete (Section 4).
3. We analyse the complexity of approximation of these optimisation problems and show that they are Poly-APXcomplete and Log-APX-hard (under PTAS-reductions), respectively (Section 5).
4. We present four polynomial-time approximation algorithms, two for k-stable semantics and two for k-stable* semantics (Section 6).
5. We analyse the general feasibility of these approximation algorithms in an experimental study and show that they perform quite good in practice (Section 7).

Section 2 gives some necessary background on abstract argumentation and Section 8 concludes the paper. Proofs of technical results can be found in an online appendix. 2

2 Abstract Argumentation

We consider abstract argumentation frameworks [Dung, 1995] defined as follows.

Definition 1. An abstract argumentation framework (AAF) F is a tuple F = (A, R) where A is a (finite) set of arguments and R ⊆ A × A is the attack relation.

For (a, b) ∈ R we also write aRb and say that a is an attacker of b. For an AF F = (A, R) and any set S ⊆ A we write

to denote the set of attacked arguments by S (S+ F ) and the set of arguments attacking S (SF ). For singleton sets {a} ⊆ A we write a+F resp. a-F instead of {a}+F resp. {a}-F . The range S⊕ F of a set S ⊆ A is defined as S⊕ F = S ∪S+ F .

Semantics are given to an AF F = (A, R) via extensions, i. e., sets of arguments that form a plausible outcome of the argumentation represented by F. In this paper, we focus on the stable semantics [Dung, 1995].

2 https://mthimm.de/misc/ijcai24 opt mt.pdf

Definition 2. Let F = (A, R) be an AF and let S ⊆ A be a set of arguments. We say that

• S is conflict-free set iff S ∩S+ F = ∅ and
• S is a stable extension iff S is conflict-free and S⊕ F = A.

Let cf(F) denote the set of all conflict-free sets of S and let st(F) denote the set of all stable extensions of F. Note that stable extensions do not necessarily exist for a given AAF.

We consider the following classical reasoning problems for AAFs [Dvoˇr´ak and Dunne, 2018] (let σ be a semantics such as st):

VERσ :

Input AF F = (A,R), S ⊆ A

CREDσ :

SKEPσ :

Output YES iff S ∈ σ(F)

Input AF F = (A,R), a ∈ A Output YES iff a ∈ ⋃ σ(F)

Input AF F = (A,R), a ∈ A Output YES iff a ∈ ⋂ σ(F)

EXISTSσ: Input AF F = (A,R)

Output YES iff σ(F) ̸= ∅

EXISTS¬∅

σ : Input AF F = (A,R)

Output YES iff there is S ∈ σ(F) with S ̸= ∅

The computational complexity of the above problems for stable semantics are as follows, cf. [Dimopoulos and Torres, 1996; Dvoˇr´ak and Dunne, 2018].

Theorem1. VERst is in P, CREDst is NP-complete, SKEPst is coNP-complete, EXISTSst is NP-complete, EXISTS¬∅ st is NPcomplete.

3 Soft Notions of Stable Extensions

In this section, we will investigate soft notions 3 of stable extensions that allow us to assess the acceptability of arguments in a more relaxed manner as with strict stable semantics. This allows us to judge arguments as "closer" being acceptable wrt. stable semantics than others.

A stable extension S is characterised by two properties: it has full range (S⊕ F = A) and it is conflict-free (S ∩ S+ F = ∅). Our first approach (Section 3.1) weakens the first property and our second approach (Section 3.2) weakens the second.

3 We use the term "soft" instead of the probably more appropriate "weak" to avoid confusion with the non-related notion of weak stable semantics from [Baumann et al., 2022].

3.1 Softening the Requirement of Full Range

We now consider a semantical notion that requires a set to be conflict-free (this is a strict requirement) and that at least a minimum number of arguments are contained in its range.

Definition 3. Let F = (A,R) be an AF, k ∈ N, and let S ⊆ A. We say that S is a k-stable extension iff S is conflictfree and |S⊕ F | ≥ k. Let stk(F) denote the set of k-stable extensions of F .

In other words, a conflict-free set S is a k-stable extension if the number of arguments in S and the number of arguments attacked by S is at least k.

Some simple observations are as follows.

Proposition 1. Let F = (A,R) be an AF, k ∈ N, S ⊆ A, and a ∈ A.

1. S is a |A|-stable extension iff S is a stable extension.
2. If S is a k-stable extension then S is a k′ -stable extension for all k′ < k.
3. S ∈ cf(F) iff S is a 0-stable extension.
4. (a, a) /∈ R iff {a} is a 1-stable extension.
5. ∅ is a 0-stable extension.

Due to items 1-3 from above we obtain

so k-stable extensions cover the complete spectrum between stable extensions and conflict-free sets of any AF F, for k = 0, . . . , |A|.

Example 2. We consider again the AAF F1 in Figure 1. Since st(F1) = st|A1|(F1) we have st6(F1) = {{a, c}, {a, f}, {d, f}}. By allowing extensions to contain less arguments in the range we obtain

Reasoning with k-stable semantics is as hard as reasoning with stable semantics when considering k as an additional input parameter.

Theorem 2. Let k ∈ N be an additional input parameter to the following problems. VERstk is in P, CREDstk is NP-complete, SKEPstk is coNP-complete, EXISTSstk is NPcomplete, EXISTS¬∅ stk is NP-complete.

3.2 Softening the Requirement of Conflict-Freeness

Our second variant for a softening of stable extensions requires that a set has full range (that is a strict requirement) and that it "satisfies" a maximal number of attacks, where a set of arguments satisfies an attack if it does not contain both the attacker and the attacked argument of that attack. More formally, for F = (A, R) and a set S ⊆ A we denote by

the set of satisfied attacks of F by S. Any attack (a, b) ∈ R \ S⊛ F is also called violated attack of F by S. Note that a set S ⊆ A is conflict-free if and only if S⊛ F = R.

Definition 4. Let F = (A, R) be an AF, k ∈ N, and let S ⊆ A. We say that S is a k-stable* extension iff S⊕ F = A and |S⊛ F | ≥ k. Let st∗k (F) denote the set of k-stable* extensions of F .

In other words, a set S with full range is a k-stable* extension if the number of satisfied attacks of S is at least k.

We make some simple observations about k-stable* extensions.

Proposition 2. Let F = (A,R) be an AF, k ∈ N, S ⊆ A, and a ∈ A.

1. S is a |R|-stable* extension iff S is a stable extension.
2. If S is a k-stable* extension then S is a k′ -stable* extension for all k′ < k.
3. A is a 0-stable* extension.
4. If a ∈ A is not attacked in F, then a ∈ S for every k-stable* extension S.

Example 3. We consider again the AAF F1 in Figure 1. Since st(F1) = st∗|R2| (F1) we have st∗11 (F1) = {{a, c}, {a, f}, {d, f}}. Due to the large number of extensions, we only give a complete list for k = 10, 9, 8:

Complexity-wise, k-stable* semantics behaves as k-stable and stable semantics.

Theorem 3. Let k ∈ N be an additional input parameter to the following problems. VERst∗k is in P, CREDst∗k is NP-complete, SKEPst∗k is coNP-complete, EXISTSst∗k is NPcomplete, EXISTS¬∅ st∗k is NP-complete.

4 Complexity of Optimisation

The notions of k-stable and k-stable* extensions "approach" the notion of stable extensions: the larger the value k the "closer" these extensions are to being stable extensions. Given an AAF F = (A,R) and an argument a ∈ A, we are interested in finding the maximum value k† such that a is contained in a k† -stable/k† -stable* extension. Formally, the main reasoning problems we are interested in are the following optimisation problems 4 :

MAXSTABLE

4 We define max ∅ = -∞

Note for MAXSTABLE, the case that no k exists with a ∈ ⋃ stk(F) can only happen when a attacks itself. For MAXSTABLE*, the output is always a finite number as a ∈ A ∈ st∗|R| (F) (see item 3 of Proposition 2).

The two problems above are optimisation variants of credulous reasoning wrt. stable semantics: we are seeking the maximum number k† such that a given argument a can be credulously inferred wrt. k† -stable/k† -stable* semantics. An analysis for the optimisation variants of skeptical reasoning (where we seek the maximum k† such that a given argument a is contained in all k† -stable/k† -stable* extensions) is left for future work.

Observe furthermore that solving MAXSTABLE is not equivalent to reasoning with stage semantics [Verheij, 1996]. For an AAF F = (A, R) recall that a set S ⊆ A is a stage extension if S is conflict-free and S⊕ F is maximal wrt. set inclusion among all conflict-free sets. In particular, stage semantics is defined in terms of maximality wrt. set inclusion while MAXSTABLE seeks sets where the range is maximal wrt. cardinality. Moreover, MAXSTABLE is defined wrt. to a given argument and every argument has a defined value, while an argument is credulously inferred wrt. stage semantics only if there is a stage extension containing that argument. However, a simple relationship between these two notions is captured in the following proposition.

Proposition 3. Let F = (A,R) be an AAF and a ∈ A. If there is a stage extension S with a ∈ S then mst(F, a) ≥ |S⊕ F |.

Another soft notion of a stable extension is that of a semistable extension [Caminada, 2006], which is an admissible 5 set that has maximal range (wrt. set inclusion). Since admissibility is a stronger notion than conflict-freeness, the bound given in Proposition 3 also applies when using semi-stable extensions instead of stage extensions. As k-stable extensions are not necessarily admissible, no more general relationships can be stated, however.

Example 4. We continue Example 2 and consider again the AAF F1 from Figure 1. Here we get

Since credulous reasoning with k-stable/k-stable* semantics is NP-complete (see Theorems 2 and 3), the problems MAXSTABLE and MAXSTABLE* are naturally in the complexity class NPO, i. e., the class containing optimisation problems where the corresponding decision problems are in NP. We will now investigate the computational complexity of

5 A set S is admissible iff S is conflict-free and for every a ∈ A and b ∈ S with aRb there is c ∈ S with cRa.

and MAXSTABLE and MAXSTABLE* from two perspectives in more detail. First, we consider the complexity of (exact) optimisation and show that both problems are FP NP[log] -complete. In Section 5 we will consider the complexity of approximation and show that MAXSTABLE is Poly-APX-complete (under PTAS-reductions) while MAXSTABLE* is Log-APXcomplete (under PTAS-reductions).

The class FP NP[log] is the class of functional problems that have a polynomial-time algorithm that may make logarithmically many calls to an NP-oracle. Membership of our problems MAXSTABLE and MAXSTABLE* for this class can be shown easily through an algorithm that does a binary search for the maximal value k† and iteratively solving the problems CREDstk and CREDst∗k , respectively. Hardness is shown through a reduction from the FP NP[log] -complete problem MAXSATSIZE, i. e., the problem of determining the maximal number of clauses of a SAT instance that can be jointly satisfied.

Theorem 4. MAXSTABLE is FP NP[log] -complete.

Theorem 5. MAXSTABLE* is FP NP[log] -complete.

5 Complexity of Approximation

We will now consider the problem of approximating the solutions to MAXSTABLE and MAXSTABLE*, i. e., we are interested in algorithms that maximise the approximation ratio AR in the following sense:

where OPT is the solution to either MAXSTABLE or MAXSTABLE* (given some F = (A,R) and a ∈ A) and APP ≤ OPT is the solution of the considered approximation algorithm. An approximation ratio of 1 (which is the maximal value for AR) therefore indicates an optimal algorithm and lower values of AR indicate worse approximation quality. Note that OPT = 0 is a possible solution for MAXSTABLE* (e. g., it is the solution for b in F = ({a, b}, {(a, b)})). Then we also necessarily have APP = 0 (due to 0 ≤ APP ≤ OPT) and we just define AR = 1 in that case.

We now investigate the approximation complexity of MAXSTABLE. For that, observe that the notion of a k-stable extension is related to another well-known notion from graph theory, namely independent sets.

Definition 5. Let G = (V, E) be an undirected graph. A set S ⊆ V is an independent set iff (S ×S) ∩E = ∅.

In other words, an independent set S of an undirected graph G = (V,E) is a set of vertices of G, such that no two vertices of S are adjacent in G. The optimisation problem MAXINDEPSET is defined as:

MAXINDEPSET

Input G = (V,E)

Output maxS⊆V {|S| | S is an independent set in G}

In other words, the problem MAXINDEPSET 6 for a given undirected graph G = (V,E) asks for finding the largest number k such that there is an independent set S ⊆ V with |S| = k. This is very much related to the problem MAXSTABLE. However, for MAXSTABLE we are seeking sets of vertices of a directed graph (instead of an undirected graph), where the cardinality of the range (instead of the cardinality of the set) is maximal. These differences actually pose a significant challenge in relating approximative approaches for MAXINDEPSET and MAXSTABLE in the proof of Theorem 6 below.

6 This problem is also called the maximum independent set problem and should not be confused with the maximal independent set problem that seeks an independent set that is maximal wrt. set inclusion (the latter problem can also be solved in polynomial time).

The problem MAXINDEPSET is Poly-APX-complete [Bazgan et al., 2005], and therefore very hard to approximate (given P ̸= NP). The complexity class Poly-APX consists of optimisation problems, which can be approximated with polynomial-time algorithms that admit an approximation ratio that is bounded by a polynomial dependent on the size of the input. We use this result to also show Poly-APXcompleteness of MAXSTABLE. So in our case, the best general lower bound of the approximation ratio we can guarantee is AR ≥ 1/f(|A|) where f is a polynomial and A is the set of arguments of the input F = (A, R).

We show Poly-APX-completeness under PTAS-reductions [Crescenzi, 1997], which have also been used to show Poly-APX-completeness of MAXINDEPSET in [Bazgan et al., 2005]. Informally speaking, a PTAS-reduction is a polynomial-time reduction from a problem A to a problem B that preserves, to some degree, the approximation ratio of an algorithm for problem B to problem A. The formal definition can be found in the proof of the theorem below (see the supplementary material).

Theorem 6. MAXSTABLE is Poly-APX-complete under PTAS-reductions.

We now turn to the approximation complexity of MAXSTABLE*. The k-stable* extension also has a wellknown counterpart in graph theory: the dominating set.

Definition 6. Let G = (V, E) be an undirected graph. A set S ⊆ V is a dominating set iff every v ∈ V is either in S or adjacent to S.

So a dominating set S of an undirected graph G = (V, E) is a set of vertices of G, such that all vertices of G are either in S or adjacent to it. The optimisation problem MINDOMSET is defined as:

MINDOMSET

Input G = (V,E) Output minS⊆V {|S| | S is a dominant set in G}

In other words, the problem MINDOMSET for a given undirected graph G = (V, E) asks for finding the smallest number k such that there is a dominating set S ⊆ V with |S| = k. The problem MINDOMSET is Log-APX-complete [Lund and Yannakakis, 1994]. The complexity class Log-APX consists of optimisation problems, which can be approximated with polynomial-time algorithms that admit an approximation ratio that is bounded by the logarithm of a polynomial dependent on the size of the input, i. e., we have AR ≥ 1/ log(f(|I|)) where f is a polynomial and |I| is the size of the instance.

Algorithm 1 GCF algorithm for MAXSTABLE.

Input: F = (A,R) and a ∈ A Output: k ∈ N such that there is a conflict-free set S with a ∈ S and k = |S⊕ F |. 1: if (a, a) ∈ R then 2: return -∞ 3: S ← {a} 4: while S ∪S+ F ∪SF ̸= A do 5: Let b ∈ A\(S∪S+ F ∪SF ) s.t. |(S∪{b})⊕F | is maximal 6: S ←S ∪ {b} 7: return |S⊕ F |

Again, we can observe that the problem MINDOMSET is related to our problem MAXSTABLE*. Observe first that although MAXSTABLE* is defined as a maximisation problem, we can consider an equivalent formalisation where we minimise the number of violated attacks (instead of maximising the number of satisfied attacks). 7 Comparing MINDOMSET with MAXSTABLE*, we see that in the latter we are seeking sets of vertices of a directed graph (instead of an undirected graph), where the cardinality of the set of edges between members in the set is minimal (instead of the cardinality of the set itself). While these differences also pose some interesting challenges in the proof, we are still able to reduce the problem MINDOMSET to MAXSTABLE* and therefore obtain Log-APX-hardness of MAXSTABLE*. Unfortunately, proving the membership of MAXSTABLE* to Log-APX is quite elusive, so we only give the lower bound.

Theorem 7. MAXSTABLE* is Log-APX-hard under PTASreductions.

6 Approximation Algorithms

Despite the quite negative theoretical results from the previous two sections, we will now discuss four simple approximation algorithms (based on greedy search) for the problems MAXSTABLE and MAXSTABLE*, for which we will investigate the empirical average approximation ratio in Section 7.

6.1 Growing Conflict-Free Sets (GCF)

Our first approximation algorithm addresses the problem MAXSTABLE, i. e., given F = (A,R) and a ∈ A we are looking for a conflict-free set S such that a ∈ S and |S⊕ F | is maximised. We do this by greedily adding arguments to a set, as long as this set remains conflict-free. Algorithm 1 depicts our GCF algorithm (growing conflict-freeness). In lines 1-2 we first check for the special case of a self-attacking argument and return -∞ as the (optimal) solution in that case. We add our query argument a to a set S in line 3 and repeat lines 5-6 as long as there are arguments, which can be added to S without violating conflict-freeness (so as long as S ∪ S+ F ∪ SF ̸= A). From those arguments, we pick one in

7 Note, however, that approximation ratios differ between the representations as minimisation and maximisation problems. We only consider the approximation ratio for the representation as maximisation problem.

Algorithm 2 SCF algorithm for MAXSTABLE.

Input: F = (A,R) and a ∈ A Output: k ∈ N such that there is a conflict-free set S with a ∈ S and k = |S⊕ F |. 1: if (a, a) ∈ R then 2: return -∞ 3: S ←A 4: while S ∩S+ F ̸= ∅ do 5: Let b ∈ S \ {a} s.t. |(S \ {b})⊛F | is maximal 6: S ←S \ {b} 7: return |S⊕ F |

line 5 that maximises the number of arguments in the range and add it to S (line 6).

Proposition 4. Let k be the output of the GCF algorithm on input F = (A,R) and a ∈ A. Let furthermore k† be the optimal solution to MAXSTABLE on F and a. Then

1. there is a conflict-free set S with a ∈ S and k = |S⊕ F |,
2. k ≥ k† /|A|, and
3. k has been determined by GCF in polynomial time.

6.2 Shrinking Conflict-Free Sets (SCF)

Our second approximation algorithm for MAXSTABLE starts from the set of all arguments and iteratively removes arguments until we end up with a conflict-free set. Algorithm 2 depicts this SCF algorithm (shrinking conflict-free sets). Lines 1-2 again cover the special case of a selfattacking query argument. We initialise the set S in line 3 with the whole set of arguments from A. In line 5 we select an argument b (which has to be different from the query argument) that, upon removal, will produce a maximal number of satisfied attacks. We terminate once we reach a conflict-free set (line 4).

Proposition 5. Let k be the output of the SCF algorithm on input F = (A,R) and a ∈ A. Let furthermore k† be the optimal solution to MAXSTABLE on F and a. Then

1. there is a conflict-free set S with a ∈ S and k = |S⊕ F |,
2. k ≥ k† /|A|, and
3. k has been determined by SCF in polynomial time.

6.3 Growing Full-Range Sets (GFR)

We now consider the problem MAXSTABLE*, i. e., given F = (A, R) and a ∈ A we are looking for a set S with a ∈ S and S⊕ F = A such that S⊛ F is maximised. We provide a variant of the GCF algorithm (Section 6.1) that starts from the set S containing just a and iteratively adds arguments until S⊕ F = A. Algorithm 3 depicts this GFR algorithm (growing full-range sets). In line 1, the set S is initialised with a and line 3 adds the argument that will maximise the range. The algorithm terminates, when full range is achieved (line 2) and returns the number of satisfied attacks S⊛ F .

Proposition 6. Let k be the output of the GFR algorithm on input F = (A,R) and a ∈ A. Let furthermore k† be the optimal solution to MAXSTABLE* on F and a. Then

Algorithm 3 GFR algorithm for MAXSTABLE*.

• Input: F = (A,R) and a ∈ A Output: k ∈ N such that there is a set S with a ∈ S, S⊕ F = A and k = |S⊛ F |. 1: S ← {a} 2: while S⊕ F ̸= A do 3: Let b ∈ A \ S s.t. |(S ∪ {b})⊕F | is maximal 4: S ←S ∪ {b} 5: return |S⊛ F |

Algorithm 4 SFR algorithm for MAXSTABLE*.

• Input: F = (A,R) and a ∈ A Output: k ∈ N such that there is a set S with a ∈ S, S⊕ F = A and k = |S⊛ F |. 1: S ←A 2: while there is b ∈ S \ {a} with (S \ {b})⊕F = A do 3: Let b be as above s.t. |(S \ {b})⊛F | is maximal 4: S ←S \ {b} 5: return |S⊛ F |

1. there is a set S with a ∈ S, S⊕ F = A, and k = |S⊛ F |,
2. k ≥ k† /|R|, and
3. k has been determined by GFR in polynomial time.

Item 2 of the above proposition only gives a polynomial bound on the approximation ratio. As mentioned right before Theorem 7, we suspect that MAXSTABLE* is Log-APXcomplete and, moreover, that the GFR algorithm is a witness for Log-APX-membership. So the bound in item 2 can likely be improved to k† /O(log |R|), but we were not yet able to formally prove this.

6.4 Shrinking Full-Range Sets (SFR)

We now provide a variant of the SCF algorithm (Section 6.2) for the problem MAXSTABLE* that starts from the set S containing all arguments and iteratively removes arguments until S⊕ F = A can no longer be sustained. Algorithm 4 depicts this SFR algorithm (shrinking full-range sets). In line 1, the set S is initialised with A. As long as there is an argument b (that is not the query argument a), such that removing b from S will retain full range (line 3), such a b is removed from S that also restores a maximal number of satisfied attacks (line 3).

Proposition 7. Let k be the output of the SFR algorithm on input F = (A,R) and a ∈ A. Let furthermore k† be the optimal solution to MAXSTABLE* on F and a. Then

1. there is a set S with a ∈ S, S⊕ F = A, and k = |S⊛ F |,
2. k ≥ k† /|R|, and
3. k has been determined by SFR in polynomial time.

Also for the SFR algorithm, we believe that the bound in item 2 above can be improved to k† /O(log |R|).

7 Experiments

We now report on a small feasibility study that analyses the average approximation ratio of the algorithms from above on existing data sets.

7.1 Experimental Setup

We implemented 8 the algorithms from Sections 6.1-6.4 in Java, building on existing implementations for AAFs in TweetyProject 9 . We also implemented algorithms OPT and OPT* that optimally solve the problems MAXSTABLE and MAXSTABLE*, respectively. The algorithms for OPT and OPT* rely on straightforward MaxSAT encodings of MAXSTABLE and MAXSTABLE* and were implemented in Java as well, using the MaxSAT solver open-wbo 2.1 10 as backend solver. Since the main aim of the feasibility study here is to analyse the approximation quality of our heuristic approaches, we did not optimise the implementations for runtime performance (which also explains why we did not use a more performant programming language) and will not go into further details on the exact design of these algorithms.

We used the ICCMA17 and the ICCMA19 datasets as benchmarks. 11 Note that the benchmarks of ICCMA17 are clustered in groups and group B contains the benchmarks for problems related to stable semantics, so we only used that group, indicated by ICCMA17-B in the following. We also did some preliminary experiments with the datasets from ICCMA21 and ICCMA23, but since the optimal approaches timed out quite often on these datasets, an analysis of the approximation ratio was not feasible.

For each AAF in the above datasets, we selected 10 arguments 12 at random and asked all algorithms to determine the solution of MAXSTABLE, resp. MAXSTABLE* with respect to these query arguments. In the following, a pair of AAF and query argument will be referred to as instance. The experiments were conducted on a server with Intel Xeon E5-2643 v3 3.40-GHz CPUs (each algorithm is single-threaded) with 192GB RAM and we set a timeout of 10 minutes per instance.

7.2 Results

Table 1 summarises the results of our feasibility study on the ICCMA17-B (containing 3492 instances) and ICCMA19 (containing 3224 instances) dataset. The column "#TO" lists the number of timeouts of the corresponding approach, the column "RT" gives the total runtime (in seconds) on all instances that did not result in a timeout, and the column "AR" gives the average approximation ratio. The numbers in parentheses in the columns "RT" and "AR" are the number of instances, where these metrics are based upon. In particular, note that the average approximation ratio of a heuristic approach is only over those instances were both the heuristic approach and the optimal approach did not time out.

8 http://tweetyproject.org/r/?r=ijcai24 opt mt

9 http://tweetyproject.org

10 https://github.com/sat-group/open-wbo

11 http://argumentationcompetition.org

12 Both datasets contained AAFs with less than 10 arguments, for those we selected all arguments.

We can notice that the average approximation ratios of our heuristic approaches are surprisingly large, given the quite negative theoretical observations in the previous section. In fact, all heuristic approaches come close to the optimal solution with an average approximation ratio of 0.889 to 0.989. For the MAXSTABLE problem, we see that the GCF approach outperforms the SCF approach both in terms of approximation ratio and runtime, the latter showing a quite significant difference. For the MAXSTABLE* problem, the situation is a bit different. Here, the SFR approach outperforms the GFR approach in terms of approximation ratio, but not in terms of runtime. It is also quite clear, that all heuristic approaches outperform their corresponding optimal approaches in terms of timeouts and runtimes. However, since optimising runtime performance is not the goal of our implementations and this feasibility study, we will not go into a deeper analysis of the runtime behaviour. However, the results in Table 1 show, despite the negative worst-case behaviour of approximation algorithms highlighted in Theorems 6 and 7, that heuristic approaches for MAXSTABLE and MAXSTABLE* give promising results on average for existing datasets.

8 Summary and FutureWork

We introduced two soft notions of stable semantics, analysed their general properties, and investigated the computational complexity of optimisation and approximation. We also presented some polynomial-time approximation algorithms for the corresponding optimisation problems and analysed their empirical approximation quality. While we showed that the theoretical approximatibility is rather bad, our algorithms performed rather well on existing datasets.

For future work, we will investigate soft notions and the corresponding optimisation problems for other classical semantical notions such as admissibility and the resulting classical complete and preferred semantics. We will also consider skeptical variants of the optimisation problems MAXSTABLE and MAXSTABLE* and investigate their complexity. Finally, we will apply the developed soft notions to the problems of ranking [Skiba et al., 2021; Amgoud and Ben-Naim, 2013; Bonzon et al., 2016] and enforcement [Baumann et al., 2021].