The proofs

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

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

(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$

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

(of Property 4)
P1 is satisfied because: $\forall A \in
{\mathcal{A}}$, if $A$ has no direct attacker ( ${\mathcal{R}}^-(A)$ is empty), then % latex2html id marker 5325
$v(A) = V_{\mbox{\scriptsize
Max}}$ and % latex2html id marker 5327
$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$

(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 % latex2html id marker 5349
$\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 % latex2html id marker 5367
$\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$

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

The translation of $Cat$ into a gradual valuation is: $V = [0,1]$, $W = [0, \infty[$, % latex2html id marker 5405
$V_{\mbox{\scriptsize Min}} = 0$ and % latex2html id marker 5407
$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$

(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:
Associativity of $\star$: $(t \star t') \star t'' = t \star (t' \star t'')$
There are two cases:
Property of $\oplus$: $(t \oplus k)
\oplus k' = t \oplus (k + k')$
We have:

(t \oplus k) \oplus k' & = & (x_1 + k, \ldots, x_n + k, \ldot...
... + k', \ldots, x_n + k + k', \ldots) \\
& = & t \oplus (k+k')

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

% latex2html id marker 1317(t \star t') \oplus k & = & {\mb...
..., x'_n + k, \ldots) \\
& = & (t \oplus k) \star (t' \oplus k)


(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:

Now, consider the maximal and minimal values:


(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 case31. 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$

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

(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\}$:
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$

(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:

% latex2html id marker 11064
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.

(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 % latex2html id marker 5911
$\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$

(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:

    \begin{displaymath}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\end{displaymath}


    \begin{displaymath}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\end{displaymath}

    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}}'$32 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:

    % latex2html id marker 11151

    $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.

(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:

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


(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:

% 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

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:

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

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

Marie-Christine Lagasquie 2005-02-04