Inferring attack relations for gradual semantics

1.Introduction

Abstract argumentation semantics associate a justification status with a set of arguments based on interactions between arguments. Such interactions can include inter-argument attacks [17], or preference-based defeats [5,6,21,29,41], or may consider both of these together with some supportive relationship [2,3,12,30]. Given such a framework, an argument may be considered justified if it appears in one (resp. many or all) extensions, where such extensions – sets of non-conflicting arguments accepted together – are computed according to the argumentation semantics, or based on the label assigned to the argument (we refer the reader to [7] for an introduction to the most common argumentation semantics).

Arguments often have associated weights, and different semantics have been proposed which consider the weight associated with an argument [2,14,30,34]. While some semantics developed in this context return whether an argument is, or is not justified [14], many other ranking-based semantics either return a preference ordering over arguments. Such ranking-based semantics have been used to, for example, identify irrationality in reasoning [20] by examining whether the initial weights associated with an argument affect the argument’s final acceptability degree in an appropriate manner (i.e., consistent with the ranking-based semantics being used); refining the results obtained by extension semantics [11,42]; and applied to multi-agent settings [16]. In this paper, we focus on gradual semantics, a subclass of ranking-based semantics which associates a numeric final acceptability degree with each argument to compute a preference ordering over arguments.

The top portion of Fig. 1 shows the reasoning process used when reasoning using gradual semantics. Here, a weighted argumentation framework consisting of arguments, attacks and initial weights associated with arguments is provided as input. A gradual semantics is then used to compute a final acceptability degree for each argument. In many semantics, these final acceptability degrees are then used to compute a preference ordering over the arguments.

More recent work has considered different combinations of inputs and outputs to the problem. For example, [34] seeks to identify a set of initial weights for arguments based on the final argument preference ordering and argumentation semantics, while [27] determines the preferences between arguments given argument justification status, semantics and argumentation framework. In this paper, and as illustrated in the bottom portion of Fig. 1, we consider the problems of determining whether a set of attacks between arguments can be identified given specific argumentation semantics, the final acceptability degrees, and the initial weights. As discussed further in Section 5, we leave the problem of using preferences over arguments as input for our problem as future work. While it is true that the problem we consider is somewhat abstract and has limited real-world applications, it serves as a departure point for potentially important applications of argumentation to opponent modelling [35,37] and preference elicitation [27].

Fig. 1.

The process (top) by which a gradual semantics is applied to compute an acceptability preference between arguments and (bottom) the inverse problem considered in this paper. The “final acceptability degrees” are now used as input. That is, given arguments, initial weights, and desirable final acceptability degrees, can we find a suitable set of attacks?

While other ranking-based semantics are described in the literature, we consider three popular weighted gradual semantics (the weighted h-categoriser, the weighted card-based, and the weighted max-based semantics [4]). These three semantics were chosen due to their similarity to one another, and due to the way in which a similar approach can be used to solve the problem we consider when these semantics are used. We show that when given all final acceptability degrees and initial weights, the problems for the weighted h-categoriser and the weighted card-based semantics are both NP-complete, while the problem can be solved in polynomial time for the weighted max-based semantics.

The remainder of this paper is structured as follows. In Section 2, we provide the necessary background to understand the remainder of the paper. Section 3 formalises the decision problem of whether attacks can be found for gradual semantics and then demonstrates that it is NP-complete for some semantics. In Section 4, we discuss solvers for our problem, and consider related and future work (including a partial version of the problem) in Section 5.

2.Background

As discussed above, we situate our work in the context of weighted abstract argumentation frameworks (WAFs), which can be encoded as graphs with weighted nodes. Each argument has an initial weight (also called “basic score” in [36]) drawn from the range [0,1]. The smaller the initial weight of an argument, the weaker the argument. The initial weight of an argument may represent different concepts such as the likelihood degree of its premises [9], the degree of trust in its source [15], or an aggregation of votes provided by users [22] among others. In this paper, the origin of the weights and arguments is left unspecified. Similarly, arguments and attacks are considered abstract notions.

Given an argument a∈A, we refer to w(a) as a’s initial weight. For any argument a∈A, the set {b∈A|(b,a)∈D}, denoted by Att(a), contains all attackers of a. Similarly, we define Att∗(a)={b∈A|(b,a)∈D and w(b)>0}, i.e., the set of attackers of a with strictly positive weights. When the current argumentation framework F is not clear from the context, we will use the notation AttF and AttF∗ respectively.

A gradual semantics σ takes as input a weighted argumentation framework and outputs a function that associates a final acceptability degree for each argument.11 Several such semantics have been described in the literature. In this paper, we focus on three widely used gradual semantics introduced by Amgoud et al., i.e. the weighted h-categoriser, the weighted max-based, and the weighted card-based semantics, denoted σHC, σMB and σCB respectively [4].

The weighted h-categoriser considers the initial weight of an argument as well as the sum of the acceptability degrees of all its attackers to determine the argument’s final acceptability degree. In this semantics, all (non-zero) attackers will be considered when determining the acceptability degree of an argument and the number of attackers is not used.

Next, we consider the weighted max-based semantics which utilises the initial weight of an argument as well as the highest acceptability degrees of its attackers to determine the argument’s final acceptability degree. In this semantics, only the strongest attacker is considered and the number of attackers is not used.

Finally, the weighted card-based semantics considers the initial weight of an argument, the number of its attackers as well as the sum of the acceptability degrees of its attackers to determine the acceptability degree of the considered argument. In this semantics, the number of attackers is the most important factor to determine the acceptability degree of an argument.

We note in passing that the properties for these semantics have been researched in depth by Amgoud et al. [4]. Perhaps the most important property, in the context of this paper, is the convergence of the σHC, σMB and σCB semantics for finite frameworks (see Theorem 7, 12, 17 in [4]). A proof of convergence for a broader class of semantics (including these three) was proved in the work of Oren et al. [33]. This means that for any given argumentation framework, semantics and initial weights, the final acceptability degrees of all arguments can always be computed.

Example 1.

An agent may believe the following arguments.

• a0: Tomatoes older than a week can go rotten; these tomatoes are a week and a half old.

• a1: Tomatoes kept in the fridge (like these ones) can last longer than a week, and so the tomatoes are not rotten.

• a2: My friend ate one of the tomatoes this morning, and it tasted fine, therefore they are not rotten.

• a3: My friend is not very good at discriminating whether something is rotten by taste, so the tomatoes might be rotten.

Here, a0 is attacked by a1 and a2, while the latter is attacked by a3. The agent ascribes each argument with an initial weight encoding the agent’s belief in the applicability or strength of the argument, i.e., w(a0)=0.9, w(a1)=0.7, w(a2)=0.7, and w(a3)=0.6. Fig. 2 illustrates this weighted argumentation framework F=⟨{a0,a1,a2,a3},{(a1,a0),(a2,a0),(a3,a2)},w⟩.

Fig. 2.

The weighted argumentation framework from Example 1.

We consider three different semantics in this paper (defined above); yielding the final acceptability degrees in Table 1. In turn, a reasoner using the weighted h-categoriser semantics σHC or σCB semantics would have preferences a1≻a3≻a2≻a0, while if it were to use σMB preferences would be a1≻a3≻a0≻a2. Note that while the σHC and σCB semantics yield similar preference orderings, the agent would be less sure of its conclusions in the latter case (due to the smaller difference in weights).

Table 1

Final acceptability degrees for each argument of Example 1 (Fig. 2) for σHC, σMB, and σCB

Argument	σHCF(ai)	σMBF(ai)	σCBF(ai)
a0	0.421	0.529	0.258
a1	0.7	0.7	0.7
a2	0.438	0.438	0.269
a3	0.6	0.6	0.6

3.Inferring attacks

In this paper, we focus on the problem of identifying whether we can infer suitable attacks between arguments given their initial weights and desirable final acceptability degrees (as shown at the bottom of Fig. 1). However, we ground most of our discussion in the following, closely-related decision problem: given a gradual argumentation semantics, a set of arguments, and associated information about these arguments (i.e., initial weights and some or all desirable final acceptability degrees), is there an attack relation over the arguments that, according to the semantics, lead to the desirable final acceptability degrees from the initial weights?

In this section, we consider the complete problem, where the initial weights and desirable final acceptability degrees for all arguments are known. We formalise this problem as follows.

We investigate this decision problem for the three gradual semantics σx, for x∈{HC,CB,MB}.

Algorithm 1

Procedure to solve the decision problem DECcMB

Proof.

We show that DECcHC is NP-complete using the subset-sum problem (SSP). Formally, SSP is defined as answering the following question. Consider a multiset of positive numbers M and a number T∈R+, is there a subset M′⊆M such that ∑m′∈M′m′=T?

To prove DECcHC is NP-complete we must demonstrate that it is in NP and identify a polynomial time reduction from SSP to DECcHC.

To demonstrate that DECcHC belongs to NP we observe that the certificate of the problem is a set of attacks. Given a set of attacks, we can check in polynomial time whether S(a)=w(a)/(1+∑b∈Att(a)S(b)) for all a∈A (as we have all initial weights and the desired final acceptability degrees), therefore the problem is in NP.

Fig. 3.

Graphical representation of the polynomial transformation (dashed lines) of an SSP instance (rectangular nodes) into an instance of DECcHC (circular nodes). The initial weight of a0 is 1 (shown in black above a0), and of a1 to an, is equal to their final acceptability degree (where final acceptability degrees are shown in blue). The initial weights of the latter arguments have thus been omitted.

Table 2

The arguments created from Example 2 using the reduction described in Proposition 2. Note that for a1…a5, the initial weight equals the desired final acceptability degree

Argument	Initial weight	Desired final acceptability degree
a0	1	0.96059
a1	0.00944
a2	0.03856
a3	0.00041
a4	0.01518
a5	0.01641

Turning to the reduction, we begin by reducing SSP to DECcHC. Let us assume we have a multiset of positive numbers M={m1,…,mn} and T∈R+. We denote ∑imi by m∗. We then create a set of n+1 arguments A={a0,a1,a2,…,an} such that for all i∈{1,…,n}, S(ai)=w(ai)=(0.4mi)/(nm∗), and we set w(a0)=1 and S(a0)=nm∗/(0.4T+nm∗). This transformation is represented in Fig. 3.

We have proved that DECcHC is in NP and that SSP is polynomial time reducible to DECcHC (the size of the argumentation framework produced is polynomial with respect to the size of the SSP instance), therefore DECcHC is NP-complete. □

Example 3

Example 3(Cont’d Example 2).

We see that the subset sum problem has a solution (using values 23,37 and 40). Analogously, a solution to DECcHC exists by having arguments a1, a4 and a5 attack argument a0, as shown in Fig. 4.

Fig. 4.

Representation of how a solution to an SSP instance (represented with the gray rectangles) can be obtained from a solution to a corresponding instance from DECcHC (the attacks drawn). Blue values for a1…a5 indicate both inital weights and final acceptability degrees, and denote final acceptability degrees for a0, which has an initial weight of 1.

To recap, our results show that DECcMB is polynomial (and indeed, can be solved in linear time), while DECcHB and DECcCB are both NP-complete. This latter result was obtained by a reduction to a variant of the subset-sum problem.

4.Identifying solutions

Rather than simply considering the decision problem, it is useful – if possible – to be able to infer the attacks induced by some set of initial weights and final acceptability degrees. We consider each semantics individually.

4.1.The weighted max-based semantics

For the weighted max-based semantics, it is trivial to modify Algorithm 1 from Proposition 1 to infer a suitable set of attacks (when possible). Rather than simply returning True or False, we return, by modifying lines 5 and 6, any set of attacks X that satisfy the condition that for all a∈A, there exists (x,a)∈X such that w(a)/S(a)=(1+S(x)). Thus, we note that this semantics does little to constrain the attacks in the framework. If we discover that there is an attack from argument ai to argument a0 in a solution, then under the max-based semantics, we can expand this solution by adding additional attacks from any argument aj to a0, where S(aj)⩽S(ai), without affecting the result.

Proposition 4

Proposition 4(Solution Expansion).

Given a set of arguments A, a weighting function w:A→[0,1], and a desirable final acceptability degree function S:A→[0,1]. If D⊆A×A is such that for all a∈A, σMBF(a)=S(a), where F=⟨A,D,w⟩ then for all a∈A, σMBF′(a)=S(a), where F′=⟨A,D′,w⟩, D′=D∪X and X⊆{(ai,aj)|∃(ak,aj)∈D and S(ai)⩽S(ak)}∪{(ai,aj)|w(aj)=0}. We say that D′ is an expansion of D.

Similarly, if we have a set of attacks that achieve the desirable final acceptability degrees for all arguments and there is an attack from ai to a0, then under the max-based semantics, we can contract this solution by removing attacks from any other argument aj to a0, where S(aj)⩽S(ai).

Proposition 5

Proposition 5(Solution Contraction).

Given a set of arguments A, a weighting function w:A→[0,1], and a desirable final acceptability degree function S:A→[0,1]. If D⊆A×A is such that for all a∈A, σMBF(a)=S(a), where F=⟨A,D,w⟩ then for all a∈A, σMBF′(a)=S(a), where (ai,a0)∈D, F′=⟨A,D′,w⟩, D′=D∖X and X⊆{(aj,a0)∈D|aj≠ai and S(aj)⩽S(ai)}∪{(aj,a0)|w(a0)=0}. We say that D′ is a contraction of D (on (ai,a0)∈D).

Example 4.

Let us consider A, w, D as shown in Fig. 5 and the desirable final acceptability degree function S such that S(a0)=0.43, S(a1)=0.30, S(a2)=0.58, and S(a3)=0.30. A contraction D′ of D on (a2,a2) will remove the attacks (a0,a2), (a1,a2), and (a3,a2) from D without changing the acceptability degrees under the max-based semantics. Likewise, an expansion D″ of D′ can be obtained by adding the attack (a0,a2) as this does not change the acceptability degrees. This is represented in Fig. 6.

Fig. 5.

The argumentation framework of Example 4.

Fig. 6.

Representation of F′=⟨A,D′,w⟩ (left), where D′ is a contraction of D on (a2,a2) and F″=⟨A,D″,w⟩ (right), where D″ is an expansion of D′.

Once a solution for the max-based semantics is found, we can reach all the other solutions by expanding this initial solution once and then successively contracting it.

Proposition 6.

Given a set of arguments A, a weighting function w:A→[0,1], and a desirable final acceptability degree function S:A→[0,1]. If D,D′⊆A×A are such that for all a∈A, σMBF(a)=S(a), σMBF′(a)=S(a) where F=⟨A,D,w⟩ and F′=⟨A,D′,w⟩ then there exists D∗⊆A×A, such that D∗ is an expansion of D, and a sequence of sets of attacks (D1,D2,…,Dn), where D1=D∗, Dn=D′ and for all 1⩽i⩽n−1,Di+1 is a contraction of Di.

Proof.

Let us consider A={a1,a2,…,an} and two arbitrary solutions D,D′⊆A×A for DECcMB. We prove this proposition by construction. By definition, for all a∈A, σMBF(a)=σMBF′(a)=S(a), where F=⟨A,D,w⟩ and F′=⟨A,D′,w⟩. This means that for all a∈A, such that w(a)≠0, maxb∈AttF(a)S(b)=maxb∈AttF′(a)S(b). Thus, D∗=D∪D′ is an expansion of D. Then, for all 1⩽i⩽n, it holds that Di+1=Di∖{(aj,ai)∈D|(aj,ai)∉D′} is a contraction of Di, where D1=D∗. It is clear that Dn+1=D′ as all attacks in D∖D′ have been removed from D∗. □

4.2.The weighted h-categoriser semantics

Let us consider the case of the weighted h-categoriser semantics. Given an input A={a1,…,an}, an initial weight function w, and a desirable final acceptability degree function S; we seek a set of attacks D⊆A×A such that for all a∈A, σHCF(a)=S(a), where F=⟨A,D,w⟩.

Recall from the definition of the weighted h-categoriser semantics that any solution must mean that the following equation holds.

S(ai)=w(ai)1+∑b∈Att(ai)S(b)

Moreover, if w(ai)≠0, we can rearrange the previous equation to obtain:

∑b∈Att(ai)S(b)=w(ai)−S(ai)S(ai)

For the complete problem, we are given w(ai) and S(ai) for all ai∈A, allowing us to compute ∑b∈Att(ai)S(b) via the above equation. In other words, for every argument ai, we can compute a target value T=∑b∈Att(ai)S(b) for which the final acceptability degrees of all its attackers must sum up to. By considering the multiset M={S(aj)|aj∈A}, we must solve a single subset-sum problem to identify the attackers for a single argument ai. Extending this to all n=|A| arguments in our framework, we can therefore identify all attacks in the framework by solving n versions of the subset-sum problem. Algorithm 2 provides the pseudo-code for this approach.

Algorithm 2

Procedure to solve DECcHC. SSP (lines 10, 13) calls a subset-sum solver which returns the elements of M that sum up to T, or false if no such elements can be found

We note in passing that the standard version of the subset-sum problem assumes that T and elements of M are all integers. If we assume that all initial weights and final acceptability degrees are rational, we can easily transform our computed T and M values to integers. The most common dynamic programming based approach to solving standard subset-sum can run in pseudo-polynomial time. However, the integers we obtain become very large very quickly, making this approach impractical. Future work will consider using state-of-the-art techniques for solving subset-sum over real numbers instead, e.g. the recent FPTAS of Costandin [13]. In addition, having transformed our problem to an instance of the subset-sum problem opens up the possibility of transforming the problem to other NP-complete problems for which efficient solvers exist, such as satisfiability.

Moreover, once a set of attacks is found to be a solution, we can obtain other solutions by replacing the attacks to a single argument x by other attacks to this argument so that the sum of the degree of the attackers remains the same. Given the simplicity of this proposition, we do not provide a proof for it here.

Proposition 7.

Consider two weighted argumentation frameworks F=⟨A,D,w⟩, F′=⟨A,D′,w⟩, and a desirable final acceptability degree function S:A→[0,1] such that σHCF(a)=S(a) for any a∈A. If all of the following hold

• x∈A

• Z⊆A×{x}

• ∑(z,x)∈ZS(z)=(w(x)−S(x))/S(x) if w(x)≠0

• D′=(D∩(A×(a∖{x})))∪Z

then for all a∈A, σHCF′(a)=S(a).

4.3.The weighted card-based semantics

We can adopt a similar approach for σCB as was done for σHC. We begin by assuming that there are k attacks from arguments with non-zero initial weight against an argument ai. Any solution must mean that the following equation holds:

S(ai)=w(ai)1+k+1k∑b∈Att(ai)S(b)

If w(ai)≠0, rearranging gives us the equation:

∑b∈Att(ai)S(b)=−k(S(ai)k+S(ai)−w(ai))S(ai)

Again, all values on the right-hand side of the equation are given for the complete problem given, allowing us to compute the value of the left-hand side for each argument. Assuming a non-zero number of attacks, while we could (naively) iterate over all k=1…n to identify the number of attacks against an argument, and thereby determine k, we observe that if S(b)=ϵ>0, limϵ→0, for all b∈Att(ai) the semantic equation reduces to the following.

S(ai)=w(ai)1+k

Solving for k, we see that:

k=w(ai)−S(ai)S(ai)

Now assume instead that S(b)=1 for all b∈Att(ai). Performing the same operations means that:

k=w(ai)−2S(ai)S(ai)

These two equations serve as an upper and lower bound for k. Since k must be an integer, we can avoid the need to iterate over the number of attacks by computing k as follows.

k=⌊w(ai)−S(ai)S(ai)⌋=⌈w(ai)−2S(ai)S(ai)⌉

The pseudo-code for this approach is described in Algorithm 3.

Algorithm 3

Procedure to solve DECcCB. kSSP (lines 11, 14) calls a subset-sum solver which returns k elements of M which sum up to T

Since k is known, the kSSP solver called in Algorithm 3 could potentially be more efficient than that used in the h-categoriser semantics.

Analogous to the result from Proposition 7, under the weighted card-based semantics, once a set of attacks is found to be a solution, we can obtain other solutions by replacing the k attacks on a single argument x by another set of k attacks to this argument so that the sum of the final acceptability degree of the attackers remains the same. Given the simplicity of this proposition, we do not provide a proof for it here.

Proposition 8.

Given two weighted argumentation frameworks F=⟨A,D,w⟩, F′=⟨A,D′,w⟩, and a desirable final acceptability degree function S:A→[0,1] such that for all a∈A, σCBF(a)=S(a). If all the following hold:

• x∈A

• Z⊆A×{x}, and

• D′=(D∩(A×(A∖{x})))∪Z,

• |Z|=⌊w(a)−S(a)S(a)⌋ and ∑(z,x)∈ZS(z)=−k(S(x)k+S(x)−w(x))S(x) if w(x)≠0.

then for all a∈A, it is the case that σCBF′(a)=S(a)

Propositions 4, 5, and 6 demonstrate that there are typically a large number of non-minimal argumentation frameworks for the weighted max-based semantics. For the weighted h-categoriser semantics, attacks can be substituted as long as the sum of the final acceptability degrees of the attacking arguments match (see Proposition 7), while for weighted card-based semantics, attacks can only be substituted by a set of attackers of the same size which final acceptability degree sums to the same value (see Proposition 8). We also note that, for all semantics, any argument with an initial weight of 0 can clearly have any number of attacks against it.

5.Discussion and future work

To this point, we have considered only the complete problem of attack inference in gradual argumentation frameworks, and we now briefly discuss the partial problem. Here, we are given a semantics, a set of arguments, a partial mapping between arguments and initial weights, and a partial mapping between arguments and final acceptability degrees, and we must determine whether attacks (and initial weights which were not provided) can be identified which make the given final acceptability degrees consistent with the semantics.

Since the complete problem is a special case of this partial problem, and since we can still verify correctness in polynomial time, the NP-completeness results of Section 3 still apply to the weighted card-based and weighted h-categoriser semantics. The behaviour of the weighted max-based version of the partial problem, which was polynomial in the complete problem, is more challenging to characterise. While it is easy to show that there are polynomial instances of the partial problem (e.g., when all initial weights are given and all but one final acceptability degree is provided), we strongly believe that the general case is NP-complete. We leave proof of this result as an element of future work. Other directions for research include providing a mapping from subset-sum to other problems for which solvers exist (e.g., satisfiability) and evaluating the performance of such solvers.22 Argumentation researchers have found that this approach has often yielded excellent results [40]. In addition, it may be interesting to evaluate such solvers on different (given) underlying graph topologies. Finally, we focused on three gradual semantics in this paper. However, many other weighted semantics have been proposed (e.g., [10,15,18,22,28]), and extending the current work to these, and in particular, to probabilistic semantics [19,23] would be interesting.

Another variant of the problem under consideration would involve identifying whether a subset of attacks from some given possible attacks (rather than all attacks) can be used to make the final acceptability degrees consistent with the initial weights. While this may be more realistic for some applications, from a complexity point of view, the results from the current work directly translate to this version of the problem.

We note in passing that we can consider another inverse problem, namely the computation of semantics for a given weighted argumentation framework and set of final acceptability degrees or preferences over arguments. This problem is trivial to solve in polynomial time, as one simply needs to check for consistency between the inputs (weighted argumentation framework) and outputs (final acceptability degrees or preferences) for each semantics.

Turning to related work, researchers have examined the notion of argument realisability in abstract argumentation frameworks [25], seeking to identify an attack relation that yields a specific labelling or extension. Recent work by Mumford et al. [31] has shown that for complete semantics and IN/OUT labellings the problem is NP-complete, whereas it can be solved in polynomial time if UNDEC labellings are also allowed. The work of Skiba et al. [38] focuses on whether, for a given ranking and ranking-based semantics, we can find an unweighted argumentation framework such that the selected ranking-based semantics induces the ranking when applied to the argumentation framework. They show that the above problem is true for a number of ranking-based semantics, including burden-based and discussion-based semantics [1], the simple product semantics on social abstract frameworks [10,22], and the probabilistic graded semantics [24,39]. Another related area to the current work is argument synthesis [32], where the attack relation must satisfy some positive and negative constraints, but where the problem is not fully constrained. There are still several open questions regarding the time complexity of these types of problems, even for the case of abstract argumentation semantics [31].

More generally, our work can be seen as a type of inverse argumentation problem. [33,34] has examined one such inverse problem in the context of the gradual semantics, seeking to identify a set of initial weights given a semantics, a set of arguments, attacks and final acceptability degrees. In the context of abstract argumentation, such inverse problems have examined inferring preferences from justified arguments [26,27], and has applications in the context of belief revision [8].

The current paper focuses on the complexity of the underlying decision problem and inferring attacks given the semantics, initial weights, and final acceptability degrees. This is arguably unrealistic and limits the applications of the current work. In most uses of gradual semantics, one considers the preferences obtained from final acceptability degrees rather than the final acceptability degrees themselves, as the latter are not (normally) exposed within an application. Thus, as future work, we intend to consider the problem of inferring attacks from a semantics, initial weights, and preferences over arguments. We believe that the complexity of this problem for a given semantics will be similar to that obtained in the current work. Given this more general problem one could, for example, determine whether an agent is rational given the initial weights they assign to a set of arguments, a semantics, and a resulting preference ordering over the arguments. Other applications, as discussed above, include opponent modelling [37] in the context of dialogue and preference elicitation.

6.Conclusions

We have considered the problem of inferring an attack relation given a gradual semantics and all initial weights and final acceptability degrees for an argumentation framework. We have shown that for the weighted max-based semantics, this problem can be solved in linear time, but that the obtained solution is (typically) not unique. For the weighted h-categoriser and weighted card-based semantics, where solutions have no redundancies, the problem becomes NP-complete. Our proofs are based on a reduction to variants of the subset-sum problem, and efficient solvers for this problem can be applied to our work, facilitating its application in domains such as opponent modelling. Finally, we have focused on the complete problem, and there are exciting avenues for future research dealing with its partial form.