Tractable algorithms for strong admissibility
Abstract
Much like admissibility is the key concept underlying preferred semantics, strong admissibility is the key concept underlying grounded semantics, as membership of a strongly admissible set is sufficient to show membership of the grounded extension. As such, strongly admissible sets and labellings can be used as an explanation of membership of the grounded extension, as is for instance done in some of the proof procedures for grounded semantics. In the current paper, we present two polynomial algorithms for constructing relatively small strongly admissible labellings, with associated min–max numberings, for a particular argument. These labellings can be used as relatively small explanations for the argument’s membership of the grounded extension. Although our algorithms are not guaranteed to yield an absolute minimal strongly admissible labelling for the argument (as doing so would have implied an exponential complexity), our best performing algorithm yields results that are only marginally larger. Moreover, the runtime of this algorithm is an order of magnitude smaller than that of the existing approach for computing an absolute minimal strongly admissible labelling for a particular argument. As such, we believe that our algorithms can be of practical value in situations where the aim is to construct a minimal or near-minimal strongly admissible labelling in a time-efficient way.
1.Introduction
In formal argumentation, one would sometimes like to show that a particular argument is (credulously) accepted according to a particular argumentation semantics, without having to construct the entire extension the argument is contained in. For instance, to show that an argument is in a preferred extension, it is not necessary to construct the entire preferred extension. Instead, it is sufficient to construct a set of arguments that is admissible. Similarly, to show that an argument is in the grounded extension, it is not necessary to construct the entire grounded extension. Instead, it is sufficient to construct a set of arguments that is strongly admissible.
The concept of strong admissibility was introduced by Baroni and Giacomin [1] as one of the properties to describe and categorise argumentation semantics. It was subsequently studied by Caminada and Dunne [3,6] who further developed strong admissibility in both its set and labelling form. In particular, the strongly admissible sets (resp. labellings) were found to form a lattice with the empty set (resp. the all-
As a strongly admissible set (labelling) can be used to explain that a particular argument is in the grounded extension (for instance, by using the discussion game of [4]) a relevant question is whether one can identify an expanation that is minimal. That is, given an argument A that is in the grounded extension, how can one obtain:
(1) a strongly admissible set that contains A, of which the number of arguments is minimal among all strongly admissible sets containing A, and
(2) a strongly admissible labelling that labels A
It has been found that the problem of computing (1) is NP-hard [11, Theorem 2]11 whereas the verification problem of (2) is co-NP-complete [7, Theorem 2].22 Moreover, it has also been observed that even computing a c-approximation for the minimum size of a strongly admissible set for a given argument is NP-hard for every
The complexity results related to minimal strong admissibility pose a problem when the aim is to provide the user with a relatively small explanation of why a particular argument is in the grounded extension. For this, one can either apply an algorithmic approach that yields an absolute minimal explanation, but has a worst-case exponential runtime, or one can apply an algorithmic approach that has a less than exponential runtime, but does not come with any formal guarantees of how close the outcome is to an absolute minimal explanation [11]. The former approach is taken in [11]. The latter approach is taken in our current paper.
In the absence of a dedicated algorithm for strong admissibility, one may be tempted to simply apply an algorithm for computing the grounded extension or labelling instead (such as [12,13]) if the aim is to do the computation in polynomial time. Still, from the perspective of minimality, this would yield the absolute worst outcome, as the grounded extension (labelling) is the maximal strongly admissible set (labelling). In the current paper we therefore introduce an alternative algorithm which, like the grounded semantics algorithms, runs in polynomial time but tends to produce a strongly admissible set (resp. labelling) that is significantly smaller than the grounded extension (resp. labelling). As the complexity results from [11] prevent us from giving any theory-based guarantees regarding how close the outcome of the algorithm is to an absolute minimal strongly admissible set, we will instead assess the performance of the algorithm using a wide range of benchmark examples.
The remaining part of the current paper is structured as follows. First, in Section 2 we give a brief overview of the formal concepts used in the current paper, including that of a strongly admissible set and a strongly admissible labelling. In Section 3 we then proceed to provide the proposed algorithm, including the associated proofs of correctness. Then, in Section 4 we assess the performance of our approach, and compare it with the results yielded by the approach in [11] both in terms of outcome and runtime. We round off with a discussion of our findings in Section 5.
2.Preliminaries
In the current section, we briefly restate some of the basic concepts in formal argumentation theory, including strong admissibility. For current purposes, we restrict ourselves to finite argumentation frameworks.
Definition 1.
An argumentation framework is a pair
As for notation, we use lower case letters at the end of the alphabet (such as x, y and z) to denote variables containing arguments, upper case letters at the end of the alphabet (such as X, Y and Z) to denote program variables containing arguments, and upper case letters at the start of the alphabet (such as A, B and C) to denote concrete instances of arguments.
When it comes to defining argumentation semantics, one can distinguish the extension approach and the labelling approach [5]. We start with the extensions approach.
Definition 2.
Let
Definition 3.
Let
an admissible set iff
a complete extension iff
a grounded extension iff
a preferred extension iff
As mentioned in the introduction, the concept of strong admissibility was originally introduced by Baroni and Giacomin [1]. For current purposes we will apply the equivalent definition of Caminada [3,6].
Definition 4.
Let
Fig. 1.
An example of an argumentation framework.
As an example (taken from [6]), in the argumentation framework of Figure 1 the strongly admissible sets are ∅,
It can be shown that each strongly admissible set is conflict-free and admissible [6]. The strongly admissible sets form a lattice (w.r.t. ⊆), of which the empty set is the bottom element and the grounded extension is the top element [6].
The above definitions essentially follow the extension based approach as described in [10]. It is also possible to define the key argumentation concepts in terms of argument labellings [2,8].
Definition 5.
Let
if
if
if
As a labelling is essentially a function, we sometimes write it as a set of pairs. Also, if
Definition 6
Definition 6([9]).
Let
Definition 7.
Let
the grounded labelling iff
a preferred labelling iff
We refer to the size of a labelling
The next step is to define a strongly admissible labelling. In order to do so, we need the concept of a min-max numbering [6].
Definition 8.
Let
if
if
It has been proved that every admissible labelling has a unique min-max numbering [6]. A strongly admissible labelling can then be defined as follows [6].
Definition 9.
A strongly admissible labelling is an admissible labelling whose min-max numbering yields natural numbers only (so no argument is numbered ∞).
As an example (taken from [6]), consider again the argumentation framework of Figure 1. Here, the admissible labelling
It has been shown that the strongly admissible labellings form a lattice (w.r.t. ⊑), of which the all-
The relationship between extensions and labellings has been well-studied [2,8]. A common way to relate extensions to labellings is through the functions
3.The algorithms
In the current section, we present an algorithmic approach for computing a relatively small33 strongly admissible labelling. For this, we provide three different algorithms. The first algorithm (Algorithm 1) basically constructs a strongly admissible labelling bottom-up, starting with the arguments that have no attackers and continuing until the main argument (the argument for which one want to show membership of a strongly admissible set) is labelled
Algorithm 1
Construct a strongly admissible labelling that labels A
3.1.Algorithm 1
The basic idea of Algorithm 1 is to start constructing the grounded labelling bottom-up, until we reach the main argument (that is, until we reach the argument that we are trying to construct a strongly admissible labelling for; this argument should hence be labelled
Obtaining the min-max numbering is important, as it can be used to show that the obtained admissible labelling is indeed strongly admissible, through the absence of ∞ in its min-max numbering. Additionally, the min-max numbering is also needed for some of the applications of strong admissibility, in particular the Grounded Discussion Game [4] where the combination of a strongly admissible labelling and its associated min-max numbering serves as a roadmap for obtaining a winning strategy.
Instead of first computing the strongly admissible labelling and then proceeding to compute the min-max numbering, we want to compute both the strongly admissible labelling and the min-max numbering in just a single pass, in order to achieve the best performance.
To see how the algorithm works, consider again the argumentation framework of Figure 1. Let C be the main argument. At the start of the first iteration of the while loop (line 21) it holds that
We now proceed to prove some of the formal properties of the algorithm. The first property to be proved is termination.
Theorem 1.
Let
Proof.
As for the first loop (the for loop of lines 9–18) we observe that it terminates as the number of arguments in Ar is finite.
As for the second loop (the while loop of lines 21–37) we first observe that no argument can be added to unproc_in more than once (that is, once an argument has been added to unproc_in, it can never be added again). This is because for an argument to be added, it has to be labelled
Next, we need to show that the algorithm is correct. That is, we need to show that the algorithm yields a strongly admissible labelling
Lemma 2.
Let
Proof.
Consider the value of
(1) if
Suppose
(a) x was labelled
(b) x was labelled
(2) if
Suppose
The next lemma presents an intermediary result that will be needed further on in the proofs.
Lemma 3.
Let
Proof.
We prove this by induction over the number of arguments that are added to
BASIS (n = 0) | Suppose the while loop has not yet added any arguments to |
STEP | Suppose that at a particular point, the while loop has added n (
|
Algorithm 1 (especially line 22 and line 30) implements a FIFO queue for the
As an example, consider again the argumentation framework of Figure 1. Let F be the main argument. Now suppose that
One of the conditions of a min-max numbering is that the min-max number of an
The key to understanding how Algorithm 1 manages to always yield the correct min-max numbering is that the
To make sure that arguments are processed in the order of their min-max numbers, we need to apply a FIFO queue instead of the set that was applied by [13]. The following two lemmas (Lemma 4 and Lemma 5) state that the
Lemma 4.
Let
Proof.
We first observe that this property is satisfied just after finishing the for loop of lines 9–18. This is because the for loop makes sure that for each argument x,
BASIS (n = 0) | Suppose no arguments have yet been added to |
STEP (n + 1) | Suppose the property holds after n arguments have been added to
|
Lemma 5.
Let
Proof.
This follows directly from Lemma 4, together with the fact that additions to and removals from
We proceed to show the correctness of
Lemma 6.
Let
Proof.
We prove this by induction over the number of loop iterations.
As for the basis of the induction (n = 1), let us consider the first loop iteration. This is just after the for loop of lines 9–18 has finished. We need to prove that
(1) if
Suppose
(2) if
This is trivially the case, as at the end of the for loop (lines 9–18) no argument is labelled out.
As for the induction step, suppose that at the start of a particular loop iteration,
(1) if
We distinguish two cases:
(a) x was already labelled
(b) x became labelled
As we now observed thatIn that case, from the fact that
As X was removed from
(2) if
We distinguish two cases:
(a) x was already labelled
In both cases, we obtain thatIn that case, it directly follows that
In that case, it follows that
(b) x became labelled
In order for a labelling to be strongly admissible, its min-max numbering has to contain natural numbers only (no ∞). We therefore proceed to show the absence of ∞ in an inductive way. That is, we show the absence of ∞ at the start of each iteration of the while loop. We then later need to do a bit of additional work to show the absence of ∞ at the moment we jump out of the while loop using the return statement.
Lemma 7.
Let
Proof.
We prove this by induction over the number of iterations of the while loop at lines 21–37.
As for the basis of induction(n = 1), let us consider the first loop iteration. This is just after the for loop at lines 9–18 has finished. We need to prove that for each
(1) if
Let x be labelled
(2) if
This is trivially the case as the end of the for loop at lines 9–18, no argument is labelled
(1) if
We distinguish two cases:
x was already labelled
x became labelled
(2) if
We distinguish two cases:
x was already labelled
x became labelled
Although most of our results so far are about the algorithm itself, we also need an additional theoretical property of grounded semantics, stated in the following lemma.
Lemma 8.
Let
Proof.
First of all, it has been observed that the grounded labelling is both strongly admissible [6] and complete (Definition 7). We proceed to prove that it is also the only argument labelling that is both strongly admissible and complete. Let
If we would not finish the algorithm after hitting the main argument and instead continued to execute the algorithm until
Lemma 9.
If in Algorithm 1 one would comment out line 16 and line 33 and add the following line (line 41) at the end:
return
then the output of the thus modified algorithm would be the grounded labelling
Proof.
We first observe that
We proceed to show that
(1) if
Suppose
(2) if
Suppose
if
From the thus obtained facts that
Using the above lemmas, we now proceed to show the correctness of the algorithm.
Theorem 10.
Let
Proof.
We first observe that as A is in the grounded extension of
(1)
This follows directly from Lemma 2.
(2)
To see that this is the case, we distinguish two cases:
(a) The return statement that was triggered was the one at line 16. In that case,
(b) The return statement that was triggered was the one at line 33. In that case, Lemma 6 tells us that the value of
(3)
To see that this is the case, we distinguish two cases:
(a) The return statement that was triggered is the one at line 16. In that case, for each
(b) The return statement that was triggered is the one at line 33. In that case, Lemma 7 tells us that at the start of the last iteration of the while loop,
It turns out that the algorithm runs in polynomical time (more specific, in cubic time).
Theorem 11.
Let
Proof.
Let n be the number of arguments in
3.2.Algorithm 2
The basic idea of Algorithm 2 is to prune the part of the strongly admissible labelling that is not needed, by identifying the part that actually is needed. This is done in a top-down way, starting by including the main argument (which is labelled
Algorithm 2
Prune a strongly admissible labelling that labels A
To see how the algorithm works, consider again the argumentation framework of Figure 1. Let C be the main argument. Suppose the input labelling
We now proceed to prove some of the formal properties of the algorithm. The first property to be proved is termination.
Theorem 12.
Let
Proof.
At the while loop of lines 12–25, we observe that only a finite number of arguments can be added to unproc_in. This is because there are only a finite number of arguments in the argumentation framework, and because no argument can be added to unproc_in more than once. The latter can be seen as follows. Following line 18, only arguments that are not already labelled
Next, we prove that the labelling that is yielded by the algorithm is smaller or equal to the labelling the algorithm started with.
Theorem 13.
Let
Proof.
In order to prove that
(1)
Let x be an arbitrary argument that is labelled
x became labelled
x became labelled
(2)
Let y be an arbitrary
Next, we prove that the output of the algorithm is at least admissible (the fact that it is also strongly admissible is proved further on).
Theorem 14.
Let
Proof.
The fact that
(1) if
Let x be an arbitrary
(2) if
Let x be an arbitrary
Next, we prove that the algorithm does not change the min-max values of the arguments it labels
Lemma 15.
Let
Next, we prove that the output numbering is actually the correct min-max numbering of the output labelling.
Theorem 16.
Let
Proof.
Since
(1) if
Let x be an arbitrary
(2) if
Let x be an arbitrary
We are now ready to state one of the main results of the current section: the output labelling is strongly admissible.
Theorem 17.
Let
Proof.
In order to show that
It turns out that the algorithm runs in polynomial time (more specific, in cubic time).
Theorem 18.
Let
Proof.
Let n be the number of arguments in
3.3.Algorithm 3
The idea of Algorithm 3 is to combine Algorithm 1 and Algorithm 2, by running them in sequence. That is, the output of Algorithm 1 is used as input for Algorithm 2.
Algorithm 3
Construct a relatively small strongly admissible labelling that labels A
As an example, consider again the argumentation framework of Figure 1. Let C be the main argument. Running Algorithm 1 yields a labelling
Given the properties of Algorithm 1 and Algorithm 2, we can prove that Algorithm 3 terminates, correctly computes a strongly admissible labelling and its associated min-max numbering, and runs in polynomial time (more specific, in cubic time).
Theorem 19.
Let
Theorem 20.
Let
Theorem 21.
Let
4.Empirical results
Now that the correctness of our algorithms has been proved and their computational complexity has been stated, the next step is to empirically evaluate their performance. For this, we compare both their runtime and output with that of other computational approaches.
4.1.Minimality
Although Algorithm 3 aims to find a relatively small strongly admissible labelling, it is not guaranteed to find an absolute smallest. This is because the problem of finding the absolute smallest admissible labelling is coNP-complete, whereas Algorithm 3 is polynomial (Theorem 21). In essence, we have given up absolute minimality in order to achieve tractability. The question, therefore, is how much we had to compromise on minimality. That is, how does the outcome of Algorithm 3 compare with what would have been an absolute minimal outcome? In order to make the comparison, we apply the ASPARTIX ASP encodings of [11] to determine the absolute minimal strongly admissible labelling.
Apart from comparing the strongly admissible labelling yielded by our algorithm with an absolute minimal strongly admissible labelling, we also compare it with the absolute maximal strongly admissible labelling. That is, we compare it with the grounded labelling. The reason for doing so is that the grounded semantics algorithms (e.g. [12,13]) are to the best of our knowledge currently the only polynomial algorithms for computing a strongly admissible labelling (in particular, for the maximal strongly admissible labelling) that have been stated in the literature. As Algorithm 3 is also polynomial (Theorem 21) this raises the question of how much improvement is made regarding minimality.
For queries, we considered the argumentation frameworks in the benchmark sets of ICCMA’17, ICCMA’19 and ICCMA’21.55 For each of the argumentation frameworks we generated a query argument that is in the grounded extension (provided the grounded extension is not empty). We used the queried argument when one was provided by the competition (for instance, when considering the benchmark examples of the Admbuster class, we took ‘a’ to be the queried argument as this was suggested by the authors of this class). After considering 994 argumentation frameworks, we found that 277 argumentation frameworks yielded a grounded extension that is not empty (meaning they could used for current purposes).
We conducted our experiments on a MacBook Pro 2020 with 8 GB of memory and an Intel Core i5 processor. To run the ASPARTIX system we used clingo v5.6.2. We set a timeout limit of 1000 seconds and a memory limit of 8 GB per query.
For each of the selected benchmark examples, we have assessed the following:
(1) the size of the grounded labelling (determined using the modified version of Algorithm 1 as described in Lemma 9)
(2) the size of the strongly admissible labelling yielded by Algorithm 1
(3) the size of the strongly admissible labelling yielded by Algorithm 3
(4) the size of the absolute minimal strongly admissible labelling (yielded by the approach of [11])
We start our analysis with comparing the output of Algorithm 1 and Algorithm 3 with the grounded labelling regarding the size of the respective labellings. We found that the size of the strongly admissible labelling yielded by Algorithm 1 tends to be smaller than the size of the grounded labelling. More specifically, the strongly admissible labelling yielded by Algorithm 1 is smaller than the size of the grounded labelling in 63% of the 277 examples we tested for. In the remaining 37% of the examples, their sizes are the same.
Figure 2 provides a more detailed overview of our findings, in the form of a bar graph. The rightmost bar represents the 37% of the cases where the output of Algorithm 1 has the same size as the grounded labelling (that is, where the size of the output of Algorithm 1 is 100% of the size of the grounded labelling). The bars on the left of this are for the cases where the size of the output of Algorithm 1 is less than the size of the grounded labelling. For instance, it was found that in 10% of the examples, the size of output of Algorithm 1 is 80% to 89% of the size of the grounded labelling. On average, we found that the size of the output of Algorithm 1 is 76% of the size of the grounded labelling.
As for Algorithm 3, we found an even bigger improvement in the size of it’s output labelling compared to the grounded labelling. More specifically, the size of the strongly admissible labelling yielded by Algorithm 3 is smaller than the grounded labelling in 88% of the 277 examples we tested for. Figure 3 provides a more detailed overview of our findings in a similar way as we previously did for Algorithm 1. On average, we found that the output of Algorithm 3 has a size that is 25% of the size of the grounded labelling.
Fig. 4.
The size of output of Algorithm 1 compared to the output Algorithm 3 (as a percentage of the size of the grounded labelling).
Apart from comparing Algorithm 1 and Algorithm 3 with the grounded labelling, it can also be insightful to compare the two algorithms with each other. In Figure 4, each dot represents one of the 277 examples.66 The horizontal axis represents the size of the output of Algorithm 1, as a percentage of the size of the grounded labelling. The vertical axis represents the size of the output of Algorithm 3 as a percentage of the size of the grounded labelling. For easy reference, we have included a dashed line indicating the situation where the output of Algorithm 1 has the same size as the output of Algorithm 3. Any dots below the dashed line represent the cases where Algorithm 3 outperforms Algorithm 1, in that it yields a smaller strongly admissible labelling. Any dots above the dashed line represents the cases where Algorithm 3 under performs Algorithm 1 in that it yields a bigger strongly admissible labelling. Unsurprisingly, there are no such cases as Theorem 22 states that the output of Algorithm 3 cannot be bigger than the output of Algorithm 1. We found that for 95% of the examples, Algorithm 3 produces a smaller labelling than Algorithm 1. Moreover, we found that on average, the output of Algorithm 3 is 32% smaller than output of Algorithm 1.
Fig. 5.
The size of output of Algorithm 3 compared to a smallest strongly admissible labelling (as a percentage of the size of the grounded labelling).
The next question is how the output of our best performing algorithm (Algorithm 3) compares with what would have been the ideal output. That is, we compare the size of the output of Algorithm 3 with the size of a minimal strongly admissible labelling for the main argument, as computed using the ASPARTIX encodings of [11]. The results are shown in Figure 5.
We found that in 91% of the 277 examples, the output of Algorithm 3 is of the same size as the smallest strongly admissible labelling for the output of the main argument. For the other 9% of the examples, the output of Algorithm 3 has a bigger size. On average, we found that the output of Algorithm 3 is 3% bigger than the smallest strongly admissible labelling for the main argument. Figure 6, provides a more detailed overview of how much bigger the output of Algorithm 3 is compared to the smallest strongly admissible labelling for the main argument.
4.2.Runtime
The next thing to study is how the runtime of our algorithms compares with the runtime of some of the existing computational approaches. In particular, we compare the runtime of Algorithm 1 and Algorithm 3 with the runtime of the ASPARTIX-based approach of [11].
Fig. 7.
The runtime of Algorithm 3 compared to the runtime of computing the grounded labelling using Algorithm 3 of [13].
![The runtime of Algorithm 3 compared to the runtime of computing the grounded labelling using Algorithm 3 of [13].](https://content.iospress.com:443/media/aac-prepress/aac--1--1-aac230012/aac--1-aac230012-g010.jpg)
We first compare the runtime of Algorithm 3 to the runtime of the modified version of Algorithm 3 of [13] for computing the grounded labelling. It turns out that the runtimes of these algorithms are very similar. On average, Algorithm 3 of [13] took 0.02 seconds (3%) more than Algorithm 3 to solve the test instances. These runtime results of Algorithm 3 and Algorithm 3 of [13] are shown in Figure 7.
Fig. 8.
The runtime of computing a smallest admissible labelling using the ASPARTIX encodings compared with the runtime of Algorithm 3.
The next question is how does the runtime of computing Algorithm 3 compare to the runtime of the ASPARTIX encoding for minimal strongly admissibility. It was observed that the runtime of ASPARTIX encoding is significantly longer than the runtime of Algorithm 3. A detailed overview of the difference in runtimes of Algorithm 3 and the ASPARTIX encoding on minimal strong admissibility is shown in Figure 8. On average, the ASPARTIX framework took 12.5 seconds (907%) more than Algorithm 3 to solve the test instances.
5.Discussion
In the current paper, we provided two algorithms (Algorithm 1 and Algorithm 3) for computing a relatively small strongly admissible labelling for an argument that is in the grounded extension. We proved that both algorithms are correct in the sense that each of them returns a strongly admissible labelling (with associated min-max numbering) that labels the main argument
The next question we examined is how small the output of Algorithm 1 and Algorithm 3 is compared to the smallest strongly admissible for the main argument. Unfortunately, previous findings make it difficult to provide formal theoretical results on this. This is because the c-approximation problem for strong admissibility is NP-hard, meaning that a polynomial algorithm (such as Algorithm 1 and Algorithm 3) cannot provide any guarantees of yielding a result within a fixed parameter c from the size of the absolute smallest strongly admissible labelling for the main argument.
Hence, instead of developing theoretical results, we decided to approach the issue of minimality in an empirical way, using a number of experiments. These experiments were based on the benchmark examples that were submitted to ICCMA’17, ICCMA’19 and ICCMA’21. We compared the output of Algorithm 1 and Algorithm 3 with both the biggest and the smallest strongly admissible set for the main argument (the biggest was computed using Algorithm 3 described in [13] and the smallest was computed using the ASPARTIX based approach on computing minimal strong admissibility in [11]). Overall, we found that Algorithm 3 yields results that are only marginally bigger than the smallest strongly admissible labelling, with a run-time that is a fraction of the time that would be required to find this smallest strongly admissible labelling. The outputs of both algorithms return a strongly admissible labelling that is significantly smaller than the biggest strongly admissible labelling (the grounded labelling), with the output of Algorithm 3 on average being only 25% of the size of the biggest strongly admissible labelling.
Although our Algorithm 3 tends to yield good results in most cases (obtaining an absolute smallest strongly admissible labelling in 91% of the examples we tested for) there are some argumentation frameworks where it will not perform well. An example of such an argumentation framework is shown in Figure 9.
Fig. 9.
An example of an argumentation framework where Algorithm 3 yields a strongly admissible labelling that is not minimal.
For the argumentation framework of Figure 9, Algorithm 3 will yield the strongly admissible labelling
To understand how such a suboptimal result was produced, it is important to realise that Algoritm 2, when choosing an
Algorithm 1 requires that the main argument (argument A) is in the grounded extension. At first sight, this would seem to require some additional computation before our algorithms are run, in order to determine whether this is indeed the case. However, it would not be difficult to modify Algorithm 1 to provide an answer to this as well.88 This could be done by not only returning a labelling and its associated min-max numbering, but by also returning a flag that indicates whether argument A is actually part of the grounded extension. This flag would be set to true if
Algorithm 2 could to some extent be optimised by adding an extra condition to line 15, so that the for-loop only runs for attackers that are not yet labelled
The research of the current paper fits into our long-term research agenda of using argumentation theory to provide explainable formal inference. In our view, it is not enough for a knowledge-based system to simply provide an answer regarding what to do or what to believe. There should also be a way for this answer to be explained. One way of doing so is by means of (formal) discussion. Here, the idea is that the knowledge-based system should provide the argument that is at the basis of its advice. The user is then allowed to raise objections (counterarguments) which the system then replies to (using counter-counter-arguments), etc. In general, we would like such a discussion to be (1) sound and complete for the underlying argumentation semantics, (2) not be unnecessarily long, and (3) be close enough to human discussion to be perceived as natural and convincing
As for point (1), sound and complete discussion games have been identified for grounded, preferred, stable and ideal semantics [4]. As for point (2), this is what we studied in the current paper, as well as in [3,6]. As for point (3), this is something that we are aiming to report on in future work.
For future research, it is possible to conduct a similar sort of analysis (as in this paper) on minimal admissible labellings. It was reported obtaining an absolute minimal admissible labelling for a main argument is also of coNP-complete complexity [3,6] therefore, it would be interesting to look into developing an algorithm that generates a small admissible labelling in polynomial time complexity. Similarly, it would also be interesting to look at the complexity and empirical results on generating minimal ideal sets.
Notes
1 Theorem 2 of [11] states that “Computing a c-approximation for the minimal size of a strongly admissible set for a given argument is NP-hard for every
2 Theorem 2 of [7] assumes that it has already been verified that the labelling in question is strongly admissible and that the only thing that still needs to be verified is that it is also minimal strongly admissible. However, the problem of verifying whether a set of arguments is strongly admissible is polynomial [6] (which carries over also to the problem of verifying whether an argument labelling is strongly admissible) including this check does not affect the co-NP-completeness of the overall problem of verifying minimal strong admissibility.
3 Small with respect to the size of the labelling.
4 The reader may have noticed that this was the output of Algorithm 1 for the example that was given in Section 3.1.
6 Please be aware that some of the dots overlap each other.
7 A small performance improvement could perhaps be made by altering line 19 of Algorithm 2. The current algorithm chooses argument Z in a non-deterministic way if there is more than one
8 We thank one of the anonymous reviewers for pointing this out.
9 We thank one of the anonymous reviewers for pointing this out.
References
[1] | P. Baroni and M. Giacomin, On principle-based evaluation of extension-based argumentation semantics, Artificial Intelligence 171: (10–15) ((2007) ), 675–700. doi:10.1016/j.artint.2007.04.004. |
[2] | M.W.A. Caminada, On the issue of reinstatement in argumentation, in: Logics in Artificial Intelligence; 10th European Conference, JELIA 2006, M. Fischer, W. van der Hoek, B. Konev and A. Lisitsa, eds, Springer, (2006) , pp. 111–123, LNAI 4160. |
[3] | M.W.A. Caminada, Strong admissibility revisited, in: Computational Models of Argument, S. Parsons, N. Oren, C. Reed and F. Cerutti, eds, Proceedings of COMMA 2014, IOS Press, (2014) , pp. 197–208. |
[4] | M.W.A. Caminada, A discussion game for grounded semantics, in: Theory and Applications of Formal Argumentation (Proceedings TAFA 2015), E. Black, S. Modgil and N. Oren, eds, Springer, (2015) , pp. 59–73. doi:10.1007/978-3-319-28460-6_4. |
[5] | M.W.A. Caminada, P. Baroni and M. Giacomin, Abstract argumentation frameworks and their semantics, in: Handbook of Formal Argumentation, Vol. 1: , College Publications, (2018) . |
[6] | M.W.A. Caminada and P.E. Dunne, Strong admissibility revisited: Theory and applications, Argument & Computation 10: ((2019) ), 277–300. doi:10.3233/AAC-190463. |
[7] | M.W.A. Caminada and P.E. Dunne, Minimal strong admissibility: A complexity analysis, in: Proceedings of COMMA 2020, H. Prakken, S. Bistarelli, F. Santini and C. Taticchi, eds, IOS Press, (2020) , pp. 135–146. |
[8] | M.W.A. Caminada and D.M. Gabbay, A logical account of formal argumentation, Studia Logica 93: (2–3) ((2009) ), 109–145, Special issue: new ideas in argumentation theory. doi:10.1007/s11225-009-9218-x. |
[9] | M.W.A. Caminada and G. Pigozzi, On judgment aggregation in abstract argumentation, Autonomous Agents and Multi-Agent Systems 22: (1) ((2011) ), 64–102. doi:10.1007/s10458-009-9116-7. |
[10] | P.M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence 77: ((1995) ), 321–357. doi:10.1016/0004-3702(94)00041-X. |
[11] | W. Dvořák and J. Wallner, Computing strongly admissible sets, in: Proceedings of COMMA 2020, H. Prakken, S. Bistarelli, F. Santini and C. Taticchi, eds, IOS Press, (2020) , pp. 179–190. |
[12] | S. Modgil and M.W.A. Caminada, Proof theories and algorithms for abstract argumentation frameworks, in: Argumentation in Artificial Intelligence, I. Rahwan and G.R. Simari, eds, Springer, (2009) , pp. 105–129. doi:10.1007/978-0-387-98197-0_6. |
[13] | S. Nofal, K. Atkinson and P.E. Dunne, Computing grounded extensions of abstract argumentation frameworks, The Computer Journal 64: ((2021) ), 54–63. doi:10.1093/comjnl/bxz138. |
