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

• If $A$ has no attacker $Lab(A) = +$.
• If $Lab(A) = ?$ then $\exists B \in {\mathcal{R}}^-(A)$ such that $Lab(B) = ?$.
• If ( $\forall B \in {\mathcal{R}}^-(A)$, $Lab(B) = -$) then $Lab(A) = +$.
• If $Lab(A) = +$ then $\forall B \in {\mathcal{R}}^-(A) \cup {\mathcal{R}}^+(A)$, $Lab(B) = -$.

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

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

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

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 ratio¹⁴).

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:

• one for aggregating the values of all the direct attackers of the argument; so, this function computes the value of the ``direct attack'';
• the other for computing the effect of the ``direct attack'' on the value of the argument: if the value of the ``direct attack'' increases then the value of this argument decreases, if the value of the ``direct attack'' decreases then the value of this argument increases.

Let $(W,\geq)$ be a totally ordered set with a minimum element ( $V_{\mbox{\scriptsize Min}}$) and a subset $V$ of $W$, that contains $V_{\mbox{\scriptsize Min}}$ and with a maximum element $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}}$, $v(A) \geq V_{\mbox{\scriptsize Min}}$
2. $\forall A \in {\mathcal{A}}$, if ${\mathcal{R}}^-(A) = \varnothing$, then $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$)

• $h(x) = x$
• $h () = V_{\mbox{\scriptsize Min}}$
• For any permutation $(x_{i1}, \ldots, x_{in})$ of $(x_1, \ldots, x_n)$, $h(x_{i1}, \ldots, x_{in}) = h(x_1, \ldots, x_n)$
• $h(x_1, \ldots, x_n, x_{n+1}) \geq h(x_1, \ldots, x_n)$
• if $x_i \geq x'_i$ then $h(x_1, \ldots, x_i, \ldots, x_n) \geq h(x_1, \ldots, x'_i, \ldots, x_n)$

and $g: W \to V$ such that

• $g(V_{\mbox{\scriptsize Min}}) = V_{\mbox{\scriptsize Max}}$
• $g(V_{\mbox{\scriptsize Max}}) < V_{\mbox{\scriptsize Max}}$
• $g$ is non-increasing (if $x \leq y$ then $g(x) \geq g(y)$)

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

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

Moreover, if $g$ is strictly non-increasing and $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 complete¹⁵ 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:

• $V = W = \{-, ?, +\}$ with $- < ? < +$,
• $V_{\mbox{\scriptsize Min}} = -$,
• $V_{\mbox{\scriptsize Max}} = +$,
• $g$ defined by $g(-) = +$, $g(+) = -$, $g( ?) = ?$
• and $h$ is the function $\max$.

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

• $V = [0,1]$,
• $W = [0, \infty[$,
• $V_{\mbox{\scriptsize Min}} = 0$,
• $V_{\mbox{\scriptsize Max}} = 1$,
• $g: W \to V$ defined by $g(x) = \frac{1}{1 + x}$
• and $h$ defined by $h(x_1, \ldots, x_n) = x_1 + \ldots + x_n$.

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:

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

• $v(E_1) = v(D_2) = v(D_3) = v(C_4) = v(B_4) = V_{\mbox{\scriptsize Max}}$
• $v(D_1) = v(C_2) = v(C_3) = v(B_3) = g(V_{\mbox{\scriptsize Max}})$
• $v(C_1) = v(B_2) = g^2(V_{\mbox{\scriptsize Max}})$
• $v(B_1) = g(h(g^2(V_{\mbox{\scriptsize Max}}), g(V_{\mbox{\scriptsize Max}})))$
• $v(A) = g(h(g(h(g^2(V_{\mbox{\scriptsize Max}}), g... ...scriptsize Max}}), g(V_{\mbox{\scriptsize Max}}), V_{\mbox{\scriptsize Max}}))$

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 arguments¹⁶.

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

• $v(E_1) = v(D_2) = v(D_3) = v(C_4) = v(B_4) = 1$,
• $v(D_1) = v(C_2) = v(C_3) = v(B_3) = \frac{1}{2}$,
• $v(C_1) = v(B_2) = \frac{2}{3}$,
• $v(B_1) = \frac{6}{13}$,
• $v(A) = \frac{78}{283}$.

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:

.

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