# control_argumentation_frameworks__ba346594.pdf

Control Argumentation Frameworks

Yannis Dimopoulos Department of Computer Science University of Cyprus yannis@cs.ucy.ac.cy

Jean-Guy Mailly LIPADE Paris Descartes University, France jean-guy.mailly@parisdescartes.fr

Pavlos Moraitis LIPADE Paris Descartes University, France pavlos@mi.parisdescartes.fr

Dynamics of argumentation is the family of techniques concerned with the evolution of an argumentation framework (AF), for instance to guarantee that a given set of arguments is accepted. This work proposes Control Argumentation Frameworks (CAFs), a new approach that generalizes existing techniques, namely normal extension enforcement, by accommodating the possibility of uncertainty in dynamic scenarios. A CAF is able to deal with situations where the exact set of arguments is unknown and subject to evolution, and the existence (or direction) of some attacks is also unknown. It can be used by an agent to ensure that a set of arguments is part of one (or every) extension whatever the actual set of arguments and attacks. A QBF encoding of reasoning with CAFs provides a computational mechanism for determining whether and how this goal can be reached. We also provide some results concerning soundness and completeness of the proposed encoding as well as complexity issues.

Introduction Argumentation is an important domain in the ﬁeld of Artiﬁcial Intelligence. Accumulated over more than two decades, there is nowadays a vast literature on various aspects of argumentation, such as abstract argumentation frameworks and their semantics (see e.g. (Dung 1995; Baroni, Caminada, and Giacomin 2011)), structured argumentation frameworks (see e.g. (Besnard and Hunter 2008; Dung, Kowalski, and Toni 2009; Kakas and Moraitis 2003)) and more recently on a particular topic called argumentation dynamics (see e.g. (Cayrol, de Saint-Cyr, and Lagasquie-Schiex 2010; Booth et al. 2013; Doutre, Herzig, and Perrussel 2014; Coste-Marquis et al. 2014; Baumann and Brewka 2010)). In this paper we propose a new family of abstract argumentation frameworks, called control argumentation frameworks, abbreviated as CAFs. A CAF integrates in a uniﬁed computational framework different notions proposed in the literature on argumentation dynamics, while simultaneously relaxes the basic assumption of complete knowledge, implicit in the majority of past works. The computational methods that are presented in this work are based on Quantiﬁed Boolean Formulas (QBFs) (Pulina 2016) solving technology. The aim is to build effective argumentation systems

Copyright c 2018, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

that can reach certain states (e.g. a set of arguments to be skeptically or credulously accepted that may support goals, decisions, actions, beliefs, etc.) regardless of the different unpredicted threats that they may face when operating in dynamic environments. These threats can be modeled through the different possible changes already studied in the literature that might affect argumentation systems namely addition/removal of arguments, and addition/removal of attacks. So, while most works on argumentation dynamics consist in deﬁning methods which modify an argumentation framework, the aim of CAFs is different. Indeed, the goal of our work is to deﬁne a framework which can resists to any future change that could occur, while maintaining some desired properties of the system.

As noted above, in the majority of the previous works, and especially in those proposing computational methods (see e.g. (Coste-Marquis et al. 2015; Wallner, Niskanen, and J arvisalo 2016)), complete knowledge about the structure of the argumentation theories is assumed. That is, all the arguments of a theory as well as the existence (or not) and the direction of the attacks between those arguments are assumed to be known. In reality however, agents need to reason by taking into account aspects of the world that are completely outside their control and may evolve constantly. For instance a decision making/aiding investment banking agent that builds an argument that supports investing in savings accounts, which is meaningful when interest rates are high but less so when rates plunge. The problem for an investment agent that aims at generating secure portfolios is that interest rates are a highly uncertain uncontrollable variable. More generally, arguments supporting particular investments decisions depend on uncertain factors such as market ﬂuctuations, expectations, political developments, etc. It is desirable that agents are able to reach conclusions under incomplete information, or even reach long-lasting conclusion, i.e. that remain valid regardless of how the world evolves. This work provides a computational framework that supports reasoning with uncertainty regarding the presence of arguments and the attacks between them. The problem of devising languages that are expressive enough to accommodate such uncertainty has been addressed in some works (see e.g. (Dupin de Saint-Cyr et al. 2016)), without however providing associated computational methods. Indeed, to the best of our knowledge, this is the ﬁrst work that proposes an argumen-

The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)

tation framework handling all possible dynamics under uncertainty, along with efﬁcient computational methods that take advantage of recent progress in methods generalizing the satisﬁability problem, namely QBFs. The second section of the paper presents background knowledge. The third section describes the CAF formalism. Then, we present a QBF-based computational method that determines whether a CAF is controllable and how to control it. Some complexity results are given, and ﬁnally the last sections describe relevant related work and interesting research tracks.1

Argumentation Systems

An argumentation framework (AF), as introduced in (Dung 1995), is a pair AF = A, R , where A is a set of arguments, and R A A is an attack relation. The relation a attacks b is denoted by (a, b) R. In (Dung 1995), different acceptability semantics were introduced. They are based on two basic concepts: defence and conﬂict-freeness. Here we focus on stable semantics: a set of arguments S A is a stable extension of AF = A, R iff 1) S is conﬂict-free (i.e. ai, aj S, (ai, aj) R) and 2) aj A \ S, ai S s.t. (ai, aj) R. Let us notice that our approach can be adapted to any extensionbased semantics. Based on the acceptability semantics, we can deﬁne the status of any argument, namely skeptically accepted (belonging to each extension), credulously accepted (belonging to some extension) and rejected arguments (belonging to no extension). For more details about argumentation semantics, we refer the reader to (Dung 1995; Baroni, Caminada, and Giacomin 2011).

Quantiﬁed Boolean Formulas

We assume that the reader is familiar with the basics of propositional logic, satisﬁability and complexity theory. Otherwise, see (Biere et al. 2009; Arora and Barak 2009) for an overview. Quantiﬁed Boolean Formulas (QBFs) are a natural extension of propositional formulas with the universal and existential quantiﬁers (Kleine B uning and Bubeck 2009). For instance, the formula x y(x y) ( x y) is satisﬁed if there is a value for x such that for all values of y the proposition (x y) ( x y) is true. More formally, a canonical QBF is of the form Q1X1Q2X2 . . . Qn XnΦ where Φ is a propositional formula, Qi { , }, Qi = Qi+1, and X1, X2, . . . , Xn disjoint sets of propositional variables such that X1 X2 . . . Xn coincides with the set of propositional variables of Φ. It is well-known that QBFs span the polynomial hierarchy. For instance, deciding whether the formula X1 X2 . . . Qi XiΦ is true is Σp i - complete, where Qi = for odd i, and Qi = for even i. The results still hold for Φ in 3CNF. We denote the formula X1 X2 . . . Qi XiΦ by Qi, . Finally, a truth assignment on a set of propositional variables V = {x1, . . . , xn} is a mapping ω : V {0, 1}.

1For space reasons, proofs are omitted.

Control Argumentation Frameworks This section deﬁnes the control argumentation framework. On a high level, a CAF is an argumentation framework where arguments are divided in three parts, ﬁxed, uncertain and control. The ﬁxed part of the global theory describes the background (basic) knowledge of an agent that allows him to solve problems when acting in a static environment. It is static (i.e. in the sense that it does not change over time) and neither the agent itself nor the environment can have an inﬂuence on it (i.e. only the user can change it). The uncertain part is a part that the agent cannot control either. It captures the changes that may occur in the environment where the agent is acting and the context dependant information. This part is controlled by the environment in the sense that changes in the environment are represented in its theory. It can change over time reﬂecting the dynamics of the environment. It is to some extent the sensory input of the system. When the agent has some goal about the ﬁxed part of the CAF (e.g. some arguments supporting an action/decision should be skeptically accepted), then this uncertain part might constitute threats for the goal of the agent. These threats are modeled through attacks against arguments in the ﬁxed part. Uncertainty is doubly present in this part of the system. Firstly, it captures the lack of information on whether some possible change has really occurred or not. This type of uncertainty is modeled through the presence or absence of the argument representing the change in the theory of this part (i.e. an argument can be on/off according to the situation). Secondly, it concerns the lack of information on the type of the threat generated by an occurred change. This type of uncertainty concerns the presence (or not) and the direction of attacks of arguments present in the uncertain part (and representing the occurred changes) against arguments in the ﬁxed part. This part captures all the possible dynamics that may occur (i.e. addition/removal of arguments, addition/removal of attacks) in argumentation systems enhanced with enforcement capabilities. Finally, the control part is controlled solely by the agent, which can decide which arguments are actually used in the system or not. The environment has no inﬂuence on this part. These arguments can protect the agent s goal against the threats arising from the uncertain part. More precisely, this part contains arguments that can propose remedial actions against the attacks addressed by arguments in the uncertain part towards arguments in the ﬁxed part, but also against arguments in the ﬁxed part when the target of the system (i.e. the supporting argument of the goal that has to be skeptically or credulously accepted) is rejected in the current stage of the ﬁxed theory.

One of the positive features of this partitioning is that our framework is modular. Indeed, if the system has to be updated, only a part of it is concerned with this update. For instance, the agent becomes aware of the existence of new threats, through the update of the uncertain part. No other part is affected. When new remedial actions are made available to the agent, the control part is concerned with this update, but not the other two parts. In the classical AFs any change modeled through the dynamics is integrated in the

(updated) basic knowledge of the agent and from that moment onwards it is part of the knowledge of the agent. However, some of these changes should not probably be integrated in a permanent way in the background knowledge of an agent as they could not be coherent with the agent s goals satisfaction and therefore having a negative impact on the action of the agent when trying to optimize his goals. For instance why in a negotiation context integrating permanently in the basic theory of a seller agent implementing his selling policy the attacks of a buyer agent representing his preferences? In our framework uncertain knowledge of a negotiating agent about his opponent (i.e. which arguments he does have in his theory and which arguments he doesn t) as well as exchanged arguments and attacks (expressing preferences) during a negotiation dialogue, would be represented in the uncertain part. So in classical AFs the basic theory is updated permanently when the environment changes irrespectively of the nature of the dynamics, while in our framework only the parts that are concerned with these dynamics are updated. So, modularity makes it easier to maintain the system and protects the satisfaction of its goals. Formally, a CAF is deﬁned as follows:

Deﬁnition 1. Let L be a language from which we can build arguments and let Args(L) be the set which contains all those arguments. A Control Argumentation Framework (CAF) is a triple CAF = F, C, U where F is the ﬁxed part, U is the uncertain part and C is the control part of CAF with:

F = AF , where AF is a set of arguments that we know they belong to the system and (AF AU) (AF AU) is an attack relation representing a set of attacks for which we are aware both of their existence and their direction. U = AU, ( ) where AU is a set of arguments for which we are not sure that they belong to the system, (((AU AF ) (AU AF ))\ ) is an attack relation representing a set of attacks for which we are aware of their existence but not of their direction and (((AU AF ) (AU AF ))\ ) is an attack relation representing a set of attacks for which we are not aware of their existence but we are aware of their direction, with = . C = AC, where AC is a set of arguments that the agent can choose to use or not, and {(ai, aj) | ai, aj (AF AC AU) and ai AC or aj AC}\( )) is an attack relation.

AF , AU and AC are disjoint subsets of Args(L).

F is the ﬁxed part of the CAF, i.e. the part of the system which cannot be inﬂuenced either by the agent or by the environment. U represents the possible changes of the environment and the context dependant information. This can be seen as threats against a goal related to the ﬁxed part. C represents everything which can be decided by the agent; this part is seen as the remedial actions to protect the goal.

Intuitively, AF , (AF AF ) is a classical AF where everything is known. The originality of our approach lies in

the other arguments and attacks. For instance, there is an attack (ai, aj) or (ai, aj) , with ai, aj AF , when we are sure that two arguments exist but we are not sure of the direction or the existence of attacks between them (e.g. due to a lack of information about the context). An attack (ai, aj) , with ai AU and aj AF , represents a situation where it is uncertain whether ai is present in the system (e.g. some of its premises could be false at the current time), but if ai is in the system, then it certainly attacks aj.

Example 1. We deﬁne a CAF CAF = F, C, U as follows:

the ﬁxed part is F = {a1, a2, a3, a4, a5}, {(a2, a1), (a3, a1), (a4, a2), (a4, a3)} ; the uncertain part is U = {a6}, , with = {(a6, a4), (a4, a6)}, and = {(a5, a1)}; the control part is C = {a7, a8, a9}, {(a7, a5), (a8, a5), (a8, a6), (a9, a6)} .

a6 AU a7 a8

Figure 1: The CAF CAF

Before talking about controllability, we need to introduce the notion of completion of a CAF. Intuitively, a completion is a classical AF which is built from the CAF, by choosing one of the possible options for each uncertain argument or attack.

Deﬁnition 2. Given a CAF CAF = F, C, U , a completion of CAF is an AF AF = A, R , s.t.

A = AF AC Acomp where Acomp AU; if (a, b) R, then (a, b) ; if (a, b) , then (a, b) R; if (a, b) and a, b A, then (a, b) R or (b, a) R; if (a, b) and a, b A, then (a, b) R.

Let us notice that the deﬁnition of a completion does not specify anything about the attacks from , since these attacks may not appear.

Example 2 (Example 1 cont.). We describe two possible completions of CAF. First, we consider a completion AF1 where the attack (a5, a1) is not included, while the argument a6 (with the attack (a6, a4)) is included. Another possible completion is AF2, where a6 is not included (so, neither the

attacks related to it) while the attack (a5, a1) is included. The completions are classical AFs, where no distinction is made between the different kinds of arguments and attacks.

Figure 2: Two possible completions of CAF

Controllability means that we can select a subset Aconf AC and the corresponding attacks {(ai, aj) | ai, aj (AF AU Aconf)} such that whatever the completion of CAF, a given target is always reached. We focus on two kinds of targets: credulous acceptance of a set of arguments (this is reminiscent of extension enforcement (Baumann and Brewka 2010)) and skeptical acceptance of a set of arguments.

Deﬁnition 3. A control conﬁguration of a CAF CAF = F, C, U is a subset Aconf AC. Given a set of arguments T AF and a semantics σ, we say that T is skeptically (resp. credulously) reached by the conﬁguration Aconf w.r.t. σ if T is included in every (resp. at least one) σextension of every completion of CAF = F, C , U , with C = Aconf, {(ai, aj) | ai, aj (AF AU Aconf)} . We say that CAF is skeptically (resp. credulously) controllable w.r.t. T and σ.

Example 3 (Example 1 cont.). We suppose that the target is T = {a1}. When we consider the control conﬁguration A conf = {a9}, T is neither skeptically nor credulously reached by A conf w.r.t. the stable semantics. Indeed, for the conﬁgured CAF CAF where C is reduced to A conf, we can exhibit the completion AF3 where a1 does not belong to a stable extension. On the contrary, the control conﬁguration A conf = {a8} yields a conﬁgured CAF CAF such that every completion accepts a1 both credulously and skeptically (see AF4 for an example of such a completion). So CAF is credulously (and skeptically) controllable w.r.t. {a1} and the stable semantics.

Controllability Through Logical Encoding We propose a method to obtain a control conﬁguration Aconf s.t. a set T of arguments is included in all extensions

Figure 3: Completions of conﬁgured CAFs

or at least one extension, whatever the evolution of AU and the actual state of the uncertain attacks. More precisely, our procedure determines if there exists such a conﬁguration, and provides it when it exists. For illustrating our approach, we focus on the stable semantics, extending the encoding from (Besnard and Doutre 2004). However, our method is generic, and can be adapted to any semantics. Especially, for complete and admissible we can also use propositional encodings from (Besnard and Doutre 2004).

Let us recall the method to encode the relation between the structure of an AF and its stable extensions. We deﬁne ﬁrst two kinds of propositional variables. Given AF = A, R , xi A, accxi is a propositional variable representing the acceptance status of the argument xi; xi, xj A, attxi,xj is a propositional variable representing the attack from xi to xj. Φst is the formula Φst =

xj A(attxj,xi accxj)]. When the att-variables are assigned the truth value corresponding to the attack relation of AF, the models of Φst (projected on the acc-variables) are in one-to-one correspondence with the the stable extensions of AF. Indeed, given AF = A, R , we deﬁne the formula ΦR st = Φst (

(xi,xj) R attxi,xj) (

(xi,xj)/ R attxi,xj). Given ω a model of ΦR st, the set {xi | ω(accxi) = } is a stable extension of AF. Similarly, for any stable extension ϵ of AF, ω s.t. ω(accxi) = iff xi ϵ is a model of ΦR st.

Back to the case of CAFs, we see that we cannot directly generalize ΦR st to obtain an encoding for the stable extensions of the completions of a CAF, since the arguments from AC which are selected by the agent (i.e. the control conﬁguration) are not known in advance. Similarly, the arguments from AU are not all present in the completion, since they are subject to evolution. xi AC AU, onxi is a propositional variable which is true when xi currently appears in the framework.

Thanks to the on-variables, we will generalize the formula ΦR st to consider the fact that an argument xi has no inﬂuence on the extensions when it is not currently in the framework (i.e. onxi is false).

Notation: A = AF AC AU, R = Now, we can propose an encoding which relates the attack relation and the arguments statuses in CAF = F, C, U :

xi AF [accxi xj A(attxj,xi accxj)] xi AC AU [accxi (onxi xj A(attxj,xi accxj))] (xi,xj) attxi,xj (xi,xj) attxi,xj attxj,xi (xi,xj)/ R attxi,xj

The ﬁrst two lines of this deﬁnition states in which condition an argument from AF is accepted; in this situation it is exactly as in the case of classical AFs: an argument is accepted when all its attackers are rejected. Then, the next two lines concerns arguments from AC and AU; since these arguments may not appear in the completion of the CAF, we add the condition that onxi is true to allow xi to be accepted. The last lines specify the case in which there is an attack in the completion: attacks from and are mandatory, and their direction is known; attacks from are mandatory, but the actual direction is not known. We do not give any constraint about , which is equivalent to the tautological constraint attxi,xj attxi,xj: the attack may appear or not. Finally, we know that attacks which are not in R do not exist. So, any model of Φst(CAF) represents a conﬁguration of CAF (given by the variables onxi, xi AC), its completions (given by the attxi,xj and onxi, xi AU variables), and one of its stable extensions (given by the accxi variables).

Given a set of arguments T, the fact that T must be included in all the stable extensions is represented by:

Φsk st (CAF, T) = Φst(CAF)

Given a set of arguments T, the fact that T must be included in at least one stable extension is represented by:

Φcr st(CAF, T) = Φst(CAF)

Now, there is a control conﬁguration s.t. T is skeptically accepted iff the formula

{onxi | xi AC} {onxi | xi AU} {attxi,xj | (xi, xj) }Ψ (Φsk st (CAF, T)) (1)

is valid, with Ψ Q deﬁned, for Q { , }, by

(xi,xj) [(( attxi,xj attxj,xi) ΨQ(Φ)) ((attxi,xj attxj,xi) ΨQ(Φ)) ((attxi,xj attxj,xi) ΨQ(Φ))]

and ΨQ(Φ) = Q{accxi | xi A}Φ.

This formula follows the deﬁnition of skeptical controllability: which consists in determining whether there is a control conﬁguration (given by the existential quantiﬁcation over onxi, xi AC) such that for every completion, every extension satisﬁes the target. However, for the universal quantiﬁcations, we cannot make a trivial use of Boolean quantiﬁers to quantify over the set of every possible completion. Indeed, if we use {attxi,xj | (xi, xj) }, the formula should be true for any assignment of the Boolean variables attxi,xj, including the case when both attxi,xj and attxj,xi are false. This speciﬁc assignment would be conﬂicting with the clause attxi,xj attxj,xi from Φst(CAF). See e.g. in example 1 the case of argument a6 and the attacks it is involved: atta6,a4 and atta4,a6 cannot be false at the same time. For this reason, the quantiﬁcation over the possible completions is made by the combination of classical Boolean quantiﬁcation over the variables onxi, xi AU and attxi,xj, (xi, xj) , and a weaker form of quantiﬁcation implemented by Ψ Q . This function allows to quantify over all the valuations of attxi,xj, (xi, xj) , except those which do not correspond to completions (and would violate attxi,xj attxj,xi). Then, for each completion, the universal quantiﬁcation over the accxi variables allows to verify that the target T is contained in every extension. For credulous controllability, we use the following encoding instead:

{onxi | xi AC} {onxi | xi AU} {attxi,xj | (xi, xj) }Ψ (Φcr st(CAF, T)) (2)

Let us notice that this time, the accxi variables are existentially quantiﬁed: T must be implied by at least one stable extension, but not necessarily all of them.

More precisely, to determine whether a CAF is controllable w.r.t. a set of arguments T and the stable semantics, we need to check the validity of one of the previous QBF encodings (depending whether we are interested in skeptical or credulous controllability). To determine the control conﬁguration which corresponds to the controllability, we need to determine the truth assignment of the onxi variables, for xi AC. The control conﬁguration is given by Aconf = {xi AC | onxi is assigned to 1}. Both these tasks can be performed by any modern QBF solver (Pulina 2016). The method is formally described in Algorithm 1. We suppose that QBFTruth is a sound and complete procedure which determines whether a QBF is true or not; QBFModel is a sound and complete procedure which returns, when it exists, a consistent assignment of the Boolean variables which are quantiﬁed at the ﬁrst existential level.

Example 4 (Example 1 cont.). We illustrate our QBF-based approach with an instantiation of the formula Φst(CAF) with CAF as deﬁned previously. Several occurrences of the pattern attxj,xi accxj appear in the logical encoding. For a matter of readability, when attxj,xi is known to be true, we replace this implication by the fact accxj. When

Algorithm 1 CAFControl

Require: CAF = F, C, U , T AF , x {sk, cr} QBFsk(CAF, T) is the formula deﬁned by (1) QBFcr(CAF, T) is the formula deﬁned by (2) if QBFTruth(QBFx(CAF, T)) then Aconf = {xi AC | onxi is assigned 1 in QBFModel(QBFx(CAF, T))} return Aconf else return end if

attxj,xi is known to be false, the implication can be removed from the encoding.

Φst(CAF) = [acca1 ( acca2 acca3 (atta5,a1 acca5))] [acca2 acca4] [acca3 acca4] [acca4 (atta6,a4 a6)]

[acca7 ona7] [acca8 ona8] [acca9 ona9] [acca5 ( acca7 acca8)] [acca6 (ona6 acca8 acca9 (atta4,a6 acca4))]

[atta2,a1 atta3,a1 atta4,a2 atta4,a3 atta7,a5 atta8,a5 atta8,a6 atta9,a6]

[atta6,a4 atta4,a6]

(xi,xj)/ R attxi,xj

To keep the encoding simple, we do not provide details on the part concerning the absence of attacks, which is summarized in (xi,xj) R attxi,xj. Φst(CAF) is the base of the encoding. The encoding adapted for the skeptical controllability is Φsk st (CAF, T) = (Φst(CAF)

xi T accxi). Finally, with the quantiﬁers, we obtain the following QBF:

ona7, ona8, ona9, ona6 atta5,a1 [(( attx4,x6 attx6,x4) Ψ) ((attx4,x6 attx6,x4) Ψ) ((attx4,x6 attx6,x4) Ψ)]

with Ψ = {accxi | xi A}Φsk st (CAF, T). It is possible to compute CAFControl(CAF, T, sk): using a QBF solver on this formula gives a valuation of the ona7, ona8, ona9 variables which corresponds to a control conﬁguration, i.e. a subset of AC such that the target T = {a1} is skeptically accepted. Here, the solutions are the control conﬁgurations which contain either a8, or a7 and a9 together.

Now we prove that our procedure for determining a control conﬁguration is sound and complete.

Proposition 1. Given a CAF CAF = F, C, U and a target T AF , 1. if CAFControl(CAF, T, sk) = Aconf, then CAF is skeptically controllable w.r.t. T and the stable semantics, and T is skeptically reached by Aconf w.r.t. the stable semantics; 2. if CAFControl(CAF, T, cr) = Aconf, then CAF is credulously controllable w.r.t. T and the stable semantics, and T is credulously reached by Aconf w.r.t. the stable semantics.

Proposition 2. Given a CAF CAF = F, C, U and a target T AF , 1. if CAF is skeptically controllable w.r.t. T and the stable semantics, then CAFControl(CAF, T, sk) = Aconf s.t. T is skeptically reached by Aconf w.r.t. the stable semantics; 2. if CAF is credulously controllable w.r.t. T and the stable semantics, then CAFControl(CAF, T, cr) = Aconf s.t. T is credulously reached by Aconf w.r.t. the stable semantics.

When a CAF is not controllable, i.e. there is no subset of C that renders a target argument acceptable for all completions, we may want to seek for a subset of C that achieves that for most of the completions. The recent techniques of (Reimer et al. 2014) on QBF with soft variables can be of use here. Roughly speaking, the idea of soft variables in QBFs is as follows. In a standard QBF Q1X1Q2X2 . . . Qn XnΦ the quantiﬁcation level of a variable x Xi is i. In other words the quantiﬁcation level of each variable is ﬁxed. In contrast, the extension presented in (Reimer et al. 2014) allows for soft variables, i.e. variables that are not assigned a speciﬁc level. Instead, each soft variable is associated with a ﬁxed set of allowed quantiﬁcation levels. Soft variables are preﬁxed with the symbol Q , L , where L is the set of allowed quantiﬁcation levels. For instance the formula F = Q , {1,2,3}x y zΦ, allows any of the levels 1,2, and 3, giving rise to three possible formulas F1 = x y zΦ, F2 = xy zΦ and F3 = y xzΦ. For each allowed quantiﬁcation level, there is an associated score deﬁned by the user. The optimization problem that arises in this context is to ﬁnd a level for each soft variable so that the associated propositional formula Φ is satisﬁed, and the sum of the scores of the soft variables is maximized. If s(x, l) denotes the score assigned to level l for variable x, assume that for the formula F of the previous example s(x, 1) = 3, s(x, 2) = 2, s(x, 3) = 1. Then, the solution to F is a truth assignment that satisﬁes F1. If F1 is unsatisﬁable, the solution to F is any satisfying assignment of F2. Similarly F3 is the solution if F2 is unsatisﬁable. Intuitively, quantiﬁcation levels that are more likely to lead to unsatisﬁability should be assigned a higher score.

Computational Complexity

We now investigate the computational complexity of determining whether a CAF is controllable, i.e. whether a goal T is skeptically (resp. credulously) reached, for a given conﬁguration. Our encodings lead to obvious upper bound of the complexity: determining whether a goal T is skeptically (resp. credulously) reached belongs to ΣP 2 (resp. ΣP 3 ). We provide a lower bound for credulous acceptance.

Deﬁnition 4. The credulous (resp. skeptical) conclusion problem is the problem of deciding for a given semantics σ, a Control Argumentation Framework CAF = F, C, U , and an argument q AF , whether there exists a control conﬁguration Aconf such that q is credulously (resp. skeptically) reached by the conﬁguration Aconf under semantics σ.

Proposition 3. The credulous conclusion problem of a CAF under the stable semantics is Σp 2-hard. Our framework generalizes existing work. This speciﬁc instance of CAFs leads to a lower complexity. Deﬁnition 5. A Simpliﬁed Control Argumentation Framework (SCAF) is a CAF F, C, U such that AU = , = , = , and is denoted as F, C, . Note that SCAFs correspond to non-strict normal extension enforcement, since a SCAF F, C, is credulously controllable w.r.t. a set T iff T can be non-strictly enforced in F with a normal expansion (Baumann and Brewka 2010) by some arguments and attacks from C. So, as a direct consequence of (Wallner, Niskanen, and J arvisalo 2016), the credulous conclusion problem for a SCAF under the stable semantics is NP-complete. Proposition 4. The credulous conclusion problem for a Simpliﬁed Control Argumentation Framework under the stable semantics is NP-complete. We also obtain a partial result for the skeptical conclusion problem. Proposition 5. The skeptical conclusion problem for a Simpliﬁed Control Argumentation Framework under the stable semantics is NP-hard.

Related Work Many works on argumentation dynamics or uncertainty in argumentation have been proposed in recent years. We describe here the more relevant approaches.

First, Partial Argumentation Frameworks (PAFs) have been proposed in (Coste-Marquis et al. 2007). Such a PAF is similar to classical Dung s AFs, with an additional relation between arguments representing ignorance. Formally, a PAF can be seen as a CAF with AC = AU = , and = = , while the ignorance relation of the PAF corresponds to our relation. (Coste-Marquis et al. 2007) uses PAFs as a tool to merge several AFs. Later, (Baumeister, Neugebauer, and Rothe 2015) studies PAFs (renamed as Attack-Incomplete AFs). The question studied in this paper is to determine the complexity of the veriﬁcation problem for several argumentation semantics, i.e given a set of arguments S and a PAF, is S an extension of every (or some) completion of the PAF. (Baumeister, Rothe, and Schadrack 2015) handle the same question for a variant of the framework, named Argument Incomplete AF. This kind of AFs are built on two different sets of arguments, corresponding respectively to AF and AU in CAFs. For all these frameworks (Coste-Marquis et al. 2007; Baumeister, Neugebauer, and Rothe 2015; Baumeister, Rothe, and Schadrack 2015), we observe that CAFs propose a more general setting to represent uncertainty in argumentative scenarios. Moreover, none of these works is concerned with argumentation dynamics nor proposes a computational method. (Boella et al. 2011) introduces a concept of potential attacks, which is related to the uncertain attacks relation . However, the difference is that potential attacks are discussed by agents, which decide to accept them (which

means to move them from to ) or reject them (which means to remove them from the framework) to obtain ﬁnally a classical AF which optimizes some criterion. Uncertainty in argumentation has also been studied in the context of probabilities (Hunter 2014). This supposes that the agent has some richer information than what is required in the deﬁnition of CAFs. It seems reasonable to consider that this kind of numeric information is not always available for the agent. However, using probabilities in argumentation dynamics could be a possible extension of our work and is kept for future work.

There is a strong relation between our contribution and extension enforcement (Baumann and Brewka 2010). As said before, there is a correspondence between the credulous conclusion problem for SCAFs and some speciﬁc extension enforcement operators. However, even our simpliﬁed framework (i.e. SCAFs) is more general than extension enforcement (since it also permits to work with the skeptical conclusion problem). Moreover, since extension enforcement does not consider uncertainty, it cannot be used to tackle situations where the agent knowledge is incomplete. On the opposite, the YALLA language (Dupin de Saint-Cyr et al. 2016) seems to be expressive enough to cover any kind of reasoning in abstract argumentation, including reasoning with uncertain attacks or arguments. However, YALLA pays the price of its generality: we are not aware of any efﬁcient algorithmic approach to handle YALLA-based reasoning. There is a connection with input/output modules (Baroni et al. 2014). However, the idea of input/output is to study the relations between sub-frameworks, i.e. how the arguments status in a sub-framework inﬂuences other sub-frameworks. These modules are not related to the enforcement of a set of arguments, and do not incorporate uncertainty. Finally, the acronym CAF has already been used in some work related to argumentation dynamics (see e.g. (Liao, Jin, and Koons 2011)) where it stands for Conditioned Argumentation Frameworks. In this work, the authors propose a division of an argumentation theory (i.e. affected, unaffected and conditioning parts) w.r.t. an update. However this division is completely different to our partitioning. Moreover, this work assumes complete information concerning the addition/deletion of arguments and attacks.

Conclusions and Future Work

In this paper, we presented a novel abstract argumentation framework called CAF, integrating in an uniﬁed and modular computational framework, all the possible argumentation dynamics considered in the literature, under uncertainty assumption. We have proposed the notion of controllability of a CAF, i.e. the fact that a CAF can anticipate all the possible threats against a given goal related to arguments acceptance.

As future work, we will study a negative counterpart of the skeptical and credulous conclusion problems, i.e. determining whether it is possible to control a CAF such that some arguments are rejected. We plan to extend our com-

plexity study with completeness results, results for the skeptical conclusion problem, and other semantics. In the current state, we search for a solution when a CAF is controllable, i.e. there is a conﬁguration which guarantees that the target is reached for any possible completion. However, there are situations where a CAF is not controllable, which leads to an unsatisﬁable logical encoding. We will study the related optimization problem, which consists in ﬁnding a conﬁguration such that the target is reached in as many completions as possible. As mentioned previously, QBFs with soft variables (Reimer et al. 2014) can be used for that. We will identify concrete applications of CAFs in order to extract benchmarks from these applications, and run our (soft) QBF-based algorithms on these benchmarks. We are also interested in the development of the structured version of CAFs. Indeed, an agent needs to know the internal structure of an argument to determine whether it is activated or not, depending on which arguments premises can be deduced from the agent s background knowledge. We do believe that the computational efﬁciency of our CAF, while generalizing the possible dynamics through consideration of uncertainty, allowing to handle unpredicted threats in dynamic environments, may be very well suited for building real world applications. Especially, we are interested in implementing self-adaptive systems ensuring real time control tasks in different contexts such as smart homes, surveillance of buildings and streets, personalized self-regulation services for humans, recommendation policies in ﬁnance and risk management, etc.

Arora, S., and Barak, B. 2009. Computational Complexity - A Modern Approach. Cambridge University Press. Baroni, P.; Boella, G.; Cerutti, F.; Giacomin, M.; van der Torre, L. W. N.; and Villata, S. 2014. On the input/output behavior of argumentation frameworks. Artif. Intell. 217:144 197. Baroni, P.; Caminada, M.; and Giacomin, M. 2011. An introduction to argumentation semantics. Knowledge Eng. Review 26(4):365 410. Baumann, R., and Brewka, G. 2010. Expanding argumentation frameworks: Enforcing and monotonicity results. In COMMA 10, 75 86. Baumeister, D.; Neugebauer, D.; and Rothe, J. 2015. Veriﬁcation in attack-incomplete argumentation frameworks. In ADT 15, 341 358. Baumeister, D.; Rothe, J.; and Schadrack, H. 2015. Veriﬁcation in argument-incomplete argumentation frameworks. In ADT 15, 359 376. Besnard, P., and Doutre, S. 2004. Checking the acceptability of a set of arguments. In NMR 04, 59 64. Besnard, P., and Hunter, A. 2008. Elements of Argumentation. MIT Press. Biere, A.; Heule, M.; van Maaren, H.; and Walsh, T., eds. 2009. Handbook of Satisﬁability, volume 185 of Frontiers in Artiﬁcial Intelligence and Applications. IOS Press.

Boella, G.; Gabbay, D. M.; Perotti, A.; van der Torre, L. W. N.; and Villata, S. 2011. Argumentative agents negotiating on potential attacks. In KES-AMSTA 11, 280 290. Booth, R.; Kaci, S.; Rienstra, T.; and van der Torre, L. 2013. A logical theory about dynamics in abstract argumentation. In SUM 13, 148 161. Cayrol, C.; de Saint-Cyr, F. D.; and Lagasquie-Schiex, M. 2010. Change in abstract argumentation frameworks: Adding an argument. J. Artif. Intell. Res. (JAIR) 38:49 84. Coste-Marquis, S.; Devred, C.; Konieczny, S.; Lagasquie Schiex, M.; and Marquis, P. 2007. On the merging of dung s argumentation systems. Artif. Intell. 171(10-15):730 753. Coste-Marquis, S.; Konieczny, S.; Mailly, J.; and Marquis, P. 2014. On the revision of argumentation systems: Minimal change of arguments statuses. In KR 14. Coste-Marquis, S.; Konieczny, S.; Mailly, J.; and Marquis, P. 2015. Extension enforcement in abstract argumentation as an optimization problem. In IJCAI 15, 2876 2882. Doutre, S.; Herzig, A.; and Perrussel, L. 2014. A dynamic logic framework for abstract argumentation. In KR 14. Dung, P. M.; Kowalski, R. A.; and Toni, F. 2009. Assumption-based argumentation. In Argumentation in Artiﬁcial Intelligence. 199 218. Dung, P. M. 1995. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Art. Intel. 77:321 357. Dupin de Saint-Cyr, F.; Bisquert, P.; Cayrol, C.; and Lagasquie-Schiex, M. 2016. Argumentation update in YALLA (yet another logic language for argumentation). Int. J. Approx. Reasoning 75:57 92. Hunter, A. 2014. Probabilistic qualiﬁcation of attack in abstract argumentation. Int. J. Approx. Reasoning 55(2):607 638. Kakas, A. C., and Moraitis, P. 2003. Argumentation based decision making for autonomous agents. In AAMAS 03, 883 890. Kleine B uning, H., and Bubeck, U. 2009. Theory of quantiﬁed boolean formulas. In Handbook of Satisﬁability. 735 760. Liao, B. S.; Jin, L.; and Koons, R. C. 2011. Dynamics of argumentation systems: A division-based method. Artif. Intell. 175(11):1790 1814. Pulina, L. 2016. The ninth QBF solvers evaluation - preliminary report. In QBF 16, 1 13. Reimer, S.; Sauer, M.; Marin, P.; and Becker, B. 2014. QBF with soft variables. In AVOCS 14. Wallner, J. P.; Niskanen, A.; and J arvisalo, M. 2016. Complexity results and algorithms for extension enforcement in abstract argumentation. In AAAI 16, 1088 1094.