The proofs

In this section, we give the proofs of all the properties presented in Sections 3 and 4.

Proof
(of Property 1) By induction from $V_{\mbox{\scriptsize Min}} \leq g(V_{\mbox{\scriptsize Max}}) < V_{\mbox{\scriptsize Max}}$ and by applying function $g$ twice.$\Box$

Proof
(of Property 2) The valuation function $v$ associates each argument $A$ with a value $v(A)$ belonging to a set $V$ which is a subset of a completely ordered set $W$.$\Box$

Proof
(of Property 3) Let ${\mathcal{C}}= A_n-A_{n-1}-\ldots-A_2-A_1$ be a cycle:

• If $n$ is even: $n = 2k$ and $v(A_1) = g(v(A_2)) = \ldots = g^{2k-1}(v(A_{2k})) = g^{2k}(v(A_1))$; so, $v(A_1)$ is a fixpoint of $g^{2k} = g^n$. It is the same for each $A_i$, $1 \leq i \leq 2k$.

  However, the $A_i$ may have different values: for example, for $n=2$, with the valuation of [13], $v(A_1) = +$ and $v(A_2) = -$ with $g(+) = -$ and $g(-) = +$. If all the $A_i$ have the same value, then this value will be a fixpoint of $g$ (because $v(A_1) = g(v(A_2)) = g(v(A_1))$).

• If $n$ is odd: $n = 2k+1$ and $v(A_1) = g(v(A_2)) = \ldots = g^{2k}(v(A_{2k+1})) = g^{2k+1}(v(A_1))$; so, $v(A_1)$ is a fixpoint of $g^{2k+1} = g^n$. It is the same for each $A_i$, $1 \leq i \leq 2k+1$.

  Since the function $g$ is non-increasing, the function $g^{2k+1}$ is also non-increasing and we can apply the following result: ``if a non-increasing function has fixpoints, these fixpoints are identical''³⁰. So, $v(A_1) = \ldots = v(A_{2k+1})$. But, $v(A_1) = g(v(A_2)) = g(v(A_1))$, so $v(A_1)$ is a fixpoint of $g$.

  So, for all the $1 \leq i \leq 2k+1$, $v(A_i)$ is a fixpoint of $g$.

$\Box$

Proof
(of Property 4)
P1 is satisfied because: $\forall A \in {\mathcal{A}}$, if $A$ has no direct attacker ( ${\mathcal{R}}^-(A)$ is empty), then $v(A) = V_{\mbox{\scriptsize Max}}$ and $g(V_{\mbox{\scriptsize Max}}) < V_{\mbox{\scriptsize Max}}$.

P2 is satisfied because if ${\mathcal{R}}^-(A) = \{A_1, \ldots, A_n\}$, $h (v(A_1),\ldots, v(A_n))$ evaluates the ``direct attack'' of $A$.

P3 is satisfied because the function $g$ is supposed to be non-increasing.

P4 is satisfied due to the properties of the function $h$.$\Box$

Proof
(of Property 5) The valuation proposed by [13] is the following:

Let ${<}{\mathcal{A}}, {\mathcal{R}}{>}$ be an argumentation system. A complete labelling of ${<}{\mathcal{A}}, {\mathcal{R}}{>}$ is a function $Et: {\mathcal{A}}\to \{+, ?, -\}$ such that:

1. If $Et(A) \in \{ ?, -\}$ then $\exists B \in {\mathcal{R}}^-(A)$ such that $Et(B) \in \{+, ?\}$
2. If $Et(A) \in \{+, ?\}$ then $\forall B \in {\mathcal{R}}^-(A)$ or $\in {\mathcal{R}}^+(A)$, $Et(B) \in \{ ?, -\}$

Moreover, [13] also defines a complete rooted labelling $Et$ with: $\forall A \in {\mathcal{A}}$, if $Et(A) = -$ then $\exists B \in {\mathcal{R}}^-(A)$ such that $Et(B) = +$.

The translation of $Et$ into a local gradual valuation is very easy:

$g$ is defined by $g(-) = +$, $g(+) = -$, $g( ?) = ?$ and $h$ is the function $\max$.$\Box$

Proof
(of Property 6) [4] introduces the following function $Cat$ (in the context of ``deductive'' arguments and for an acyclic graph):

• if ${\mathcal{R}}^-(A) = \emptyset$, then $Cat(A) = 1$
• if ${\mathcal{R}}^-(A) \neq \emptyset$ with ${\mathcal{R}}^-(A) = \{A_1, \ldots, A_n\}$, $Cat(A) = \frac{1}{1 + Cat(A_1) + \ldots + Cat(A_n)}$

The translation of $Cat$ into a gradual valuation is: $V = [0,1]$, $W = [0, \infty[$, $V_{\mbox{\scriptsize Min}} = 0$ and $V_{\mbox{\scriptsize Max}} = 1$ and $g: W \to V$ is defined by $g(x) = \frac{1}{1 + x}$ and $h$ is defined by $h(\{x_1, \ldots, x_n\}) = x_1 + \cdots + x_n$.$\Box$

Proof
(of Property 7) Let $t=(x_1, \ldots, x_n, \ldots)$, $t'=(y_1, \ldots, y_n, \ldots)$, $t''=(z_1, \ldots, z_n, \ldots)$ be tuples.

Commutativity of $\star$: $t \star t' = t' \star t$

There are two cases:

• if $t$ or $t'$ $=$ $0^{\infty}$, the property is given by Definition 8.
• if $t$ and $t'$ $\neq$ $0^{\infty}$:
  $$\begin{eqnarray*} % latex2html id marker 1303t \star t' & = & {\mbox{\tt Sort... ...s, y_n, \ldots, x_1, \ldots, x_n, \ldots) \\ & = & t' \star t \end{eqnarray*}$$
  
  
  
  

Associativity of $\star$: $(t \star t') \star t'' = t \star (t' \star t'')$

There are two cases:

• if $t$ or $t'$ or $t''$ $=$ $0^{\infty}$, we can simplify the expression. For example, if $t = 0^{\infty}$:
  $$\begin{eqnarray*} (t \star t') \star t'' & = & t' \star t'' \\ & = & t \star (t' \star t'') \end{eqnarray*}$$
  
  
  
  

• if $t$, $t'$ and $t''$ $\neq$ $0^{\infty}$:
  $$\begin{eqnarray*} % latex2html id marker 1312(t \star t') \star t'' & = & {\m... ...s, z_1, \ldots, z_n, \ldots) \\ & = & t \star (t' \star t'') \end{eqnarray*}$$
  
  
  
  

Property of $\oplus$: $(t \oplus k) \oplus k' = t \oplus (k + k')$

We have:

$$\begin{eqnarray*} (t \oplus k) \oplus k' & = & (x_1 + k, \ldots, x_n + k, \ldot... ... + k', \ldots, x_n + k + k', \ldots) \\ & = & t \oplus (k+k') \end{eqnarray*}$$

Distributivity: $(t \star t') \oplus k = (t \oplus k) \star (t' \oplus k)$

We have:

$$\begin{eqnarray*} % latex2html id marker 1317(t \star t') \oplus k & = & {\mb... ..., x'_n + k, \ldots) \\ & = & (t \oplus k) \star (t' \oplus k) \end{eqnarray*}$$

$\Box$

Proof
(of Property 9) First, we show that the relation $\succeq$ defined by Algorithm 1 is a partial ordering:

Let $u$, $v$, $w$ be three tupled values, the relation $\succeq$ defined by Algorithm 1 is:

• reflexive: $u \succeq u$ because $u = u$, so $u \succeq u$ AND $u \succeq u$ (case 1 of Algorithm 1);
• transitive: suppose that $u \succeq v$ and $v \succeq w$ and consider all the possible cases:
  • if $u = v$:
    • if $v = w$: then $u = w$ so $u \succeq w$,
    • if $\vert v_i\vert \leq \vert w_i\vert$ AND $\vert v_p\vert > \vert w_p\vert$: then $\vert v_i\vert = \vert u_i\vert \leq \vert w_i\vert$ AND $\vert v_p\vert = \vert u_p\vert > \vert w_p\vert$, so $u \succeq w$,
    • if $\vert v_i\vert < \vert w_i\vert$ AND $\vert v_p\vert \geq \vert w_p\vert$: then $\vert v_i\vert = \vert u_i\vert < \vert w_i\vert$ AND $\vert v_p\vert = \vert u_p\vert \geq \vert w_p\vert$, so $u \succeq w$,
    • if $\vert v_i\vert = \vert w_i\vert$ AND $\vert v_p\vert = \vert w_p\vert$ AND $v_p \leq_{lex\infty} w_p$ AND $v_i \geq_{lex\infty} w_i$: then $\vert v_i\vert = \vert u_i\vert = \vert w_i\vert$ AND $\vert v_p\vert = \vert u_p\vert = \vert w_p\vert$ AND $v_p = u_p \leq_{lex\infty} w_p$ AND $v_i = u_i \geq_{lex\infty} w_i$, so $u \succeq w$;

  • if $\vert u_i\vert \leq \vert v_i\vert$ AND $\vert u_p\vert > \vert v_p\vert$:
    • if $v = w$: then $\vert u_i\vert \leq \vert v_i\vert = \vert w_i\vert$ AND $\vert u_p\vert > \vert v_p\vert = \vert w_p\vert$ so $u \succeq w$,
    • if $\vert v_i\vert \leq \vert w_i\vert$ AND $\vert v_p\vert > \vert w_p\vert$: then $\vert u_i\vert \leq \vert v_i\vert \leq \vert w_i\vert$ AND $\vert u_p\vert > \vert v_p\vert > \vert w_p\vert$, so $u \succeq w$,
    • if $\vert v_i\vert < \vert w_i\vert$ AND $\vert v_p\vert \geq \vert w_p\vert$: then $\vert u_i\vert \leq \vert v_i\vert < \vert w_i\vert$ AND $\vert u_p\vert > \vert v_p\vert \geq \vert w_p\vert$, so $u \succeq w$,
    • if $\vert v_i\vert = \vert w_i\vert$ AND $\vert v_p\vert = \vert w_p\vert$: then $\vert u_i\vert \leq \vert v_i\vert = \vert w_i\vert$ AND $\vert u_p\vert > \vert v_p\vert = \vert w_p\vert$, so $u \succeq w$;

  • if $\vert u_i\vert < \vert v_i\vert$ AND $\vert u_p\vert \geq \vert v_p\vert$:
    • if $v = w$: then $\vert u_i\vert < \vert v_i\vert = \vert w_i\vert$ AND $\vert u_p\vert \geq \vert v_p\vert = \vert w_p\vert$ so $u \succeq w$,
    • if $\vert v_i\vert \leq \vert w_i\vert$ AND $\vert v_p\vert > \vert w_p\vert$: then $\vert u_i\vert < \vert v_i\vert \leq \vert w_i\vert$ AND $\vert u_p\vert \geq \vert v_p\vert > \vert w_p\vert$, so $u \succeq w$,
    • if $\vert v_i\vert < \vert w_i\vert$ AND $\vert v_p\vert \geq \vert w_p\vert$: then $\vert u_i\vert < \vert v_i\vert < \vert w_i\vert$ AND $\vert u_p\vert \geq \vert v_p\vert \geq \vert w_p\vert$, so $u \succeq w$,
    • if $\vert v_i\vert = \vert w_i\vert$ AND $\vert v_p\vert = \vert w_p\vert$: then $\vert u_i\vert < \vert v_i\vert = \vert w_i\vert$ AND $\vert u_p\vert \geq \vert v_p\vert = \vert w_p\vert$, so $u \succeq w$;

  • if $\vert u_i\vert = \vert v_i\vert$ AND $\vert u_p\vert = \vert v_p\vert$ AND $u_p \leq_{lex\infty} v_p$ AND $u_i \geq_{lex\infty} v_i$:
    • if $v = w$: then $\vert u_i\vert = \vert v_i\vert = \vert w_i\vert$ AND $\vert u_p\vert = \vert v_p\vert = \vert w_p\vert$ AND $u_p \leq_{lex\infty} v_p = w_p$ AND $u_i \geq_{lex\infty} v_i = w_i$ so $u \succeq w$,
    • if $\vert v_i\vert \leq \vert w_i\vert$ AND $\vert v_p\vert > \vert w_p\vert$: then $\vert u_i\vert = \vert v_i\vert \leq \vert w_i\vert$ AND $\vert u_p\vert = \vert v_p\vert > \vert w_p\vert$, so $u \succeq w$,
    • if $\vert v_i\vert < \vert w_i\vert$ AND $\vert v_p\vert \geq \vert w_p\vert$: then $\vert u_i\vert = \vert v_i\vert < \vert w_i\vert$ AND $\vert u_p\vert = \vert v_p\vert \geq \vert w_p\vert$, so $u \succeq w$,
    • if $\vert v_i\vert = \vert w_i\vert$ AND $\vert v_p\vert = \vert w_p\vert$ AND $v_p \leq_{lex\infty} w_p$ AND $v_i \geq_{lex\infty} w_i$: then $\vert u_i\vert = \vert v_i\vert = \vert w_i\vert$ AND $\vert u_p\vert = \vert v_p\vert = \vert w_p\vert$ AND $u_p \leq_{lex\infty} v_p \leq_{lex\infty} w_p$ AND $u_i \geq_{lex\infty} v_i \geq_{lex\infty} w_i$, so $u \succeq w$.
    In all cases, $u \succeq w$.

Now, consider the maximal and minimal values:

• The tupled value $[0^{\infty},()]$ is the unique maximal element for the preordering $\succeq$: let $v$ be a tupled value such that $v \neq [0^{\infty},()]$, then $\vert v_p\vert \leq \infty$ and $\vert v_i\vert \geq 0$. Compare $[0^{\infty},()]$ and $v$ with Algorithm 1: $[0^{\infty},()] \neq v$ so the case number 1 is not used; then, $\vert()\vert = 0 \leq \vert v_i\vert$ AND $\vert^{\infty}\vert = \infty \geq \vert v_p\vert$ so there are two cases:
  • if $\vert v_p\vert = \infty$ and $\vert v_i\vert = 0$, the case 3 of Algorithm 1 is applied and $[0^{\infty},()] \succ v$,
  • else $\vert v_p\vert \leq \infty$ and $\vert v_i\vert \geq 0$, the case 5 of Algorithm 1 is applied and $[0^{\infty},()] \succ v$.

• The tupled value $[(),1^{\infty}]$ is the unique minimal element for the preordering $\succeq$: let $v$ be a tupled value such that $v \neq [(),1^{\infty}]$, then $\vert v_i\vert \leq \infty$ and $\vert v_p\vert \geq 0$. Compare $[(),1^{\infty}]$ and $v$ with Algorithm 1: $[(),1^{\infty}] \neq v$ so the case number 1 is not used; then, $\vert()\vert = 0 \leq \vert v_p\vert$ AND $\vert 1^{\infty}\vert = \infty \geq \vert v_i\vert$ so there are two cases:
  • if $\vert v_i\vert = \infty$ and $\vert v_p\vert = 0$, the case 2 of Algorithm 1 is applied and $[(),1^{\infty}] \prec v$,
  • else $\vert v_i\vert \leq \infty$ and $\vert v_p\vert \geq 0$, the case 6 of Algorithm 1 is applied and $[(),1^{\infty}] \prec v$.

$\Box$

Proof
(of Property 10) The principle P1$'$ is satisfied by Definition 10 and by the fact that $[0^{\infty},()]$ is the unique maximal element of $v({\mathcal{A}})$ (see Property 9).

The principle P2$'$ is satisfied because of Definition 10.

The principles P3$'$ and P4$'$ are satisfied: all the possible cases of improvement/degradation of the defence/attack for a given argument (see Definition 16) are applied case by case³¹. Each case leads to a new argument. Using Algorithm 1, the comparison between the argument before and after the application of the case shows that the principle P3$'$ (or P4$'$, depending on the applied case) is satisfied. $\Box$

Proof
(of Property 11) From Definition 10.$\Box$

Proof
(of Property 12) First, we consider the case of the preferred extensions: Let $E$ be a preferred extension $\subseteq {\mathcal{A}}$, we assume that $E$ does not contain all the unattacked arguments of ${\mathcal{A}}$. So, let $A \in {\mathcal{A}}$ be an unattacked argument such that $A \not\in E$.
Consider $E \cup \{A\}$:

• If $E \cup \{A\}$ is conflict-free then, with $A$ an unattacked argument and $E$ a preferred extension, $E \cup \{A\}$ collectively defends itself, so $E \cup \{A\}$ is admissible and $E \subseteq E \cup \{A\}$. This contradicts the fact that $E$ is a preferred extension.
• If $E \cup \{A\}$ contains at least one conflict, then:
  • $\exists B \in E$ such that $B {\mathcal{R}}A$. This is impossible since $A$ is unattacked.
  • or $\exists B \in E$ such that $A {\mathcal{R}}B$. But, since $A$ is unattacked, $\nexists C \in E$ such that $C {\mathcal{R}}A$. So, $E$ does not collectively defend $B$, which is in contradiction with the fact that $E$ is a preferred extension.

So, the assumption ``$E$ does not contain all the unattacked arguments of ${\mathcal{A}}$'' cannot hold.

Now, we consider stable extensions: Let $E$ be a stable extension $\subseteq {\mathcal{A}}$, we assume that $E$ does not contain all the unattacked arguments of ${\mathcal{A}}$. So, let $A \in {\mathcal{A}}$ be an unattacked argument such that $A \not\in E$.
Since $A \not\in E$ there exists in $E$ another argument $B$ which attacks $A$; This is impossible since $A$ is unattacked.
So, the assumption ``$E$ does not contain all the unattacked arguments of ${\mathcal{A}}$'' cannot hold.$\Box$

Proof
(of Property 13) An argument and one of its direct attackers cannot belong to the same extension in the sense of [9] because the extension must be conflict-free. So, since $A$ is uni-accepted, it means that $A$ belongs to all the extensions, and none of the direct attackers of $A$ belongs to these extensions.

For the converse, we use the following counterexample in the case of the preferred semantics:

There are two preferred extensions $\{K,H,G\}$ and $\{A,E,K,H\}$. The argument $A$ is cleanly-accepted ($B$ and $C$ do not belong to any preferred extension, and $A$ belongs to at least one of the two extensions). But, $A$ is not uni-accepted because it does not belong to all preferred extensions.

$\Box$

Proof
(of Property 14) First, $A$ uni-accepted $\Rightarrow$ $A$ cleanly-accepted is the result of Property 13.

Conversely, let $A$ be a cleanly-accepted argument, there exists at least one stable extension $E$ such that $A \in E$ and $\forall B, B {\mathcal{R}}A$, $B \not\in E'$, $\forall E'$ stable extension. Using a reductio ad absurdum, we assume that there exists a stable extension $E''$ such that $A \not\in E''$; but, if $A \not\in E''$, it means that $\exists B \in E''$ such that $B {\mathcal{R}}A$, so, the direct attacker $B$ of $A$ belongs to a stable extension; so, there is a contradiction with the assumption ($A$ is cleanly-accepted); so, $E''$ does not exist and $A$ is uni-accepted.$\Box$

Proof
(of Theorem 1)

1. We consider the arguments $B \in {\mathcal{A}}$ such that $B \neq A$. Let $X_i$ be a leaf, the path ${\mathcal{C}}\in {\mathcal{C}}(X_i,A)$ is $X_i^1-\ldots-X_i^{l_i}-A$ with $X_i^1 = X_i$ and $l_i$ denoting the length of the path (if $l_i$ is even, this path is a defence branch for $A$, else it is an attack branch).

   The constraints from $X_i^1$ to $X_i^{l_i}$ are the following:

   
   

   $$X_i^1 \succ X_i^3 \succ \ldots \succ X_i^{l_i} \succ X_i^{l_i... ...ots \succ X_i^4 \succ X_i^2 \mbox{ if }l_i \mbox{ odd }\geq 1$$
   
   
   or
   
   $$X_i^1 \succ X_i^3 \succ \ldots \succ X_i^{l_i-1} \succ X_i^{l... ...ots \succ X_i^4 \succ X_i^2 \mbox{ if }l_i \mbox{ even }\geq 2$$
   
   

   So, for the path $X_i^1-\ldots-X_i^{l_i}$, the set of the well-defended arguments is $\{X_i^1, X_i^3, \ldots, X_i^{l_i}\}$ if $l_i$ is odd, $\{X_i^1, X_i^3, \ldots, X_i^{l_i-1}\}$ otherwise (this is the set of all the arguments having a value strictly better than those of their direct attackers). This set will denoted by ACCEP$_i$.

   By definition, this set is conflict-free, it defends all its elements (because it contains only the leaf of the path and all the arguments which are defended by this leaf) and it attacks all the other arguments of the path. If we try to include another argument of the path $X \in \{X_i^1, \ldots, X_i^{l_i}\} \setminus$ ACCEP$_i$, we obtain a conflict (because all the other arguments of the path are attacked by the elements of ACCEP$_i$). So, for $\{X_i^1, \ldots, X_i^{l_i}\}$, ACCEP$_i$ is the only preferred and stable extension.

   Consider ${\mathcal{A}}' = {\mathcal{A}}\setminus \{A\}$, with ${\mathcal{R}}'$ being the restriction of ${\mathcal{R}}$ to ${\mathcal{A}}'$³² and UNIONACCEP$=\cup_i$ ACCEP$_i$, then UNIONACCEP is the only preferred and stable extension of ${<}{\mathcal{A}}', {\mathcal{R}}'{>}$.

   So, $\forall B \in{\mathcal{A}}, B \neq A$, $B$ is accepted iff $B$ well-defended.

2. Now, consider $A$. If $A$ is accepted then UNIONACCEP $\cup \{A\}$ is the only preferred and stable extension of ${{<}{\mathcal{A}},{\mathcal{R}}{>}}$. So, $\forall i$, $X_i^{l_i}$ does not belong to the extension. Then, $\forall i$, $X_i^{l_i-1} \succ X_i^{l_i}$. Therefore, each branch leading to $A$ is a defence branch for $A$. So, $\forall i$, $v(X_i^{l_i}) = [()(l_i-1)]$. So, $v(A) = [(l_1, l_2, \ldots, l_n)()]$. Then, $\forall i$, $v(A) \succ v(X_i^{l_i})$. Therefore, $A$ is well-defended.

   Using the following example, we show that the converse is false:

   

   $A$ is well-defended ($A \succ B_1$, $A \succ B_2$ and $A$ is incomparable with $A_1$) but not accepted.

3. Now, if $A$ is well-defended and all the branches leading to $A$ are defence branches for $A$, then UNIONACCEP $\cup \{A\}$ is conflict-free and $A$ is defended against each of its direct attackers (because $X_i^{l_i-1} \in$ UNIONACCEP for each branch $i$). So, UNIONACCEP $\cup \{A\}$ is the preferred and stable extension of ${{<}{\mathcal{A}},{\mathcal{R}}{>}}$ and $A$ is accepted.

$\Box$

Proof
(of Lemma 1) Let ${{<}{\mathcal{A}},{\mathcal{R}}{>}}$ be an argumentation system with a finite relation ${\mathcal{R}}$ without cycles (so, there is only one non empty preferred and stable extension denoted by $E$). We know that:

• if $A$ is exi-accepted and if $A$ has a direct attacker denoted by $B$ then $B$ is not-accepted,
• if $B$ is not-accepted then there exists at least one argument $C$ such that $C {\mathcal{R}}B$ and $C$ is exi-accepted (because $B$ does not belong to $E$ and $E$ is stable, so $C$ must $\in E$). So, a fortiori, if $B$ is not-accepted and has only one direct attacker $C$, then $C$ will be exi-accepted.

The proof is done by induction on the depth of a proof tree for $A$ or $C$.

• Basic case for $(i)$: $A$ is exi-accepted with only one direct attacker $B$ ( $B {\mathcal{R}}A$) and $C_1 \ldots C_n$ are the direct attackers of $B$; so, we have a proof tree whose depth is 2 for $A$ and one of the unattacked $C_i$, for example $C_1$; so:
  $$\begin{eqnarray*} % latex2html id marker 1473v(B) & = & g(h(v(C_1), \ldots, v... ...hspace*{1cm}\mbox{ because }v(C_1) = V_{\mbox{\scriptsize Max}} \end{eqnarray*}$$
  
  
  
  

  so:

  $$\begin{eqnarray*} % latex2html id marker 1481v(A) & = & g(v(B)) \\ & \geq & g^2(V_{\mbox{\scriptsize Max}}) \end{eqnarray*}$$
  
  
  
  

  But, Property 1 says that $g^2(V_{\mbox{\scriptsize Max}}) \geq g(V_{\mbox{\scriptsize Max}})$, so $v(A) \geq v(B)$.

• Basic case for $(ii)$: $C {\mathcal{R}}B$ with $C$ the only direct attacker of $B$; so, we have a proof tree whose depth is 0 for $C$, i.e. $C$ is unattacked; so, $v(C) = V_{\mbox{\scriptsize Max}}$ and $v(B) = g(V_{\mbox{\scriptsize Max}}) \leq v(C)$ (following Definition 6).

• General case for $(i)$: $A$ is exi-accepted with only one direct attacker $B$ ( $B {\mathcal{R}}A$) and $C_1 \ldots C_n$ are the direct attackers of $B$, with one of the $C_i$ exi-accepted, for example $C_1$; we consider the subgraph leading to $C_1$ to which we add $C_1 {\mathcal{R}}B {\mathcal{R}}A$, and we assume:
  $g(v(C_1)) \leq v(C_1)$ (induction assumption issued from $(ii)$)

  So:

  $$\begin{eqnarray*} % latex2html id marker 1492v(B) & = & g(h(v(C_1), \ldots, v... ...q & h(v(C_1), \ldots, v(C_n)) \hspace*{1cm}\mbox{property of }h \end{eqnarray*}$$
  
  
  
  

  and with the non-increasing of $g$:

  $$\begin{eqnarray*} v(A) & = & g(v(B)) \\ & \geq & g(h(v(C_1), \ldots, v(C_n))) = v(B) \end{eqnarray*}$$
  
  
  
  

• General case for $(ii)$: $B$ is not-accepted, so $C$ is exi-accepted; we assume that $C$ has several direct attackers $D_1 \ldots D_p$ which are all not-accepted (because $C$ is exi-accepted); we consider each subgraph leading to $D_i$ to which we add $D_i {\mathcal{R}}C {\mathcal{R}}B$ and we assume:
  $\forall i=1 \ldots p$, $g(v(D_i)) \geq v(D_i)$ (induction assumption issued from $(i)$)

  so:

  $$\begin{eqnarray*} v(C) & = & g(h(v(D_1), \ldots, v(D_p))) \\ & \geq & h(v(D_1... ...pace*{1cm}\hspace*{1cm}\mbox{corresponds to the premise of }(*) \end{eqnarray*}$$
  
  
  
  

  so:

  $$\begin{eqnarray*} v(B) & = & g(v(C)) \\ & \leq & g(h(v(D_1), \ldots, v(D_p))) = v(C) \end{eqnarray*}$$
  
  
  
  

$\Box$

Proof
(of Theorem 2) Assume that $(*)$ is true and consider $A \in {\mathcal{A}}$ which is exi-accepted. Let $B_i$, $i = 1\ldots n$, be the direct attackers of $A$. Then, for all $i = 1\ldots n$, in the subgraph leading to $B_i$ and completed with $B_i {\mathcal{R}}A$, we apply the lemma and we obtain: $g(v(B_i)) \geq v(B_i)$, $\forall i= 1\ldots n$. Thus, we have:

$$\begin{eqnarray*} % latex2html id marker 1511v(A) & = & g(h(v(B_1), \ldots, v(... ...(B_i), \forall i = 1 \ldots n \hspace*{1cm}\mbox{ property of }h \end{eqnarray*}$$

So, $A$ is well-defended.

For the converse, let $A \in {\mathcal{A}}$ be well-defended. Let $B_1, \ldots, B_n$ be the direct attackers of $A$ and assume that $A$ is not exi-accepted. Then, there exists at least one direct attacker $B_i$ of $A$ such that $B_i$ is exi-accepted (because there is only one preferred and stable extension). We can apply $(ii)$ of the lemma on the subgraph leading to $B_i$ completed with $B_i {\mathcal{R}}A$ and we obtain $g(v(B_i)) \leq v(B_i)$. So, there exists $B_i$ a direct attacker of $A$ such that:

$$\begin{eqnarray*} % latex2html id marker 1516v(A) & = & g(h(v(B_1), \ldots, v... ... of }g\\ & \leq & v(B_i) \hspace*{1cm}\mbox{ using the lemma } \end{eqnarray*}$$

This is in contradiction with $A$ well-defended. So, $A$ is exi-accepted.$\Box$