An efficient algorithm of fuzzy reinstatement labelling

1.   Introduction

Dung's theory of argumentation frameworks (abbreviated as AF) ^[1] has been applied in a large variety of fields, ranging from decision-making ^[2,3], non-monotonic reasoning ^[4], multi-agent systems ^[5,6], to law ^[7], voting ^[8], etc. In fuzzy AFs, arguments and/or attacks are assigned fuzzy degrees to capture the uncertainty issued from the partly trusted information in case of incompleteness, ambiguity, vagueness, etc.

A core problem in fuzzy AFs is to explore the fuzzy semantics, i.e., to calculate an acceptable degree for each argument by changing the initial fuzzy degree of the argument. Researchers has proposed a variety of approaches for this aim. Some literature identified the acceptable degrees of arguments by establishing fuzzy semantic systems. For example, ^[9,10] partly accepted the attack relation and defence relation between fuzzy argument sets, and built a fuzzy system including the $x$-conflict-free sets, $y$-admissible sets, $y$-preferred sets, etc.; ^[11] introduced sufficient attacks and weakening acceptability between fuzzy sets of arguments, then established a fuzzy extension system in Dung's way. More works provided algorithms for modifying the degrees based on the investigation of the principles for modifying the degrees of arguments and/or the properties of the accepted degrees.

For instance, ^[12,13,14] investigated more than twenty principles and/or properties, and established several algorithms to calculate the acceptable degrees of arguments. ^[15] introduced three principles and defined a semantics called the fuzzy reinstatement labelling ($FRL)$, which identified a class of acceptable degrees of arguments and has been proven to be a preferred extension in ^[11]. Moreover, ^[15,16] investigated an algorithm named the fuzzy labelling algorithm ($FLAlg$), to calculate the $FRL$ by infinitely approximating the limit of an iteration sequence.

The theory in ^[15,16] not only established the semantic system $FRL$ to identify the acceptability of arguments, but also studied the algorithm $FLAlg$ to calculate the $FRL$. However, the $FLAlg$ can not provide an exact $FRL$. In addition, its complexity not only depends on the number of arguments, but also depends on the accuracy of approximation degrees. When higher accuracy is acquired, the length of the sequence and hence the amount of computation will quickly increase. Therefore, if an algorithm can avoid the process of infinite approximation, its computational complexity will be significantly reduced because it has nothing to do with accuracy. The purpose of this paper is to explore such a new algorithm for $FRL$.

In this paper, firstly, we investigate the limits of the $FLAlg$ for some basic cases of fuzzy AFs, including trees, even cycles, and odd cycles. Exact values of the limit are provided for such fuzzy AFs instead of the approximation proposed by $FLAlg$. Then, we give a new algorithm of $FRL$: A fuzzy AF is divided into simple subframes along strongly connected components (SCCs). Every subframe on different SCCs is calculated separately. And the final result for $FRL$ is obtained by combining the values in the subframes.

The efficiency of the new algorithm is embodied in two aspects. First, an exact limit of the $FLAlg$ is provided directly for trees, odd cycles, and even cycles by the theorems in Section 3. In particular, for the trees and odd cycles, the infinite approximation process is avoided; and for the even cycles, the infinite approximating process is converted into a finite process by adding a stop condition in Theorem 5 (2). Second, for the complex fuzzy AFs, the complexity of the new algorithm decreases with the reduction of the number of arguments: The limit of the $FLAlg$ for simple subframe can be obtained directly; and the values of complicated subframe, whose arguments are less, is computed by the $FLAlg$.

The contents are arranged as follows. Section 2 reviews some basic concepts of fuzzy AFs. In Section 3, we provide some calculation methods for some basic cases of fuzzy AFs, including trees, odd cycles, and even cycles. In Section 4, the efficient algorithm of fuzzy reinstatement labelling is provided. In Section 5, we show the relationship between the fuzzy reinstatement labelling and the preferred semantics in ^[11]. Finally, we conclude this paper.

2.   Fuzzy labellings of da Costa Pereira et al.

In this section, we will review some related background knowledge in the paper ^[15] by da Costa Pereira et al.

The uncertainty in da Costa Pereira et al.'s framework comes from the trustworthiness of the source proposing the piece of information (argument).

Definition 1. A fuzzy AF in ^[15] is a tuple $\langle\mathcal{A}, \rightarrow \rangle$, where $\mathcal{A}\colon Args\rightarrow [0, 1]$ assigns a trust degree to each argument in $Args$, and $\rightarrow$ is a crisp set of attacks between the arguments in $Args$.

Denote $src(A)$ the set of the sources of $A$. The value of $\mathcal{A}(A)$ is shown below,

where $\tau_s$ is the degree to which the source $s\in src(A)$ is trusted.

Definition 2. (Fuzzy AF-labelling) Let $\langle\mathcal{A}, \rightarrow \rangle$ be a fuzzy argumentation framework. A fuzzy AF-labelling is a total function $\alpha\colon\mathcal{A}\rightarrow [0, 1]$.

In fact, there are many argumentation systems similar to the above models, such as ^{[12,13,17,18,19]}. And in this paper, we take da Costa Pereira's model as an example to illustrate our algorithm.

In order to explore the acceptability of arguments, two intuitive postulates are introduced in ^[15]:

● The acceptability of an argument should not be greater than the degree to which the arguments attacking it are unacceptable:

● An argument cannot be more acceptable than the degree to which its sources are trusted:

Definition 3. (Fuzzy reinstatement labelling) Let $\alpha$ be a fuzzy AF-labelling. It is said that $\alpha$ is a fuzzy reinstatement labelling iff, for each argument $A$,

The definition of fuzzy reinstatement labelling is very similar to a preferred semantics, which indicates that an agent should accept as large as possible trust degree of argument. Naturally, the acceptable degree of each argument cannot be greater than the initial degree of trust. In the meantime, intuitively, the acceptable degree of each argument cannot be greater than the complement of defeated degree which is defeated. It seems as $B$ is defeated by $A$ and $A$ is accepted, then $B$ is unacceptable. Also in Caminada's labelling theory ^[20], if $Lab(A) = in$ and $A$ attacks $B$, then $Lab(B) = out$. So the arguments with a defeated degree are futile since they are defeated by accepted arguments. Therefore, the belief degree of argument cannot be greater than the complement degree of defeated degree, namely $\alpha(A)\leq 1-\max_{B\colon B\rightarrow A}\alpha(B)$.

In order to define admissible labelling, the absence of illegally labeled arguments is required. In fact, some arguments may be illegally labeled, i.e. $\alpha(A)\neq\min\{\mathcal{A}(A), 1-\max_{B\colon B\rightarrow A}\alpha(B)\}$. Inspired by Caminada's idea in ^[21], a fuzzy labelling algorithm for calculating fuzzy reinstatement labelling is provided. The way of changing the illegal label of an argument, without creating other illegally labeled arguments, is introduced as follows.

Definition 4. (The fuzzy labelling algorithm ($FLAlg$), Definition 12 on Page 5 of ^[15]) Let $\alpha_t$ be a fuzzy labelling. An iteration in $\alpha_t$ is carried out by computing a new labelling $\alpha_{t+1}$ for all arguments $A$ as follows:

where $\alpha_0(A) = \mathcal{A}(A)$.

Note that Eq (2.1) guarantees that $\alpha_t(A)\leq\mathcal{A}(A)$ for all arguments $A$ and each $t$. This definition defines a sequence $\{\alpha_t\}_{t = 0, 1, ...}$ of labellings.

Theorem 1. (Theorem 1 in ^[15])The sequence $\{\alpha_t\}_{t = 0, 1, ...}$ defined above converges.

Then the limit of $\alpha_t(A)$ is the fuzzy reinstatement labelling of $A$, i.e. $\alpha(A) = \lim_{t\rightarrow \infty}\alpha_t(A)\in[0, 1]$. da Costa Pereira et al. ^[15] show that the convergence speed of the labelling algorithm is linear (as their proof of convergence suggests).

In the following sections, we will find a way to calculate the exact values of $\alpha$ for some special cases, instead of approaching it by $\alpha_t$.

3.   Limits of the $FLAlg$ in some special fuzzy AFs

This section further studies the $FLAlg$, and presents its limits for some particular fuzzy AFs: (1) The trees ^[22]---the fuzzy AFs without cycles, (2) the cycles with odd/even number of nodes.

In a fuzzy AF, if a set of arguments $A_1, A_2, ..., A_n$ satisfies that $(A_i, A_{i+1})\in \rightarrow$, for $i = 1, 2, ..., n$, and $(A_n, A_1)\in \rightarrow$, then we call it a cycle in the fuzzy AF. Intuitively, a cycle is the following graph.

Moreover, if $n$ is odd, the cycle is called an odd cycle; and if $n$ is even, the cycle is called an even cycle.

3.1.   Limits of $FLAlg$ in trees

In the previous literature, there are amounts of related work that concentrates on the semantics of uncertain AFs without circles, such as ^[13,17,23]. In their papers, under the uncertain argumentation settings, every argument may have a basic strength, which is expressed as the weight of the argument. In this paper, the weight is represented by fuzzy degrees. Generally speaking, the exploitation of the semantics of acyclic argument frameworks is a basic requirement. An acyclic fuzzy AF is formed as Figure 1, we intend to directly obtain the exact limit of these arguments rather than continuously approaching the limit of the iteration sequence in Definition 4.

We first introduce some notations, for an argument $A\in Args$, denote the set $\{B\in Args\colon (B, A)\in \rightarrow \}$ by att(A). And for a set $S\subseteq Args$ of arguments, denote the set $\{B\in Args\colon \exists A\in S \; {\rm{ s.t. }}\; (B, A)\in \rightarrow \}$ by att(S).

First, we calculate the $FRL$ for some simple cases, which will be helpful to understand the main calculation theorem. If an argument is not attacked, it is reasonable to maintain its initial value. Then we have the next lemma.

Lemma 1. Suppose $A$ is an argument in a fuzzy AF $\langle\mathcal{A}, \rightarrow \rangle$, with $att(A) = \emptyset$.Then $\lim_{t\rightarrow \infty}\alpha_t(A) = \mathcal{A}(A)$.

If an argument $B$ is attacked by an argument $A$ with $\mathcal{A}(A)+\mathcal{A}(B)\leq1$, then we can ignore the influence of $A$ on $B$. In this case, the $FRL$ of $B$ also should keep its initial value. This can be summarised as the next lemma.

Lemma 2. If $att(B) = \{A\}$, with $\mathcal{A}(A)+\mathcal{A}(B)\leq1$, then $\alpha_t(B) = \mathcal{A}(B)$ for all $t = 0, 1, ...$Therefore,

Another simple case is that $B$ is attacked by only one argument $A$, which is not attacked. In this case, the $FRL$ of $B$ is either $\mathcal{A}(B)$ or $1-\mathcal{A}(A)$. And we get the next lemma.

Lemma 3. Suppose $att(B) = \{A\}$ and $att(A) = \emptyset$ in a fuzzy AF $\langle\mathcal{A}, \rightarrow \rangle$. The limit of $\alpha_t(B)$ is the minimum of $\mathcal{A}(B)$ and $1-\mathcal{A}(A)$, i.e.$\lim_{t\rightarrow \infty}\alpha_t(B) = \min\{\mathcal{A}(B), 1-\mathcal{A}(A)\}$.

Proof. See Appendix A.1.

As we know, for any $A\in\mathcal{A}$, $\alpha_t(A)$ always converges. The following theorem shows that if an argument $B$ has only one attacker $A$, then the limits of $B$ is the minimum of $\mathcal{A}(B)$ or $1-\alpha(A)$.

Theorem 2. Suppose $att(B) = \{A\}$ and $\lim_{t\rightarrow \infty}\alpha_t(A) = a$.Then the limit of $\alpha_t(B)$ is the minimum of $\mathcal{A}(B)$ and $1-a$, i.e.

Proof. See Appendix A.2.

Example 1. Consider the AF in the form of attack sequence $A_0\rightarrow A_1 \rightarrow A_2\rightarrow... \rightarrow A_n$. By Theorem 3.1, if for each $A_i$, $i = 0, 1, ..., n$, the initial labelling $\mathcal{A}(A_i)$ is big enough, the limits of them will be $a, 1-a, a, 1-a, ...$, where $a = \mathcal{A}(A_0)$.

For an attack sequence $A_0\rightarrow A_1 \rightarrow A_2\rightarrow...$, if we calculate the arguments one by one according to Theorem 3.1, we can obtain the next result.

Proposition 1. Given an attack sequence $A_0\rightarrow A_1 \rightarrow A_2\rightarrow...$, if for some $i_0\in N$, $\mathcal{A}(A_{i_0}) \leq \min_{j\colon j < i_0} \{1-\mathcal{A}(A_j), \mathcal{A}(A_j)\}$, then

Proof. See Appendix A.3.

Theorem 2 can be extended to the next theorem, which is the main result of this subsection and computes the $FRL$ of nodes in acyclic fuzzy AF.

Theorem 3. (Calculation theorem for acyclic nodes) In a fuzzy AF $\langle\mathcal{A}, \rightarrow \rangle$, if $att(B) = \{A_1, ..., A_n\}$ and $\alpha(A_i)$, $i = 1, 2, ..., n$, are already obtained, then

Proof. See Appendix A.4.

Example 2. Let $\langle\mathcal{A}, \rightarrow \rangle$ be a fuzzy AF with $\mathcal{A} = \{(A, 0.3),$ $(B, 0.6),$ $(C, 0.7),$ $(D, 0.8),$ $(E, 0.8)\}$ and $\rightarrow = \{A\rightarrow B, B\rightarrow C, C\rightarrow E, A\rightarrow D, D\rightarrow E\}$.

The fuzzy reinstatement labelling of each argument can be calculated as follows:

From Lemma 1,

By Theorem 2, we can get

By Theorem 3, we have

3.2.   Limits of $FLAlg$ in cycles

Now, we deal with fuzzy AFs of odd circles and even circles.

We first introduce some notations. Given a cycle $A_1\rightarrow A_2\rightarrow...\rightarrow A_n\rightarrow A_1$, by Theorem 1, for any $1\leq i\leq n$, $\alpha(A_i)$ always exists. And we denote $\alpha(A_i) = a_i$. Given a finite set of arguments $\{A_1, ..., A_n\}$, there must be some $i_0\in\{1, 2, ..., n\}$ s.t. $\mathcal{A}(A_{i_0}) = \min_{i = 1, ..., n}\mathcal{A}(A_i)$. When $\{A_1, ..., A_n\}$ is a cycle, even or odd, without loss of generality, we can suppose $i_0 = 1$, i.e., $\mathcal{A}(A_1) = \min_{i = 1, ..., n}\mathcal{A}(A_i)$.

The fuzzy reinstatement labelling of odd cycles can be calculated by the following theorem.

Theorem 4. (Calculation theorem for odd circle) Suppose $\langle\mathcal{A}, \rightarrow \rangle$ is a fuzzy AF in the form of an odd cycle, like $A_1\rightarrow A_2\rightarrow...\rightarrow A_n\rightarrow A_1$.Without loss of generality, we may assume that $\mathcal{A}(A_1) = \min_{i = 1, ..., n} \mathcal{A}(A_i)$.Let $a = \mathcal{A}(A_1)$.

(1) If $a < 0.5$, the fuzzy reinstatement labelling can be calculated as the line

(2) If $a\geq 0.5$, all the fuzzy reinstatement labellings are 0.5, i.e., $\alpha(A_i) = 0.5$, for all $1\leq i \leq n$.

Proof. See Appendix A.5.

Example 3. Consider $AF = \{A\rightarrow B\rightarrow C \rightarrow A\}$. If $\mathcal{A}(A) = 1, \mathcal{A}(B) = 0.8, \mathcal{A}(C) = 0.7$, then by Theorem 4, $\alpha(A) = \alpha(B) = \alpha(C) = 0.5$.

If $\mathcal{A}(A) = 4, \mathcal{A}(B) = 0.8, \mathcal{A}(C) = 0.7$, then by Theorem 4, $\alpha(A) = \alpha(C) = 0.4$ and $\alpha(B) = 0.6$.

Now, let's consider the even cycles.

Theorem 5. (Calculation theorem for even circle) Let $\langle\mathcal{A}, \rightarrow \rangle$ be fuzzy AF in form of an even cycle:

Suppose $m_1 = \min_{i = 1, ..., n}\{\mathcal{A}(A_{2i-1})\} = \mathcal{A}(A_1)$and $m_2 = \min_{i = 1, ..., n}\{\mathcal{A}(A_{2i})\} = \mathcal{A}(A_{2i_0})$, for some $i_0\leq n$.

(1) If $m_1+m_2\leq1$, then the reinstatement labellings can be calculated as a line

(2) If $m_1+m_2 > 1$, then there must exist some $N\in\mathbb{N}$, such that $\forall t\geq N$, $\alpha_t(A_{2i-1})\in(1-m_2, m_1)$, and $\alpha_t(A_{2i})\in(1-m_1, m_2)$, $\forall i = 1, 2, ..., n$.And the reinstatement labellings can be calculated as follows: For any $i\in \{1, 2, ..., n\}$,

Moreover, $\sum_{i = 1}^{2n}\alpha(A_i) = n$.

From the supposition $\mathcal{A}(A_1) = \min_{i = 1, 2, ..., 2n}\mathcal{A}(A_i)$, we have $m_1\leq m_2$. In other words, given an even cycle, the line in Eq (3.1) is started from the least element of the even cycle.

Proof. See Appendix A.6.

Corollary 1. For the case $m_1+m_2 > 1$ in Theorem 5, suppose that for $i\in \{0, 1, 2, ..., n-1\}$,

Then $\alpha$ is a fuzzy reinstatement labelling.

Proof. In this case, let $N = 1$, then from the proof of Theorem 5, it is valid.

It should be emphasized that the result of Theorem 5 coincides with the exact value of the limit of da Costa Pereira's $FLAlg$ while the result of Corollary 1 is not. But the result of Corollary 1 satisfies the requirement of fuzzy reinstatement labelling in Definition 3. Namely, the result of Corollary 1 also can be regarded as a reasonable fuzzy reinstatement labelling.

Example 4. Let $AF = \{A\rightarrow B\rightarrow C \rightarrow D\rightarrow A\}$, and $\mathcal{A}(A) = 1, \mathcal{A}(B) = 0.34, \mathcal{A}(C) = 0.8, \mathcal{A}(D) = 0.3$. Then the fuzzy reinstatement of $A$, calculated by Theorem 5, is 0.78, instead of 0.79, which is calculated by Eq (3.3) in the corollary.

4.   An efficient algorithm of fuzzy reinstatement labelling

The main aim of this section is to propose a new algorithm for fuzzy reinstatement labelling considering a single node, a simple cycle, or a complicated cycle.

In the previous section, we calculated the fuzzy reinstatement labellings for three simple fuzzy AFs: Fuzzy AFs without cycles and fuzzy AFs consisting of odd cycles or even cycles. However, for a general fuzzy AF, it often consists of many simple nodes (not in circles), odd circles, even circles, and complicated circles (including multiple odd circles and even circles). For instance, the fuzzy AF in Figure 2.

It is beyond doubt that the fuzzy AF in Figure 2 can be calculated by the algorithm in Definition 4. However, it should be emphasized that when using the previous fuzzy labelling algorithm $FLAlg$ to calculate each argument, we should always consider the fuzzy labelling of all the attackers, and in turn the attackers of attackers. And thus in the case of arbitrary fuzzy AF, no matter simple nodes, odd circles, even circles, and complicated circles, we need to iteratively use the Eq (2.1) in Definition 4. The complexity of this algorithm is obviously high even for these simple nodes and simple circles. Inspired by Baroni's idea in ^[24], in this section, we will provide a strongly connected components decomposed scheme for a general fuzzy AF. Unlike crisp AFs, the arguments of fuzzy AFs are associated with fuzzy degrees and thus we need to provide some modifications to this scheme. In this partition, each fuzzy AF is partitioned into many sub-frameworks which are simply strongly connected components (abbreviated as SCCs) and each SCC is a single node, odd circle, even circle, or complicated circle. For these single-node SCCs, odd circle SCCs, and even circle SCCs, they will be resolved by our method in Section 3 and complicated circle SCCs are computed by Eq (2.1) in $FLAlg$. It should be stressed that the complexity of $FLAlg$ is positively correlated with the number of arguments. And thus, with the reduction of arguments, those complicated circles sub-frameworks are easily calculated by da Costa Pereira's technology. In this way, each complicated fuzzy AF is partitioned into many simple sub-frameworks whose fuzzy reinstatement labellings can be efficiently computed. Therefore, an efficient algorithm can be provided based on this decomposition.

4.1.   Partition of fuzzy AFs

In this section, we introduce the strongly connected components decomposed for fuzzy AFs. When a fuzzy AF is partitioned into many sub-frameworks, the raised question is that in which condition, the combination fuzzy reinstatement labellings of these sub-frameworks is a fuzzy reinstatement labelling of the original fuzzy AF. Since our partition is based on strongly connected components in graph theory, we first introduce the definition of strongly connected components in fuzzy AFs.

Definition 5. Given a fuzzy AF $\langle\mathcal{A}, \rightarrow \rangle$, the binary relation of path-equivalence between nodes, denoted as $PE_{FAF}\subseteq Args\times Args$, is defined as follows:

● $\forall A\in Args$, $(A, A)\in PE_{FAF}$.

● Given two distinct arguments $A, B\in Args, (A, B)\in PE_{FAF}$ if and only if there is a chain of attack relation from $A$ to $B$ and a chain of attack relation from $B$ to $A$.

Definition 6. The strongly connected components of fuzzy AFs are the equivalence classes of nodes with the belief degree in $\mathcal{A}$ under the relation of path-equivalence. Given a node $A\in Args$, we define the strongly connected component $A$ belongs to is denoted as $SCC_{FAF}(A)$ where $SCC_{FAF}(A) = \{(B, \mathcal{A}(B))\mid (A, B)\in PE_{FAF}\}$. The set of the strongly connected components of fuzzy AF is denoted as $SCCS_{FAF}$.

We extend to strongly connected components the notion of parents, denoting the set of the other strongly connected components that attack a strongly connected component $S$ as $sccparents_{FAF}(S)$.

Definition 7. Given a fuzzy argumentation framework $\langle \mathcal{A}, \rho\rangle$ and a strongly connected component $S\in SCCS_{FAF}$, we define

A strongly connected component S such that $sccparents_{FAF}(S) = \varnothing$ is called initial.

Example 5. In Figure 2, $SCC_1 = \{(A, 0.4)\}$, $SCC_2 = \{(B, 0.8)\}$, $SCC_3 = \{(C, 0.7), (D, 0.8)\}$, $SCC_4 = \{(E, 0.7), (F, 0.9), (G, 0.6)\}$, $SCC_5 = \{(H, 0.6), (L, 0.6), (M, 0.6), (N, 0.6)\}\}$, $SCCS_{FAF} = \{\{(A, 0.4)\}, \{(B, 0.8)\}, \{(C, 0.7),$ $(D, 0.8)\}, \{(E, 0.7), (F, 0.9), (G, 0.6)\}, \{(H, 0.6), (L, 0.6), (M, 0.6), (N, 0.6)\}\}$.

From Definition 3, it shows that the fuzzy reinstatement labelling of each argument is only dependent on the fuzzy reinstatement labellings of its attackers. Thus, according to attack relation, we can draw a partial order of SCCs. For instance, for the fuzzy AF in Figure 2, we can first calculate the fuzzy reinstatement labelling of $A$ and $B$. This step is easy to complete by applying Theorem 3. Then according to the fuzzy reinstatement labelling of $B$, the following SCC ($C$ and $D$) can be calculated by Theorem 5. But, the fuzzy reinstatement labellings of $C$ and $D$ are certainly affected by the fuzzy reinstatement labelling of $B$ from Definition 3. Therefore, the core of the question is how to remove the influence of the previous SCCs on the next SCC. We take the fuzzy AF in Figure 2 as an example.

Example 6. From Theorem 3, we have $\alpha(A) = 0.4$ and $\alpha(B) = 0.6$. Since $B$ attacks $C$ and $\alpha(B) = 0.6$, we have that $B$ with a degree of at least 0.4 is defeated by $C$ and thus the maximum fuzzy reinstatement labelling of $B$ cannot surplus 0.6 from Definition 3. In other words, the defeated degree of $B$ is 0.4. As we have shown in Section 2, the arguments with the defeated degrees are futility since it is defeated by accepted arguments. Therefore, the arguments with defeated degrees form a defeated part which is defeated by the fuzzy reinstatement labellings of their attackers. The maximal possibility of an argument is the extent to which the other arguments fail to refute its truth. Thus, for an SCC, if we remove the defeated part which is affected by their parents, then this SCC is obviously unaffected by its SCC parents. For example, in Figure 2, from that $\alpha(B) = 0.6$ and thus the defeated degree of $C$ w.r.t. $B$ is 0.6. Consequently, $SCC_3$ is modified as $\{(C, 0.4), (D, 0.8)\}$ (see Figure 3). In which, $(C, 0.4)$ is unaffected by $\alpha(B) = 0.6$.

Then by applying Theorem 5, the fuzzy reinstatement labelling of the modified $SCC_3$ is $\alpha(C) = 0.3$ and $\alpha(D) = 0.7$. From that $\alpha(D) = 0.7$, $SCC_4$ is modified as $\{(E, 0.3), (F, 0.9), (G, 0.6)\}$ (see Figure 4).

Then by applying Theorem 4, the fuzzy reinstatement labelling of the modified $SCC_4$ can be directly obtained: $\alpha(E) = 0.3$, $\alpha(F) = 0.7$, and $\alpha(G) = 0.3$. From that $\alpha(F) = 0.7$, $SCC_5$ is modified as $\{(H, 0.3), (L, 0.6), (M, 0.6), (N, 0.6)\}$ (see Figure 5).

Then by applying fuzzy labelling algorithm, the fuzzy reinstatement labelling of the modified $SCC_5$ is $\alpha(H) = 0.3$, $\alpha(L) = 0.6$, $\alpha(M) = 0.4$, and $\alpha(N) = 0.4$.

From the above statement, we can obtain a combination fuzzy reinstatement labelling $\alpha(A) = 0.4$, $\alpha(B) = 0.6$, $\alpha(C) = 0.3$, $\alpha(D) = 0.7$, $\alpha(E) = 0.3$, $\alpha(F) = 0.7$, $\alpha(G) = 0.3$, $\alpha(H) = 0.3$, $\alpha(L) = 0.6$, $\alpha(M) = 0.4$, and $\alpha(N) = 0.4$. From Definition 3, it is easy to verify that the combination labelling is a fuzzy reinstatement labelling of the original fuzzy AF.

From this example, we can see that when a fuzzy AF is partitioned into many simple sub-frameworks by removing the defeated part, the complexity of the computation can be largely decreased. Is this example a coincidence? We will prove that when we partition a general fuzzy AF into many sub-frameworks by our means, the combination labelling is always a fuzzy reinstatement labelling of the original fuzzy AF.

Before the important theorem, we provide some notations.

Definition 8. Given a fuzzy AF $(Args, \rightarrow)$. Suppose $S\in SCCS_{FAF}$ and $\alpha$ be a fuzzy reinstatement labelling of $sccparents(S)$. The defeat part of $S$ is denoted as

Then the residual part is denoted as

Definition 9. Given a fuzzy AF $(Args, \rightarrow)$ and $S\in SCCS_{FAF}$. The sub-frameworks partition of the fuzzy AF along the strongly connected components is processed as follows:

A sub-framework refers to $S$ is defined as

where $\rightarrow_S = \rightarrow \cap (RP_S\times RP_S)$.

From Definitions 8 and 9, it shows that the partition forms a partial order. A modification of the specific SCC is based on its parents.

Suppose $\alpha_1$, $\alpha_2$, $\alpha_3$, ..., $\alpha_n$ are fuzzy reinstatement labellings of these sub-frameworks respectively, then the combination fuzzy reinstatement labelling is defined as follows:

Definition 10. Suppose $\alpha_1$, $\alpha_2$, $\alpha_3$, ..., $\alpha_n$ are fuzzy reinstatement labellings of these sub-frameworks respectively, then the combination labelling $\alpha$ is defined as the disjunction of $\alpha_1$, $\alpha_2$, $\alpha_3$, ..., $\alpha_n$.

Namely for each argument $A\in Args$ and $A\in S_i$, $\alpha(A) = \alpha_i(A)$.

Then the main conclusion is introduced in the following theorem.

Theorem 6. Suppose $\alpha_1$, $\alpha_2$, $\alpha_3$, ..., $\alpha_n$ are fuzzy reinstatement labellings of these sub-frameworks respectively, then the combination labelling $\alpha$ is a fuzzy reinstatement labelling of the original fuzzy AF.

Proof. See Appendix B.

From the above definitions and theorem, we provide a SCC decomposed scheme for fuzzy AF. This method can partition a fuzzy AF into many simple sub-frameworks along with the strongly connected components. And the combination labelling of these sub-frameworks is a fuzzy reinstatement labelling of the original fuzzy AF.

4.2.   Efficient algorithm of fuzzy reinstatement labelling

In this section, we provide the application of our SCC-decomposed method. The application procedure can be summarized as follows:

(1) The fuzzy AF is partitioned into its strongly connected components; they form a partial order which encodes the dependencies existing among them according to the attack relation.

(2) The initial SCCs remain unchanged and are calculated by our method or $FLAlg$; the following SCCs are modified according to the fuzzy reinstatement labelling of their parents SCCs.

(3) When all the sub-frameworks are computed, the fuzzy reinstatement labellings of these sub-frameworks are obtained; the combination of these fuzzy reinstatement labellings is a fuzzy reinstatement labelling of the original fuzzy AF.

The algorithm for the computation of fuzzy reinstatement labelling consists of Algorithms 1 and 2. In Algorithms 1, we process the computation of simple argumentation, which is a single node, a simple circle, or a complicated circle. If fuzzy AF is a single node, then the fuzzy reinstatement labelling is easy to obtain (lines 1–4). Analogously, if fuzzy AF is an odd circle, then the fuzzy reinstatement labelling can be calculated by Theorem 3.3 (lines 5–16). And, if fuzzy AF is an even circle, then the fuzzy reinstatement labelling can be calculated by Theorem 3.4 (lines 17–36). Finally, if fuzzy AF is a complicated circle, then the fuzzy reinstatement labelling can be calculated by the algorithm in Definition 2.1 (lines 37–45). Algorithm 2 implements the partition of a general fuzzy AF. In line 1, the strongly connected components of the fuzzy AF are identified. From ^[25], we have that an algorithm is available, which receives as input a fuzzy AF and returns as output a sequence $(S_1, ..., S_n)$ including the strongly connected components of the fuzzy AF in topological order, i.e. if $\exists A\in Supp(S_i)$, $B\in Supp(S_j)$ such that $A$ attacks $B$ then $i < j$. This can be done in linear time under the number of attacks ^[26]. Hence, if an SCC is initial, then it remains unchanged and be calculated by Algorithms 1. If an SCC is not initial, then it should be modified according to Definition 9. Then Algorithms 1 is again provoked. Finally, the fuzzy reinstatement labelling $\alpha$ is a combination of fuzzy labelling of all the strongly connected components.

Compared to $FLAlg$, our algorithm directly provides an exact value of three types of simple fuzzy AFs---the trees, the even cycles, and the odd cycles. For these simple cases, the infinite approximation process in $FLAlg$ is avoided, and the computational complexity has nothing to do with accuracy. For fuzzy AFs with many simple SCCs, our algorithm effectively puts forward the approximate limit of $FLAlg$ by reducing the number of arguments in the infinite approximation process. But for the complex SCCs including few such simple nodes, our algorithm is not evidently better than the $FLAlg$. As a result, when being applied in other fields, like the multi-agent systems ^[5,27], the input-output systems ^[28,29,30], control theory ^[31,32,33], etc., our algorithm is more suitable for the fuzzy AFs with many simple SCCs, especially for the most common fuzzy AFs---the trees.

5.   Relation to Gödel fuzzy AFs

This section makes a parallel between the fuzzy reinstatement labelling and preferred extension in Gödel fuzzy AFs (abbreviated as GFAF).

In the past sections, we have shown that: Regardless of the too low values,

(1) In sequences, the values of $\alpha(A)$ can be listed as $a, 1-a, a, 1-a...$

(2) In cycles, no matter even or odd, the values of $\alpha(A)$ can be listed as $a, 1-a, a, 1-a...$

(3) For the arguments $A$, which there are no arguments attack, $\alpha(A) = \mathcal{A}(A)$.

Actually, these are also properties of preferred/stable extensions in GFAF. Then we can guess: Fuzzy reinstatement labelling can be seen as a preferred/stable extension. Before proving this result, let's see a lemma first.

Lemma 4. For each argument $A$, $\alpha(A) = \mathcal{A}(A)$ or, there is an argument $B$, which attacks $A$, such that $\alpha(A)+\alpha(B) = 1$.

Proof. See Appendix C.

Theorem 7. Denote a fuzzy set $E$ as $E(A) = \alpha(A), \forall A\in Args$. Then, when considering $\langle\mathcal{A}, \rightarrow \rangle$ as a GFAF, $E$ is a preferred/stableextension.

Proof. If $B$ attacks $A$, then $E(A)+E(B)\leq1$. That is, $E$ is conflict-free.

By Lemma 4, it sufficiently attacks all the arguments in $\mathcal{A}$ out of $E$.

Then it is a stable extension. Thus a preferred extension.

From the above theorem and statement, we can show that the fuzzy reinstatement labelling is a preferred semantics extension of GFAF. And thus our algorithm can also be used to calculate the preferred semantics of GFAF.

6.   Discussion

Fuzzy AFs deal with the uncertain arguments and/or attacks caused by incompleteness, ambiguity, vagueness, etc. The basic method of studying fuzzy semantics is to restore the initial ambiguity and establish fuzzy extensions, such as ^[9,11,14,15]. In recent years, these achievements have been developed in various ways. For example, ^[34] extended the extension method by combining the ranking method. ^[35] considers the inverse problem for gradual semantics: Given an AF and a desired argument ranking, whether there exist initial weights such that a particular semantics produces the given ranking. ^[36] explores the AFs with support in the labelling approach, and introduces a polynomial-time algorithm to execute it. ^[37] redefines the argumentative process and characterises graded entailment of arguments through a label-based framework. Unlike these works, this paper does not introduce any new semantics. On the contrary, an optimized algorithm for the semantics $FRL$ is proposed.

In the previous literature, the decomposition of AFs is usually used to reduce the computational complexity of argument acceptance. For instance, ^[24] first provided the SCC-decomposed scheme for Dung's AFs. ^[38] introduced a decomposition in the context of dynamics AFs, while ^[39] exploited a tree-based decomposition. ^[40,41] proposed a division-based method based on the directionality principle and the SCC-recursiveness principle. ^[25] investigated an SCC-recursive meta-algorithm based on some topology-related properties. In this paper, we have implemented a simple SCC-recursive decomposition on fuzzy AF to reduce the computational complexity of $FRL$.

This work develops the calculation of $FRL$ in two aspects: Firstly, the new algorithm directly provides an exact value of the limits of the algorithm $FLAlg$ for simple fuzzy AFs (including trees, odd cycles and even cycles). Since the new algorithm avoids the infinite approximation process in $FLAlg$, its calculation complexity depends only on the number of the arguments and the structure of the AFs. But it has nothing to do with accuracy. Secondly, this paper modifies the SCC method ^[24] to calculate the fuzzy semantics $FRL$. The results show that this decomposition method is not only suitable for regular AFs, but also suitable for fuzzy AFs, and it may be applied to other quantitative AFs.

There are also some limitations in our method. For the complicated cycles, the exact limit of the $FLAlg$ has not been put forward. This kind of subframe is still calculated by $FLAlg$. Therefore, the new algorithm can only partly solve the infinite approximation process. Especially, for the fuzzy AFs, where most elements are in complicated subframes, this method is not obviously better than the $FLAlg$.

7.   Conclusions

In this paper, we explored the semantics of an uncertain argumentation system---fuzzy AF. We focused on the fuzzy reinstatement labelling of fuzzy AFs. And we provide an efficient algorithm for fuzzy reinstatement labelling. It should be noted that the results of our algorithm are approximate to, but not equal to, the outcomes of $FLAlg$. The main contributions of this paper are listed as follows:

● We provided some results to directly calculate the exact result of the limits of $FLAlg$ for simple fuzzy AFs, like the trees, the odd cycles, and the even cycles.

● We provided a SCC decomposed scheme for fuzzy AF. By this scheme, the semantics of fuzzy AFs can be calculated separately on their SCCs sub-frameworks.

● We provided an effective algorithm for calculating the fuzzy reinstatement labelling in fuzzy AFs. The more SCCs in fuzzy AFs (especially simple nodes and simple circles), the higher the efficiency of the algorithm. The more SCCs (especially simple nodes and simple circles) in fuzzy AFs, the more efficient the algorithm is. And it is also applicable to the preferred semantics of GFAF.

In the future, the SCC decomposition can be applied to other argumentation frameworks, including qualitative argumentation frameworks and quantitative argumentation frameworks, such as GFAF, Janssen's fuzzy AF, and weighted AF. And more topological properties will be investigated for the AFs.

Appendix

A.   Proofs of lemmas and theorems in Section 3

A.1.   Proof of Lemma 3

From Eq (2.1), if $\mathcal{A}(B)\leq1-\mathcal{A}(A)$, Lemma 2 shows $\lim_{t\rightarrow \infty}\alpha_t(B) = \mathcal{A}(B) = \min\{\mathcal{A}(B), 1-\mathcal{A}(A)\}$.

Suppose $\mathcal{A}(B) > 1-\mathcal{A}(A)$. From Eq (2.1), we have

As $t\rightarrow \infty$, $\lim_{t\rightarrow \infty}\alpha_t(B) = 1-\mathcal{A}(A) = \min\{\mathcal{A}(B), 1-\mathcal{A}(A)\}$.

A.2.   Proof of Theorem 3.1

Before the proof of Theorem 2, let's look at Lemma 5.

Lemma 5. Let $\{a_t\}_{t = 0, 1, ...}, \{b_t\}_{t = 0, 1, ...}$ be two convergent sequence in [0, 1]. Then the following two formulas are valid:

Proof. We only prove the first one here, and the second one can also prove the same.

Let $\lim_{t\rightarrow \infty}(a_t) = a, \lim_{t\rightarrow \infty}(b_t) = b$.

If $a < b$, then as $a_t$ converges to $a$ and $b_t$ converges to $b$, there is some natural number $N$, such that $\forall t > N$, $a_t < b_t$, i.e. $\forall t > N,$ $\min\{a_t, b_t\} = a_t$. Therefore,

$a > b$ is similar to the above.

Finally, let's consider the case $a = b$. For any $\varepsilon > 0$, there is some natural number $N$, such that $\forall t > N$, $a-\varepsilon < a_t < a+\varepsilon, b-\varepsilon < b_t < b+\varepsilon$, i.e. $\forall t > N,$ $\min\{a_t, b_t\}\in(a-\varepsilon, a+\varepsilon)$. It is

which ends the proof.

Now, let's show the proof of Theorem 2.

Proof. For convenience, denote $\lim_{t\rightarrow \infty}\alpha_t(A) = a$ and $\lim_{t\rightarrow \infty}\alpha_t(B) = b.$

In Eq 2.1, let $t$ tend to $\infty$ on both sides of = , we can get

Since $\lim_{t\rightarrow \infty}\alpha_t(B) = b$, $\lim_{t\rightarrow \infty}\alpha_t(A) = a$ and $\mathcal{A}(B)$ converges to itself, as a constant sequence. By Lemma 5, we have

which means $b = \frac{1}{2}b+\frac{1}{2}\min\{\mathcal{A}(B), 1-a\}$, i.e. $b = \min\{\mathcal{A}(B), 1-a)\}$.

A.3.   Proof of Proposition 1

Obviously, $\lim_{t\rightarrow \infty}\alpha_t(A_{i_0-1})$ is no bigger than $\max_{j < i_0}\{1-\mathcal{A}(A_j), \mathcal{A}(A_j)\}$. Then

If $\max_{j < i_0}\{1-\mathcal{A}(A_j), \mathcal{A}(A_j)\} = 1-\mathcal{A}(A_{j_0})$ for some $j_0 < i_0$, we have $\mathcal{A}(A_{i_0})+1-\mathcal{A}(A_{j_0})\leq1$, because $\mathcal{A}(A_{i_0})\leq\mathcal{A}(A_{j_0})$.

If $\max_{j < i_0}\{1-\mathcal{A}(A_j), \mathcal{A}(A_j)\} = \mathcal{A}(A_{j_1})$, for some $j_1 < i_0$, we have $\mathcal{A}(A_{i_0})+\mathcal{A}(A_{j_1}) = \mathcal{A}(A_{i_0})+1-(1-\mathcal{A}(A_{j_1}))\leq1$, because $\mathcal{A}(A_{i_0})\leq1-\mathcal{A}(A_{j_1})$.

Therefore, in both cases, we have

i.e. $\mathcal{A}(A_{i_0})\leq1-\lim_{t\rightarrow \infty}\alpha_t(A_{i_0-1})$.

By Theorem 2, $\lim_{t\rightarrow \infty}\alpha_t(A_{i_0}) = \mathcal{A}(A_{i_0})$ is valid.

A.4.   Proof of Theorem 3.2

Let's first look at Lemma 6.

Lemma 6. Suppose part of an AF $\langle\mathcal{A}, \rightarrow \rangle$ is in the form

with $\lim_{t\rightarrow \infty}\alpha_t(A) = a$ and $\lim_{t\rightarrow \infty}\alpha_t(B) = b$. If there are no more arguments in $Args$ attacking $C$, then the limit of $\alpha_t(C)$ equals to the minimum of $\mathcal{A}(C)$, $1-a$ and $1-b$, i.e.

Proof. For convenience, suppose $\lim_{t\rightarrow \infty}\alpha_t(C) = c.$

Let $t$ tend to $\infty$ on both sides of "=" in Eq (2.1),

By Lemma 5, we get

Therefore, $c = \frac{1}{2}c+\frac{1}{2}\min\{\mathcal{A}(C), \min\{1-a, 1-b\}\}$. It equals $c = \min\{\mathcal{A}(C), 1-a, 1-b\}$.

According to Lemma 6, the fuzzy reinstatement labelling of nodes attacked by multiple arguments can be calculated.

Theorem 3 can be proven the same as Lemma 6. Together with Theorem 2, the fuzzy reinstatement labelling of any fuzzy AFs without cycles can be calculated.

A.5.   Proof of Theorem 4

(1) It's only necessary to show $a_1 = \alpha(A_1) = \mathcal{A}(A_1)$.

If $a_1 < a = \mathcal{A}(A_1) < 0.5$, then from Theorem 2, we have $a_2 = \min\{1-a_1, \cal{A}(A_2)\}$. Because $a_1 < a < 0.5$ and $a\leq \cal{A}(A_2)$, we have $a_2\geq a$.

Then $a_3 = \min\{1-a_2, \mathcal{A}(A_3)\}\leq 1-a$. Following, we can get for all odd $i$, $a_i\leq 1-a$ and for all even $i$, $a_i\geq a$.

Particularly, $n$ is odd and $a_n\leq 1-a$. By Theorem 2, we have $a_1\geq 1-a_n\geq 1-(1-a) = a$. Contradiction.

From the fact that $a_1\leq\mathcal{A}(A_1)$, we have $a_1 = \mathcal{A}(A_1)$. Following, all the other limits can be calculated by Theorem 2 step by step.

(2) If $a_1 < 0.5$, we can get $a_2 = \min\{1-a_1, \mathcal{A}(A_2)\}\geq 0.5$ by Theorem 2. Following, $a_3\leq 0.5$, $a_4\geq 0.5$, ..., $a_n\leq 0.5$. Next, we can get $a_1\geq 0.5$. Contradiction. Hence, $a_1\geq 0.5$.

Similarly, we have $a_i\geq 0.5$ for all $i\in\{1, 2, ..., n\}$. It follows that $1-a_i\leq\mathcal{A}(A_i)$, for all $i = 1, 2, ..., n$.

Therefore, for $i = 1, 2, ..., n-1$, $a_{i+1} = \min\{\mathcal{A}(A_i), 1-a_i\} = 1-a_i$; and $a_1 = 1-a_n$. Because $n$ is odd, the unique solution is $a_1 = a_2 = ... = a_n = 0.5$.

A.6.   Proof of Theorem 5

(1) It is only necessary to show that $\alpha(A_1) = \mathcal{A}(A_1)$.

From $a_{2i_0}\leq \mathcal{A}(A_{2i_0}) = m_2$, we have $1-a_{2i_0}\geq 1-m_2\geq m_1$. Together with $\mathcal{A}(A_{2i_0+1})\}\geq m_1$, we get $a_{2i_0+1} = \min\{1-a_{2i_0}, \mathcal{A}(A_{2i_0+1})\}\geq m_1$. Next, we can get $a_{2i_0+2} = \min\{1-a_{2i_0+1}, \mathcal{A}(A_{2i_0+2})\}\leq 1-m_1$. Similarly, for all $i\geq i_0$, $a_{2i}\leq 1-m_1$. Particularly, $a_{2n}\leq 1-m_1$.

By Theorem 2, we have $a_1 = \min\{1-a_{2n}, \mathcal{A}(A_1)\} = m_1$.

(2) It can be obtained by the following four lemmas, i.e. Lemmas 7–10.

Before proving the case (2), let's show some facts.

Lemma 7. There exists some natural number $N\in\mathbb{N}$, such that $\forall t\geq N$, $\alpha_t(A_{2i+1})\in(1-m_2, m_1)$, and $\alpha_t(A_{2i})\in(1-m_1, m_2)$, $\forall i = 0, 1, ..., n-1$.

Proof. Because $m_1+m_2 > 1$, we have $1-m_1 < m_2\leq \mathcal{A}(A_{2i})$ and $1-m_2 < m_1\leq \mathcal{A}(A_{2i-1})$, for all $i = 1, 2, ..., n$. It just needs to show that, $\forall i = 0, 1, ..., n-1$

Obviously, the limits are in $[1-m_2, m_1] \; {\rm{ and }}\; [1-m_1, m_2].$ The rest is to show $lim_{t\rightarrow \infty}\alpha_t(A_{2i+1})\neq m_1 \; {\rm{ and }}\; lim_{t\rightarrow \infty}\alpha_t(A_{2i})\neq m_2.$

If not, suppose $lim_{t\rightarrow \infty}\alpha_t(A_{2i+1}) = m_1$, then $lim_{t\rightarrow \infty}\alpha_t(A_{2i}) = 1- m_1.$ Given another $AF' = (\mathcal{A'}, \rightarrow)$, with the same arguments and attack relations of $AF$. But the initial value of $A_k, k = 0, 1, ..., 2n-1,$ is $\mathcal{A'}(A_k) = \mathcal{A}(A_{k-1})$ (for simplicity, we denote $A_{-1} = A_{2n-1}$, and the same goes for the rest of the paper). Consequently, the value of $\alpha(A_{2i+1})$ should be $m_2$, which does not equal to $1-m_1$. Contradiction.

Lemma 8. There is some natural number $N\in\mathbb{N}$, such that

Proof. By Lemma 7, there is some $t_0\in\mathbb{N}$, such that $\forall i = 0, 1, ..., n-1$, $\alpha_{t_0}(A_{2i+1})+m_2 > 1$, and $\alpha_{t_0}(A_{2i})+m_1 > 1$. It follows that for all $i = 0, 1, ..., n-1$,

Sum both sides of both equations for all $i = 0, 1, ..., n-1$, we can obtain

Let $N = t_0+1$, the proof ends.

Lemma 9. Let $N\in \mathbb{N}$ such that $\forall t\geq N, \sum_{k = 0}^{2n-1}\alpha_t(A_k) = n.$

And suppose

Then for all $t\geq N$,

Proof. From Lemma 8, clear for $t = N$. And by summing both sides of the Eqs A.3 separately, we can get that for $t+1$ the results hold.

Lemma 10. Let $N\in \mathbb{N}$ such that $\forall t\geq N, \sum_{k = 0}^{2n-1}\alpha_t(A_k) = n.$ Then for all $t\geq N$, $\exists i_{1t}, i_{2t}, j_{1t}, j_{2t}$, such that $\alpha_t(A_{2i_{1t}})\leq x$, $\alpha_t(A_{2i_{2t}})\geq x$, $\alpha_t(A_{2j_{1t}+1})\leq y$ and $\alpha_t(A_{2j_{2t}+1})\geq y$.

Proof. Obvious from Lemma 9.

The proof of Theorem 5 is clear by the above lemmas and the first part of Theorem 5.

B.   Proof of Theorem 4.1 in Section 4

We only need to prove that the combination labelling $\alpha$ satisfies the equation in Definition 3. Namely for each argument $A$,

If $A\in S_i = SCC_i$ and $\alpha(A)\neq\mathcal{A}(A)$, then we only need to prove that $\alpha(A) = 1-\max_{B\colon B\rightarrow A}\alpha(B)$. From that $\alpha_1$, $\alpha_2$, $\alpha_3$, ..., $\alpha_n$ is a fuzzy reinstatement labelling of these sub-frameworks respectively and $\alpha$ is a combination labelling, we have that $\alpha(A) = \alpha_i(A) = \min\{RP_{S_i}(A), 1-\max_{B\colon B\rightarrow A}\alpha(B)\}$. If $\alpha_i(A) = 1-\max_{B\colon B\rightarrow A}\alpha(B)$, then the prove is complete. Otherwise, if $\alpha_i(A) = RP_{S_i}(A)$, then from Definition 8, $\alpha_i(A) = RP_{S_i}(A) = min\{\mathcal{A}(A), 1-DP_{S_i}(A)\}$. Since $\alpha_i(A) = \alpha(A)\neq \mathcal{A}(A)$, we have $\alpha(A) = \alpha_i(A) = 1-DP_{S_i}(A)$. Again utilizing Definition 8, $DP_{S_i} = \{(A, a)\mid a = \max_{B:B\rightarrow A}\alpha(B) \; {\rm{ where }}\; B\in sccparents(S_i)\}$ and thus $\alpha(A) = \alpha_i(A) = 1-DP_{S_i}(A) = 1-\max_{B\colon B\rightarrow A}\alpha(B)$. As a result, $\alpha(A) = 1-\max_{B\colon B\rightarrow A}\alpha(B)$. The proof is complete.

C.   Proof of Lemma 4 in Section 5

If not, i.e. $\alpha(A) < \mathcal{A}(A)$ and for any $B$, which attacks $A$, $\alpha(A)+\alpha(B) < 1$. Let's deduce some contradictions.

Denote $b = \max\{\alpha(B)\colon B\; attacks\; A\}$, and

Because $\alpha_t(A), t = 1, 2, ...$ is convergent to $\alpha(A)$, for all arguments $A$, there is a natural number $N$, such that $\forall t > N$, $\alpha_t(A) > \alpha(A)-\epsilon$ and $\alpha_t(B) < b+\epsilon$, for any $B$ attacks $A$. Then,

By the definition of $\epsilon$, $\min\{1-b-\epsilon, \mathcal{A}(A)\} > \alpha(A)+3\epsilon$, which means

contradiction.

Conflict of interest

The authors declare no conflicts of interest.