Strong Admissibility, a Tractable Algorithmic Approach MartinCaminada caminadam@cardiff.ac.uk School of Computer Science & Informatics Cardiff University SriHarikrishnan harikrishnans@cardiff.ac.uk School of Computer Science & Informatics Cardiff University
2022 Cardiff Wales United Kingdom
Strong Admissibility, a Tractable Algorithmic Approach 1613-0073 ECEA203D400C6FA35274039561227BD8 GROBID - A machine learning software for extracting information from scholarly documents strong admissibility, polynomial algorithms

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.
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 [2,3] who further developed strong admissibility in both its set and labelling form. 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 explanation that is minimal. That is, given an argument 𝐴 that is in the grounded extension, how can one obtain:

(1) a strongly admissible set that contains 𝐴, of which the number of arguments is minimal among all strongly admissible sets containing 𝐴, and (2) a strongly admissible labelling that labels 𝐴 in, of which the number of in and out labelled arguments (its size, cf. [5]) is minimal among all strongly admissible labellings that label 𝐴 in.

It has been found that the verification problem of ( 1) is NP-complete [6] whereas the verification problem of ( 2) is co-NP-complete [5]. Moreover, it has also been observed that even computing a 𝑐-approximation for the minimum size of a strongly admissible set for a given argument is NP-hard for every 𝑐 β‰₯ 1 [6]. This is in sharp contrast with the complexity of the general verification problem of strong admissibility (i.e. verifying whether a set/labelling is strongly admissible, without the constraint that it also has to be minimal) which has been found to be polynomial [3].

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 an 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. The former approach is taken in [6]. The latter approach is taken in our current paper. As the complexity results from [6] prevent us from giving any theory-based guarantees regarding how close the outcome of the algorithm is to an absolute minimal strongly admissible labelling, we will instead assess the performance of the algorithm using a wide range of benchmark examples.

Preliminaries

In the current section, we briefly restate some of the key concepts of formal argumentation theory, including strong admissibility. For current purposes, we restrict ourselves to finite argumentation frameworks.

Definition 1.

An argumentation framework is a pair (Ar , att) where Ar is a finite set of arguments and att is a binary relation on Ar . For any π‘₯, 𝑦 ∈ Ar we say that π‘₯ attacks 𝑦 iff (π‘₯, 𝑦) ∈ att.

If π‘₯ is an argument, we write π‘₯ + for the arguments attacked by π‘₯ and π‘₯ βˆ’ for the arguments that attack π‘₯. As for notation, we use lower case letters at the end of the alphabet (such as π‘₯, 𝑦 and 𝑧) to denote variables containing arguments, upper case letters at the end of the alphabet (such as 𝑋, π‘Œ and 𝑍) to denote program variables containing arguments, and upper case letters at the start of the alphabet (such as 𝐴, 𝐡 and 𝐢) to denote concrete instances of arguments. For current purposes, we apply the labelling-based version of abstract argumentation theory, following [7,8]. Definition 2. Let (Ar , att) be an argumentation framework. An argument labelling is a function β„’π‘Žπ‘ : Ar β†’ {in, out, undec}. An argument labelling is called an admissible labelling iff for each π‘₯ ∈ Ar it holds that:

β€’ if β„’π‘Žπ‘(π‘₯) = in then for each 𝑦 that attacks π‘₯ it holds that β„’π‘Žπ‘(𝑦) = out β€’ if β„’π‘Žπ‘(π‘₯) = out then there exists a 𝑦 that attacks π‘₯ such that β„’π‘Žπ‘(𝑦) = in β„’π‘Žπ‘ is called a complete labelling iff it is an admissible labelling and for each π‘₯ ∈ Ar it also holds that:

β€’ if β„’π‘Žπ‘(π‘₯) = undec then there is a 𝑦 that attacks π‘₯ such that β„’π‘Žπ‘(𝑦) = undec, and for each 𝑦 that attacks π‘₯ such that β„’π‘Žπ‘(𝑦) ΜΈ = undec it holds that β„’π‘Žπ‘(𝑦) = out

As a labelling is a function, we sometimes write it as a set of pairs. Also, if β„’π‘Žπ‘ is a labelling, we write in(β„’π‘Žπ‘) for {π‘₯ ∈ Ar | β„’π‘Žπ‘(π‘₯) = in}, out(β„’π‘Žπ‘) for {π‘₯ ∈ Ar | β„’π‘Žπ‘(π‘₯) = out} and undec(β„’π‘Žπ‘) for {π‘₯ ∈ Ar | β„’π‘Žπ‘(π‘₯) = undec}. As a labelling is also a partition of the arguments into sets of in-labelled arguments, out-labelled arguments and undec-labelled arguments, we sometimes write it as a triplet (in(β„’π‘Žπ‘), out(β„’π‘Žπ‘), undec(β„’π‘Žπ‘)).

Definition 3 ([9]

). Let β„’π‘Žπ‘ and β„’π‘Žπ‘ β€² be argument labellings of argumentation framework (Ar , att). We say that β„’π‘Žπ‘ βŠ‘ β„’π‘Žπ‘ β€² iff in(β„’π‘Žπ‘) βŠ† in(β„’π‘Žπ‘ β€² ) and out(β„’π‘Žπ‘) βŠ† out(β„’π‘Žπ‘ β€² ). Definition 4. Let β„’π‘Žπ‘ be a complete labelling of argumentation framework (Ar , att). β„’π‘Žπ‘ is said to be the grounded labelling iff β„’π‘Žπ‘ is the (unique) smallest (w.r.t. βŠ‘) complete labelling.

We refer to the size of a labelling β„’π‘Žπ‘ as |in(β„’π‘Žπ‘)βˆͺout(β„’π‘Žπ‘)|. We observe that if β„’π‘Žπ‘ βŠ‘ β„’π‘Žπ‘ β€² then the size of β„’π‘Žπ‘ is smaller or equal to the size of β„’π‘Žπ‘ β€² , but not necessarily vice versa. In the remainder of the current paper, we use the terms smaller, bigger, minimal and maximal in relation to the size of the respective labellings, unless stated otherwise.

The next step is to define a strongly admissible labelling. In order to do so, we need the concept of a min-max numbering [3].1 Definition 5. Let β„’π‘Žπ‘ be an admissible labelling of argumentation framework (Ar , att). A min-max numbering is a total function β„³β„³ β„’π‘Žπ‘ : in(β„’π‘Žπ‘) βˆͺ out(β„’π‘Žπ‘) β†’ N βˆͺ {∞} such that for each π‘₯ ∈ in(β„’π‘Žπ‘) βˆͺ out(β„’π‘Žπ‘) it holds that:

β€’ if β„’π‘Žπ‘(π‘₯) = in then β„³β„³ β„’π‘Žπ‘ (π‘₯) = π‘šπ‘Žπ‘₯({β„³β„³ β„’π‘Žπ‘ (𝑦) | 𝑦 attacks π‘₯ and β„’π‘Žπ‘(𝑦) = out}) + 1 (with π‘šπ‘Žπ‘₯(βˆ…) defined as 0) β€’ if β„’π‘Žπ‘(π‘₯) = out then β„³β„³ β„’π‘Žπ‘ (π‘₯) = π‘šπ‘–π‘›({β„³β„³ β„’π‘Žπ‘ (𝑦) | 𝑦 attacks π‘₯ and β„’π‘Žπ‘(𝑦) = in}) + 1 (with π‘šπ‘–π‘›(βˆ…) defined as ∞) It has been proved that every admissible labelling has a unique min-max numbering [3]. A strongly admissible labelling can then be defined as follows [3]. Definition 6. A strongly admissible labelling is an admissible labelling whose min-max numbering yields natural numbers only (no argument is numbered ∞).

As an example (taken from [3]), consider the argumentation framework of Figure 1. Here, the admissible labelling β„’π‘Žπ‘ 1 = ({𝐴, 𝐢, 𝐹, 𝐺}, {𝐡, 𝐸, 𝐻}, {𝐷}) has min-max numbering {(𝐴 : 1), (𝐡 : 2), (𝐢 : 3), (𝐸 : 4), (𝐹 : 5), (𝐺 : ∞), (𝐻 : ∞)}, which means that it is not strongly admissible. The admissible labelling β„’π‘Žπ‘ 2 = ({𝐴, 𝐢, 𝐷, 𝐹 }, {𝐡, 𝐸}, {𝐺, 𝐻}) has min-max numbering {(𝐴 : 1), (𝐡 : 2), (𝐢 : 3), (𝐷 : 1), (𝐸 : 2), (𝐹 : 3)}, which means that it is strongly admissible.

It has been shown that the strongly admissible labellings form a lattice (w.r.t. βŠ‘) of which the all-undec labelling is the bottom element and the grounded labelling is the top element [3].

The Algorithms

In the current section, we present an algorithmic approach for computing a relatively small 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 construct the strongly admissible labelling, sometimes also referred to as the argument in question) is labelled in. The second algorithm (Algorithm 2) then takes the output of the first algorithm and tries to prune it. That is, it tries to identify only those in and out labelled arguments that are actually needed for the strongly admissible labelling. The third algorithm (Algorithm 3) then combines Algorithm 1 (which is used as the construction phase) and Algorithm 2 (which is used as the pruning phase). Overall, we assume that it has already been established that the main argument is in the grounded extension and that the aim is merely to find a (relatively small) explanation for this.

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 in). As such, the idea is to take an algorithm for computing the grounded labelling and modify it accordingly.

We have chosen the algorithm of [10] for this purpose, as it has been shown to run faster than some of its alternatives (such as [11]). We had to adjust this algorithm in two ways. First, as mentioned above, we want the algorithm to stop once it hits the main argument, instead of continuing to construct the entire grounded labelling. Second, we want it to compute not just the strongly admissible labelling itself, but also its associated min-max numbering.

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 ∞. 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, the idea is to compute both the strongly admissible labelling and the min-max numbering in just a single pass, in order to achieve the best runtime performance.

To see how the algorithm works, consider again the argumentation framework of Figure 1. Let 𝐢 be the main argument. At the start of the first iteration of the while loop (line Algorithm 1 Construct a strongly admissible labelling that labels 𝐴 in and its associated min-max numbering.

Input: An argumentation framework AF = (Ar , att), an argument 𝐴 ∈ Ar that is in the grounded extension of AF . Output: A strongly admissible labelling β„’π‘Žπ‘ where 𝐴 ∈ in(β„’π‘Žπ‘), the associated min-max numbering β„³β„³ β„’π‘Žπ‘ . let 𝑋 be the argument at the front of unproc_in 39: // If we get here, A is not in the grounded extension, 40: // so we may want to print an error message 21) it holds that β„’π‘Žπ‘ = ({𝐴, 𝐷}, βˆ…, {𝐡, 𝐢, 𝐸, 𝐹, 𝐺, 𝐻}), β„³β„³ β„’π‘Žπ‘ = {(𝐴 : 1), (𝐷 : 1)} and unproc_in = [𝐴, 𝐷]. At the first iteration of the while loop, the argument in front of unproc_in (𝐴) is selected (line 22). This then means that 𝐡 gets labelled out and 𝐢 gets labelled in. Hence, the algorithm hits the main argument (𝐢) at line 33 and terminates. This yields a labelling β„’π‘Žπ‘ = ({𝐴, 𝐢, 𝐷}, {𝐡}, {𝐸, 𝐹, 𝐺, 𝐻}) and associated min-max numbering β„³β„³ β„’π‘Žπ‘ = {(𝐴 : 1), (𝐡 : 2), (𝐢 : 3), (𝐷 : 1)}.

Algorithm 1 (especially lines 22 and 30) implements a FIFO queue for the in labelled arguments it processes. This is an important difference from the algorithm of [10], which uses a set for this purpose. Using a set will work fine if the aim is merely to compute a strongly admissible labelling (as is the case for [10] where the aim is to compute the grounded labelling). However, if the aim is also to compute the associated min-max numbering, having a set as the basic data structure could compromise the algorithm's correctness.

As an example, consider again the argumentation framework of Figure 1. Let 𝐹 be the main argument. Now suppose that unproc_in is a set instead of a queue. In that case, at the start of the first iteration of the while loop (line 21) it holds that β„’π‘Žπ‘ = ({𝐴, 𝐷}, βˆ…, {𝐡, 𝐢, 𝐸, 𝐹, 𝐺, 𝐻}), β„³β„³ β„’π‘Žπ‘ = {(𝐴 : 1), (𝐷 : 1)} and unproc_in = {𝐴, 𝐷}. At the first iteration of the while loop, an argument 𝑋 from unproc_in is selected (line 22). As a set has no order, it would be possible to select 𝐴 (so 𝑋 = 𝐴). This then means that 𝐡 gets labelled out and 𝐢 gets labelled in. Hence, at the end of the first iteration of the while loop (and therefore at the start of the second iteration of the while loop) it holds that β„’π‘Žπ‘ = ({𝐴, 𝐢, 𝐷}, {𝐡}, {𝐸, 𝐹, 𝐺, 𝐻}), β„³β„³ β„’π‘Žπ‘ = {(𝐴 : 1), (𝐡 : 2), (𝐢 : 3), (𝐷 : 1)} and unproc_in = {𝐢, 𝐷}. At the second iteration of the while loop, suppose 𝐢 is the selected argument (so 𝑋 = 𝐢). This means that 𝐸 gets labelled out and 𝐹 gets labelled in. Hence, at the moment the algorithm hits the main argument (𝐹 , at line 33) and terminates, it holds that β„’π‘Žπ‘ = ({𝐴, 𝐢, 𝐷, 𝐹 }, {𝐡, 𝐸}, {𝐺, 𝐻}) and β„³β„³ β„’π‘Žπ‘ = {(𝐴 : 1), (𝐡 : 2), (𝐢 : 3), (𝐷 : 1), (𝐸 : 4), (𝐹 : 5)}. Unfortunately β„³β„³ β„’π‘Žπ‘ is incorrect. This is because out labelled argument 𝐸 is numbered 4, whereas its two in labelled attackers 𝐢 and 𝐷 are numbered 3 and 1, respectively, so the correct min-max number of 𝐸 should be 2 instead of 4, which implies that the correct min-max number of 𝐹 should be 3 instead of 5.

One of the conditions of a min-max numbering is that the min-max number of an out labelled argument should be the minimal value of its in labelled attackers, plus 1. This seems to require that the min-max number of each in labelled attackers is already known, before being able to assign the min-max number of the out labelled argument. At the very least, it would seem that the min-max number of an out labelled argument needs to be recomputed each time the min-max number of one of its in labelled attackers becomes known. Yet, Algorithm 1 does none of this. It determines the min-max number of an out labelled argument as soon as the min-max number of its first in labelled attacker becomes known (line 26) without waiting for the min-max number of any other in labelled attacker to become available. In spite of this, Algorithm 1 still manages to always yield the correct min-max numbering.

The key to understanding how Algorithm 1 manages to do this is that the in labelled arguments are processed in the order of their min-max numbers. That is, once an in labelled attacker is identified, any subsequently identified in labelled attacker will have a min-max number greater or equal to the first one and will therefore not change the minimal value (in the sense of Definition 5, first bullet point). This avoids having to recalculate the min-max number of an out labelled attacker when more of its in labelled arguments become available, therefore speeding up the algorithm.

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 [10]. This FIFO queue is a key component of Algorithm 1, as the correctness of the algorithm critically depends on it. Overall, the correctness of the algorithm can be stated as follows. 2Theorem 1. Let AF = (Ar , att) be an argumentation framework and let 𝐴 be an argument in the grounded extension of AF . Let both AF and 𝐴 be given as input to Algorithm 1. Let β„’π‘Žπ‘ and β„³β„³ β„’π‘Žπ‘ be the output of the algorithm. It holds that β„’π‘Žπ‘ is a strongly admissible labelling that labels 𝐴 in and has β„³β„³ β„’π‘Žπ‘ as its min-max numbering.

It turns out that the algorithm runs in polynomial (cubic) time.

Theorem 2. Let AF = (Ar , att) be an argumentation framework and let 𝐴 be an argument in the grounded extension of AF . Let both AF and 𝐴 be given as input to Algorithm 1. Let β„’π‘Žπ‘ and β„³β„³ β„’π‘Žπ‘ be the output of the algorithm. It holds that Algorithm 1 computes β„’π‘Žπ‘ and β„³β„³ β„’π‘Žπ‘ in O(𝑛3 ) time

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 in), then including all its attackers (which are labelled out), for each of which a minimally numbered in labelled attacker is included, etc. The idea is to keep doing this until reaching the (in labelled) arguments that have no attackers. Each argument that has not been included by this process is unnecessary for the strongly admissible labelling and can be made undec, resulting in a labelling that is smaller or equal to the strongly admissible labelling one started with.

To see how the algorithm works, consider again the argumentation framework of Figure 1. Let 𝐢 be the main argument. Suppose the input labelling β„’π‘Žπ‘ 𝐼 is ({𝐴, 𝐢, 𝐷}, {𝐡}, {𝐸, 𝐹, 𝐺, 𝐻}) and its associated input labelling numbering β„³β„³ β„’π‘Žπ‘π‘‚ is {(𝐴 : 1), (𝐡 : 2), (𝐢 : 3), (𝐷 : 1)}. 3 At the start of the first iteration of the while loop, it holds that β„’π‘Žπ‘ 𝑂 = ({𝐢}, βˆ…, {𝐴, 𝐡, 𝐷, 𝐸, 𝐹, 𝐺, 𝐻}), β„³β„³ β„’π‘Žπ‘π‘‚ = {(𝐢 : 1)} and unproc_in = [𝐢]. The first iteration of the while loop then removes 𝐢 from unproc_in (line 14), labels its attacker 𝐡 out (line 16), numbers 𝐡 with 2 (line 17), adds 𝐴 to unproc_in (line 20), labels 𝐴 in (line 21) and numbers 𝐴 with 1 (line 22). The second iteration of the while loop then removes 𝐴 from unproc_in (line 14). However, as 𝐴 does not have any attackers, the for loop (lines 15-24) is skipped. As unproc_in is now empty, the while loop is finished and the algorithm terminates, with β„’π‘Žπ‘ 𝑂 = ({𝐴, 𝐢}, {𝐡}, {𝐷, 𝐸, 𝐹, 𝐺, 𝐻}) and β„³β„³ β„’π‘Žπ‘π‘‚ = {(𝐴 : 1), (𝐡 : 2), (𝐢 : 3)} being its results.

We now proceed to state some of the formal properties of the algorithm, the first property being correctness.

Algorithm 2 Prune a strongly admissible labelling that labels 𝐴 in and its associated min-max numbering.

Input: An argumentation framework AF = (Ar , att), an argument 𝐴 ∈ Ar that is in the grounded extension of AF , A strongly admissible labelling β„’π‘Žπ‘ 𝐼 where 𝐴 ∈ in(β„’π‘Žπ‘ 𝐼 ), the associated min-max numbering β„³β„³ β„’π‘Žπ‘πΌ .

Output: A strongly admissible labelling β„’π‘Žπ‘ 𝑂 βŠ‘ β„’π‘Žπ‘ 𝐼 where 𝐴 ∈ in(β„’π‘Žπ‘ 𝑂 ), the associated min-max numbering β„³β„³ β„’π‘Žπ‘π‘‚ . end for 25: end while Theorem 3. Let AF = (Ar , att) be an argumentation framework, 𝐴 be an argument in the grounded extension of AF , β„’π‘Žπ‘ 𝐼 be a strongly admissible labelling where 𝐴 is labelled in and β„³β„³ β„’π‘Žπ‘πΌ be the associated min-max numbering. Let AF , 𝐴, β„’π‘Žπ‘ 𝐼 and β„³β„³ β„’π‘Žπ‘πΌ be given as input to Algorithm 2. Let β„’π‘Žπ‘ 𝑂 and β„³β„³ β„’π‘Žπ‘π‘‚ be the output of Algorithm 2. It holds that β„’π‘Žπ‘ 𝑂 is a strongly admissible labelling that labels 𝐴 in and has β„³β„³ β„’π‘Žπ‘π‘‚ as its min-max numbering. Theorem 4. Let AF = (Ar , att) be an argumentation framework, 𝐴 be an argument in the grounded extension of AF , β„’π‘Žπ‘ 𝐼 be a strongly admissible labelling where 𝐴 is labelled in and β„³β„³ β„’π‘Žπ‘πΌ be the associated min-max numbering. Let AF , 𝐴, β„’π‘Žπ‘ 𝐼 and β„³β„³ β„’π‘Žπ‘πΌ be given as input to Algorithm 2. Let β„’π‘Žπ‘ 𝑂 and β„³β„³ β„’π‘Žπ‘π‘‚ be the output of Algorithm 2. It holds that β„’π‘Žπ‘ 𝑂 βŠ‘ β„’π‘Žπ‘ 𝐼 It turns out that the algorithm runs in polynomial (cubic) time.

Theorem 5. Let AF = (Ar , att) be an argumentation framework, 𝐴 be an argument in the grounded extension of AF , β„’π‘Žπ‘ 𝐼 be a strongly admissible labelling where 𝐴 is labelled in and β„³β„³ β„’π‘Žπ‘πΌ be the correct min-max numbering of β„’π‘Žπ‘ 𝐼 . Let AF , 𝐴, β„’π‘Žπ‘ 𝐼 and β„³β„³ β„’π‘Žπ‘πΌ be given as input to Algorithm 2. Let β„’π‘Žπ‘ 𝑂 and β„³β„³ β„’π‘Žπ‘π‘‚ be the output of Algorithm 2. It holds that Algorithm 2 computes β„’π‘Žπ‘ 𝑂 and β„³β„³ β„’π‘Žπ‘π‘‚ in O(𝑛) 3 time.

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 𝐴 in and its associated min-max numbering.

Input: An argumentation framework AF = (Ar , att), an argument 𝐴 ∈ Ar that is in the grounded extension of AF .

Output: A strongly admissible labelling β„’π‘Žπ‘ where 𝐴 ∈ in(β„’π‘Žπ‘), the associated min-max numbering β„³β„³ β„’π‘Žπ‘ . As an example, consider again the argumentation framework of Figure 1. Let 𝐢 be the main argument. Running Algorithm 1 yields a labelling ({𝐴, 𝐢, 𝐷}, {𝐡}, {𝐸, 𝐹, 𝐺, 𝐻}) with associated numbering {(𝐴 : 1), (𝐡 : 2), (𝐢 : 3), (𝐷 : 1)} (as explained in Section 3.1). Feeding this labelling and numbering into Algorithm 2 then yields an output labelling ({𝐴, 𝐢}, {𝐡}, {𝐷, 𝐸, 𝐹, 𝐺, 𝐻}) with associated output numbering {(𝐴 : 1), (𝐡 : 2), (𝐢 : 3)} (as explained in Section 3.2).

Given the properties of Algorithm 1 and Algorithm 2, we can prove that Algorithm 3 correctly computes a strongly admissible labelling and its associated min-max numbering, yields an output that is smaller or equal to the output of Algorithm 1, and runs in polynomial (cubic) time.

Theorem 6. Let AF = (Ar , att) be an argumentation framework and let 𝐴 be an argument in the grounded extension of AF . Let both AF and 𝐴 be given as input to Algorithm 3. Let β„’π‘Žπ‘ and β„³β„³ β„’π‘Žπ‘ be the output of the algorithm. It holds that β„’π‘Žπ‘ is a strongly admissible labelling that labels 𝐴 in and has β„³β„³ β„’π‘Žπ‘ as its min-max numbering.

Proof. This follows from Theorem 1 and Theorem 3. Theorem 7. Let AF = (Ar , att) be an argumentation framework, 𝐴 be an argument in the grounded extension of AF . Let AF and 𝐴 be given as input to Algorithm 1 and Algorithm 3. Let β„’π‘Žπ‘ 𝐼 and β„³β„³ β„’π‘Žπ‘πΌ be the output of Algorithm 1 and let β„’π‘Žπ‘ 3 and β„³β„³ β„’π‘Žπ‘3 be the output of Algorithm 3. It holds that β„’π‘Žπ‘ 3 βŠ‘ β„’π‘Žπ‘ 𝐼 Proof. This follows from Theorem 4, together with Theorem 1 and the way Algorithm 3 is defined (by successively applying Algorithm 1 and Algorithm 2) Theorem 8. Let AF = (Ar , att) be an argumentation framework and let 𝐴 be an argument in the grounded extension of AF . Let both AF and 𝐴 be given as input to Algorithm 3. Let β„’π‘Žπ‘ and β„³β„³ β„’π‘Žπ‘ be the output of the algorithm. It holds that Algorithm 3 computes β„’π‘Žπ‘ and β„³β„³ β„’π‘Žπ‘ in 𝑂(𝑛 3 ) time.

Proof. This follows from Theorem 2 and Theorem 5.

Empirical Results

Now that the formal properties of our algorithms have been stated, the next step is to empirically evaluate their performance. For this, we looked at the benchmark examples that have applied in ICCMA'17 and ICCMA'19, 4 of which we used the 277 example argumentation frameworks whose grounded extension is not empty. We implemented our algorithms in C++ and ran the performance tests on a MacBook Pro 2020 with 8GB of memory and an Intel Core i5 processor.

Compared to the grounded labelling, we found that Algorithm 1 yields an output that is smaller than the grounded labelling in 63% of the examples, with the average output size being 76% of the size of the grounded labelling. Algorithm 3 yields an output that is smaller than the grounded labelling in 88% of the examples, with the average output size being just 25% of the size of the grounded labelling. These findings are relevant as the only previously available polynomial algorithms for strong admissibility are those for computing the grounded extension/labelling (e.g. [10]).

Next, we compared the output of our best performing algorithm (Algorithm 3) for finding a small strongly admissible labelling with the size of an absolute minimal strongly admissible labelling for the argument in question, for which we used the ASPARTIX encodings of [6]. We found that in 91% of the examples, the output of Algorithm 3 is of the same size as an absolute minimal strongly admissible labelling for the argument in question, with the average output being just 3% bigger than the size of an absolute smallest strongly admissible labelling for the argument in question.

As for runtime, we first compared the runtime of our Algorithm 3 with the runtime of Algorithm 3 of [10] for computing the grounded labelling. 5 We found that the differences in runtime are minimal, with the former algorithm taking just 0.02 seconds (3%) longer than the latter algorithm. 6 Next, we compared the runtime of our Algorithm 3 with the runtime of the ASPARTIX encodings of [6] for computing an absolute minimal strongly admissible labelling. 7We found that the latter approach has a runtime that is 12.5 seconds (907%) longer than the former approach. That is, our Algorithm 3 is able to provide an answer in less than a tenth of the time it would have taken to compute an absolute minimal answer. A more detailed analysis of our results, including a pointer to the source code of our software, can be found in [12].

Discussion

In the current paper, we provided two polynomial algorithms (Algorithm 1 and Algorithm 3) for constructing a relatively small strongly admissible labelling and its associated min-max numbering, for a particular argument. The correctness and complexity of the algorithms has been stated in a formal way, with proofs available in [12].

The fact that the 𝑐-approximation problem for minimal strong admissibility is NP-complete for every 𝑐 β‰₯ 1 means that polynomial algorithms (such as ours) cannot give any formal guarantees of how close their output is to having the size of an absolute minimal strongly admissible labelling for the argument in question. As such, we had to rely on an empirical evaluation of this (using the benchmark examples of ICCMA'17 and ICCMA'19). Overall, our results indicate that the output of Algorithm 3 is only marginally larger (3%) than an absolute minimal strongly admissible labelling for the argument in question, while taking less than a tenth of the runtime that would be needed to compute such a minimal strongly admissible labelling.

As a strongly admissible labelling and its associated min-max numbering can serve as an explanation of membership of the grounded extension, our algorithms can be useful for obtaining, in a time-efficient way, an explanation that is not overly long. Such an explanation can then for instance be used as the basis for the argument-based discussion game of [4], where the combination of the strongly admissible labelling and its associated min-max numbering serves as a roadmap for selecting the moves to be played by the computer when reacting to the user's possible counterarguments [4].

In the current paper, we focussed on strong admissibility, but a similar development of algorithms and associated empirical analysis could be done as future research in the context of admissible labellings and ideal labellings, in order to obtain relatively small explanations for (credulous) preferred semantics and ideal semantics, which could be used in the respective discussion games for these semantics [13].

Figure 1 :Figure 1: An example of an argumentation framework.
23:remove 𝑋 from unproc_in 24: for each π‘Œ ∈ 𝑋 + with β„’π‘Žπ‘(π‘Œ ) ΜΈ = out do 25: β„’π‘Žπ‘(π‘Œ ) ← out 26: β„³β„³ β„’π‘Žπ‘ (π‘Œ ) ← β„³β„³ β„’π‘Žπ‘ (𝑋) + 1 27: for each 𝑍 ∈ π‘Œ + with β„’π‘Žπ‘(𝑍) = undec do 28: undec_pre(𝑍) ← undec_pre(𝑍) βˆ’ 1 29: if undec_pre(𝑍) = 0 then 30: add 𝑍 to the rear of unproc_in 31: β„’π‘Žπ‘(𝑍) ← in 32: β„³β„³ β„’π‘Žπ‘ (𝑍) ← β„³β„³ β„’π‘Žπ‘ (π‘Œ ) + 1 33: if 𝑍 = 𝐴 then return β„’π‘Žπ‘ and β„³β„³ β„’π‘Žπ‘ 34:
the rear of unproc_in 21: β„’π‘Žπ‘ 𝑂 (𝑍) ← in 22:β„³β„³ β„’π‘Žπ‘π‘‚ (𝑍) ← β„³β„³ β„’π‘Žπ‘πΌ (𝑍)
Ar β†’ {in, out, undec} 3: β„³β„³ β„’π‘Žπ‘ : in(β„’π‘Žπ‘) βˆͺ out(β„’π‘Žπ‘) β†’ N βˆͺ {∞} 4: undec_pre : Ar β†’ N 5: unproc_in : [𝑋 1 , ...𝑋 𝑛 ] (𝑋 𝑖 ∈ Ar for each 1 ≀ 𝑖 ≀ 𝑛, with 𝑛 β‰₯ 0) Next, we initialize and process the arguments that have no attackers 8: unproc_in ← [] // unproc_in becomes the empty list of arguments6:7: // 10:β„’π‘Žπ‘(𝑋) ← undec11:undec_pre(𝑋) ← |𝑋 βˆ’ |12:if undec_pre(𝑋) = 0 then13:add 𝑋 to the rear of unproc_in14:β„’π‘Žπ‘(𝑋) ← in15:end if18: end for19:20: // We proceed to process the arguments that do have attackers21: while unproc_in is not empty do22:
1: // We start with the type definitions 2: β„’π‘Žπ‘ : 9: for each 𝑋 ∈ Ar do β„³β„³ β„’π‘Žπ‘ (𝑋) ← 1 16: if 𝑋 = 𝐴 then return β„’π‘Žπ‘ and β„³β„³ β„’π‘Žπ‘ 17:
1: // We start with the type definitions 2: β„’π‘Žπ‘ 𝑂 : Ar β†’ {in, out, undec} 3: β„³β„³ β„’π‘Žπ‘π‘‚ : in(β„’π‘Žπ‘) βˆͺ out(β„’π‘Žπ‘) β†’ N βˆͺ {∞} 4: unproc_in : [𝑋 1 , ...𝑋 𝑛 ] (𝑋 𝑖 ∈ Ar for each 1 ≀ 𝑖 ≀ 𝑛) // list of arguments 5: // Initialize β„’π‘Žπ‘ 𝑂 and include the main argument 6: β„’π‘Žπ‘ 𝑂 ← (βˆ…, βˆ…, Ar ) // β„’π‘Žπ‘ 𝑂 becomes the all-undec labelling 7: unproc_in ← [𝐴] β„’π‘Žπ‘ 𝐼 ) attacker of π‘Œ that is also labelled in by πΏπ‘Žπ‘ 𝑂 then Let 𝑍 be a minimal (w.r.t β„³β„³ β„’π‘Žπ‘πΌ ) in labelled (w.r.t πΏπ‘Žπ‘ 𝐼 ) attacker of π‘Œ19:
8: β„’π‘Žπ‘ 𝑂 (𝐴) ← in 9: β„³β„³ β„’π‘Žπ‘π‘‚ (𝐴) ← β„³β„³ β„’π‘Žπ‘πΌ (𝐴) 10: 11: // Next, process the other arguments in a top-down way 12: while unproc_in is not empty do 13: let 𝑋 be the argument at the front of unproc_in 14: remove 𝑋 from unproc_in 15: for each attacker π‘Œ of 𝑋 do 16: β„’π‘Žπ‘ 𝑂 (π‘Œ ) ← out 17: β„³β„³ β„’π‘Žπ‘π‘‚ (π‘Œ ) ← β„³β„³ β„’π‘Žπ‘πΌ (π‘Œ ) 18:if there is no minimal (w.r.t β„³β„³ β„’π‘Žπ‘πΌ ) in labelled (w.r.t
Please notice that for the purpose of Definition 5, ∞ is defined such that βˆ€π‘₯ ∈ N : ∞+π‘₯ = ∞ and π‘šπ‘Žπ‘₯({π‘₯, ∞}) = ∞. Also, the condition that "β„’π‘Žπ‘(𝑦) = out" in the first point of Definition 5 is technically superfluous, but has been added for clarity. The formal proof of this result, as well as of some of the other results, had to be omitted due to a lack of space, but can be found in a separate technical report[12]. The reader may have noticed that this was the output of Algorithm 1 for the example that was given in Section 3.1. See http://argumentationcompetition.org/ We modified the latter algorithm to return the grounded labelling instead of the grounded extension. We also made minor corrections by removing some duplicate code. Please be aware, however, that Algorithm 3 of[10] does not yield the min-max numbering, whereas Algorithm 3 does. Please notice that the latter is currently the only implementation for minimal strong admissibility.
On principle-based evaluation of extension-based argumentation semantics PBaroni MGiacomin Artificial Intelligence 171 2007 Strong admissibility revisited MCaminada Computational Models of Argument; Proceedings of COMMA 2014 SParsons NOren CReed FCerutti IOS Press 2014 Strong admissibility revised: theory and applications MCaminada PDunne Argument & Computation 10 2019 A discussion game for grounded semantics MCaminada Theory and Applications of Formal Argumentation (proceedings TAFA 2015) EBlack SModgil NOren Springer 2015 Minimal strong admissibility: a complexity analysis MCaminada PDunne Proceedings of COMMA 2020 HPrakken SBistarelli FSantini CTaticchi COMMA 2020 IOS Press 2020 Computing strongly admissible sets WDvoΕ™Γ‘k JWallner Proceedings of COMMA 2020 HPrakken SBistarelli FSantini CTaticchi COMMA 2020 IOS Press 2020 On the issue of reinstatement in argumentation MCaminada Logics in Artificial Intelligence; 10th European Conference, JELIA 2006 MFischer WVan Der Hoek BKonev ALisitsa Springer 2006 4160 A logical account of formal argumentation MCaminada DGabbay Studia Logica 93 2009 Special issue: new ideas in argumentation theory On judgment aggregation in abstract argumentation MCaminada GPigozzi Autonomous Agents and Multi-Agent Systems 22 2011 Computing grounded extensions of abstract argumentation frameworks SNofal KAtkinson PDunne The Computer Journal 64 2021 Proof theories and algorithms for abstract argumentation frameworks SModgil MCaminada Argumentation in Artificial Intelligence IRahwan GSimari Springer 2009 Strong Admissibility, a Tractable Algorithmic Approach (proofs MCaminada SHarikrishnan 2022 Cardiff University Technical Report Argumentation semantics as formal discussion MCaminada Handbook of Formal Argumentation College Publications 2018 1