Characterizing strongly admissible sets

Abstract

The concept of strong admissibility plays an important role in dialectical proof procedures for grounded semantics allowing, as it does, concise proofs that an argument belongs to the grounded extension without having necessarily to construct this extension in full. One consequence of this property is that strong admissibility (in contrast to grounded semantics) ceases to be a unique status semantics. In fact it is straightforward to construct examples for which the number of distinct strongly admissible sets is exponential in the number of arguments. We are interested in characterizing properties of collections of strongly admissible sets in the sense that any system describing the strongly admissible sets of an argument framework must satisfy particular criteria. In terms of previous studies, our concern is the signature and with conditions ensuring realizability. The principal result is to demonstrate that a system of sets describes the strongly admissible sets of some framework if and only if that system has the property of being decomposable.

Keywords

Strong admissibility signature realizability argumentation semantics

1. Introduction

The formal model of abstract argumentation proposed in the watershed paper of Dung [8] has given rise not only to a coherent and consistent view of argumentation semantics but also to a uniform basis against which issues in algorithmic and computational complexity can be gauged. In addition to the set-theoretic semantics formulated by Dung, a number of alternative forms have been promoted. One of these, strong admissibility is the subject of the present article.

The concept of strong admissibility was first introduced in the work of Baroni and Giacomin [3] and has subsequently been studied by Caminada and Dunne [6,7]. Strong admissibility is especially useful for showing that a particular argument is part of the grounded extension. As the grounded extension is the (unique) biggest strongly admissible set, showing membership of any strongly admissible set is sufficient to prove that the argument is in the grounded extension.

In this paper our aim is to examine the nature of strong admissibility from the perspective of signature and realizability. These concepts for argumentation semantics were introduced and analyzed in detail in Dunne et al. [10,11], one concern of their study being to characterize those subsets of sets of n arguments for which there is some af, $H$ , whose solution sets under a given semantics are exactly the set described. A detailed overview of work on realizability may be found in the survey article of Baumann [4].

This paper is structured as follows. First, in Section 2 we present some formal preliminaries regarding abstract argumentation and strong admissibility. In Section 3 the technical condition underpinning our results is presented and then, in Section 4 we present a necessary condition for a system of sets to be the strongly admissible sets of some af. The characterization is completed in Section 5 wherein the necessary condition presented in Section 4 is shown to be also sufficient. Conclusions and further directions are presented in Section 6.

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. We note that the focus on finite structures is not imposed in Dung’s original work and some study of infinite frameworks has been carried out, e.g. on realizability by Baumann and Spanring [5], modelling and description of infinite systems in Baroni et al. [2].

Definition 1.
(Dung [8]) An argumentation framework is a pair $(X, A)$ where $X$ is a finite set of entities, called arguments, and $A$ a binary relation on $X$ . For any $p, q \in X$ we say that p attacks q if $⟨ p, q ⟩ \in A$ .
Definition 2.
Let $(X, A)$ be an argumentation framework, $x \in X$ and $S \subseteq X$ . We define ${x}^{+}$ as ${y \in X ∣ x attacks y}$ , ${x}^{-}$ as ${y \in X ∣ y attacks x}$ , $S^{+}$ as $⋃ {{x}^{+} ∣ x \in X}$ , and $S^{-}$ as $⋃ {{x}^{-} ∣ x \in X}$ . The set S is said to be conflict-free if $S \cap S^{+} = \emptyset$ . A set S is said to defend x iff ${x}^{-} \subseteq S^{+}$ . The characteristic function $F : 2^{X} \to 2^{X}$ is defined as $F (S) = {x ∣ S defends x}$ .
Definition 3.
Let $(X, A)$ be an argumentation framework. A subset S of $X$ is said to be:
an admissible set if S is conflict-free and $S \subseteq F (S)$ ;

a complete extension if S is conflict-free and $S = F (S)$ ;

a grounded extension if S is the smallest (w.r.t. ⊆) complete extension;

a preferred extension if S is a maximal (w.r.t. ⊆) complete extension.
We use the notation $cf$ for the collection of conflict-free sets and, similarly, $adm$ , $com$ , $gr$ and $pr$ respectively to denote the forms above so that, e.g. $adm (H)$ describes those subsets of arguments in $H$ that are admissible, i.e. $S \in adm (H)$ if and only if S is admissible.

It is well known (being illustrated in Dung’s original paper [8]) that for any af, $H$ , $\begin{matrix} pr (H) \subseteq adm (H) \subseteq cf (H) . \end{matrix}$ Furthermore while $com (H) \subseteq adm (H)$ (“every complete set is admissible”) the converse does not necessarily hold so that one may have admissible sets that are not complete.

The examples presented above are just a small selection of those approaches that have been studied. We refer the interested reader to the treatment of Baroni, Caminada and Giacomin [1] for a comprehensive overview. The concept of strong admissibility was first introduced by Baroni and Giacomin [3]. For current purposes we will, however, apply the equivalent definition of Caminada [6].
Definition 4.
Let $(X, A)$ be an argumentation framework. A subset S of $X$ is strongly admissible if every $x \in S$ is defended by some $T \subseteq S ∖ {x}$ , T being also strongly admissible.

It can be shown that each strongly admissible set is an admissible subset of the grounded extension [7].

To illustrate, consider the example in Fig. 1 from Caminada [6].

Fig. 1.
Example af.

We have $\begin{matrix} {\emptyset, {A}, {D}, {A, C}, {A, D}, {A, C, D}, {A, C, F}, {D, F}, {A, C, D, F}} \end{matrix}$ as the strongly admissible sets. The grounded extension of this framework being ${A, C, D, F}$ . Every strongly admissible set is a subset of ${A, C, D, F}$ . Notice that the sets $\begin{matrix} {{G}, {H}, {F}, {C, H}, {C, H, F}} \end{matrix}$ are all admissible, however none of these are strongly admissible.
3. Signatures and realizability

An arbitrary semantics, σ, describes a set of subsets of $X$ so that for an af, $H$ , $\begin{matrix} σ (H) = {S \subseteq X : S satisfies the criteria of σ} . \end{matrix}$ For example, with $σ = cf$ and $H = (X, A)$ , we have $\begin{matrix} cf (H) = {S \subseteq X : S^{+} \cap S = \emptyset} . \end{matrix}$

Definition 5.
The signature of a semantics σ, denoted $Σ_{σ}$ is $\begin{matrix} Σ_{σ} = {S \subseteq 2^{X} : \exists H with σ (H) = S} . \end{matrix}$

The counterpart to the concept of signature is that of being realizable.
Definition 6.
Let $S \subseteq 2^{X}$ , that is to say a set of subsets of $X$ . The set $S$ is said to be realizable with respect to a semantics σ if there is an af, $H = (Z, A)$ for which $X \subseteq Z$ and $σ (H) = S$ .

Notice that in this definition we allow arguments $z \in Z$ which are not acceptable with respect to the conditions specified by σ: so-called auxiliary arguments. The form whereby such additional arguments are not permitted is dubbed “compact realizability” and has been studied (together with divers other formulations) in Baumann [4].

With regard to these notions of signature and realizability the central question of interest, discussed in Dunne et al. [10,11] is the following:

For an argumentation semantics, σ, describe necessary and sufficient conditions, $Π : 2^{2^{X}} \to {⊤, ⊥}$ , under which,
For all afs $H$ , $Π (σ (H))$ holds. (signature)

For all $S \subseteq 2^{X}$ that satisfy $Π (S)$ , there is an af $H$ for which $σ (H) = S$ . (realizable)
In [11] characterization of such conditions are presented for (among others) $σ \in {adm, com, pr}$ , i.e. admissible, complete, and preferred semantics.

In the current work we consider the case of strong admissibility denoting the relevant semantics as $σ = str$ .

It turns out that we may identify some requirements for membership in $Σ_{s t r}$ from a number of properties already known from Baroni and Giacomin [3] and Caminada [6].

We first introduce some further notational ideas.
Definition 7.
As is standard we distinguish $N$ (the set of positive integers ${1, 2, 3, \dots}$ ) and $W$ (the set of non-negative integers ${0} \cup N$ ).

Let $S$ be a subset of $2^{X}$ . The set which we denote $[S]$ is the system $S_{[k]}$ formed by setting $S_{[0]} = S$ and for $k > 0$ $\begin{matrix} S_{[k]} = ⋃_{(P, Q) \in S_{[k - 1]} \times S_{[k - 1]}} {{P \cup Q}} \end{matrix}$ until the point $S_{[k]} = S_{[k - 1]}$ is reached.

We say that $S$ is $[]$ -closed if $S = [S]$ , i.e. $k = 1$ in the process just described since $S = S_{[0]}$ (by definition) and $S_{[0]} = S_{[1]}$ .

As a small example of the process of forming $[S]$ suppose we have $\begin{array}{l} S = {{1}, {2}, {3, 4}, {3, 4, 5}}, \\ S_{[0]} = {{1}, {2}, {3, 4}, {3, 4, 5}}, \\ S_{[1]} = S_{[0]} \cup {{1, 2}, {1, 3, 4}, {1, 3, 4, 5}, {2, 3, 4}, {2, 3, 4, 5}}, \\ S_{[2]} = S_{[1]} \cup {{1, 2, 3, 4}, {1, 2, 3, 4, 5}}, \\ S_{[3]} = S_{[2]} . \end{array}$

A final idea, is that of a decomposition of a system of sets.
Definition 8.
Given a system of sets $S \subseteq 2^{X}$ its r-partial decomposition, denoted $Δ_{r} (S)$ is formed as an ordered sequence of subsets of $S$ which we denote $(S^{(0)}, S^{(1)}, \dots, S^{(r)})$ with the $S^{(i)} \subseteq S$ pairwise disjoint, i.e. $S^{(i)} \cap S^{(j)} = \emptyset$ .

$Δ_{r} (S)$ is formed from $S$ by applying the following process.

If $\emptyset \notin S$ then $Δ_{r} (S) = \emptyset$ . Otherwise, $\begin{matrix} Δ_{r} (S) = \{\begin{matrix} ({\emptyset}) & if r = 0 and \emptyset \in S, \\ (Δ_{r - 1} (S); S^{(r)}) & if r > 0 . \end{matrix} \end{matrix}$ In this $Δ_{r - 1} (S) = (S^{(0)}, S^{(1)}, \dots, S^{(r - 1)})$ the $(r - 1)$ -partial decomposition of $S$ . The system of sets in $S^{(r)}$ ( $r > 0$ ) contains all subsets of $S$ of the form $\begin{matrix} {{{y} \cup T} : y \notin ⋃_{i = 0}^{r - 1} ⋃_{U \in S^{(i)}} U and T is \subseteq -minimal in [⋃_{i = 0}^{r - 1} S^{(i)}] with y \cup T \in S} . \end{matrix}$ If $\emptyset \notin S$ or the process used to define $S^{(r)}$ cannot be applied further then $S^{(r)} = \emptyset$ . Using this convention every system of subsets of $2^{X}$ has some r-partial decomposition, although for r large enough ( $r > | X |$ for example), $S^{(r)} = \emptyset$ .
Definition 9.
We say that $S \subseteq 2^{X}$ is decomposable if for some $r \in W$ $\begin{matrix} S = [⋃_{i = 0}^{r} S^{(i)}] \end{matrix}$ with $(S^{(0)}, \dots, S^{(r)})$ formed using $S$ according to the prescription given. If $S$ is decomposable we denote its full decomposition by $Δ (S)$ without indicating r.

Again, as a small illustration, suppose that $\begin{matrix} S = {\emptyset, {1}, {2}, {1, 3}, {2, 4}, {1, 3, 5}, {2, 4, 6}, {1, 3, 5, 7}, {1, 2, 3, 4, 7}} . \end{matrix}$ We have, $\begin{matrix} S^{(0)} = {\emptyset} . \end{matrix}$ To form $S^{(1)}$ we can only use single element sets from $S$ , leading to $\begin{matrix} S^{(1)} = {{1}, {2}} . \end{matrix}$ Notice that ${1} \cup \emptyset \in S$ and that $\emptyset \in [S^{(0)}]$ is a minimal such set. We further observe that if there are no sets $S \in S$ for which $| S | = 1$ then $S$ has (at best) a 0-partial decomposition.

Continuing this example, in order to form $S^{(2)}$ we must identify those minimal sets $T \in [S^{(0)} \cup S^{(1)}]$ together with those single elements, x, for which ${x} \cup T \in S$ . In the example we find these to be $\begin{array}{l} {1} with 3, \\ {2} with 4 \end{array}$ so giving $\begin{matrix} S^{(2)} = {{1, 3}, {2, 4}} . \end{matrix}$ In forming $S^{(3)}$ the range of sets we may choose from are those $T \in [S^{(0)} \cup S^{(1)} \cup S^{(2)}]$ and we require single elements, x, with which ${x} \cup T \in S$ and T is a minimal set. Here we find $\begin{array}{l} {1, 3} with 5, \\ {2, 4} with 6 \end{array}$ giving $\begin{matrix} S^{(3)} = {{1, 3, 5}, {2, 4, 6}} . \end{matrix}$

Notice that ${1, 2, 3, 4, 7}$ , although in $S$ with ${1, 2, 3, 4} \in [S^{(0)} \cup S^{(1)} \cup S^{(2)}]$ cannot be included in $S^{(3)}$ : the reason being because of the set ${1, 3, 5, 7}$ in $S$ . The element, 5, is first introduced in $S^{(3)}$ so any sets in $S$ containing 5 and some as yet unrecovered item (such as 7) cannot be built until 5 is available. If it were the case that ${1, 3, 5, 7} \notin S$ then we could add ${1, 2, 3, 4, 7}$ to $S^{(3)}$ via ${1, 2, 3, 4} \in [S^{(0)} \cup S^{(1)} \cup S^{(2)}]$ .

The final stage of the decomposition of $S$ forms $S^{(4)}$ as $\begin{matrix} S^{(4)} = {{1, 2, 3, 4, 7}, {1, 3, 5, 7}} . \end{matrix}$

We stress the distinction between $S^{(k)} = \emptyset$ and $S^{(0)} = {\emptyset}$ : the former case describes the situation where either no further expansion (or any expansion whatsoever) via the process of Definition 8, is possible. Thus if $\emptyset \notin S$ then $S^{(k)} = \emptyset$ for all $k \in W$ . Similarly, noting the requirement for new members of $X$ to be used when progressing from $S^{(k)}$ to $S^{(k + 1)}$ , it is easily seen that $S^{(r)} = \emptyset$ whenever $r > | X |$ .

We further note the requirement that T witnessing ${y} \cup T \in S^{(k)}$ is minimal with respect to ⊆, e.g. if y is a new element introduced in forming $S^{(k)}$ , and ${{u, v, w}, {u, v}, {v, w}} \subseteq [S^{(k - 1)}]$ then $S^{(k)}$ could contain ${u, v, y}$ or ${v, w, y}$ or ${{u, v, y}, {v, w, y}}$ : in all three cases, however, $S^{(k)}$ would not contain ${u, v, w, y}$ . Similarly were ${u, v, w, y} \in S^{(k)}$ then neither ${u, v, y}$ nor ${v, w, y}$ would be.

Two properties of decomposable systems are given in the next lemmata.
Lemma 1.
Let $S \subseteq 2^{X}$ . For all $k \in W$ , $Δ_{k} (S)$ is unique.
Proof.
Let $S \subseteq 2^{X}$ have an r-partial decomposition $\begin{matrix} Δ_{r} (S) = (S^{(0)}, S^{(1)}, \dots, S^{(r)}) . \end{matrix}$ Suppose, for the sake of contradiction, that $(T^{(0)}, T^{(1)}, \dots, T^{(r)})$ is an r-partial decomposition of $S$ differing from $Δ_{r} (S)$ .

Choose $p \in W$ to be the least value for which $S^{(p)} \neq T^{(p)}$ . Since it is the case that $S^{(p)} \neq T^{(p)}$ we must have some subset $S \in S$ for which $S \in S^{(p)}$ but $S \notin T^{(p)}$ (or vice-versa).

By definition $S \in S^{(p)}$ indicates that, in addition to $S \in S$ , we have $S = U \cup {y}$ , $U \in [⋃_{k = 0}^{p - 1} S^{(k)}]$ and no strict subset V of U for which $V \in [⋃_{k = 0}^{p - 1} S^{(k)}]$ and $V \cup {y} \in S$ . Furthermore $\begin{matrix} y \notin ⋃_{i = 0}^{p - 1} ⋃_{W \in S^{(i)}} W . \end{matrix}$ We have chosen p as the smallest value for which $S^{(p)} \neq T^{(p)}$ and so $S^{(p - 1)} = T^{(p - 1)}$ . In consequence, $[⋃_{k = 0}^{p - 1} S^{(k)}] = [⋃_{k = 0}^{p - 1} T^{(k)}]$ and, hence, U is a minimal set (wrt ⊆) in $[⋃_{k - 0}^{p - 1} T^{(k)}]$ for which ${y} \cup U \in S$ . It is also the case that $\begin{matrix} y \notin ⋃_{i = 0}^{p - 1} ⋃_{W \in T^{(i)}} W . \end{matrix}$ The inclusion of $y \cup U$ as part of $S^{(p)}$ or $T^{(p)}$ is dependent only on $S$ (since U must be a minimal set for which $y \cup U \in S$ ) and the structure of $[⋃_{k = 0}^{p - 1} S^{(k)}]$ (respectively $[⋃_{k = 0}^{p - 1} T^{(k)}]$ ). The underlying set $S$ is the same regardless of how it is decomposed. We have, however, chosen p as the least value at which $S^{(p)} \neq T^{(p)}$ . Now we obtain the required contradiction since in order for $S^{(p)}$ to differ from $T^{(p)}$ would require $\begin{matrix} [⋃_{i = 0}^{p - 1} S^{(p - 1)}] \neq [⋃_{i = 0}^{p - 1} T^{(p - 1)}] \end{matrix}$ so contradicting the choice of p.

We conclude that the r-partial decomposition of $S$ is unique. □
Lemma 2.
Let $(S^{(0)}, \dots, S^{(r)})$ be the r-partial decomposition of $S$ and $Y$ be $\begin{matrix} Y = ⋃_{i = 1}^{r} ⋃_{T \in S^{(i)}} T = {x_{1}, x_{2}, \dots, x_{t}} . \end{matrix}$ Then $Y$ may be partitioned into disjoint sets $(T_{1}, T_{2}, \dots, T_{k})$ each having an associated $q_{i}$ with $\begin{matrix} 1 ⩽ q_{1} < q_{2} < \dots < q_{k} = r \end{matrix}$ and for all $1 ⩽ p < k$ $\begin{matrix} ⋃_{j = 1}^{p} T_{j} = ⋃_{i = 1}^{q_{p}} ⋃_{S \in S^{(i)}} S \end{matrix}$ but $\begin{matrix} ⋃_{j = 1}^{p} T_{j} \neq ⋃_{i = 1}^{q_{p} - 1} ⋃_{S \in S^{(i)}} S; ⋃_{j = 1}^{p} T_{j} \neq ⋃_{i = 1}^{q_{p} + 1} ⋃_{S \in S^{(i)}} S . \end{matrix}$
Proof.
The partition simply follows the ordering by which individual elements of $X$ are added to $S^{(i)}$ so that, $\begin{array}{l} T_{1} = {y : {y} \in S}, \\ T_{2} = {y : {y} \cup U \in S, U \subseteq T_{1}, y \notin T_{1}, and U is a minimal such subset of T_{1}}, \\ \dots \end{array}$ and, in general, $\begin{matrix} T_{i} = {y : y \cup U \in S, U \subseteq ⋃_{j = 1}^{i - 1} T_{j}, y \notin ⋃_{j = 1}^{i - 1} T_{j}, and U minimal} . \end{matrix}$ □

Before presenting our main results it may be helpful to look at two example systems both of which are decomposable.

Consider $S$ defined as $\begin{array}{l} {\emptyset, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, \\ {1, 4}, {1, 2, 4}, {1, 3, 4}, {1, 2, 3, 4}, \\ {2, 3, 5}, {1, 2, 3, 5}, {1, 2, 3, 4, 5}} . \end{array}$ This has a 2-decomposition as $\begin{array}{l} S^{(0)} = {\emptyset}, \\ S^{(1)} = {{1}, {2}, {3}}, \\ S^{(2)} = {{1, 4}, {2, 3, 5}} . \end{array}$ Each set in $S^{(2)}$ is formed as the union of a new argument (4 or 5) with a set in $[S^{(1)}]$ . Notice that ${1, 2, 3, 4, 5} \notin S^{(2)}$ but is in $[S^{(2)}]$ (via ${1, 4} \cup {2, 3, 5}$ ).

We cannot defer adding ${2, 3, 5}$ to a later level: the definition states that since we are able to include ${2, 3, 5}$ in $S^{(2)}$ it is required to do so.

The system $[S \cup {{1, 4, 5}}]$ , is also decomposable, however, now the decomposition would be $\begin{matrix} S^{(0)} = {\emptyset} \\ S^{(1)} = {{1}, {2}, {3}} \\ S^{(2)} = {{1, 4}} \\ S^{(3)} = {{1, 4, 5}, {2, 3, 5}} \end{matrix}$ Now we cannot add ${2, 3, 5}$ to $S^{(2)}$ since we cannot add ${1, 4, 5}$ at the same time: ${1, 4} \notin [S^{(1)}]$ and ${1, 5} \notin [S^{(1)}]$ and since 1 occurs as an element of sets in $S^{(1)}$ a decomposition including ${1, 4, 5}$ would need ${1, 4} \in [S^{(1)}]$ .

It is also the case that both systems of sets are in $Σ_{str}$ as can easily be seen by inspecting Fig. 2.

Fig. 2.
Realization of $str (H)$ for example system.

The implied partitions from Lemma 2 being $\begin{array}{l} ({1, 2, 3}; {4, 5}) first case, \\ ({1, 2, 3}; {4}; {5}) second case . \end{array}$ On the other hand, a system such as $\begin{matrix} {\emptyset, {1}, {1, 2}, {1, 3, 4}, {1, 2, 3, 4}} \end{matrix}$ is not decomposable (this system, however, is $[]$ -closed) since there is no way of including ${1, 3, 4}$ in a decomposition.

Applying the process described in Definition 8 would yield $\begin{array}{l} S^{(0)} = {\emptyset}, \\ S^{(1)} = {{1}}, \\ S^{(2)} = {{1, 2}} \end{array}$ and no further expansion is possible.

Were the set ${1, 3}$ to be added the resulting system would be decomposable. Applying the process described in Definition 8 would then yield $\begin{array}{l} S^{(0)} = {\emptyset}, \\ S^{(1)} = {{1}}, \\ S^{(2)} = {{1, 2}, {1, 3}}, \\ S^{(3)} = {{1, 3, 4}} . \end{array}$
4. Strongly admissible systems are decomposable

With the concept of decomposability we obtain Theorem 1. We note that the partition structure and its properties in relationship to the characteristic function are used (although not explicity phrased as such) in the algorithm of Caminada and Dunne [7] by which verification of a set as strongly admissible is shown to be decidable in polynomial time.

Theorem 1.
Let $X$ be a finite set of n arguments and $S \subseteq 2^{X}$ .

If $S \in Σ_{str}$ then $S$ is decomposable.
Proof.
Consider any $S \in Σ_{str}$ and let $H = (X, A)$ be any af witnessing the realizability of $S$ , i.e. for which $str (H) = S$ .

To begin consider the following partition of $\begin{matrix} {x \in X : \exists S \in str (H) with x \in S} . \end{matrix}$ This partition is formed as $(P_{0}; P_{1}; \dots; P_{t})$ with $P_{i} = F_{H}^{i}$ and $\begin{matrix} F_{H}^{i} = \{\begin{matrix} \emptyset & if i = 0, \\ F_{H} (F_{H}^{i - 1}) ∖ F_{H}^{i - 1} & if i > 0 . \end{matrix} \end{matrix}$ Here $F_{H} (U)$ is the characteristic function of conflict-free sets U with respect to $H = (X, A)$ so that $\begin{matrix} F_{H} (U) = {x \in X : \forall y \in {x}^{-} \exists z_{y} \in U s . t . ⟨ z_{y}, y ⟩ \in A} . \end{matrix}$ Notice that this is a partition of ${x \in X : \exists S \in str (H) with x \in S}$ and, furthermore the grounded extension, $GE (H)$ satisfies, $\begin{matrix} GE (H) = ⋃_{i = 0}^{t} P_{i} . \end{matrix}$ This partition will form the basis for constructing the decomposition of $S$ as $\begin{matrix} (S^{(0)}, S^{(1)}, \dots, S^{(t)}) . \end{matrix}$ Fix $S^{(0)} = {\emptyset}$ and $S^{(1)} = {{x} : x \in P_{1}}$ . Every ${x} \in S^{(1)}$ satisfies $x \in F_{H}^{1} = F_{H} (\emptyset)$ so not only is ${x} \in S$ , i.e. $s t r (H)$ but also every subset of $P_{1}$ (such corresponding to some union of a subset of $S^{(1)}$ ) is in $S$ .

Now suppose we continue this construction relative to elements ( $S^{(k - 1)}$ , $k ⩾ 2$ ) already built (via the template specified in Definition 8) and the system $S$ . Consider which sets would be included in $S^{(k)}$ . We have $S \in S^{(k)}$ whenever $S = y \cup U$ and $\begin{matrix} y \notin ⋃_{i = 0}^{k - 1} ⋃_{T \in S^{(i)}} T \end{matrix}$ and U is a ⊆-minimal set in $[⋃_{i = 0}^{k - 1} S^{(i)}]$ for which $y \cup U \in S$ .

We now argue that for all k, the proposition, $Q (k)$ holds, where $\begin{matrix} Q (k) \equiv {(S \in S and S \subseteq ⋃_{i = 0}^{k} P_{i}) \Leftrightarrow S \in [⋃_{i = 0}^{k} S^{(i)}]} . \end{matrix}$ This will establish the Theorem: $S \in Σ_{str} \Rightarrow S is decomposable$ .

To see this is the case, notice that $Q (k)$ treats $S = str (H)$ as a sequence of sets built by adding single arguments, y, (according to the partition $(P_{0}; P_{1}; \dots; P_{r})$ described earlier) to (minimal) strongly admissible sets, S, that defend y, i.e. have $y \in F_{H} (S)$ . Noting the closure of $str (H)$ under set union, so that $S \in str (H)$ and $T \in str (H)$ leads to $S \cup T \in str (H)$ , applying the closure operation $[\dots]$ to $S^{(i)}$ ensures that all $S \in [S^{(i)}]$ are also in $str (H)$ .

We have already shown that $Q (1)$ and $Q (0)$ hold.

Suppose, as an inductive hypothesis, we have demonstrated $Q (k)$ for all $0 ⩽ k ⩽ r - 1$ for some $r ⩽ t$ (t being the number of classes in the partition of ${x \in X : \exists S \in str (H) with x \in S}$ from Lemma 2).

Consider $P_{r}$ . By definition, $P_{r}$ contains $F_{H} (F_{H}^{r - 1}) ∖ F_{H}^{r - 1}$ and (from the construction) no argument $y \in P_{r}$ occurs in $\begin{matrix} ⋃_{i = 0}^{r - 1} ⋃_{T \in S^{(i)}} T . \end{matrix}$ From the fact that $y \in F_{H} (F_{H}^{r - 1}) ∖ F_{H}^{r - 1}$ we can find some strongly admissible subset, U, using only arguments in $⋃_{i = 0}^{r - 1} P_{i}$ which defends y. To see this just work back from $k = r - 1$ constructing $W_{r - 1}$ (the subset of $P_{r - 1}$ that defends y which, since $y \in F_{H} (F_{H}^{r - 1}) ∖ F_{H}^{r - 1}$ , is well-defined); then $W_{r - 2}$ as the subset of $P_{r - 2}$ that collectively defends $W_{r - 1}$ and, in general, $W_{j}$ as the subset of $P_{j}$ that defends $W_{j + 1}$ . The set $\begin{matrix} ⋃_{j = 0}^{r - 1} W_{i} \end{matrix}$ is in $str (H)$ (thence also in $S$ ). Furthermore every set, U, for which U is formed as the union of sets $\begin{matrix} {V_{i} : V_{i} \subseteq P_{i} with V_{i} \subseteq F_{H} (V_{i - 1}) ∖ V_{i - 1} (and 1 ⩽ i ⩽ r - 1)} \end{matrix}$ is in $str (H)$ and thus in $\begin{matrix} [⋃_{i = 0}^{r - 1} S^{(i)}] \end{matrix}$ from the inductive assumption $Q (r - 1)$ . The argument y is such that $y \cup U \in S$ and we have just seen that this can be rewritten as $\begin{matrix} y \cup ⋃_{i = 0}^{r - 1} V_{i} V_{i} \subseteq P_{i} . \end{matrix}$ Now, since we can find some set, U with $y \cup U \in S$ and $U \subseteq ⋃_{i = 0}^{r - 1} P_{i}$ we can certainly find a minimal such set. Furthermore such minimal sets can be divided by exactly the same process, i.e. expressed as the union of sets $\begin{matrix} {Z_{i} : Z_{i} \subseteq P_{i} with Z_{i} \subseteq F_{H} (Z_{i - 1}) ∖ Z_{i - 1}, 1 ⩽ i ⩽ r - 1} . \end{matrix}$ We deduce that for every $y \in P_{r}$ we can identify minimal subsets $U_{1}, \dots, U_{r}$ for which $y \cup U_{i} \in S$ and $S^{(r)}$ including $y \cup U_{i}$ . Hence every set formed in $\begin{matrix} [⋃_{i = 0}^{r} S^{(i)}] \end{matrix}$ is in $str (H)$ .

We have shown, $\begin{matrix} S \in [⋃_{i = 0}^{r} S^{(i)}] \Rightarrow S \in S . \end{matrix}$ To complete the proof we need $\begin{matrix} S \in str (H) \Rightarrow S \in [⋃_{i = 0}^{r} S^{(i)}] . \end{matrix}$ We have already demonstrated the inductive base: $S \subseteq P_{1}$ (the only case, other than $S = \emptyset$ for which $S \in str (H)$ and $S \in [S^{(0)} \cup S^{(1)}]$ ). Hence assume, as inductive hypothesis, it has been shown for all $0 ⩽ k ⩽ r - 1$ ( $r ⩽ t$ ) that $\begin{matrix} (S \in str (H) and S \subseteq ⋃_{i = 0}^{r - 1} P_{i}) \Rightarrow S \in [⋃_{i = 0}^{r - 1} S^{(i)}] . \end{matrix}$ We extend this to argue that $\begin{matrix} (S \in str (H) and S \subseteq ⋃_{i = 0}^{r} P_{i}) \Rightarrow S \in [⋃_{i = 0}^{r} S^{(i)}] . \end{matrix}$ Let $S \in str (H)$ with $S \subseteq ⋃_{i = 0}^{r} P_{i}$ . If $S \cap P_{r} = \emptyset$ then no further argument is required (the case has been dealt with under our Inductive assumptions). Thus consider $\begin{matrix} S \cap P_{r} = {y_{1}, y_{2}, \dots, y_{m}} . \end{matrix}$ We know that – by the definition of strongly admissible – there is some subset, U of $S ∖ {y_{1}, \dots, y_{m}}$ such that $U \in str (H)$ and, furthermore $y_{i} \in F_{H} (U)$ for each i. Notice that from the construction of $P_{r}$ it cannot be the case that $y_{i}$ is needed to defend attacks upon $y_{j}$ . We know that $U \in str (H)$ and $U \subseteq ⋃_{i = 0}^{r - 1} P_{i}$ . Therefore, from the inductive hypothesis $\begin{matrix} U \in [⋃_{i = 0}^{r - 1} S^{(i)}] . \end{matrix}$ For the construction of $S^{(r)}$ we have sets $U_{1}, U_{2}, \dots, U_{m}$ for which $\begin{matrix} y_{i} \cup U_{i} \in S \end{matrix}$ with $U_{i}$ a ⊆ smallest set in $⋃_{i = 1}^{r - 1} P_{i}$ with $U_{i} \in str (H)$ . We now have, $\begin{matrix} {U_{1}, U_{2}, \dots, U_{m}} \subseteq [⋃_{i = 0}^{r - 1} S^{(i)}] (I.H.) \end{matrix}$ and $y_{i} \cup U_{i} \in S^{(r)}$ (from the minimality of $U_{i}$ ). Hence $\begin{matrix} ⋃_{i = 1}^{m} (y_{i} \cup U_{i}) \in [⋃_{i = 0}^{r} S^{(i)}] \end{matrix}$ and $\begin{matrix} ⋃_{i = 1}^{m} U_{i} \subseteq U \in [⋃_{i = 0}^{r - 1} S^{(i)}] . \end{matrix}$ Hence, $\begin{matrix} U \cup ⋃_{i = 1}^{m} (y_{i} \cup U_{i}) = U \cup {y_{1}, \dots, y_{m}} \in [⋃_{i = 0}^{r} S^{(i)}] . \end{matrix}$ Completing the argument that if $S \in Σ_{str}$ then $S$ is decomposable. □

If we look at the case from Fig. 1, we had $s t r (H)$ as, $\begin{matrix} {\emptyset, {A}, {D}, {A, C}, {A, D}, {A, C, D}, {A, C, F}, {D, F}, {A, C, D, F}} . \end{matrix}$ Since this is (self-evidently) a set of sets formed by the strongly admissible sets of an af, the result of Theorem 1 asserts that this system is decomposable. Such a decomposition is given by $\begin{array}{l} S^{(0)} = {\emptyset}, \\ S^{(1)} = {{A}, {D}}, \\ S^{(2)} = {{A, C}}}, \\ S^{(3)} = {{A, C, F}, {D, F}} \end{array}$ with which every $S \in str (H)$ is formed by taking the union of (sometimes more than 2) appropriate sets from $(S^{(0)}, S^{(1)}, S^{(2)}, S^{(3)})$ , e.g. ${A, C, D}$ is ${A, C} \cup {D}$ the former in $S^{(2)}$ , the latter in $S^{(1)}$ . We further note that we cannot include ${D, F}$ in $S^{(2)}$ despite ${D} \in S^{(1)}$ : the reason being the need to include all minimal sets with F at the same time, however ${A, C, F}$ is one such set and C first appears in $S^{(2)}$ delaying ${A, C, F}$ to $S^{(3)}$ .
5. Decomposable systems are strongly admissible

We now complete the characterization of strong admissibility, the first part of which was demonstrated in Theorem 1 by showing that any system of sets $S$ which is decomposable is in $Σ_{str}$ , i.e. there is an af, $H$ , for which $str (H) = S$ . We need some additional preliminaries.

Given $y \in X$ and $H$ define $F_{H}^{- 1} (y)$ to be the subset of $2^{X ∖ {y}}$ for which $S \in F_{H}^{- 1} (y)$ if ${y} \cup S$ is conflict-free, $y \in F_{H} (S) ∖ S$ and for all strict subsets T of S $y \notin F_{H} (T) ∖ T$ .

The concept $F_{H}^{- 1} (y)$ was introduced in Dunne [9] where it is dubbed the “inverse characteristic function” of y with respect to $H$ .1

¹
The actual case considered in the present paper is denoted $Ϝ_{H, cf}^{- 1} (y)$ in [9] in order to distinguish ⊆-minimal sets. In [9] properties of $F_{H, cf}^{- 1} (y)$ are studied, this concept covering all subsets, S, for which ${y} \cup S$ is conflict-free and $y \in F_{H} (S)$ . It is, of course, clear that $Ϝ_{H, cf}^{- 1} (y) \subseteq F_{H, cf}^{- 1} (y)$ .

Lemma 3.

Let $T \subset 2^{X ∖ {y}}$ all of whose members are incomparable, i.e. if $(P, Q) \in T \times T$ then $P ⊄ Q$ and $Q ⊄ P$ . Let $Z = ⋃_{T \in T} T$ . There is an af $H = (X, A)$ in which ${y} \cup Z \subseteq X$ and $T = F_{H}^{- 1} (y)$ .

Proof.

Given $T$ as described in the Lemma statement consider the (monotone) Boolean function $f_{T}$ over the propositional variables $Z = (z_{1}, z_{2}, \dots, z_{n})$ defined via $\begin{matrix} f_{T} (z_{1}, \dots, z_{n}) \equiv \underset{T \in T}{⋁} (\underset{z_{i} \in T}{⋀} z_{i}) . \end{matrix}$ It is clearly the case that $f_{T} [S] = ⊤$ if and only if $S \supseteq T$ for some $T \in T$ . The specification of $f_{T}$ is given in implicant form, i.e. as a disjunction of product terms. It is, however, well known that any Boolean function has an equivalent specification in implicate form, i.e as a conjunction of clauses. It follows that we can translate $T$ to another system of subsets over $Z$ , $\begin{matrix} P = {P_{1}, P_{2}, \dots, P_{m}} \end{matrix}$ with the sets in $P$ being incomparable and $\begin{matrix} f_{T} (z_{1}, \dots, z_{n}) \equiv ⋀_{k = 1}^{m} (\underset{z_{i} \in P_{k}}{⋁} z_{i}) . \end{matrix}$ Build the af $H = (X, A)$ with $X = Z \cup {y} \cup {p_{1}, p_{2}, \dots, p_{m}}$ m being the number of clause sets in $P$ . Add attacks $⟨ p_{k}, y ⟩$ for each $1 ⩽ k ⩽ m$ and an attack $⟨ z_{i}, p_{j} ⟩$ whenever $z_{i} \in P_{j} \in P$ . If $U \supseteq T \in T$ then $U^{+} = {p_{1}, p_{2}, \dots, p_{m}}$ since the implicant (disjunction of product terms using $T$ ) and implicate (conjunction of clauses using $P$ ) describe exactly the same propositional function. In order for $f_{T} [S] = ⊤$ to hold some $T \in T$ must describe a subset of S, or (equivalently), S must include at least one $z_{i}$ from every clause $P_{k} \in P$ . From the latter interpretation we see that each attack on y is defended by $T^{+}$ , i.e. $t \in F_{H} (T) ∖ T$ and no strict subset of T suffices to defend y. □

We note that the relationship between “sets of arguments providing a defence against attacks on y” and the well-known formalisms from propositional logic of cnf and dnf has already been often exploited in formal argumentation. A similar use to that of Lemma 3 is found in Dunne et al. [11].

It is shown in [9, Thm. 4] that this construction is optimal. Given some incomparable system of subsets, $S$ , with $P$ the set of clauses in the unique minimal cnf equivalent to $f_{S} (Z)$ , any af in which: for all $S \in S$ , $S \cup {y}$ is conflict-free and $S^{+} \supseteq {y}^{-}$ must be such that $| {y}^{-} | ⩾ | P |$ .

In particular, the realization of an af, $H = (X, A)$ in which $F_{H}^{- 1} (y) = T$ for some incomparable system of subsets $T$ drawn from $Z$ may use exponentially many auxiliary arguments. This is not only in cases for which $| T | \sim 2^{| Z |}$ , e.g. when $| Z | = 2 n$ and $T$ comprises all subsets of size n from $Z$ . Perhaps less obviously, one might have (again with $| Z | = 2 n$ ) $| T | = n$ but, with the construction used, $2^{n}$ auxiliary arguments in $X$ . For example if $\begin{matrix} T = {{z_{i}, z_{n + i}} : 1 ⩽ i ⩽ n} . \end{matrix}$ The implicant form of $f_{T} (z_{1}, \dots, z_{2 n})$ used in the proof of Lemma 3 is $\begin{matrix} ⋁_{i = 1}^{n} z_{i} \land z_{n + i} . \end{matrix}$ The implicate form giving rise to the system of sets $P$ has $2^{n}$ clauses leading to $| X | = 1 + n + 2^{n}$ .

The principal importance of Lemma 3, is as a vehicle by which to establish Theorem 2.

Theorem 2.

If $S \subseteq 2^{X}$ is decomposable then $S \in Σ_{str}$ .

Proof.

Given $S \subseteq 2^{X}$ which is decomposable let $\begin{matrix} (S^{(0)}, S^{(1)}, \dots, S^{(r)}) \end{matrix}$ be the decomposition of $S$ and $(P_{0}; P_{1}; \dots; P_{t})$ the partition of $⋃_{i = 1}^{r} ⋃_{S \in S^{(i)}} S$ described in Lemma 2 (recalling that $P_{0} = {\emptyset}$ ). We use an inductive construction to build, $H_{k}$ satisfying $\begin{matrix} s t r (H_{k}) = [⋃_{i = 0}^{k} S^{(i)}] . \end{matrix}$ The inductive bases ( $k = 0$ and $k = 1$ ) are easily dealt with. In the former case, since $S^{(0)} = {\emptyset}$ , we can use any $H_{0}$ for which every $x \in X$ is attacked by at least one other argument. In the case of $k = 1$ , $H_{1}$ comprises the arguments in $P_{1}$ only with $A_{1} = \emptyset$ .

Now let us assume, inductively that we have built $H_{t}$ for all $t ⩽ k - 1$ . We wish to form $H_{k}$ . From the properties of the partition and formulation of the decomposition of $S$ we know that each set in $S^{(k)}$ has the form $y \cup U$ where $y \notin ⋃_{i = 1}^{k - 1} P_{i}$ and U is a subset minimal set in $[⋃_{i = 0}^{k - 1} S^{(i)}]$ for which $y \cup U \in S$ . For each $y \in P_{k}$ define $\begin{matrix} G (y) = {{U} : y \cup U \in S^{(k)}} . \end{matrix}$ We wish to develop $H_{k - 1}$ to $H_{k}$ in such a way that $G (y) \subseteq str (H_{k})$ . These subsets, $G (y)$ must be such that $\begin{matrix} G (y) = F_{H_{k}}^{- 1} (y) . \end{matrix}$ We can now apply the outcome of Lemma 3. Identify each of the arguments contributing to sets in $G (y)$ (all such arguments being in $H_{k - 1}$ ) and then use the result of Lemma 3 to add the required defences of y as minimal sets in $str (H_{k})$ .

This suffices to complete the inductive proof. □

Returning to the system presented in Fig. 1, we saw that this corresponds to the system of sets $\begin{matrix} {\emptyset, {A}, {D}, {A, C}, {A, D}, {A, C, D}, {A, C, F}, {D, F}, {A, C, D, F}} \end{matrix}$ which has decomposition $\begin{array}{l} S^{(0)} = {\emptyset}, \\ S^{(1)} = {{A}, {D}}, \\ S^{(2)} = {{A, C}}}, \\ S^{(3)} = {{A, C, F}, {D, F}} . \end{array}$ In forming the af with $str (H) = [S^{(0)} \cup S^{(1)}]$ we require only the two arguments ${A, D}$ and $A = \emptyset$ . To add $S^{(2)}$ we have a new argument (C) which requires A as a defender. Thus we can add ${C}$ and an argument x together with attacks $⟨ A, x ⟩$ and $⟨ x, C ⟩$ . Finally we must account for the cases in $S^{(3)}$ which introduce F which can be defended by either D alone or by ${A, C}$ . We can extend the framework constructed so far adding arguments ${y, F}$ with $⟨ y, F ⟩ \in A$ . Now, however, we need both $⟨ C, y ⟩ \in A$ and $⟨ D, y ⟩ \in A$ . The first will ensure ${A, C, F} \in str (H)$ and the second that ${D, F} \in str (H)$ .

Combining Theorem 1 and Theorem 2 gives Corollary 1.

Let $S \subseteq 2^{X}$ . $\begin{matrix} S \in Σ_{str} \Leftrightarrow S is decomposable . \end{matrix}$

6. Conclusions & extensions

Our principal aim in this paper has been to present a characterization of strong admissibility, as first presented in Baroni and Giacomin [3], in terms of the notions of signature and realizability from Dunne et al. [10,11]. Our main result, summarized as Corollary 1, being that a collection of subsets of $X$ describes the strongly admissible sets of some af if and only if that collection possesses the property of being decomposable. The notion of decomposability raises a number of combinatorial and complexity-theoretic questions, some of which we briefly discuss here. One specific aspect of interest concerns the contrast between a framework having exponentially many sets in $str (H)$ but with the possibility of describing these through a much more concise description of its decomposition. As a very simple example, the af, $(X, A)$ in which $A = \emptyset$ has exactly $2^{| X |}$ strongly admissible sets (every subset of $X$ ). These, however, are succinctly described via the 1-decomposition, $({\emptyset}; {{x_{1}}, {x_{2}}, \dots, {x_{n}}})$ . On the other hand there are cases in which the number of distinct sets in $S^{(2)}$ must be exponential in $| X |$ : a simple example of such behaviour being the incomparable system formed by all subsets of $X$ containing exactly $| X | / 2$ members. Hence one direction for further work would concern exploring the relationship between $| str (H) |$ and its decomposition. One complexity-theoretic question concerns the following: given S it is known that verifying $S \in str (H)$ can be carried out efficiently from the results of Caminada and Dunne [7]. If we ask instead whether for some k, $S \in S^{(k)}$ it is unclear whether this continues to be tractable: intractability is suggested by complexity-theoretic study of “minimal labellings” on the other hand there may be some variation of the algorithm from [7] that could be applied.

Finally we have some questions of interest regarding signatures of analogues of strong admissibility in variant afs. One such being the collective attacks model introduced in Neilsen and Parsons [13] and studied with respect to realizability for the canonical Dung semantics in Dvorak et al. [12]. We leave these and similar questions for further work.

Footnotes

Acknowledgements

The author would like to thank Martin Caminada for useful discussions regarding the strong admissibility semantics.

References

Baroni,

Caminada and

Giacomin, Abstract argumentation frameworks and their semantics, in: Handbook of Formal Argumentation, Vol. 1, 2018, pp. 157–234.

Baroni,

Cerutti,

P.E.

Dunne and

Giacomin, Automata for infinite argumentation structures, Artificial Intelligence 203 (2013), 104–150. doi:10.1016/j.artint.2013.05.002.

Baroni and

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.

Baumann, On the nature of argumentation semantics: Existence and uniqueness, expressibility, and replaceability, Journal of Applied Logics 4(8) (2017), 2779–2886.

Baumann and

Spanring, A study of unrestricted abstract argumentation frameworks, in: IJCAI, Vol. 17, 2017, pp. 807–813. doi:10.24963/ijcai.2017/112.

M.W.A.

Caminada, Strong admissibility revisited, in: Computational Models of Argument; Proceedings of COMMA 2014,

Parsons,

Oren,

Reed and

Cerutti, eds, IOS Press, 2014, pp. 197–208.

M.W.A.

Caminada and

P.E.

Dunne, Strong admissibility revised: Theory and applications, Argument & Computation (2019), in print.

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.

P.E.

Dunne, The inverse characteristic function in argumentation frameworks: Properties and complexity (submitted), 2020, www.csc.liv.ac.uk/~ped/combined.pdf.

10.

P.E.

Dunne,

Dvořák,

Linsbichler and

Woltran, Characteristics of multiple viewpoints in abstract argumentation, in: 14th International Conference on the Principles of Knowledge Representation and Reasoning, 2014.

11.

P.E.

Dunne,

Dvořák,

Linsbichler and

Woltran, Characteristics of multiple viewpoints in abstract argumentation, Artificial Intelligence 228 (2015), 153–178. doi:10.1016/j.artint.2015.07.006.

12.

Dvořák,

Fandinno and

Woltran, On the expressive power of collective attacks, Argument & Computation 10(2) (2019), 191–230. doi:10.3233/AAC-190457.

13.

S.H.

Nielsen and

Parsons, A generalization of Dung’s abstract framework for argumentation: Arguing with sets of attacking arguments, in: International Workshop on Argumentation in Multi-Agent Systems, Springer, 2006, pp. 54–73.