On the Links Between Truth Discovery and Bipolar Argumentation¶

Complex attacks¶

In what follows, let \(\trcls{R}\) denote the transitive closure of the relation \(R\) 1.

Note that, perhaps confusingly, a mediated attack is not necessarily a super-mediated attack. 4

NOTE: I think the definition of super-mediated attacks should mention the transitive closure of support, which makes the above remark incorrect. Change later if necessary.

To look at how complex attacks can be interpreted in the TD network, let us first introduce some notation.

• For \(f \in \F\), write

  \[\mut_N(f) = \{g \in \F : \obj_N(g) = \obj_N(f), g \ne f\}\]

  for the facts mutually incompatible with \(f\).

• For \(s \in \S\), write

  \[\antifacts_N(s) = \bigcup_{f \in \facts_N(s)}{\mut_N(f)}\]

  for all the facts mutually incompatible with the beliefs of \(s\). By definition of a TD network \(\antifacts_N(s)\) and \(\facts_N(s)\) are disjoint. It is worth noting that two sources \(s\) and \(t\) disagree on at least one object if and only if \(\facts_N(s) \cap \antifacts_N(t) \ne \emptyset\).

• For \(s \in \S\), \(n \in \Nat\), define \(\friends_N^n(s) \subseteq \S\) recursively as follows:

  \[\begin{aligned} \friends_N^1(s) &= \{t \in \S : \facts_N(s) \cap \facts_N(t) \ne \emptyset \} \\ \friends_N^{n+1}(s) &= \bigcup_{t \in \friends_N^n(s)}{\friends_N^1(t)} \end{aligned}\]

  Then write \(\friends_N^*(s) = \bigcup_{n \in \Nat}{\friends_N^n(s)}\).

• For \(f \in \F\), write

  \[\antisrc_N(f) = \bigcup_{g \in \mut_N(f)}{\src_N(g)}\]

  for all the sources holding a belief contradicting \(f\). By definition of a TD network \(\antisrc_N(f)\) and \(\src_N(f)\) are disjoint.

(TODO: I conjecture that (4) and (5) characterise all the mediated attacks, (7) and (8) characterise all the supported attacks (which according to (6) characterises the secondary attacks also), and that (9) and (10) characterise the super-mediated attacks.)

Fig. 4 shows the \(\suppattack\), \(\medattack\) and \(\smedattack\) relations for the BAF from Fig. 3. By the above proposition, \(\secattack\) is obtained by symmetry from \(\suppattack\), so is omitted here.

Note that sources in the underlying TD network do not have any second order friends, so examples more interesting than this one are available.

Figure 4¶

Do these attacks make sense for truth discovery?¶

To investigate this, let us consider a more interesting TD BAF where sources \(s\) and \(t\) agree on one object but disagree on another, as shown in Fig. 5.

Figure 5¶

There are two interesting points regarding the complex attacks generated here.

• Self-attacking arguments. It can be seen that \(f\) attacks itself under \(\suppattack\), \(\secattack\) and \(\medattack\) (and similarly for \(g\)). For sources, it can be seen that \(s\) and \(t\) attack themselves under \(\smedattack\).

• Inconsistency. We have both \(s \supp f\) and \(s \suppattack f\), i.e. \(s\) both supports and attacks \(f\). Similarly we have both \(f \supp s\) and \(f \smedattack s\).

Fig. 5 can be converted to a regular AF by discarding the supports and adding each type of complex attack. In principle one could also consider adding combination of different kinds of complex attack. Here the only such combination we shall consider is the supported attacks together with the super-mediated ones, since this is proposed in [CLagasquieSchiex13] in the case of the “deductive support” interpretation (where \(a \supp b\) means that \(b\) should be accepted whenever \(a\) is).

Adding mediated attacks. We have

That is, augmenting the attack relation with mediated attacks results in \(f\) and \(g\) attacking all arguments (including themselves).

In this case there are no admissible extensions, so no conclusions can be drawn.

Adding supported attacks. We have

That is, in all arguments attack \(f\) and \(g\). It can be seen that in this case \(\{s, t, h\}\) is an admissible, grounded, preferred and stable extension. It is interesting that \(s\) and \(t\) are accepted when they support (and attack!) non-accepted arguments \(f\) and \(g\) respectively. As will be seen below, this is remedied by additionally adding the super-mediated attacks.

Adding secondary attacks. For secondary attacks we have

This is the same as for mediated attacks; consequently no conclusions can be drawn.

Adding super-mediated attacks. We have

That is, all arguments attack \(s\) and \(t\), and \(f\) and \(g\) attack each other.

Here there are two preferred extensions: \(\{f, h\}\) and \(\{g, h\}\). Note that both are stable. The grounded extension is \(\{h\}\).

Adding supported and super-mediated attacks. We have

That is, all arguments attack every other argument except \(h\). It is easy to see that \(\{h\}\) is the only conflict-free set, and it is admissible, grounded, preferred and stable.

TODO IN THIS SECTION:

• Attempt a proof for the conjecture after the proposition

• Look at safe and closed for \(\supp\) extensions from [CLagasquieSchiex13], and the semantics defined in terms of these concepts

• Look at the meta-argumentation semantics defined in [BGvdTV10]

• Look at the coalition meta-argumentation approach from Cayrol and Lagasquie-Shiex

• Look at all the semantics I’ve discussed:

  • Extensions of \(\attack \cup \suppattack \cup \smedattack\) (but which Dung semantics? Just \(\subseteq\)-maximal conflict-free sets?)

  • Ones from the above bullet points

  • Define a TD operator using these and try to characterise it in the TD language

Local Gradual Valuation¶

[CLS05a] define the local graduation valuation family of semantics, wherein the valuation of an argument is given by combining the valuations of its supporters and attackers. Two specific instances are given, which are termed LocMax and LocSum in [BRT19]. Note that since we allow BAFs with cycles, neither LocMax nor LocSum define a unique semantics.

In what follows, for a relation \(R \subseteq X \times X\) let us write \(R^-(x) = \{y \in X : y R x\}\) and \(R^+(x) = \{y \in X : x R y\}\). Then \(\supp^-(a)\) is the set of arguments supporting \(a\), \(\attack^+(a)\) is the set of arguments attacked by \(a\), etc.

With the restriction that \(\sigma\) maps into \([-1, 1]\), there are TD BAFs for which no LocMax valuation exists. Indeed, consider the TD BAF from Fig. 3, and suppose some \(\sigma\) satisfying (1) exists. Then we have the following system of equations, where for brevity we abuse notation by writing \(s\) for \(\sigma(s)\) etc.

First note that from (4), (5) and (6) we get \(t \ge i + 1 = u = v\). Consequently \(\max\{t, u, v\} = t\) and, from (10), \(i = t - h\).

Next, from (7) and (8) we get \(s = f + g = t\). This means

and hence \(i = t - h \ge 1\); but since \(i \in [-1, 1]\) this means \(i = 1\). Finally, this means \(u = v = i + 1 = 2 \notin [-1, 1]\), which is a contradiction.

Without the restriction that valuations lie in \([-1, 1]\), the above system of equations does have solutions, e.g. for any \(x \ge 2\) take \(s = t = x\), \(u = v = 2\), \(f = 1\), \(g = h = x - 1\) and \(i = 1\). 7 However it is difficult to justify adding 1 in (3) - (6) in this case.

TODO: is it worth investigating LocSum?

1

Note that the original sources do not use the notion of the transitive closure, and instead spell out the details of a chain of supports. I am pretty confident the definition with the transitive closure is equivalent.

2

Note that [BGvdTV10] disagrees with the secondary attack notion from [CLagasquieSchiex13], claiming that it leads to inconsistencies.

3

Secondary attacks are called indirect defeats in [CLS05b].

4

This is because in the definition of a mediated attack we allow indirect support from \(b\) to \(c\) (i.e. we use \(\trcls{\supp}\)) whereas for a super-mediated attack a direct support is required (i.e. we use \(\supp\)).

5

It’s possible that this terminology is a bit silly and/or pretentious…

6

See [ABN13] for more discussion around why extension-based semantics are not always appropriate.

7

In this solution \(f \le h\); I think there are also solutions where \(h < f\).