Yes, no, maybe, I don’t know: Complexity and application of abstract argumentation with incomplete knowledge

2.1.Propositional logic

We consider a set V of Boolean variables, i.e. variables that can be assigned a value in B={0,1}, where 0 is interpreted as false and 1 as true. A well-formed propositional formula ϕ is then:

An interpretation is then a mapping ω:V→B, i.e. an assignment of a truth value to every variable. The notion can be generalized to formulas:

2.2.Computational complexity

In this part, we briefly describe some background notions on computational complexity, that are important for understanding the relative hardness of the computational problems that will be presented. First, let us mention that we focus on decision problems, that are computational problems that must be answered by a binary answer “YES” or “NO”. We will describe complexity classes, that are simply sets of decision problems that share some properties regarding the time (or space) necessary for solving them. The first one is made of problems that are considered to be tractable: P is the set of decision problems that can be solved in polynomial time. More formally, for any P∈P, there is a deterministic algorithm that can decide any instance i of P in (at most) nk computation steps, where n is the size of the instance i, and k∈N is a fixed constant. The assumption that the algorithm is deterministic is important here. A subclass of P that we consider in this paper is L, the set of decision problems that can be decided in logarithmic space by a deterministic algorithm.

While all these problems are considered as “easy” ones, we also define classes characterized by non-deterministic algorithms that are considered as computationally hard. Let us first introduce NP, the set of decision problems that can be solved in polynomial time by a non-deterministic algorithm. Another way to characterize NP is to use the notion of witness. Given an instance i of a problem P∈NP, define w(i) the set of potential witnesses that prove that i is a “YES” instance of P. NP is the set of decision problems such that for each instance i,

The complementary of a complexity class C is C‾={P‾∣P∈C}, where the complementary problem P‾ of P is the decision problem built on the same set of instances as P, such that the “YES” instances become “NO” instances (and vice-versa). Then, coNP can be defined as NP‾. It is well-known that P⊆NP and P⊆coNP.11

The classes P, NP and coNP form the first levels of the polynomial hierarchy [79]. To define higher levels, we need to introduce the concept of oracle. An oracle for a class C can be seen as a black box that solves a problem from C in a single step. Then, the complexity class CC′ is the set of decision problems that can be solved by a C algorithm that has access to a C′ oracle. For instance, PNP is the set of problems that can be solved in polynomial time by a deterministic algorithm that has access to an NP oracle. The concept of oracles allows to define recursively the classes ΔkP, ΣkP and ΠkP, where k∈N. Formally,

Fig. 1.

The polynomial hierarchy.

We present a last complexity class, namely DP, which stands for Differential Polynomial Time. It was first introduced by [75], as the set of decision problems

Let us conclude this part on computational complexity with the notion of hardness. Intuitively, a problem P is said to be C-hard if it is as hard as any problem P′∈C. The notion of “as hard as” is formally defined through the notion of reduction. A reduction from P′ to P is a mapping f:IP′→IP (where IP′ and IP are, respectively, the instances of P′ and the instances of P), such that i∈IP′ is a “YES” instance of P′ if and only if f(i) is a “YES” instance of P. If f can be computed in polynomial time, then we write P′⩽fPP, which means that P is (at least) as hard as P′. For C a class of the polynomial hierarchy with k⩾1, we say that P is C-hard if and only if ∀P′∈C, P′⩽fPP. A notion of P-hardness can also be defined, using logarithmic reductions instead of polynomial ones, i.e. f must be computable in polynomial time, using logarithmic space. While the notion of hardness provides a lower bound for the complexity of a problem, the membership of a problem P to a class C provides an upper bound. When both bounds coincide (i.e. P is C-hard, and P∈C), we say that P is C-complete. This means, intuitively, that P is one of the hardest problems in C. Since ⩽fP (and the logarithmic counterpart) is transitive, there is no need to prove that P′⩽fPP for each P′∈C for showing that P is C-hard; proving that P′⩽fPP for some C-hard problem P′ is enough. SAT (and variants of it) can be used for that, since it is the first problem that was proven to be NP-complete [32].

We refer the interested reader to [7] for more details on the theory of computational complexity.

2.3.Abstract argumentation

Abstract argumentation has been introduced by Dung [44] as the study of arguments acceptability based only on their relationship. It means that arguments are considered as atomic pieces of information: their internal structure and their origin are ignored in the reasoning process. Only the attacks between them matter for determining which arguments can be accepted. Formally:

In this paper, we consider only finite AFs, i.e. A is a finite set of arguments. For a,b∈A, we say that a attacks b if (a,b)∈R. The notion of attack can be extended to sets of arguments: S⊆A attacks an argument b∈A if there is some a∈S that attacks b. Finally, an argument a∈A is defended by the set S⊆A if, ∀b∈S such that (b,a)∈R, ∃c∈S such that (c,b)∈R (i.e. each attacker of a is counter-attacked by an element of S).

Fig. 2.

An example of argumentation framework.

The acceptability of arguments is classically evaluated through the notion of extensions, i.e. sets of collectively acceptable arguments. A set of arguments has to satisfy some properties to be an extension. The basic principles that underly most extension-based semantics are conflict-freeness and admissibility:

Conflict-free and admissible sets of an AF F are (respectively) denoted cf(F) and adm(F). Conflict-freeness means that a set of arguments must be internally coherent in order to be acceptable, and admissibility means that it must somehow survive any threat, i.e. any attack against it.

From these basic requirements, extensions are defined following four semantics, proposed in [44]. Formally, an extension-based semantics is a mapping from an AF F=⟨A,R⟩ to a set of sets of arguments σ(F)⊆2A.

Other semantics have been defined since then; see [9] for an overview. It is well-known since Dung’s seminal paper [44] that, for any AF F, |gr(F)|=1, stb(F)⊆pr(F)⊆co(F), and |pr(F)|⩾1. On the contrary, the stable semantics is not universally defined, i.e. there are some AFs F with stb(F)=∅.

From a set of extensions σ(F), two classical reasoning modes are used to determine the set of acceptable arguments.

We use credσ(F) and skepσ(F) to denote the sets of credulously and skeptically acceptable arguments. Under most semantics, skepσ(F)⊆credσ(F) and the rejected arguments are A∖credσ(F). Notice that it is not the case under the stable semantics, for AFs F such that stb(F)=∅. In that case, credstb(F)=∅, and skepstb(F)=A.

The complexity of various reasoning problems has been studied in the past. A recent overview is provided by [48]. Let us formally define some of these problems, namely Verification (Ver), Credulous Acceptability (CA), Skeptical Acceptability (SA) and Non-Empty Existence (NE), that will be of interest in the rest of the paper.

Their complexity is described in Table 2. In the table, “trivial” means that the answer is trivially “NO” for any instance: indeed, ∅ is conflict-free and admissible for every AF, so there is no skeptically acceptable argument with respect to conflict-freeness and admissibility.

Finally, let us discuss the specificity of some semantics regarding the empty set and skeptical acceptability. The stable semantics is the only semantics for which there are AFs F such that stb(F)=∅. We have already mentioned that, in this case, the classical definition of skeptical acceptability leads to the acceptability of each argument. This may seem counterintuitive for some applications. This has conducted to the definition of an alternative decision problem, which consists in determining whether the AF has at least one extension (here, the non-emptyness is not important), and then whether the given argument is skeptically accepted. This is the problem of Existence and Skeptical Acceptability (ExSA), formally:

3.1.Attack-incompleteness and argument-incompleteness

From a historical point of view, the first model that extends Dung’s abstract argumentation framework with incompleteness is the so-called Partial Argumentation Framework (PAF), proposed in [33]. A PAF is a tuple P=⟨A,R,I,N⟩ where A is a set of arguments, and R, I, N form a partition of A×A, where R is the attack relation, I is the ignorance relation, and N is the non-attack relation. Intuitively, (a,b)∈R means that the agent knows for sure that a attacks b, while (a,b)∈I means that the agent ignores whether it is the case or not. Finally, (a,b)∈N means that the agent knows for sure the that a does not attack b. As mentioned by the authors of the original paper, N can be deduced from R and I (since N=(A×A)∖(R∪I)), thus any PAF can be fully specified by ⟨A,R,I⟩. This model is used in a context of merging several argumentation frameworks, each of them representing the knowledge of one agent [33] (see Section 5.1 for more details). The notion of completion of a PAF ⟨A,R,I⟩ is defined as a standard AF that “solves” the uncertainty in the PAF, i.e. ⟨A,R′⟩ such that R⊆R′⊆R∪I. The model was further studied in [29], where semantics adapted to this setting are defined (see Section 3.4), without using the notion of completion.

While the literature on PAFs is quite sparse, the model has been later re-named as Attack-Incomplete Argumentation Framework (Att-IAF) [16]. An Att-IAF is then a tuple ⟨A,R,R?⟩ (where R? corresponds to I in PAFs). The focus of [16] is the verification problem, i.e. given an Att-IAF I, a set of arguments S and a semantics σ, is S a σ-extension of some (or each) completion of I?

Then, a similar question has been studied for Argument-Incomplete Argumentation Framework (Arg-IAF) [19], i.e. argumentation frameworks where the actual existence of some arguments is uncertain. An Arg-IAF is a tuple ⟨A,A?,R⟩ such that R⊆A∪A?, and a completion is then a standard AF ⟨A′,R′⟩ where A⊆A′⊆A∪A?, and R′=R∩(A′×A′).

The (generalized) Incomplete Argumentation Framework models situations where both arguments and attacks can be uncertain. We focus on this framework in the rest of the section, and give more details on the reasoning based on completions (similar to the approach studied in [16, 19]), and the reasoning based on redefinition of basic notions like conflict-freeness and defense (in the spirit of [29]).

3.2.The generalized IAF model

Incomplete AFs were first defined in [18], which generalizes the work from [16, 19].

Elements in A and R are called certain (or definite) arguments and attacks, while A? and R? are uncertain arguments and attacks. We have already briefly discussed, in the introduction, the intuitive meaning of the different kinds of arguments and attacks. Roughly speaking, they can be seen as an abstraction of information regarding the internal structure of arguments (e.g. the validity of the arguments premises may change through time), or additional knowledge (e.g. unknown preferences between arguments). They can also represent potential evolution of the AF (e.g. in the case of a debate, uncertain arguments and attacks can be seen as those that can be used – or not – by other agents). Notice a particular case: an uncertain argument a∈A? that certainly attacks (or is attacked by) another argument b∈A∪A?, i.e. (a,b)∈R (or (b,a)∈R). This specific kind of attack is sometimes called conditionally definite, which means that this attacks certainly exists if a and b actually exist. A concrete case where this happens is a debate, where a is an argument that could be used by another agent. We can be sure that – if it appears in the debate – a attacks b (e.g. because a thorough analysis of their internal content shows some logical inconsistency between them), but there is no certainty that the opponent will use a.

Fig. 3.

An IAF I.

The (most classical) way of reasoning with an IAF is based on the notion of completions, that are (standard) AFs corresponding to a possible resolution of the uncertainty encoded in the IAF. Before formally defining completions, we introduce a notation: given a set of attacks Att and a set of arguments Arg, Att|Arg≜Att∩(Arg×Arg).

This model is quite general, and includes previously defined models (i.e. those described in Section 3.1) as subclasses. First, a Partial AF (PAF) [33] P=⟨A,R,I⟩ can be seen as an IAF with A?=∅ and R?=I. Recall that the same model was studied under the name Attack Incomplete AF (Att-IAF) in [16]. On the contrary, an Argument Incomplete AF (Arg-IAF) [19] is a tuple ⟨A,A?,R⟩, i.e. an IAF with R?=∅.

Fig. 4.

The completions of I.

Two families of reasoning approaches have been defined. In most of the cases, reasoning is based on the set of completions. For instance, an argument is possibly accepted if it is accepted in some completion, and necessarily accepted if it is accepted in each completion. We describe this approach in Section 3.3. Another approach (the first one, from a chronological point of view) consists in adapting the basic notions of conflict-freeness and defense, on which Dung’s semantics are based. This allows to define new semantics suited to the specific framework at hand. It was proposed in [29] for PAFs and later generalized to IAFs [65], and we describe it in Section 3.4.

3.3.Possible and necessary reasoning

Similarly to credulous and skeptical reasoning, based on a set of extensions, two modes of reasoning can be used when inference is made from a set of completions. Possible reasoning is the counterpart (for completions) of credulous reasoning (for extensions). It means that we expect some property to be satisfied in some completion. On the contrary, necessary reasoning is the counterpart (for completions) of skeptical reasoning (for extension): the property must be satisfied in each completion. A natural example where both reasoning modes make sense is a trial. There may be uncertainty arising in such scenario. The prosecutor’s goal is to prove that the defendant is guilty without any doubt, i.e. it must be a consequence of every completion. On the contrary, the defendant’s lawyer has to prove that the defendant may be innocent (this is the presumption of innocence), i.e. it must be a consequence of some completion.

Possible and necessary modes of reasoning can be combined with any decision problem of interest regarding argumentation frameworks. Interestingly, being “skeptical” about the completions does not means that the agent has to be skeptical about the extensions (and vice-versa). So, both credulous and skeptical reasoning, as well as verification and non-empty existence, have been adapted for IAFs under the possible and necessary views.

3.3.1.Complexity

Now we discuss the different reasoning problems for IAFs that have been studied in the literature, as well as their complexity.

Verification. The first study on extension verification for IAFs was described in [18]:22

• σ-IncPV Given I=⟨A,A?,R,R?⟩ an IAF and S⊆A∪A?, is there F∈comp(I) such that S∩A′ is a σ-extension of F?

• σ-IncNV Given I=⟨A,A?,R,R?⟩ an IAF and S⊆A∪A?, for each F∈comp(I), is S∩A′ a σ-extension of F?

Example 6.

Let us consider again I=⟨A,A?,R,R?⟩ (Fig. 3), and the set S={a,b}. Since S is not conflict-free regarding the certain attack relation R, it is not conflict-free in any completion of I, thus it cannot be an extension for any semantics considered in this paper. The pair (I,S) is thus a “NO” instance for σ-IncPV and σ-IncNV.

Now, consider S′={a,c,d,e}. S′ is a σ-extension (σ∈{co,pr,stb,gr}) for some completions of I (e.g. F8, see Fig. 4), so (I,S′) is a “YES” instance for σ-IncPV. It is, however, a “NO” instance for σ-IncNV, because it is not conflict-free in completions where (a,c) exists (e.g. F12).

Finally, we show that there is no “YES” instance with I for σ-IncNV (for σ one of the semantics considered here). Towards a contradiction, suppose that there is some set S″ such that S″∩Ai′ is a σ-extension of Fi=⟨Ai′,Ri′⟩ for each completion Fi∈comp(I). S″ must contain c, d and e since they are unattacked in e.g. F12, they appear in every σ-extension of it. For similar reasons, S″ must contain b (which is unattacked in e.g. F4, thus it belongs to every extension of it). Already we face a contradiction: if b∈S″, then S″∉σ(F12) because b is attacked by the (unattacked) arguments d and e in F12.

Further research on extension verification has been conducted. In [50], a set of arguments for which the answer to σ-IncPV (respectively σ-IncNV) is “YES” is called a possible (respectively necessary) i-extension. The authors identify some issues with this definition (for instance, a set of arguments could be identified as a possible i-extension even if it is not conflict-free). To remedy this issue, they define i∗-extensions, and the corresponding verification problems:

• σ-IncPV^∗ Given I=⟨A,A?,R,R?⟩ an IAF and S⊆A∪A?, is there F∈comp(I) such that S is a σ-extension of F?

• σ-IncNV^∗ Given I=⟨A,A?,R,R?⟩ an IAF and S⊆A∪A?, for each F∈comp(I), is S a σ-extension of F?

Example 7.

Observe that in I=⟨A,A?,R,R?⟩ (Fig. 3), S={b,c,e} is a possible σ i-extension (σ∈{co,pr,stb,gr}), i.e. (I,S) is a “YES” instance for σ-IncPV. For instance, in F1=⟨A1′,R1′⟩ (Fig. 4), S∩A1′={b,c} is a σ-extension. It is counterintuitive, since S is not conflict-free in completions where S⊆Ai′. On the contrary, (I,S) is a “NO” instance for σ-IncPV^∗, since there is no completion such that S is an extension of it.

We refer the interested reader to [50] for a more detailed discussion of the difference between i-extensions and i∗-extensions.

Argument acceptability. Then, the (possible and necessary) variants of credulous and skeptical acceptability are studied in [15, 17]:

• σ-PCA Given I=⟨A,A?,R,R?⟩ an IAF and a∈A, is there F∈comp(I) such that a∈⋃E∈σ(F)E?

• σ-NCA Given I=⟨A,A?,R,R?⟩ an IAF and a∈A, for each F∈comp(I), is a∈⋃E∈σ(F)E?

• σ-PSA Given I=⟨A,A?,R,R?⟩ an IAF and a∈A, is there F∈comp(I) such that a∈⋂E∈σ(F)E?

• σ-NSA Given I=⟨A,A?,R,R?⟩ an IAF and a∈A, for each F∈comp(I), is a∈⋂E∈σ(F)E?

Example 8.

We continue the previous example, with I=⟨A,A?,R,R?⟩ from Fig. 3. Notice that, since all the completions are acyclic graphs, they all have one extension which is complete, preferred, stable and grounded at the same time (this result is known since Dung’s seminal paper [44]). (I,a) is a “YES” instance for σ-PCA and σ-PSA for all considered semantics, since a belongs to the (unique) extension of some completions of I (e.g. F3), but it is a “NO” instance for σ-NCA and σ-NSA because a is not accepted in each completion (see e.g. F1). On the contrary, (I,c) is a “YES” instance for σ-NCA and σ-NSA, since c belongs to the (unique) extension of every completion.

Non-empty existence. The variants of non-empty existence have been defined in [77, 78]:

• σ-PNE Given I=⟨A,A?,R,R?⟩ an IAF, is there F∈comp(I) with a non-empty σ-extension?

• σ-NNE Given I=⟨A,A?,R,R?⟩ an IAF, for each F∈comp(I), does F have a non-empty σ-extension?

Example 9.

The IAF I from Fig. 3 is a “YES” instance for both σ-PNE and σ-NNE, since all the completions possess (exactly) one non-empty extension for all the semantics under consideration.

Actually, [77] also mentions the “existence problem”, where the answer is true if there is an extension (empty or not). For most semantics, the answer to this question is trivially “YES” for any AF (thus, for any completion of any IAF). The only case where this problem is not trivial is the stable semantics, but then it coincides with the non-empty existence problem, so we choose not to give more details about this (less demanding) version.

The complexity of these problems under various classical semantics is summarized in Table 4.

Table 4

Complexity of reasoning with IAFs under σ∈{adm,stb,co,gr,pr} [15, 18, 50, 77]. C-c means C-complete

σ	σ-IncPV	σ-IncNV	σ-IncPV∗	σ-IncNV∗	σ-PCA	σ-NCA	σ-PSA	σ-NSA	σ-PNE	σ-NNE
adm	NP-c	P	P	P	NP-c	Π2P-c	trivial	trivial	NP-c	Π2P-c
stb	NP-c	P	P	P	NP-c	Π2P-c	Σ2P-c	coNP-c	NP-c	Π2P-c
co	NP-c	P	P	P	NP-c	Π2P-c	NP-c	coNP-c	NP-c	Π2P-c
gr	NP-c	P	P	P	NP-c	coNP-c	NP-c	coNP-c	P	P
pr	Σ2P-c	coNP-c	Σ2P-c	coNP-c	NP-c	Π2P-c	Σ3P-c	Π2P-c	NP-c	Π2P-c

Existence and skeptical acceptability. Like in the case of classical AFs, the ExSA problem (or more precisely its adaptations to IAFs) has only been studied for σ∈{cf≠∅,adm≠∅,stb}. The formal definition is as follows:

• σ-PExSA Given I=⟨A,A?,R,R?⟩ an IAF and a∈A, is there F∈comp(I) such that σ(F)≠∅ and a∈⋂E∈σ(F)E?

• σ-NExSA Given I=⟨A,A?,R,R?⟩ an IAF and a∈A, for each F∈comp(I), do σ(F)≠∅ and a∈⋂E∈σ(F)E hold?

Complexity of these problems was also established, results are reported in Table 5.

Table 5

Complexity of σ-PExSA and σ-NExSA under σ∈{cf≠∅,adm≠∅,stb} [73]. C-c means C-complete

σ	σ-PExSA	σ-NExSA
cf≠∅	in P	in P
adm≠∅	Σ2P-c	Π2P-c
stb	Σ2P-c	Π2P-c

Fig. 5.

An IAF and its two completions.

Example 10.

Let I=⟨A,A?,R,R?⟩ be the IAF depicted in Fig. 5(a), with its completions comp(I)={F1,F2} given in Fig. 5(b) and 5(c). F1 has no stable extension, while F2 has one stable extension {b}. Thus, (I,b) is a “YES” instance for stb-PExSA, and a “NO” instance for stb-NExSA.

3.4.Direct semantics for PAFs and IAFs

Besides the possible and necessary reasoning modes described previously, [29] defines semantics for Partial AFs (recall that it corresponds to Att-IAFs, i.e. IAFs with A?=∅), based on alternative definitions of the basic notions of conflict-freeness and acceptability that underly Dung’s semantics. Here we call these semantics “direct semantics”, opposed to the completion-based reasoning presented before. In the following, we adapt the definitions of [29] to be consistent with the notations used in this paper.

Intuitively, R-conflict-freeness considers that the incompatibility between a and b, when (a,b)∈R?, is not severe enough to prevent a and b of being accepted together. Thus, uncertain attacks can be ignored for identifying R-conflict-freeness. On the contrary, R-R?-conflict-freeness excludes all conflicts (both certain and uncertain) from acceptable sets.

Fig. 6.

A PAF P.

In standard AFs, the notion of admissibility combines conflict-freeness and self-defense [44]. More precisely, Dung defines an argument a as acceptable with respect to a set of arguments S if each attacker of a is attacked by an element in S. This notion is also extended to PAFs.

Similarly to R-conflict-freeness, R-acceptability considers uncertain attacks as “not serious enough” for requiring to be counterattacked. On the contrary, R-R?-acceptability implies that an argument is defended against all its attacks, not only the certain ones. Notice that a quite cautious view is adopted here, since only certain attacks can be used to defend an argument (even against uncertain attacks).

Then, different versions of admissibility can be defined by combining a notion of conflict-freeness with a notion of acceptability. More precisely:

One may wonder why there is no notion of admissibility characterized by R-conflict-freeness and R-R?-acceptability. It is proven that such a set would actually be R-R?-conflict-free, thus it would be a R-R?-admissible as well. We use adm(P), admR(P) and admR,R?(P) to denote, respectively, the admissible, R-admissible and R-R?-admissible sets of a PAF P. The definitions straightforwardly imply that admR,R?(P)⊆admR(P)⊆adm(P).

Then, [29] focuses on three versions of the preferred semantics, based on the different notions of admissibility defined in Definition 9.

The original paper discusses the properties of these semantics (for instance the inclusion links between different semantics, or the relations between the semantics of the PAF and the semantics of the completions) as well as computational issues. Interestingly, contrary to possible and necessary reasoning that can be harder than classical reasoning with AFs (recall Section 3.3.1), reasoning with these new semantics keep the complexity of Dung’s AFs. In particular, credulous and skeptical acceptability are (respectively) NP-complete and Π2P-complete for the three PAF variants of the preferred semantics.

This approach has been recently generalized to IAFs in [65]. The concepts of conflict-freeness and acceptability are adapted to IAFs under the names weak conflict-freeness (respectively weak defense) corresponding to R-conflict-freeness (respectively R-acceptability) and strong conflict-freeness (respectively strong defense) corresponding to R-R?-conflict-freeness (respectively R-R?-acceptability). Then, the three types of admissibility are also defined for IAFs, where “simple” admissibility is renamed weak admissibility, R-admissibility is mixed admissibility, and R-R?-admissibility is strong admissibility. However, the paper excludes mixed admissibility from further study after proving that it does not satisfy Dung’s fundamental lemma, i.e. the fact that if an admissible set S defends an argument a, then S∪{a} is admissible as well. Then, [65] adapts the definitions of preferred, complete and stable semantics to weak and strong admissibility, and provides complexity results, reported in Table 6. This paper left open the question of grounded semantics, as well as tight complexity result for skeptical acceptability under (weak and strong) complete semantics.

3.5.Rich IAFs: A closer look to uncertainty of the third kind

Besides uncertain arguments (A?) and uncertain attacks (R?), a third kind of uncertainty can be considered: uncertainty about the direction of attacks. This idea has been introduced in Control AFs [39] (see Section 4). However, such a new kind of uncertainty can also be applied in the context of IAFs. This leads to the definition of Rich IAFs (RIAFs) [63].

The new relation ↔?, borrowed from [39], is a symmetric (uncertain) conflict relation: if (a,b)∈↔?, then we are sure that there is a conflict between a and b, but not of the direction of the attack. This new relation impacts the definition of completions.

Again, we use comp(rI) to denote the set of completions of a RIAF rI.

Example 14.

Figure 7 depicts a RIAF rI=⟨A={a,b,c,d,e},A?={f},R={(c,a),(d,b),(d,c)},R?={(e,a),(f,d)},↔?={(a,b),(b,a)}⟩.

Fig. 7.

The RIAF rI.

We do not give here the full set of completions of rI. Let us focus on one option for each of (e,a), (f,d) and f, and we only illustrate the three options for (a,b). These three completions F1, F2 and F3 are given at Fig. 8.

Fig. 8.

Three completions of rI.

Similarly, for each other configuration of (e,a), (f,d) and f, there are three options for the conflict between a and b, leading to three different completions.

Although this richer framework is strictly more expressive than IAFs (i.e. any IAF is a RIAF, but some RIAFs cannot be translated into an equivalent IAF), the complexity of reasoning with RIAFs is the same as the complexity of reasoning with IAFs (see [63] for more details).

3.6.Restricting the set of completions

Several approaches have been proposed recently (and concurrently) that allow to restrict the set of completions of an IAF. There are several motivations to do that. As a first natural example of such motivation (borrowed from [53]), consider a situation where to agents Ag1 and Ag2 are participating in a debate. Ag1 knows that Ag2 may use one of two arguments a1 and a2, such that a1 (respectively a2) corresponds to the point of view of right-wing (respectively left-wing) politicians. Ag1 also knows that Ag2 is politically oriented, i.e. Ag2 certainly has some preferences between a1 and a2, but she does not know exactly which of right-wing or left-wing corresponds to Ag2’s orientation. So, the AF of Ag2 is one of those described at Fig. 9.

Fig. 9.

The possible AFs of Ag2.

However, there is no simple way to represent these AFs with the formalisms presented in previous section, i.e. there is no IAF I with comp(I)={F1,F2}. A possible solution is to define an IAF structure that admits a set of completions F such that {F1,F2}⊆F, and to add a constraint that excludes from the reasoning all the AFs different from F1 or F2.

A similar motivation is given in [66], where the issue of representing any set of AFs as the completions of a (constrained) IAF is related to AF revision [35] and merging [38] whose result might not be representable by a single AF but by a set of AFs instead.

A third motivation is the notion of correlation between arguments [51]. For instance, considering structured argumentation settings [22, 23], if a1 and a2 are uncertain arguments such that a1 is a sub-argument of a2, then a2 cannot belong to a completion without a1 belonging too. Such a constraint can be intuitively represented as a2⇒a1. Different kinds of correlations are proposed by [51], in the context of Arg-IAFs (i.e. IAFs with R?=∅).

Then, a completion of I is valid (with respect to δ) under some conditions.

An Arg-IAF with dependencies is then a pair made of an Arg-IAF I=⟨A,A?,R⟩ and a set of dependencies Δ, and [51] studies the complexity of two decision problems: