Inferring attack relations for gradual semantics

Abstract

A gradual semantics takes a weighted argumentation framework as input and outputs a final acceptability degree for each argument, with different semantics performing the computation in different manners. In this work, we consider the problem of attack inference. That is, given a gradual semantics, a set of arguments with associated initial weights, and the final desirable acceptability degrees associated with each argument, we seek to determine whether there is a set of attacks on those arguments such that we can obtain these acceptability degrees. The main contribution of our work is to demonstrate that the associated decision problem, i.e., whether a set of attacks can exist which allows the final acceptability degrees to occur for given initial weights, is NP-complete for the weighted h-categoriser and card-based semantics, and is polynomial for the weighted max-based semantics, even for the complete version of the problem (where all initial weights and final acceptability degrees are known). We then briefly discuss how this decision problem can be modified to find the attacks themselves and conclude by examining the partial problem where not all initial weights or final acceptability degrees may be known.

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\mathrm{,}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.

Definition 1.

A (abstract) weighted argumentation framework is a triple $\mathcal{F}=⟨\mathcal{A}\mathrm{,}\mathcal{D}\mathrm{,}\mathit{w}⟩$ where $\mathcal{A}$ is a finite set of arguments, $\mathcal{D}\subseteq \mathcal{A}\times \mathcal{A}$ is a binary attack relation, and $\mathit{w}:\mathcal{A}\to [0\mathrm{,}1]$ is a total weighting function which associates an initial weight between 0 and 1 to each argument.

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

A gradual semantics σ takes as input a weighted argumentation framework and outputs a function that associates a final acceptability degree for each argument.1 ¹

Often, the final step in using a gradual semantics involves using this final acceptability degree to compute a preference ordering over arguments.

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 ${\mathit{\sigma }}_{\mathit{HC}}$ , ${\mathit{\sigma }}_{\mathit{MB}}$ and ${\mathit{\sigma }}_{\mathit{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.

Definition 2.

The weighted h-categoriser semantics, denoted ${\mathit{\sigma }}_{\mathit{HC}}$ , is the function that takes as input any weighted argumentation framework $\mathcal{F}=⟨\mathcal{A}\mathrm{,}\mathcal{D}\mathrm{,}\mathit{w}⟩$ and returns the function ${\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}:\mathcal{A}\to [0\mathrm{,}1]$ such that for all $\mathit{a}\in \mathcal{A}$ , ${\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}\mathrm{(}\mathit{a}\mathrm{)}={\mathit{HC}}_{\infty }\mathrm{(}\mathit{a}\mathrm{)}$ , where: $$\begin{array}{c}{\mathit{HC}}_{\mathit{i}}\mathrm{(}\mathit{a}\mathrm{)}=\left\{\begin{array}{ll}\mathit{w}\mathrm{(}\mathit{a}\mathrm{)}& \text{if }\mathit{i}=0\\ \frac{\mathit{w}\mathrm{(}\mathit{a}\mathrm{)}}{1+{\sum }_{\mathit{b}\in \mathtt{Att}\mathrm{(}\mathit{a}\mathrm{)}}{\mathit{HC}}_{\mathit{i}-1}\mathrm{(}\mathit{b}\mathrm{)}}& \text{otherwise}\end{array}\right.\end{array}$$

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.

Definition 3.

The weighted max-based semantics, denoted ${\mathit{\sigma }}_{\mathit{MB}}$ , is the function that takes as input any weighted argumentation framework $\mathcal{F}=⟨\mathcal{A}\mathrm{,}\mathcal{D}\mathrm{,}\mathit{w}⟩$ and returns the function ${\mathit{\sigma }}_{\mathit{MB}}^{\mathcal{F}}:\mathcal{A}\to [0\mathrm{,}1]$ such that for all $\mathit{a}\in \mathcal{A}$ , ${\mathit{\sigma }}_{\mathit{MB}}^{\mathcal{F}}\mathrm{(}\mathit{a}\mathrm{)}={\mathit{MB}}_{\infty }\mathrm{(}\mathit{a}\mathrm{)}$ , where: $$\begin{array}{c}{\mathit{MB}}_{\mathit{i}}\mathrm{(}\mathit{a}\mathrm{)}=\left\{\begin{array}{ll}\mathit{w}\mathrm{(}\mathit{a}\mathrm{)}& \text{if }\mathit{i}=0\\ \frac{\mathit{w}\mathrm{(}\mathit{a}\mathrm{)}}{1+{max}_{\mathit{b}\in \mathtt{Att}\mathrm{(}\mathit{a}\mathrm{)}}{\mathit{MB}}_{\mathit{i}-1}\mathrm{(}\mathit{b}\mathrm{)}}& \text{otherwise}\end{array}\right.\end{array}$$

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.

Definition 4.

The weighted card-based semantics, denoted ${\mathit{\sigma }}_{\mathit{CB}}$ , is the function that takes as input any weighted argumentation framework $\mathcal{F}=⟨\mathcal{A}\mathrm{,}\mathcal{D}\mathrm{,}\mathit{w}⟩$ and returns the function ${\mathit{\sigma }}_{\mathit{CB}}^{\mathcal{F}}:\mathcal{A}\to [0\mathrm{,}1]$ such that for all $\mathit{a}\in \mathcal{A}$ , ${\mathit{\sigma }}_{\mathit{CB}}^{\mathcal{F}}\mathrm{(}\mathit{a}\mathrm{)}={\mathit{CB}}_{\infty }\mathrm{(}\mathit{a}\mathrm{)}$ , where: $$\begin{array}{c}{\mathit{CB}}_{\mathit{i}}\mathrm{(}\mathit{a}\mathrm{)}=\left\{\begin{array}{ll}\mathit{w}\mathrm{(}\mathit{a}\mathrm{)}& \text{if }\mathit{i}=0\text{ or }|{\mathtt{Att}}^{\ast }\mathrm{(}\mathit{a}\mathrm{)}|=0\\ \frac{\mathit{w}\mathrm{(}\mathit{a}\mathrm{)}}{1+|{\mathtt{Att}}^{\ast }\mathrm{(}\mathit{a}\mathrm{)}|+\frac{{\sum }_{\mathit{b}\in {\mathtt{Att}}^{\ast }\mathrm{(}\mathit{a}\mathrm{)}}{\mathit{CB}}_{\mathit{i}-1}\mathrm{(}\mathit{b}\mathrm{)}}{|{\mathtt{Att}}^{\ast }\mathrm{(}\mathit{a}\mathrm{)}|}}& \text{otherwise}\end{array}\right.\end{array}$$

Here, $|{\mathtt{Att}}^{\ast }\mathrm{(}\mathit{a}\mathrm{)}|$ denotes the number of arguments attacking a with non-zero final acceptability degree.

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 ${\mathit{\sigma }}_{\mathit{HC}}$ , ${\mathit{\sigma }}_{\mathit{MB}}$ and ${\mathit{\sigma }}_{\mathit{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.

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

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

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

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

Here, ${\mathit{a}}_0$ is attacked by ${\mathit{a}}_1$ and ${\mathit{a}}_2$ , while the latter is attacked by ${\mathit{a}}_3$ . The agent ascribes each argument with an initial weight encoding the agent’s belief in the applicability or strength of the argument, i.e., $\mathit{w}\mathrm{(}{\mathit{a}}_0\mathrm{)}=0.9$ , $\mathit{w}\mathrm{(}{\mathit{a}}_1\mathrm{)}=0.7$ , $\mathit{w}\mathrm{(}{\mathit{a}}_2\mathrm{)}=0.7$ , and $\mathit{w}\mathrm{(}{\mathit{a}}_3\mathrm{)}=0.6$ . Fig. 2 illustrates this weighted argumentation framework $\mathcal{F}=⟨\{{\mathit{a}}_0\mathrm{,}{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\mathrm{,}{\mathit{a}}_3\}\mathrm{,}\{\mathrm{(}{\mathit{a}}_1\mathrm{,}{\mathit{a}}_0\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{a}}_2\mathrm{,}{\mathit{a}}_0\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{a}}_3\mathrm{,}{\mathit{a}}_2\mathrm{)}\}\mathrm{,}\mathit{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 ${\mathit{\sigma }}_{\mathit{HC}}$ or ${\mathit{\sigma }}_{\mathit{CB}}$ semantics would have preferences ${\mathit{a}}_1\succ {\mathit{a}}_3\succ {\mathit{a}}_2\succ {\mathit{a}}_0$ , while if it were to use ${\mathit{\sigma }}_{\mathit{MB}}$ preferences would be ${\mathit{a}}_1\succ {\mathit{a}}_3\succ {\mathit{a}}_0\succ {\mathit{a}}_2$ . Note that while the ${\mathit{\sigma }}_{\mathit{HC}}$ and ${\mathit{\sigma }}_{\mathit{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 ${\mathit{\sigma }}_{\mathit{HC}}$ , ${\mathit{\sigma }}_{\mathit{MB}}$ , and ${\mathit{\sigma }}_{\mathit{CB}}$

Argument	${\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$	${\mathit{\sigma }}_{\mathit{MB}}^{\mathcal{F}}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$	${\mathit{\sigma }}_{\mathit{CB}}^{\mathcal{F}}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$
${\mathit{a}}_0$	0.421	0.529	0.258
${\mathit{a}}_1$	0.7	0.7	0.7
${\mathit{a}}_2$	0.438	0.438	0.269
${\mathit{a}}_3$	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.

Problem 1.

The decision problem ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{x}}$ , where $\mathit{x}\in \{\mathit{MB}\mathrm{,}\mathit{HC}\mathrm{,}\mathit{CB}\}$ is: Given a set of arguments $\mathcal{A}$ , a gradual semantics ${\mathit{\sigma }}_{\mathit{x}}$ , a weighting function w, and a total desired final acceptability degree function $\mathit{S}:\mathcal{A}\to [0\mathrm{,}1]$ , is there a set of attacks $\mathcal{D}\subseteq \mathcal{A}\times \mathcal{A}$ such that for all $\mathit{a}\in \mathcal{A}$ , ${\mathit{\sigma }}_{\mathit{x}}^{\mathcal{F}}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}$ , where $\mathcal{F}=⟨\mathcal{A}\mathrm{,}\mathcal{D}\mathrm{,}\mathit{w}⟩$ ?

We investigate this decision problem for the three gradual semantics ${\mathit{\sigma }}_{\mathit{x}}$ , for $\mathit{x}\in \{\mathit{HC}\mathrm{,}\mathit{CB}\mathrm{,}\mathit{MB}\}$ .

Proposition 1.

${\mathcal{DEC}}_{\mathit{c}}^{\mathit{MB}}$ is polynomial and can be decided in $\mathit{O}\mathrm{(}\mathit{n}\mathrm{)}$ time and space.

Proof.

We create the set $\mathit{L}=\{1+\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}|\mathit{b}\in \mathcal{A}\}$ , for which an $\mathit{O}\mathrm{(}1\mathrm{)}$ lookup can be performed. We can then use Algorithm 1 to solve ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{MB}}$ :

In the Algorithm 1, line 2 checks whether arguments with zero (resp. non-zero) initial weights and non-zero (resp. zero) desired final acceptability degrees exist; the presence of such arguments would mean that the weighted-max-based semantics cannot be satisfied (line 3). Line 5 then checks the existence of an attacking argument with a suitable acceptability degree (via a lookup in the set L) to satisfy the weighted-max-based semantics in $\mathit{O}\mathrm{(}1\mathrm{)}$ time. Since lines 1–8 iterate over all arguments, the time complexity is $\mathit{O}\mathrm{(}\mathit{n}\mathrm{)}$ ; similarly, storing L takes $\mathit{O}\mathrm{(}\mathit{n}\mathrm{)}$ space.

Algorithm 1

Procedure to solve the decision problem ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{MB}}$

Proposition 2.

${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HC}}$ is NP-complete.

Proof.

We show that ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HC}}$ is NP-complete using the subset-sum problem ( $\mathcal{SSP}$ ). Formally, $\mathcal{SSP}$ is defined as answering the following question. Consider a multiset of positive numbers M and a number $\mathit{T}\in {\mathbb{R}}^{+}$ , is there a subset ${\mathit{M}}^{\prime }\subseteq \mathit{M}$ such that ${\sum }_{{\mathit{m}}^{\prime }\in {\mathit{M}}^{\prime }}{\mathit{m}}^{\prime }=\mathit{T}$ ?

To prove ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HC}}$ is NP-complete we must demonstrate that it is in NP and identify a polynomial time reduction from $\mathcal{SSP}$ to ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HC}}$ .

To demonstrate that ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HC}}$ 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 $\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{w}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{/}\mathrm{(}1+{\sum }_{\mathit{b}\in \mathtt{Att}\mathrm{(}\mathit{a}\mathrm{)}}\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}\mathrm{)}$ for all $\mathit{a}\in \mathcal{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 $\mathcal{SSP}$ instance (rectangular nodes) into an instance of ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HC}}$ (circular nodes). The initial weight of ${\mathit{a}}_0$ is 1 (shown in black above ${\mathit{a}}_0$ ), and of ${\mathit{a}}_1$ to ${\mathit{a}}_{\mathit{n}}$ , 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 ${\mathit{a}}_1\dots {\mathit{a}}_5$ , the initial weight equals the desired final acceptability degree

Argument	Initial weight	Desired final acceptability degree
${\mathit{a}}_0$	1	0.96059
${\mathit{a}}_1$	0.00944
${\mathit{a}}_2$	0.03856
${\mathit{a}}_3$	0.00041
${\mathit{a}}_4$	0.01518
${\mathit{a}}_5$	0.01641

Turning to the reduction, we begin by reducing $\mathcal{SSP}$ to ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HC}}$ . Let us assume we have a multiset of positive numbers $\mathit{M}=\{{\mathit{m}}_1\mathrm{,}\dots \mathrm{,}{\mathit{m}}_{\mathit{n}}\}$ and $\mathit{T}\in {\mathbb{R}}^{+}$ . We denote ${\sum }_{\mathit{i}}{\mathit{m}}_{\mathit{i}}$ by ${\mathit{m}}^{\ast }$ . We then create a set of $\mathit{n}+1$ arguments $\mathcal{A}=\{{\mathit{a}}_0\mathrm{,}{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{n}}\}$ such that for all $\mathit{i}\in \{1\mathrm{,}\dots \mathrm{,}\mathit{n}\}$ , $\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}=\mathit{w}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}=\mathrm{(}0.4{\mathit{m}}_{\mathit{i}}\mathrm{)}\mathrm{/}\mathrm{(}\mathit{n}{\mathit{m}}^{\ast }\mathrm{)}$ , and we set $\mathit{w}\mathrm{(}{\mathit{a}}_0\mathrm{)}=1$ and $\mathit{S}\mathrm{(}{\mathit{a}}_0\mathrm{)}=\mathit{n}{\mathit{m}}^{\ast }\mathrm{/}\mathrm{(}0.4\mathit{T}+\mathit{n}{\mathit{m}}^{\ast }\mathrm{)}$ . This transformation is represented in Fig. 3.

Example 2.

Consider the $\mathcal{SSP}$ instance where $\mathit{T}=100$ and $\mathit{M}=\{23\mathrm{,}94\mathrm{,}1\mathrm{,}37\mathrm{,}40\}$ . Here, $\mathit{n}=5$ and ${\mathit{m}}^{\ast }=195$ . Using our transformation, we obtain the arguments, initial weights, and final acceptability degrees shown in Table 2.

• We now demonstrate that using the above reduction, denoted g, if there exists a solution to an instance x of $\mathcal{SSP}$ , then the instance $\mathit{g}\mathrm{(}\mathit{x}\mathrm{)}$ of ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HC}}$ also has a solution. If there exists an ${\mathit{M}}^{\prime }\subseteq \mathit{M}$ such that ${\sum }_{{\mathit{m}}^{\prime }\in {\mathit{M}}^{\prime }}{\mathit{m}}^{\prime }=\mathit{T}$ , then $\mathcal{D}=\{\mathrm{(}\mathit{f}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{,}{\mathit{a}}_0\mathrm{)}|\mathit{m}\in {\mathit{M}}^{\prime }\}$ is a set of attacks such that for all $\mathit{a}\in \mathcal{A}$ , ${\mathit{\sigma }}^{\mathcal{F}}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}$ , where f associates the corresponding argument and $\mathcal{F}=⟨\mathcal{A}\mathrm{,}\mathcal{D}\mathrm{,}\mathit{w}⟩$ . Indeed, we have for all $\mathit{i}\in \{1\mathrm{,}\dots \mathrm{,}\mathit{n}\}$ , ${\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}=\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ since ${\mathit{a}}_{\mathit{i}}$ is not attacked and: $$\begin{array}{rl}{\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}\mathrm{(}{\mathit{a}}_0\mathrm{)}& ={\displaystyle \frac{1}{1+{\sum }_{\mathit{m}\in {\mathit{M}}^{\prime }}\mathit{S}\mathrm{(}\mathit{f}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}}}\\ & ={\displaystyle \frac{1}{1+\frac{0.4\mathit{T}}{\mathit{n}{\mathit{m}}^{\ast }}}}\\ & ={\displaystyle \frac{\mathit{n}{\mathit{m}}^{\ast }}{\mathit{n}{\mathit{m}}^{\ast }+0.4\mathit{T}}}\\ & =\mathit{S}\mathrm{(}{\mathit{a}}_0\mathrm{)}\end{array}$$

• We now show the reduction in the other direction – if an instance $\mathit{g}\mathrm{(}\mathit{x}\mathrm{)}$ of ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HC}}$ has a solution then the instance x of $\mathcal{SSP}$ has a solution. If there exists $\mathcal{D}\subseteq \mathcal{A}\times \mathcal{A}$ such that for all $\mathit{b}\in \mathcal{A}$ , ${\mathit{\sigma }}^{\mathcal{F}}\mathrm{(}\mathit{b}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}$ , then ${\mathit{M}}^{\prime }=\{\mathrm{(}\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}\mathit{n}{\mathit{m}}^{\ast }\mathrm{)}\mathrm{/}0.4|\mathrm{(}\mathit{b}\mathrm{,}{\mathit{a}}_0\mathrm{)}\in \mathcal{D}\}\subseteq \mathit{M}$ is such that ${\sum }_{{\mathit{m}}^{\prime }\in {\mathit{M}}^{\prime }}{\mathit{m}}^{\prime }=\mathit{T}$ , where $\mathcal{F}=⟨\mathcal{A}\mathrm{,}\mathcal{D}\mathrm{,}\mathit{w}⟩$ . Indeed: $$\begin{array}{rl}{\displaystyle \sum }_{{\mathit{m}}^{\prime }\in {\mathit{M}}^{\prime }}{\mathit{m}}^{\prime }& =\mathrm{(}{\displaystyle \sum }_{\mathrm{(}\mathit{b}\mathrm{,}{\mathit{a}}_0\mathrm{)}\in \mathcal{D}}\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}\mathrm{)}{\displaystyle \frac{\mathit{n}{\mathit{m}}^{\ast }}{0.4}}\\ & =\mathrm{(}{\displaystyle \sum }_{\mathrm{(}\mathit{b}\mathrm{,}{\mathit{a}}_0\mathrm{)}\in \mathcal{D}}{\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}\mathrm{(}\mathit{b}\mathrm{)}\mathrm{)}{\displaystyle \frac{\mathit{n}{\mathit{m}}^{\ast }}{0.4}}\\ & =\mathrm{(}{\displaystyle \frac{1}{\frac{\mathit{n}{\mathit{m}}^{\ast }}{0.4\mathit{T}+\mathit{n}{\mathit{m}}^{\ast }}}}-1\mathrm{)}{\displaystyle \frac{\mathit{n}{\mathit{m}}^{\ast }}{0.4}}\\ & =\mathrm{\left(}{\displaystyle \frac{0.4\mathit{T}}{\mathit{n}{\mathit{m}}^{\ast }}}\mathrm{\right)}{\displaystyle \frac{\mathit{n}{\mathit{m}}^{\ast }}{0.4}}\\ & =\mathit{T}\end{array}$$

  Note that $\mathrm{(}{\mathit{a}}_0\mathrm{,}{\mathit{a}}_0\mathrm{)}\notin \mathcal{D}$ . Indeed, if $\mathrm{(}{\mathit{a}}_0\mathrm{,}{\mathit{a}}_0\mathrm{)}\in \mathcal{D}$ then we have that ${\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}\mathrm{(}{\mathit{a}}_0\mathrm{)}=1\mathrm{/}\mathrm{(}1+{\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}\mathrm{(}{\mathit{a}}_0\mathrm{)}+\mathit{Y}\mathrm{)}$ , where $\mathit{Y}={\sum }_{\mathit{b}\in \mathtt{Att}\mathrm{(}{\mathit{a}}_0\mathrm{)}\setminus \{{\mathit{a}}_0\}}{\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}\mathrm{(}\mathit{b}\mathrm{)}$ . Hence, $\mathrm{(}{\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}{\mathrm{(}{\mathit{a}}_0\mathrm{)}}^2+{\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}\mathrm{(}{\mathit{a}}_0\mathrm{)}-1\mathrm{)}\mathrm{/}\mathrm{(}-{\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}\mathrm{(}{\mathit{a}}_0\mathrm{)}\mathrm{)}=\mathit{Y}$ and since $\mathit{Y}⩾0$ , we conclude that $0⩽{\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}\mathrm{(}{\mathit{a}}_0\mathrm{)}⩽\frac{-1+\sqrt{5}}{2}\simeq 0.618$ . However, we get a contradiction as $\mathit{S}\mathrm{(}{\mathit{a}}_0\mathrm{)}={\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}\mathrm{(}{\mathit{a}}_0\mathrm{)}$ and: $$\begin{array}{c}{\displaystyle \frac{\mathit{T}}{\mathit{n}{\mathit{m}}^{\ast }}}⩽1\\ {\displaystyle \frac{0.4\mathit{T}}{\mathit{n}{\mathit{m}}^{\ast }}}⩽0.4\\ {\displaystyle \frac{0.4\mathit{T}+\mathit{n}{\mathit{m}}^{\ast }}{\mathit{n}{\mathit{m}}^{\ast }}}⩽1.4\\ \mathit{S}\mathrm{(}{\mathit{a}}_0\mathrm{)}⩾0.714\end{array}$$

We have proved that ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HC}}$ is in NP and that $\mathcal{SSP}$ is polynomial time reducible to ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HC}}$ (the size of the argumentation framework produced is polynomial with respect to the size of the $\mathcal{SSP}$ instance), therefore ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HC}}$ is NP-complete. □

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 ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HC}}$ exists by having arguments ${\mathit{a}}_1$ , ${\mathit{a}}_4$ and ${\mathit{a}}_5$ attack argument ${\mathit{a}}_0$ , as shown in Fig. 4.

Fig. 4.

Representation of how a solution to an $\mathcal{SSP}$ instance (represented with the gray rectangles) can be obtained from a solution to a corresponding instance from ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HC}}$ (the attacks drawn). Blue values for ${\mathit{a}}_1\dots {\mathit{a}}_5$ indicate both inital weights and final acceptability degrees, and denote final acceptability degrees for ${\mathit{a}}_0$ , which has an initial weight of 1.

Proposition 3.

${\mathcal{DEC}}_{\mathit{c}}^{\mathit{CB}}$ is NP-complete.

Proof.

Similar to the previous proof, we show that ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{CB}}$ is NP-complete using the k-subset-sum problem ( $\mathit{k}\mathcal{SSP}$ ). Formally, $\mathit{k}\mathcal{SSP}$ is defined as answering the following question. Consider a multiset of positive numbers M and a number $\mathit{T}\in {\mathbb{R}}^{+}$ , is there a subset ${\mathit{M}}^{\prime }\subseteq \mathit{M}$ such that ${\sum }_{{\mathit{m}}^{\prime }\in {\mathit{M}}^{\prime }}{\mathit{m}}^{\prime }=\mathit{T}$ and $|{\mathit{M}}^{\prime }|=\mathit{k}$ ?

We first observe that the certificate of the problem ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{CB}}$ is a set of attacks. Given a set of attacks, we can check in polynomial time whether $\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{w}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{/}\mathrm{(}1+|{\mathtt{Att}}^{\ast }\mathrm{(}\mathit{a}\mathrm{)}|+{\sum }_{\mathit{b}\in {\mathtt{Att}}^{\ast }\mathrm{(}\mathit{a}\mathrm{)}}\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}\mathrm{/}|{\mathtt{Att}}^{\ast }\mathrm{(}\mathit{a}\mathrm{)}|\mathrm{)}$ for all $\mathit{a}\in \mathcal{A}$ , meaning that the problem is in NP.

We now reduce $\mathit{k}\mathcal{SSP}$ to ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{CB}}$ . Let us assume we have a multiset of positive numbers $\mathit{M}=\{{\mathit{m}}_1\mathrm{,}\dots \mathrm{,}{\mathit{m}}_{\mathit{n}}\}$ , $1⩽\mathit{k}⩽\mathit{n}$ , and $\mathit{T}\in {\mathbb{R}}^{+}$ . We denote by ${\mathit{m}}^{\ast }={max}_{{\mathit{m}}_{\mathit{i}}\in \mathit{M}}{\mathit{m}}_{\mathit{i}}$ and $\mathit{u}=\frac{\sqrt{{\mathit{k}}^2+2\mathit{k}+4\mathrm{/}\mathit{k}+1}-\mathit{k}-1}{3}$ (note that $\mathit{u}\in ]0\mathrm{,}\mathrm{(}2\sqrt{2}-2\mathrm{)}\mathrm{/}3]$ when $\mathit{k}⩾1$ ). We create $\mathit{n}+1$ arguments $\mathcal{A}=\{{\mathit{a}}_0\mathrm{,}{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{n}}\}$ such that for all $\mathit{i}\in \{1\mathrm{,}\dots \mathrm{,}\mathit{n}\}$ , $\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}=\mathit{w}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}=\mathit{u}{\mathit{m}}_{\mathit{i}}\mathrm{/}{\mathit{m}}^{\ast }$ and we set $\mathit{w}\mathrm{(}{\mathit{a}}_0\mathrm{)}=1$ and $\mathit{S}\mathrm{(}{\mathit{a}}_0\mathrm{)}=1\mathrm{/}\mathrm{(}1+\mathit{k}+\mathit{T}\mathit{u}\mathrm{/}\mathrm{(}\mathit{k}{\mathit{m}}^{\ast }\mathrm{)}\mathrm{)}$ .

If there exists an ${\mathit{M}}^{\prime }\subseteq \mathit{M}$ such that ${\sum }_{{\mathit{m}}^{\prime }\in {\mathit{M}}^{\prime }}{\mathit{m}}^{\prime }=\mathit{T}$ and $|{\mathit{M}}^{\prime }|=\mathit{k}$ , then $\mathcal{D}=\{\mathrm{(}\mathit{f}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{,}{\mathit{a}}_0\mathrm{)}|\mathit{m}\in {\mathit{M}}^{\prime }\}$ is a set of k attacks such that for all $\mathit{a}\in \mathcal{A}$ , ${\mathit{\sigma }}^{\mathcal{F}}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}$ , where f associates the corresponding argument with m and $\mathcal{F}=⟨\mathcal{A}\mathrm{,}\mathcal{D}\mathrm{,}\mathit{w}⟩$ . Indeed, we have for all $\mathit{i}\in \{1\mathrm{,}\dots \mathrm{,}\mathit{n}\}$ , ${\mathit{\sigma }}_{\mathit{CB}}^{\mathcal{F}}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}=\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ since ${\mathit{a}}_{\mathit{i}}$ is not attacked and: $$\begin{array}{rl}{\mathit{\sigma }}_{\mathit{CB}}^{\mathcal{F}}\mathrm{(}{\mathit{a}}_0\mathrm{)}& ={\displaystyle \frac{1}{1+\mathit{k}+\frac{{\sum }_{\mathit{m}\in {\mathit{M}}^{\prime }}\mathit{S}\mathrm{(}\mathit{f}\mathrm{(}\mathit{m}\mathrm{)}\mathrm{)}}{\mathit{k}}}}\\ & ={\displaystyle \frac{1}{1+\mathit{k}+\frac{\frac{\mathit{T}\mathit{u}}{{\mathit{m}}^{\ast }}}{\mathit{k}}}}\\ & ={\displaystyle \frac{1}{1+\mathit{k}+\frac{\mathit{T}\mathit{u}}{\mathit{k}{\mathit{m}}^{\ast }}}}\end{array}$$

Assume we have a solution to the associated ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{CB}}$ instance, i.e. we have $\mathcal{D}\subseteq \mathcal{A}\times \mathcal{A}$ such that for all $\mathit{b}\in \mathcal{A}$ , ${\mathit{\sigma }}^{\mathcal{F}}\mathrm{(}\mathit{b}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}$ . We know that ${\mathit{a}}_0$ is attacked by k arguments in $\mathcal{D}$ as its value lies between $[1\mathrm{/}\mathrm{(}\mathit{k}+2\mathrm{)}\mathrm{,}1\mathrm{/}\mathrm{(}\mathit{k}+1\mathrm{)}]$ and that arguments ${\mathit{a}}_1$ to ${\mathit{a}}_{\mathit{n}}$ are not attacked (except if they or their attackers have initial weights of 0). We can build ${\mathit{M}}^{\prime }=\{\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}\ast {\mathit{m}}^{\ast }\mathrm{/}\mathit{u}|\mathrm{(}\mathit{b}\mathrm{,}{\mathit{a}}_0\mathrm{)}\in \mathcal{D}\}\subseteq \mathit{M}$ such that $|{\mathit{M}}^{\prime }|=\mathit{k}$ and ${\sum }_{{\mathit{m}}^{\prime }\in {\mathit{M}}^{\prime }}{\mathit{m}}^{\prime }=\mathit{T}$ . Indeed: $$\begin{array}{rl}{\displaystyle \sum }_{{\mathit{m}}^{\prime }\in {\mathit{M}}^{\prime }}{\mathit{m}}^{\prime }& =\mathrm{(}{\displaystyle \sum }_{\mathrm{(}\mathit{b}\mathrm{,}{\mathit{a}}_0\mathrm{)}\in \mathcal{D}}\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}\mathrm{)}{\displaystyle \frac{{\mathit{m}}^{\ast }}{\mathit{u}}}\\ & =\mathrm{\left(}{\displaystyle \frac{\mathit{T}\mathit{u}}{{\mathit{m}}^{\ast }}}\mathrm{\right)}{\displaystyle \frac{{\mathit{m}}^{\ast }}{\mathit{u}}}\\ & =\mathit{T}\end{array}$$

We show that $\mathrm{(}{\mathit{a}}_0\mathrm{,}{\mathit{a}}_0\mathrm{)}\notin \mathcal{D}$ by contradiction. Assume we have this self-attack, then the maximum value with self attack possible for ${\mathit{\sigma }}_{\mathit{CB}}^{\mathcal{F}}\mathrm{(}{\mathit{a}}_0\mathrm{)}$ is determined by computing the unique fixed-point of the function $\mathit{z}\mathrm{(}\mathit{x}\mathrm{)}=1\mathrm{/}\mathrm{(}1+\mathit{k}+\mathit{x}\mathrm{/}\mathit{k}\mathrm{)}$ which is: $$\begin{array}{c}0\mathrm{<}{\displaystyle \frac{-{\mathit{k}}^2+\sqrt{\mathit{k}\mathrm{(}{\mathit{k}}^3+2{\mathit{k}}^2+\mathit{k}+4\mathrm{)}}-\mathit{k}}{2}}⩽1\end{array}$$

Moreover, it holds that: $$\begin{array}{rl}{\displaystyle \frac{-{\mathit{k}}^2+\sqrt{\mathit{k}\mathrm{(}{\mathit{k}}^3+2{\mathit{k}}^2+\mathit{k}+4\mathrm{)}}-\mathit{k}}{2}}& \mathrm{<}{\displaystyle \frac{1}{1+\mathit{k}+\mathit{u}}}\\ & \mathrm{<}{\displaystyle \frac{1}{1+\mathit{k}+\frac{\mathit{T}\mathit{u}}{\mathit{k}{\mathit{m}}^{\ast }}}}\\ & \mathrm{<}\mathit{S}\mathrm{(}{\mathit{a}}_0\mathrm{)}\end{array}$$

This is a contradiction with $\mathit{S}\mathrm{(}{\mathit{a}}_0\mathrm{)}={\mathit{\sigma }}_{\mathit{CB}}^{\mathcal{F}}\mathrm{(}{\mathit{a}}_0\mathrm{)}$ .

□

To recap, our results show that ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{MB}}$ is polynomial (and indeed, can be solved in linear time), while ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HB}}$ and ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{CB}}$ 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 $\mathit{a}\in \mathcal{A}$ , there exists $\mathrm{(}\mathit{x}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{X}$ such that $\mathit{w}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{/}\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}=\mathrm{(}1+\mathit{S}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{)}$ . 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 ${\mathit{a}}_{\mathit{i}}$ to argument ${\mathit{a}}_0$ in a solution, then under the max-based semantics, we can expand this solution by adding additional attacks from any argument ${\mathit{a}}_{\mathit{j}}$ to ${\mathit{a}}_0$ , where $\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{j}}\mathrm{)}⩽\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ , without affecting the result.

Proposition 4 (Solution Expansion).

Given a set of arguments $\mathcal{A}$ , a weighting function $\mathit{w}:\mathcal{A}\to [0\mathrm{,}1]$ , and a desirable final acceptability degree function $\mathit{S}:\mathcal{A}\to [0\mathrm{,}1]$ . If $\mathcal{D}\subseteq \mathcal{A}\times \mathcal{A}$ is such that for all $\mathit{a}\in \mathcal{A}$ , ${\mathit{\sigma }}_{\mathit{MB}}^{\mathcal{F}}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}$ , where $\mathcal{F}=⟨\mathcal{A}\mathrm{,}\mathcal{D}\mathrm{,}\mathit{w}⟩$ then for all $\mathit{a}\in \mathcal{A}$ , ${\mathit{\sigma }}_{\mathit{MB}}^{{\mathcal{F}}^{\prime }}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}$ , where ${\mathcal{F}}^{\prime }=⟨\mathcal{A}\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}\mathit{w}⟩$ , ${\mathcal{D}}^{\prime }=\mathcal{D}\cup \mathit{X}$ and $\mathit{X}\subseteq \{\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{,}{\mathit{a}}_{\mathit{j}}\mathrm{)}|\exists \mathrm{(}{\mathit{a}}_{\mathit{k}}\mathrm{,}{\mathit{a}}_{\mathit{j}}\mathrm{)}\in \mathcal{D}\mathit{\text{ and }}\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}⩽\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{k}}\mathrm{)}\}\cup \{\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{,}{\mathit{a}}_{\mathit{j}}\mathrm{)}|\mathit{w}\mathrm{(}{\mathit{a}}_{\mathit{j}}\mathrm{)}=0\}$ . We say that ${\mathcal{D}}^{\prime }$ is an expansion of $\mathcal{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 ${\mathit{a}}_{\mathit{i}}$ to ${\mathit{a}}_0$ , then under the max-based semantics, we can contract this solution by removing attacks from any other argument ${\mathit{a}}_{\mathit{j}}$ to ${\mathit{a}}_0$ , where $\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{j}}\mathrm{)}⩽\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ .

Proposition 5 (Solution Contraction).

Given a set of arguments $\mathcal{A}$ , a weighting function $\mathit{w}:\mathcal{A}\to [0\mathrm{,}1]$ , and a desirable final acceptability degree function $\mathit{S}:\mathcal{A}\to [0\mathrm{,}1]$ . If $\mathcal{D}\subseteq \mathcal{A}\times \mathcal{A}$ is such that for all $\mathit{a}\in \mathcal{A}$ , ${\mathit{\sigma }}_{\mathit{MB}}^{\mathcal{F}}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}$ , where $\mathcal{F}=⟨\mathcal{A}\mathrm{,}\mathcal{D}\mathrm{,}\mathit{w}⟩$ then for all $\mathit{a}\in \mathcal{A}$ , ${\mathit{\sigma }}_{\mathit{MB}}^{{\mathcal{F}}^{\prime }}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}$ , where $\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{,}{\mathit{a}}_0\mathrm{)}\in \mathcal{D}$ , ${\mathcal{F}}^{\prime }=⟨\mathcal{A}\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}\mathit{w}⟩$ , ${\mathcal{D}}^{\prime }=\mathcal{D}\setminus \mathit{X}$ and $\mathit{X}\subseteq \{\mathrm{(}{\mathit{a}}_{\mathit{j}}\mathrm{,}{\mathit{a}}_0\mathrm{)}\in \mathcal{D}|{\mathit{a}}_{\mathit{j}}\ne {\mathit{a}}_{\mathit{i}}\mathit{\text{ and }}\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{j}}\mathrm{)}⩽\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}\}\cup \{\mathrm{(}{\mathit{a}}_{\mathit{j}}\mathrm{,}{\mathit{a}}_0\mathrm{)}|\mathit{w}\mathrm{(}{\mathit{a}}_0\mathrm{)}=0\}$ . We say that ${\mathcal{D}}^{\prime }$ is a contraction of $\mathcal{D}$ (on $\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{,}{\mathit{a}}_0\mathrm{)}\in \mathcal{D}$ ).

Example 4.

Let us consider $\mathcal{A}$ , w, $\mathcal{D}$ as shown in Fig. 5 and the desirable final acceptability degree function S such that $\mathit{S}\mathrm{(}{\mathit{a}}_0\mathrm{)}=0.43$ , $\mathit{S}\mathrm{(}{\mathit{a}}_1\mathrm{)}=0.30$ , $\mathit{S}\mathrm{(}{\mathit{a}}_2\mathrm{)}=0.58$ , and $\mathit{S}\mathrm{(}{\mathit{a}}_3\mathrm{)}=0.30$ . A contraction ${\mathcal{D}}^{\prime }$ of $\mathcal{D}$ on $\mathrm{(}{\mathit{a}}_2\mathrm{,}{\mathit{a}}_2\mathrm{)}$ will remove the attacks $\mathrm{(}{\mathit{a}}_0\mathrm{,}{\mathit{a}}_2\mathrm{)}$ , $\mathrm{(}{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\mathrm{)}$ , and $\mathrm{(}{\mathit{a}}_3\mathrm{,}{\mathit{a}}_2\mathrm{)}$ from $\mathcal{D}$ without changing the acceptability degrees under the max-based semantics. Likewise, an expansion ${\mathcal{D}}^{″}$ of ${\mathcal{D}}^{\prime }$ can be obtained by adding the attack $\mathrm{(}{\mathit{a}}_0\mathrm{,}{\mathit{a}}_2\mathrm{)}$ 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 ${\mathcal{F}}^{\prime }=⟨\mathcal{A}\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}\mathit{w}⟩$ (left), where ${\mathcal{D}}^{\prime }$ is a contraction of $\mathcal{D}$ on $\mathrm{(}{\mathit{a}}_2\mathrm{,}{\mathit{a}}_2\mathrm{)}$ and ${\mathcal{F}}^{″}=⟨\mathcal{A}\mathrm{,}{\mathcal{D}}^{″}\mathrm{,}\mathit{w}⟩$ (right), where ${\mathcal{D}}^{″}$ is an expansion of ${\mathcal{D}}^{\prime }$ .

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 $\mathcal{A}$ , a weighting function $\mathit{w}:\mathcal{A}\to [0\mathrm{,}1]$ , and a desirable final acceptability degree function $\mathit{S}:\mathcal{A}\to [0\mathrm{,}1]$ . If $\mathcal{D}\mathrm{,}{\mathcal{D}}^{\prime }\subseteq \mathcal{A}\times \mathcal{A}$ are such that for all $\mathit{a}\in \mathcal{A}$ , ${\mathit{\sigma }}_{\mathit{MB}}^{\mathcal{F}}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}$ , ${\mathit{\sigma }}_{\mathit{MB}}^{{\mathcal{F}}^{\prime }}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}$ where $\mathcal{F}=⟨\mathcal{A}\mathrm{,}\mathcal{D}\mathrm{,}\mathit{w}⟩$ and ${\mathcal{F}}^{\prime }=⟨\mathcal{A}\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}\mathit{w}⟩$ then there exists ${\mathcal{D}}^{\ast }\subseteq \mathcal{A}\times \mathcal{A}$ , such that ${\mathcal{D}}^{\ast }$ is an expansion of $\mathcal{D}$ , and a sequence of sets of attacks $\mathrm{(}{\mathcal{D}}_1\mathrm{,}{\mathcal{D}}_2\mathrm{,}\dots \mathrm{,}{\mathcal{D}}_{\mathit{n}}\mathrm{)}$ , where ${\mathcal{D}}_1={\mathcal{D}}^{\ast }$ , ${\mathcal{D}}_{\mathit{n}}={\mathcal{D}}^{\prime }$ and for all $1⩽\mathit{i}⩽\mathit{n}-1\mathrm{,}{\mathcal{D}}_{\mathit{i}+1}$ is a contraction of ${\mathcal{D}}_{\mathit{i}}$ .

Proof.

Let us consider $\mathcal{A}=\{{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{n}}\}$ and two arbitrary solutions $\mathcal{D}\mathrm{,}{\mathcal{D}}^{\prime }\subseteq \mathcal{A}\times \mathcal{A}$ for ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{MB}}$ . We prove this proposition by construction. By definition, for all $\mathit{a}\in \mathcal{A}$ , ${\mathit{\sigma }}_{\mathit{MB}}^{\mathcal{F}}\mathrm{(}\mathit{a}\mathrm{)}={\mathit{\sigma }}_{\mathit{MB}}^{{\mathcal{F}}^{\prime }}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}$ , where $\mathcal{F}=⟨\mathcal{A}\mathrm{,}\mathcal{D}\mathrm{,}\mathit{w}⟩$ and ${\mathcal{F}}^{\prime }=⟨\mathcal{A}\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}\mathit{w}⟩$ . This means that for all $\mathit{a}\in \mathcal{A}$ , such that $\mathit{w}\mathrm{(}\mathit{a}\mathrm{)}\ne 0$ , ${max}_{\mathit{b}\in {\mathtt{Att}}_{\mathcal{F}}\mathrm{(}\mathit{a}\mathrm{)}}\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}={max}_{\mathit{b}\in {\mathtt{Att}}_{{\mathcal{F}}^{\prime }}\mathrm{(}\mathit{a}\mathrm{)}}\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}$ . Thus, ${\mathcal{D}}^{\ast }=\mathcal{D}\cup {\mathcal{D}}^{\prime }$ is an expansion of $\mathcal{D}$ . Then, for all $1⩽\mathit{i}⩽\mathit{n}$ , it holds that ${\mathcal{D}}_{\mathit{i}+1}={\mathcal{D}}_{\mathit{i}}\setminus \{\mathrm{(}{\mathit{a}}_{\mathit{j}}\mathrm{,}{\mathit{a}}_{\mathit{i}}\mathrm{)}\in \mathcal{D}|\mathrm{(}{\mathit{a}}_{\mathit{j}}\mathrm{,}{\mathit{a}}_{\mathit{i}}\mathrm{)}\notin {\mathcal{D}}^{\prime }\}$ is a contraction of ${\mathcal{D}}_{\mathit{i}}$ , where ${\mathcal{D}}_1={\mathcal{D}}^{\ast }$ . It is clear that ${\mathcal{D}}_{\mathit{n}+1}={\mathcal{D}}^{\prime }$ as all attacks in $\mathcal{D}\setminus {\mathcal{D}}^{\prime }$ have been removed from ${\mathcal{D}}^{\ast }$ . □

4.2. The weighted h-categoriser semantics

Let us consider the case of the weighted h-categoriser semantics. Given an input $\mathcal{A}=\{{\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{n}}\}$ , an initial weight function w, and a desirable final acceptability degree function S; we seek a set of attacks $\mathcal{D}\subseteq \mathcal{A}\times \mathcal{A}$ such that for all $\mathit{a}\in \mathcal{A}$ , ${\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}$ , where $\mathcal{F}=⟨\mathcal{A}\mathrm{,}\mathcal{D}\mathrm{,}\mathit{w}⟩$ .

Recall from the definition of the weighted h-categoriser semantics that any solution must mean that the following equation holds. $$\begin{array}{c}\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}={\displaystyle \frac{\mathit{w}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}{1+{\sum }_{\mathit{b}\in \mathtt{Att}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}}}\end{array}$$

Moreover, if $\mathit{w}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}\ne 0$ , we can rearrange the previous equation to obtain: $$\begin{array}{c}{\displaystyle \sum }_{\mathit{b}\in \mathtt{Att}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}={\displaystyle \frac{\mathit{w}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}-\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}{\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}}\end{array}$$

For the complete problem, we are given $\mathit{w}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ and $\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ for all ${\mathit{a}}_{\mathit{i}}\in \mathcal{A}$ , allowing us to compute ${\sum }_{\mathit{b}\in \mathtt{Att}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}$ via the above equation. In other words, for every argument ${\mathit{a}}_{\mathit{i}}$ , we can compute a target value $\mathit{T}={\sum }_{\mathit{b}\in \mathtt{Att}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}$ for which the final acceptability degrees of all its attackers must sum up to. By considering the multiset $\mathit{M}=\{\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{j}}\mathrm{)}|{\mathit{a}}_{\mathit{j}}\in \mathcal{A}\}$ , we must solve a single subset-sum problem to identify the attackers for a single argument ${\mathit{a}}_{\mathit{i}}$ . Extending this to all $\mathit{n}=|\mathcal{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 ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{HC}}$ . 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 $\mathcal{F}=⟨\mathcal{A}\mathrm{,}\mathcal{D}\mathrm{,}\mathit{w}⟩$ , ${\mathcal{F}}^{\prime }=⟨\mathcal{A}\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}\mathit{w}⟩$ , and a desirable final acceptability degree function $\mathit{S}:\mathcal{A}\to [0\mathrm{,}1]$ such that ${\mathit{\sigma }}_{\mathit{HC}}^{\mathcal{F}}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}$ for any $\mathit{a}\in \mathcal{A}$ . If all of the following hold

$\mathit{x}\in \mathcal{A}$

$\mathit{Z}\subseteq \mathcal{A}\times \{\mathit{x}\}$

${\sum }_{\mathrm{(}\mathit{z}\mathrm{,}\mathit{x}\mathrm{)}\in \mathit{Z}}\mathit{S}\mathrm{(}\mathit{z}\mathrm{)}=\mathrm{(}\mathit{w}\mathrm{(}\mathit{x}\mathrm{)}-\mathit{S}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{)}\mathrm{/}\mathit{S}\mathrm{(}\mathit{x}\mathrm{)}$ if $\mathit{w}\mathrm{(}\mathit{x}\mathrm{)}\ne 0$

${\mathcal{D}}^{\prime }=\mathrm{(}\mathcal{D}\cap \mathrm{(}\mathcal{A}\times \mathrm{(}\mathit{a}\setminus \{\mathit{x}\}\mathrm{)}\mathrm{)}\mathrm{)}\cup \mathit{Z}$

then for all $\mathit{a}\in \mathcal{A}$ , ${\mathit{\sigma }}_{\mathit{HC}}^{{\mathcal{F}}^{\prime }}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}$ .

4.3. The weighted card-based semantics

We can adopt a similar approach for ${\mathit{\sigma }}_{\mathit{CB}}$ as was done for ${\mathit{\sigma }}_{\mathit{HC}}$ . We begin by assuming that there are k attacks from arguments with non-zero initial weight against an argument ${\mathit{a}}_{\mathit{i}}$ . Any solution must mean that the following equation holds: $$\begin{array}{c}\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}={\displaystyle \frac{\mathit{w}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}{1+\mathit{k}+\frac{1}{\mathit{k}}{\sum }_{\mathit{b}\in \mathtt{Att}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}}}\end{array}$$

If $\mathit{w}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}\ne 0$ , rearranging gives us the equation: $$\begin{array}{c}{\displaystyle \sum }_{\mathit{b}\in \mathtt{Att}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}=-{\displaystyle \frac{\mathit{k}\mathrm{(}\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}\mathit{k}+\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}-\mathit{w}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}\mathrm{)}}{\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}}\end{array}$$

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 $\mathit{k}=1\dots \mathit{n}$ to identify the number of attacks against an argument, and thereby determine k, we observe that if $\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}=\mathit{ϵ}\mathrm{>}0$ , $lim\mathit{ϵ}\to 0$ , for all $\mathit{b}\in \mathtt{Att}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ the semantic equation reduces to the following. $$\begin{array}{c}\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}={\displaystyle \frac{\mathit{w}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}{1+\mathit{k}}}\end{array}$$ Solving for k, we see that: $$\begin{array}{c}\mathit{k}={\displaystyle \frac{\mathit{w}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}-\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}{\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}}\end{array}$$ Now assume instead that $\mathit{S}\mathrm{(}\mathit{b}\mathrm{)}=1$ for all $\mathit{b}\in \mathtt{Att}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ . Performing the same operations means that: $$\begin{array}{c}\mathit{k}={\displaystyle \frac{\mathit{w}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}-2\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}{\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}}\end{array}$$

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. $$\begin{array}{c}\mathit{k}=\lfloor {\displaystyle \frac{\mathit{w}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}-\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}{\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}}\rfloor =\lceil {\displaystyle \frac{\mathit{w}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}-2\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}{\mathit{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}}}\rceil \end{array}$$

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

Algorithm 3

Procedure to solve ${\mathcal{DEC}}_{\mathit{c}}^{\mathit{CB}}$ . 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 $\mathit{k}\mathcal{SSP}$ 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 $\mathcal{F}=⟨\mathcal{A}\mathrm{,}\mathcal{D}\mathrm{,}\mathit{w}⟩$ , ${\mathcal{F}}^{\prime }=⟨\mathcal{A}\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}\mathit{w}⟩$ , and a desirable final acceptability degree function $\mathit{S}:\mathcal{A}\to [0\mathrm{,}1]$ such that for all $\mathit{a}\in \mathcal{A}$ , ${\mathit{\sigma }}_{\mathit{CB}}^{\mathcal{F}}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}$ . If all the following hold:

$\mathit{x}\in \mathcal{A}$

$\mathit{Z}\subseteq \mathcal{A}\times \{\mathit{x}\}$ , and

${\mathcal{D}}^{\prime }=\mathrm{(}\mathcal{D}\cap \mathrm{(}\mathcal{A}\times \mathrm{(}\mathcal{A}\setminus \{\mathit{x}\}\mathrm{)}\mathrm{)}\mathrm{)}\cup \mathit{Z}$ ,

$|\mathit{Z}|=\lfloor \frac{\mathit{w}\mathrm{(}\mathit{a}\mathrm{)}-\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}}{\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}}\rfloor$ and ${\sum }_{\mathrm{(}\mathit{z}\mathrm{,}\mathit{x}\mathrm{)}\in \mathit{Z}}\mathit{S}\mathrm{(}\mathit{z}\mathrm{)}=-\frac{\mathit{k}\mathrm{(}\mathit{S}\mathrm{(}\mathit{x}\mathrm{)}\mathit{k}+\mathit{S}\mathrm{(}\mathit{x}\mathrm{)}-\mathit{w}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{)}}{\mathit{S}\mathrm{(}\mathit{x}\mathrm{)}}$ if $\mathit{w}\mathrm{(}\mathit{x}\mathrm{)}\ne 0$ .

then for all $\mathit{a}\in \mathcal{A}$ , it is the case that ${\mathit{\sigma }}_{\mathit{CB}}^{{\mathcal{F}}^{\prime }}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{S}\mathrm{(}\mathit{a}\mathrm{)}$

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

²

An implementation of our algorithms using an optimised depth-first-search SSP solver can be found at https://github.com/jhudsy/Gradual_Attack_Inference. We do not provide experimental data as the performance of our solver demonstrates the exponential growth of the underlying subset-sum problem. Systems with more than ∼13 arguments can only rarely be solved in reasonable time using our implementation.

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.