In order to make AAFs suitable for modeling disputes in scenarios with di
erent characteristics, several variants have been proposed. In particular, Weighted
AAFs are a variant of AAFs where the arguments and/or the attacks can be
associated with weights. The paper in [
(a) (b)
Example 1. Ann, Mary, Carl and John are reviewing a notebook. Their reviews contain the following six arguments: a=`Since it contains up-to-date components, it is expensive' b=`Nowadays, it is easy to nd cheap up-to-date components. Therefore, that aspect does not imply the price.' c=`Since its brand is not high quality, it does not contain up-to-date components' d =`Since its battery is lightweight, it is lightweight overall' e=`It is heavy' f =`The battery is very heavy'.
Figure 2 shows the corresponding argumentation graph, properly augmented to highlight who-claims-what (for instance, a and d are claimed by Mary, and e is claimed by both Ann and Carl). The numbers in brackets represent the trustworthiness scores, on a scale of 1 to 10, assigned to the agents on the basis of their past reviews.
As a matter of fact, reasoning on reviews is a hot topic attracting the interest of the research community, owing to the popularity of ecommerce sites. In this context, reasoning on extensions is useful, since the fact that a set of arguments is an extension means that it provides a reasonable summary of the main features and critical aspects of the reviewed object. Analogously, reasoning on the acceptance of an argument helps understand if it can be reasonably considered representative of the object. Now, in the T-AAF F of Example 1, argument a does not belong to any extension. However, a is proposed by Mary, who has a high trust degree. Thus, the analyst can bene t from knowing that, although a is not accepted, it becomes accepted in the AAF F (with = 2) obtained from F by discarding what said only by agents whose trust degree is . This means that the analyst can choose now to consider a a robust argument, given that F does not contain what said by agents with \low" trust degrees (we recall that we are in a scale from 1 to 10). Analogously, even if S = fa; f g is not an (admissible) extension in F , it can be somehow considered a reasonable summary of the reviews, since it is an extension over the same F . In general, denoting as \ -extension" (resp., \ -accepted") a set (resp., an argument) that is an extension (resp., accepted) over F , the following two problems over a T-AAF F are of interest to the analyst: { min-Tver (F; S): What is the minimum trust degree such that the set S is a -extension over F under ? { min-Tacc (F; a): What is the minimum trust degree such that the argument a is -accepted over F under ?
The complexity of min-Tver (F; S) and min-Tacc (F; a) has been
characterized in [
d a
Mary (8) b
Ann (1) for the admissible, complete, stable and preferred semantics. In this paper, we provide methods for computing min-Tver (F; S) and min-Tacc (F; a) for the semantics for which they resulted to be intractable (see Table 1). Our strategy is based on the translation of min-Tver (F; S) and min-Tacc (F; a) into Integer Linear Programming (ILP), so that they can be e ciently computed by exploiting the many heuristics already implemented in the commercial solvers. ver acc and and Tver Tacc min-Tver
min-Tacc ad,st,co gr pr
P NP-c FP FPNP [log n]-c
P P FP FP coNP-c NP-c FPNP [log n]-c FPNP [log n]-c { admissible (ad ): S is an admissible extension i S is con ict-free and its arguments are acceptable w.r.t. S; { stable (st ): S is a stable extension i S is con ict-free and S attacks each argument in A n S; { complete (co): S is a complete extension i S is admissible and every argument acceptable w.r.t. S is in S; { grounded (gr ): S is a grounded extension i S is a minimal (w.r.t. ) complete set of arguments; { preferred (pr ): S is a preferred extension i S is a maximal (w.r.t. ) complete set of arguments.
Accepted arguments. An argument a is (credulously) accepted under a semantics i a belongs to some extension of F . In some sense, checking the acceptability of an argument is a way of deciding whether a represents a robust point of view in the discussion modeled by F .
Classical problems: ver and acc. Given an AAF F , a semantics , a set of
arguments S and an argument a, the fundamental problems of verifying whether
S is a extension and whether a is (credulously) accepted (under ) will be
denoted as ver (F; S) and acc (F; a), respectively. The complexity of these
problems, widely studied in the literature [
We here recall the Trust-aware AAFs (proposed in [
Let F = hA; Di be an AAF and U the set of agents proposing the arguments in A. Function ! : U ! 2A returns, for each agent u, the set of arguments proposed by u. We assume that every argument is proposed by at least one agent, and the same argument can be proposed by several agents. The set of agents proposing an argument a is denoted as ! 1(a).
We assume the presence of an agent trust function U assigning to each agent u 2 U a trust degree U (u), i.e., a positive integer providing a measure of how trustworthy u is considered. Regarding the trustworthiness of an argument a, it seems natural to derive the trust degree of a from the trust degrees of the agents who propose a. In this regard, the trustworthiness of arguments is modeled with the argument trust function T U;!; U (or, more simply, T ) assigning to each argument a the positive integer equal to the maximum trust degree of the agents that propose, i.e., T (a) = maxu2! 1(a) U (u).
For the sake of simplicity, and without loss of generality, from now on we will only implicitly consider the set of users U and the functions ! and U , and we will explicitly consider only the argument trust function T implied by them.
We now recall the de nition of the Trust-aware Abstract Argumentation Frameworks.
De nition 1 (T-AAF). Given an abstract argumentation framework hA; Di and an argument trust function T over A, the triple F = hA; D; T i is called Trust-aware Abstract Argumentation Framework (T-AAF).
We denote as T (F ) the set of distinct trust degrees of F 's arguments augmented with 0.
Example 2. (Continuing Example 1 - Fig. 2) From the users' trust degrees, we have T (e) = max( U (Ann); U (Carl )) = 2, T (a) = T (d) = 8, T (c) = 2, T (b) = 1, T (f ) = 9. Moreover, we have: T (F ) = f0; 1; 2; 8; 9g.
We now recall the de nition of the concept F of -restrictions, that is the TAAF consisting of all and only the arguments of the original T-AAF F with trust greater than and of all and only the attacks in F between these arguments. Let F = hA; D; T i be a T-AAF, a trust value, and a semantics. The restriction of F is the T-AAF F = hA0; D0; T 0i where A0 = faj a 2 A ^ T (a) > g, D0 = D \(A0 A0), and T 0 is the restriction of T over A0. The T-AAF F will be also called the \ -restriction of F ". Basically, considering the -restriction of F means considering as a threshold, and then taking into account only what said by the agents whose trust degree is greater than , while discarding what said only by agents whose trust degree is . Observe that F = F when = 0, since the trust function assigns only positive values.
We now recall how the classical notions of extension and accepted argument (reviewed in Section 2) are adapted to the case of T-AAFs. Given a T-AAF F and a trust degree , a -extension of F " (shorthand for \trusted extension with trust level ") under the semantics is any set of arguments that is an extension of F under . Basically, a -extension for F is a set of arguments that meets the conditions of the semantics in the T-AAF obtained from the original one by discarding the arguments proposed by agents whose trust degree is . In turn, an argument a of F is said to be -accepted (shorthand for \trustingly accepted with trust level ") under if a belongs to at least one -extension under . The rationale of -acceptance is analogous to -extension: An argument a may not be accepted in the original T-AAF, but it can still be -accepted for some , meaning that a turns out to be a \robust" argument when discarding what said by users not su ciently trustworthy (w.r.t. the threshold ). The reason is that the removal of arguments (and the consequent removal of the attacks involving the removed arguments) can change the number of extensions and their composition.
Example 3. (Continuing examples 1, 2) Under = ad, fc; f g is a -extension even with = 0, while fa; f g is a -extension for = 2 but not for lower degrees in T (F ). Under all the considered semantics, there is no 2 T (F ) such that d is -accepted, while a is -accepted for = 2, but not for any lower 2 T (F ).
Now we recall the de nitions of the fundamental problems min-Tver (F; S) and min-Tacc (F; a).
De nition 2 (min-Tver (F; S)). min-Tver (F; S): Given a T-AAF F , a semantics , and a set S of arguments of F , what is the minimum trust degree in T (F ) (if exists) such that S is a -extension of F under ? De nition 3 (min-Tacc (F; a)). min-Tacc (F; a): Given a T-AAF F , a semantics , and an argument a of F , what is the minimum trust degree in T (F ) (if exists) such that a is -accepted under ?
The choice of minimizing the value of required to make S a -extension and a -accepted goes in the direction of discarding as few agents as possible from the dispute. This way, what the the agents said is tried to be preserved as much as possible, and agents with low trust degrees are discarded at rst, coherently with the assumption that low values of trust degrees correspond to less reliable agents. In fact, if the output of min-Tver and min-Tacc is \low", it means that considering S as an extension and a as accepted is quite reasonable: indeed, only users with low trust degree must be discarded to make S extension and a accepted. The case that is \high", instead, represents a clue of a possible risky situation: considering S as an extension and a as accepted requires to discard some/many trustworthy agents, thus it could be the case of questioning the robustness of S and a.
Example 4. From the discussion in Example 3 regarding the set fc; f g and the argument a, it follows that min-Tverad (F; fc; f g) = 0 and min-Taccad (F; a) = 2.
min-Tver and min-Tacc are the natural optimization counterparts of the following decision problems over a given T-AAF F and under a semantics : { Tver (F; S; ): Is S a -extension of F under for some ? { Tacc (F; a; ): Is a -accepted for F under for some ?
The complexity of these problems was studied in [
We rst recall the characterization of the complexity of the decisional variants Tver (F; S; ) and Tacc (F; a; ).
Theorem 1. [
) is in F P for
The ptime results for 2 fad; co; st; grg straightforwardly follows from the fact that Tver (F; S; ) can be decided by iteratively invoking an algorithm solving ver (F ; S) (that is in P ), for each 2 T (F ) smaller than or equal to . Furthermore, the fact that Tverpr (F; S; ) is coNP -complete can be proved by observing that a polynomial size witness for the answer \false" consists of x supersets S1; : : : ; Sx of S witnessing that S is not maximally admissible in F 1 ; : : : ; F x , respectively, and the coNP -hardness straightforwardly follows from the fact that verpr is coNP -hard.
Similar arguments were exploited in [
Theorem 2. [
) is NP -complete for every
2 fad; co; st; prg
As regards min-Tver (F; S) and min-Tacc (F; a), from Theorems 1 and 2 it
can be proved that min-Tver (F; S) is in FP for 2 fad; co; st; grg and
minTacc (F; a) is in FP for = gr. Speci cally, both for min-Tver (F; S) and
min-Tacc (F; a) we can reason as done for Tver (F; S; ) and Tacc (F; a; ),
that is by trying the trust degrees in T (F ) in ascending order. Moreover,
reasoning analogously ot the case of Tver (F; S; ) and Tacc (F; a; ), in [
Theorem 3. [
The characterization of the computational complexity of min-Tver (F; S) and min-Tacc (F; a) is relevant not only from a theoretical standpoint, but also in a practical perspective, since it suggests suitable computational strategies for these problems. We consider the two problems separately.
Solving min-Tver (F; S). The proof of Theorem 3 in [
Hence, we focus on = pr. Theorem 3 states that min-Tverpr (F; S) is in FP NP , and this suggests to try a solution based on Integer Linear Programming (ILP), that is well-suited for research problems inside this complexity class. Generally speaking, resorting to ILP solvers (such as CPLEX) is a reasonable choice (if allowed by the expressiveness of ILP), as this exploits a number of heuristics implemented in the commercial solvers that in many cases enhance the e ciency of evaluating even hard instances.
The core of our approach is a system of linear inequalities IminTver(F; S) over binary variables that is parametric on the T-AAF F = hA; D; T i and the set S, and that tests whether S is a preferred extension in F z0 , for di erent values of z0 . In particular, z0 ranges over the ordered sequence 10 ; : : : ; m0 of trust degrees extracted from T (F ) where: 1. 10 is the result of min-Tverad (F; S), i.e., the minimum trust degree such that S is admissible for F 10 ; 2. m0 = mina2S T (a); 3. 20 ; : : : ; m0 1 are the trust degrees in T (F ) between 1 and m. The reason for this restriction of the search space is that S cannot be a preferred extension in any F with < 10 (since S would not be admissible) or m0 (since some of its arguments would not be present in F ).
Given this, for each argument ai of F , we represent the membership of ai to S with the boolean constant si. Moreover, for each z 2 [1::m] we use suitable variables and inequalities for testing whether S is a preferred extension in F z . The fact that an argument ai is maintained or discarded in F z (corresponding to the fact that its trust degree T (ai) is higher or lower than z) is represented with a boolean variable xiz (xiz = 1 means that ai is NOT discarded in F z ). Then, in order to test whether S is a preferred extension in F z , we search for a superset Sz0 of S that is admissible and such that jSz0j > jSj. We encode the membership of an argument ai to Sz0 using a binary variable s0iz, where s0iz = 1 i ai 2 S0 . Morez over, for every z 2 [1::m], we use a boolean variable yz to express the result of the comparison jSz0j jSj. Then, for every z, we enforce jSz0j jSj to be as large as possible by means of the objective function. This leads to the following ILP instance IminTver(F; S): <>>>>>>>>8>>>>>>>>>>> ((((((m543210a))))))xsssxMMP00iiiizzz +z(x2s1i[ss0i1szz0ij:0iz:zm](y2zz yzz) z T (ai) + 1 9=>>=>>>>>9;> z88ii2;2j[j1[1(::a:m:in;]a],j )2D; >>:>>> ((67)) xxiizz ++ ss0jjz ; z 2 [1::m]
T (ai) xiz) 1 Plj(al;ai)2D sl + 1
Plj(al;ai)2D s0l + 1 where M = maxai2A T (ai).
The semantics of the inequalities is the following: (0) yz = 1 i jSz0j > jSj, for each z 2 [1::m]; (1) every Sz0 is a superset of S; (2) every Sz0 (and thus S) contains only non-discarded arguments; (3; 4) an argument ai is discarded in F z i T (ai) z; (5) every Sz0 (and thus S) is con ict free; (6) S is admissible; (7) every Sz0 is admissible.
The result R of IminTver(F; S) can be easily translated into what asked by min-Tverpr (F; S): the position of the leftmost bit 0 in R (if any) is the index of the minimum trust degree in T (F ) such that S is a preferred extension over F . Obviously, if all the bits of R are 1, it means that there is no way of making S a preferred extension by removing all the arguments less trustworthy than some threshold.
Solving min-Tacc (F; a). The case = gr can be solved by the
polynomialtime algorithm described in the proof of Theorem 4 in [
As for the other semantics, analogously to what said for min-Tver (F; S), the FP NP [log n]-completeness backs an ILP-based approach. Our formulation of min-Tacc (F; a) as an ILP instance IminTacc(F; a) is based on searching an extension S that contains a. We represent the membership of an argument ai to S with a boolean variable si (where the variable sj corresponding to a is constrained to be 1), and the fact that ai is maintained or discarded (owing to the threshold ) with a boolean variable xi (xi = 1 means \ai is NOT discarded"). The objective function consists in minimizing . Observe that we can resort to the same ILP instance to solve min-Tacc (F; a) under any 2 fad; co; prg, since an argument belongs to a complete or a preferred extension if and only if it belongs to an admissible extension. This leads to the following formulation for IminTacc(F; a) under any 2 fad; co; prg: 8 min >>>> (0) 0 T (a) 1 > >>> (1) sj = 1 (where j is the index of a in A) ><> (2) xi si 8i 2 [1::n] >>>>>>:>>>> ((((3456)))) sxMMii ++(xss1ijj xT1Pi()alji()al;ai)2TD(asil)++11 8888iiii;;22jjjj[[((11aa::ii::nn;;aa]]jj )) 22 DD where inequalities (1) (6) have the following meaning: (0) the threshold ranges from 0 to T (a) 1 (a threshold a); (1) a belongs to S; (2) an argument can belong to S only if it is not discarded; (3; 4) an argument ai is discarded i T (ai) ; (5) S is con ict-free; (6) S is admissible.
xi si
X lj(al;ai)2D sl 8i 2 [1::n]; stating that every argument in F outside S must be attacked by some argument in S. 6
There are a lot of works extending AAFs: most of them have the aim of
handling uncertainty [
The reasonability of associating weights with arguments or attacks has been
widely discussed in the literature, and, as observed in [
It is worth noting that the results in [
In this regard, the interest of the research community to extending the
framework in [
We have provided some computational strategies for the intractable cases of
the problems min-Tver and min-Tacc proposed in [
We have provided a translation of the cases of min-Tver and min-Tacc that have been shown to be inside the class FP NP into ILP instances so that a well-established ILP solver can be invoked. Generally speaking, resorting to ILP solvers (such as CPLEX) is a reasonable choice (if allowed by the expressiveness of ILP, that is bounded by FP NP ), as this exploits a number of heuristics implemented in the commercial solvers that in many cases enhance the e ciency of evaluating even hard instances. Future work will be devoted to implement ILP-based strategies and compare them with the usage of SAT-solvers, that are commonly used as tools for verifying/generating the extensions and deciding the acceptance of arguments in \classical" abstract argumentation. 31. Thimm, M.: A probabilistic semantics for abstract argumentation. In: Proc. European Conf. on Arti cial Intelligence (ECAI), Montpellier, France. pp. 750{755 (2012)