Local approach (generic valuation)

Some existing proposals can already be considered as examples of local valuations.


In [13]'s approach, a labelling of a set of arguments assigns a status (accepted, rejected, undecided) to each argument using labels from the set $\{+, -, ?\}$. $+$ (resp. $-$, $?$) represents the ``accepted'' (resp. ``rejected'', ``undecided'') status. Intuitively, an argument labelled with $?$ is both supported and weakened.

Definition 4 ([13]'s labellings)   Let ${<}{\mathcal{A}}, {\mathcal{R}}{>}$ be an argumentation system. A complete labelling of ${<}{\mathcal{A}}, {\mathcal{R}}{>}$ is a function $Lab : {\mathcal{A}}\to \{+,
?, -\}$ such that:
  1. If $Lab(A) \in \{ ?, -\}$ then % latex2html id marker 3253
$\exists B \in
{\mathcal{R}}^-(A)$ such that $Lab(B) \in \{+, ?\}$
  2. If $Lab(A) \in \{+, ?\}$ then $\forall B \in
{\mathcal{R}}^-(A) \cup {\mathcal{R}}^+(A)$, $Lab(B) \in \{ ?, -\}$

The underlying intuition is that an argument can only be weakened (label $-$ or $?$) if one of its direct attackers is supported (condition 1); an argument can get a support only if all its direct attackers are weakened and an argument which is supported (label $+$ or $?$) weakens the arguments it attacks (condition 2). So:

Every argumentation system can be completely labelled. The associated semantics is that $S$ is an acceptable set of arguments iff there exists a complete labelling $Lab$ of ${<}{\mathcal{A}}, {\mathcal{R}}{>}$ such that $S
= \{A \vert Lab(A) = +\}$.

Other types of labellings are introduced in [13] among which the so-called ``rooted labelling'' which induces a corresponding ``rooted'' semantics. The idea is to reject only the arguments attacked by accepted arguments: an attack by an ``undecided'' argument is not rooted since an ``undecided'' attacker may become rejected.

Definition 5 ([13]'s labellings - continuation)   The complete labelling $Lab$ is rooted iff $\forall A \in
{\mathcal{A}}$, if $Lab(A) = -$ then % latex2html id marker 3307
$\exists B \in {\mathcal{R}}^-(A)$ such that $Lab(B) = +$.

The rooted semantics enables to clarify the links between all the other semantics introduced in [13] and some semantics introduced in [9].

Example 3   On the following example:

% latex2html id marker 9115
\includegraphics[scale=0.6]{/home/lagasq/recherche/argumentation/eval-accep/JAIR-final/ex4bis.eps}

For $n$ even, we obtain $Lab(A_n) = Lab(A_{n-2}) = \ldots = Lab(A_2) = +$ and $Lab(A_{n-1}) = Lab(A_{n-3}) = \ldots = Lab(A_1) = -$.

For $n$ odd, we obtain $Lab(A_n) = Lab(A_{n-2}) = \ldots = Lab(A_1) = +$ and $Lab(A_{n-1}) = Lab(A_{n-3}) = \ldots = Lab(A_2) = -$


Another type of local valuation has been introduced recently in [4] for ``deductive'' arguments. The approach can be characterised as follows. An argument is structured as a pair % latex2html id marker 3323
$\langle\textit{support},\textit{conclusion}\rangle$, where support is a consistent set of formulae that enables to prove the formula conclusion. The attack relation considered here is strict and cycles are not allowed. The notion of a ``tree of arguments'' allows a concise and exhaustive representation of attackers and defenders of a given argument, root of the tree. A function, called a ``categoriser'', assigns a value to a tree of arguments. This value represents the relative strength of an argument (root of the tree) given all its attackers and defenders. Another function, called an ``accumulator'', synthesises the values assigned to all the argument trees whose root is an argument for (resp. against) a given conclusion. The phase of categorisation therefore corresponds to an interaction-based valuation. [4] introduces the following function $Cat$:

Intuitively, the larger the number of direct attackers of an argument, the lower its value. The larger the number of defenders of an argument, the larger its value.

Example 3 (continuation) We obtain:

$Cat(A_n) = 1$, $Cat(A_{n-1}) = 0.5$, $Cat(A_{n-2}) = 0.66$, $Cat(A_{n-3}) =
0.6$, ..., and $Cat(A_1) = (\sqrt{5} - 1)/2$ when $n \to \infty$ (this value is the inverse of the golden ratio14).

So, we have:

If $n$ is even $Cat(A_{n-1}) \leq \ldots \leq Cat(A_3) \leq Cat(A_1) \leq Cat(A_2)
\leq \ldots \leq Cat(A_n) = 1$

If $n$ is odd $Cat(A_{n-1}) \leq \ldots \leq Cat(A_2) \leq Cat(A_1) \leq
Cat(A_3) \leq \ldots \leq Cat(A_n) = 1$


Our approach for local valuations is a generalisation of these two previous proposals in the sense that [4]'s $Cat$ function and [13]'s labellings are instances of our approach.

The main idea is that the value of an argument is obtained with the composition of two functions:

Let $(W,\geq)$ be a totally ordered set with a minimum element ( % latex2html id marker 3361
$V_{\mbox{\scriptsize Min}}$) and a subset $V$ of $W$, that contains % latex2html id marker 3367
$V_{\mbox{\scriptsize Min}}$ and with a maximum element % latex2html id marker 3369
$V_{\mbox{\scriptsize Max}}$.

Definition 6 (Generic gradual valuation)   Let ${<}{\mathcal{A}}, {\mathcal{R}}{>}$ be an argumentation system. A valuation is a function $v: {\mathcal{A}}\to V$ such that:

  1. $\forall A \in
{\mathcal{A}}$, % latex2html id marker 3377
$v(A) \geq V_{\mbox{\scriptsize Min}}$
  2. $\forall A \in
{\mathcal{A}}$, if ${\mathcal{R}}^-(A) = \varnothing$, then % latex2html id marker 3383
$v(A)
= V_{\mbox{\scriptsize Max}}$
  3. $\forall A \in
{\mathcal{A}}$, if ${\mathcal{R}}^-(A) = \{A_1, \ldots, A_n\}
\neq \varnothing$, then $v(A) = g( h (v(A_1),\ldots, v(A_n)))$

with $h: V^* \to W$ such that ($V^*$ denotes the set of all finite sequences of elements of $V$)

and $g: W \to V$ such that

Note that $h(x_1, \ldots, x_n) \geq \max (x_1,\ldots, x_n)$ is a logical consequence of the properties of the function $h$.

A first property on the function $g$ explains the behaviour of the local valuation in the case of an argument which is the root of only one branch (like in Example 3):

Property 1   The function $g$ satisfies for all $n \geq 1$:

\begin{displaymath}
% latex2html id marker 3435
g(V_{\mbox{\scriptsize Max}}) \l...
...g^2(V_{\mbox{\scriptsize Max}}) \leq V_{\mbox{\scriptsize Max}}\end{displaymath}

Moreover, if $g$ is strictly non-increasing and % latex2html id marker 3439
$g(V_{\mbox{\scriptsize Max}}) > V_{\mbox{\scriptsize Min}}$, the previous inequalities become strict.

A second property shows that the local valuation induces an ordering relation on arguments:

Property 2 (Complete preordering)   Let $v$ be a valuation in the sense of Definition 6. $v$ induces a complete15 preordering $\succeq$ on the set of arguments ${\mathcal{A}}$ defined by: $A
\succeq B$ iff $v(A) \geq v(B)$.

A third property handles the cycles:

Property 3 (Value in a cycle)   Let ${\mathcal{C}}$ be an isolated cycle of the attack graph, whose length is $n$. If $n$ is odd, all the arguments of the cycle have the same value and this value is a fixpoint of the function $g$. If $n$ is even, the value of each argument of the cycle is a fixpoint of the function $g^n$.

The following property shows the underlying principles satisfied by all the local valuations defined according to our schema:

Property 4 (Underlying principles)   The gradual valuation given by Definition 6 respects the following principles:

P1
The valuation is maximal for an argument without attackers and non maximal for an attacked and undefended argument.
P2
The valuation of an argument is a function of the valuation of its direct attackers (the ``direct attack'').
P3
The valuation of an argument is a non-increasing function of the valuation of the ``direct attack''.
P4
Each attacker of an argument contributes to the increase of the valuation of the ``direct attack'' for this argument.

The last properties explain why [13,4] are instances of the local valuation described in Definition 6:

Property 5 (Link with [13])  
Every rooted labelling of ${<}{\mathcal{A}}, {\mathcal{R}}{>}$ in the sense of [13] can be defined as an instance of the generic valuation such that:

Property 6 (Link with [4])   The gradual valuation of [4] can be defined as an instance of the generic valuation such that:

Note that, in [4], the valued graphs are acyclic. However, it is easy to show that the valuation proposed in [4] can be generalised to graphs with cycles (in this case, we must solve second degree equations - see Example 5).

Example 4   Consider the following graph:

% latex2html id marker 9263
\includegraphics[scale=0.6]{/home/lagasq/recherche/argumentation/eval-accep/JAIR-final/autrexemple.eps}

In this example, with the generic valuation, we obtain:

So, we have:

$E_1, D_2, D_3, C_4, B_4$

$\succeq$

$C_1, B_2$

$\succeq$

$D_1, C_2, C_3, B_3$

However, the constraints on $v(A)$ and $v(B_1)$ are insufficient to compare $A$ and $B_1$ with the other arguments.

The same problem exists if we reduce the example to the hatched part of the graph in the previous figure; we obtain $E_1, D_2 \succeq C_1
\succeq D_1, C_2$, but $A$ and $B_1$ cannot be compared with the other arguments16.

Now, we use the instance of the generic valuation proposed in [4]:

So, we have:

$E_1, D_2, D_3, C_4, B_4$

$\succeq$

$C_1, B_2$

$\succeq$

$D_1, C_2, C_3, B_3$

$\succeq$

$B_1$

$\succeq$

$A$

However, if we reduce the example to the hatched part of the graph, then the value of $A$ is $\frac{13}{19}$. So, $v(A)$ is better than $v(B_1)$ and $v(D_1)$, but also than $v(C_1)$ ($A$ becomes better than its defender).

Example 5 (Isolated cycle)   Consider the following graph reduced to an isolated cycle:

\includegraphics[scale=0.7]{/home/lagasq/recherche/argumentation/eval-accep/JAIR-final/cas10.eps}.

A generic valuation gives $v(A) = v(B) =$ fixpoint of $g^2$.

If we use the instance proposed by [4], $v(A)$ and $v(B)$ are solutions of the following second degree equation: $x^2 + x - 1 = 0$.

So, we obtain: $v(A) = v(B) = \frac{-1 +
\sqrt{5}}{2} \approx 0.618$ (the inverse of the golden ratio again).

Marie-Christine Lagasquie 2005-02-04