July 2020

Estimating Stability for Efficient
Argument-based Inquiry
Daphne ODEKERKEN a,b , AnneMarie BORG a and Floris BEX a,ca Department of Information and Computing Sciences, Utrecht University 1b National Police Lab AI, Netherlands Police
c Tilburg Institute for Law, Technology and Society, Tilburg University
Abstract. We study the dynamic argumentation task of detecting stability: givena specific structured argumentation setting, can adding information change the acceptability status of some propositional formula? Detecting stability is not tractablefor every input, but efficient computation is essential in practical applications. We
present a sound approximation algorithm that recognises stability for many inputs
in polynomial time and we discuss several of its properties. In particular, we show
under which constraints on the input our algorithm is complete. The proposed algorithm is currently applied for fraud inquiry at the Dutch National Police - weprovide an English demo version that also visualises the output of the algorithm.
Keywords. dynamic argumentation, structured argumentation, inquiry

1. Introduction
One task of the police is the intake of citizens’ reports on crimes: the citizen tells thepolice what happened; subsequently, additional questions can be asked to determine if
the citizen has been the victim or witness of a crime. Certain high-volume crimes can bereported online. This can be as simple as filling out a web form, but can also be a more involved online dialogue with a (possibly artificial) agent. One specific high volume crimethat can be reported online at the Dutch National Police is internet trade fraud. This concerns fake web shops and malicious second-hand traders on platforms such as eBay. In[3], an initial sketch was given for an artificial agent handling the intake of internet tradefraud by combining natural language processing with symbolic techniques for reasoning
about crime reports. During the subsequent development of the intake agent, we regarded
intake as argument-based inquiry [4]. In this inquiry, defeasible rules representing thelaws and practices surrounding trade fraud are combined with the citizen’s knowledge ofthe specific situation they observed, to build arguments for and against the main claim
made by the citizen: that they have been the victim of trade fraud.
The first contribution of this paper is to present the implemented version of the intake agent. It has been released on the web site of the Dutch Police2 where it handles theintake of hundreds of fraud reports every day. Because the police web site only shows
1 This research has been partly funded by the Dutch Ministry of Justice and the Dutch National Police.
2 https://aangifte.politie.nl/iaai-preintake

July 2020

Question policy

Next question
Report text

Information
extraction

Observations
STABILITY

Argumentation
settingnoyes“fraud”
stable?

Substantiatedconclusion

Figure 1. Overview of the hybrid inquiry agent for the intake of fraud complaints.

the Dutch user interface, we provide a demo3 of an English version that gives more insight in the underlying reasoning. The agent’s architecture is illustrated in Figure 1. The
information extraction component uses natural language processing techniques to automatically extract the initial observations from the free text user input [12]. These observations are then combined with rules concerning trade fraud in the argumentation setting
to build arguments for and against the claim “fraud”. The stability component decides if
any additional observations that the citizen could possibly add in the future can change
the acceptability status of the “fraud” claim. If not, the dialogue terminates; otherwise
a question policy component finds the best question to ask given current observations.
The stability component is thus an important part of the agent’s architecture: it provides
a termination criterion that prevents the agent from asking unnecessary questions. If, forexample, it is already clear from the initial observations that we are not dealing withfraud because the citizen simply received a product they did not like, the agent will notcontinue to exhaustively inquire [4] about further details of the situation.
The rest of this paper focuses on a more theoretical study of the stability componentof the intake agent. Stability in structured argumentation is a form of dynamic argumentation that was introduced in [14]. Informally, a claim is stable if more information cannot change the acceptability of the claim, where this acceptability depends on the acceptability of arguments for this claim in terms of Dung’s grounded semantics [7]. Detecting
stability is complex: a brute-force approach would involve generating and evaluating all
possible future argumentation setups given new observations, which would require far
too much time in an applied setting. In this paper, we provide some new insights on thecomplexity of the stability problem by showing that it is CoNP-hard.
A sound approximation algorithm for stability was provided in [14]. However, theconditions under which the algorithm is complete were not studied in-depth. When investigating these conditions, we identified the nontrivial issues of irrelevant labels andsupport cycles, in the presence of which the algorithm from [14] does not detect a stablesituation. In this paper, we solve these issues by proposing a new approximation algorithm consisting of an alternative labelling and a preprocessing step. We prove4 that therefined algorithm has polynomial time complexity and that it is sound. Furthermore, we
specify constraints on the input under which the new algorithm is complete.
Section 2 below specifies the structured argumentation setup for which we formallydefine the stability problem in Section 3. In Section 4 we then identify issues with thealgorithm of [14], propose our refined algorithm and study its properties. Section 5 discusses related work in dynamic argumentation and Section 6 concludes the paper.
3 https://nationaal-politielab.sites.uu.nl/estimating-stability-for-efficient-argument-based-inquiry/
4 Due to space restrictions, proofs are omitted in this paper. The proofs are available at https://nationaal-politielab.sites.uu.nl/estimating-stability-for-efficient-argument-based-inquiry/

July 2020

2. Preliminaries
Our argumentation setup is a variation on ASPIC+ [11], albeit simplified in that we only
consider axiom premises, defeasible rules and no preferences. From a theoretical perspective, this can be considered to be a limitation; however, from a practical point ofview this simplification makes it more feasible for police employees without backgroundin formal argumentation to adapt or create rule sets. We add the notion of queryable literals Q. These literals can be obtained (i.e. added to the knowledge base) by querying
the citizen, thus restricting the possibilities of updating the knowledge base.
Definition 1 (Argumentation Setup). An argumentation setup AS is a tuple AS =(L, R, Q, K) where:• L is a finite propositional language, closed under classical negation (¬). The literals will be denoted by lower-case letters. We write a = −b iff a = ¬b or b = ¬a.
• R is a finite set of defeasible rules a1 , . . . , am ⇒ c such that {a1 , . . . , am , c} ⊆ L.
Where r ∈ R, ants(r) = {a1 , . . . , am } are the antecedents of r and cons(r) = c isits consequent. We refer to a rule with consequent c as “a rule for c”.
• Q ⊆ L is a set of queryable literals, s.t. l ∈ Q iff −l ∈ Q.
• K ⊆ Q is the knowledge base, which must be consistent: if l ∈ K then −l 6∈ K.
Based on an argumentation setup, arguments can be constructed from R and K.
Definition 2 (Argument). Let AS = (L, R, Q, K) be an argumentation setup. We denote
by Arg(AS) the set of arguments inferred from AS. An argument A ∈ Arg(AS) is:• an observation-based argument c iff c ∈ K.
The conclusion conc(A) of A is c. The set of subarguments sub(A) of A is {c}.
• a rule-based argument A1 , . . . , Am ⇒ c iff for each i ∈ [1 . . m]: Ai is in Arg(AS)with conclusion ci and there is a rule r : c1 , . . . , cm ⇒ c in R.
The conclusion conc(A) of A is c. The set of subarguments sub(A) of A is
sub(A1 ) ∪ . . . ∪ sub(Am ) ∪ {A}. The top rule top-rule(A) of A is r.
We refer to an argument with conclusion c as “an argument for c”. We refer to a rulebased argument with top rule r as “an argument based on r”.
Definition 3 (Attack). Let AS = (L, R, Q, K) be an argumentation setup. For two arguments A, B ∈ Arg(AS) we say that A attacks B on B0 iff A’s conclusion is c, there is a
subargument B0 ∈ sub(B) such that conc(B0 ) = −c and −c 6∈ K.
Our definition of attack corresponds to rebuttal in ASPIC+ [11]. From Definition 3
it follows directly that observation-based arguments cannot be attacked.
Example 1 (Online trade fraud). Let AS = (L, R, Q, K), visualised in Figure 2, be
an argumentation setup in the domain of online trade fraud. L consists of the literals{b, sm, sp, rp, rm, u, s,t, sd, rd, d, f } and their negations. Squares represent literals fromL, rounded squares are queryable literals (from Q) and literals in K are shaded. Rules are
represented by double-lined arrows and attacks as single-lined arrows. Arg(AS) includes
an argument for f based on the rule sd, ¬rd, d ⇒ f and an argument for ¬ f based onb,t ⇒ ¬ f . These arguments attack each other.

July 2020

¬f

f

¬rd

sd
sm

b

sp

¬b

¬rp

b

¬rm

d
¬b

u

b

b
s

t

¬b

Figure 2. Example of an argumentation setup AS from the law enforcement domain. b: citizen tried to buy a
product (as opposed to selling a product); sm: citizen sent money; sp: citizen sent product; rp: citizen received
product; rm: citizen received money; u: suspicious url; s: screenshot of payment; t: trusted web shop; sd: citizen
delivered; rd: citizen received delivery; d: deception; f : fraud. Note that the literals b and ¬b are visualised
multiple times and attacks between them are omitted for clarity.

Like in ASPIC+ , the evaluation of arguments is done using the semantics of [7].
We choose grounded semantics since it is the most skeptical semantics, which fits theapplication in police investigation. We subsequently use the grounded extension to define
the acceptability of literals in an argumentation setup.
Definition 4 (Grounded Extension). Let AS = (L, R, Q, K) be an argumentation setup
and let S ⊆ Arg(AS). S is said to be conflict-free iff there are no A, B ∈ S such that A
attacks B. S defends A ∈ Arg(AS) iff for each B ∈ Arg(AS) that attacks A there is a C ∈ S
that attacks B. S is admissible iff it is conflict-free and defends all its arguments. S is
a complete extension iff it is admissible and contains all the arguments it defends. The
grounded extension G(AS) is the least (w.r.t. ⊆) complete extension.
Definition 5 (Acceptability). Let AS = (L, R, Q, K) be an argumentation setup. The
acceptability of literal l ∈ L given AS is:• unsatisfiable iff there is no argument for l in Arg(AS);• defended iff there exists an argument for l in Arg(AS) that is also in the grounded
extension G(AS);• out iff there exists an argument for l in Arg(AS), but each argument for l in Arg(AS)is attacked by an argument in the grounded extension G(AS);• blocked iff there exists an argument for l in Arg(AS), but no argument for l is in
the grounded extension G(AS) and at least one argument for l is not attacked byan argument in G(AS).
Note that these acceptability statuses are complementary: e.g. if l is not unsatisfiable,
defended or out, then it is blocked. This follows directly from the definition.
Example 2 (Example 1 continued). In argumentation setup AS from Figure 2, G(AS)
contains (unattacked) arguments for sm, b, ¬rp, u, t, sd, ¬rd and d, so these literals are
defended in AS. There are arguments for f and ¬ f in Arg(AS) that attack each other, butthese are not attacked or defended by any argument in G(AS), so f and ¬ f are blocked in
AS. Each other literal l ∈ L is unsatisfiable in AS: there is no argument for l in Arg(AS).
3. Stability
Using Definition 5, we can determine the acceptability status of a literal l ∈ L in a given
argumentation setup AS = (L, R, Q, K). However, by adding more information, l’s ac-

July 2020

ceptability status may change. Informally, l is stable in AS if its acceptability status cannot change by adding any combination of queryables to the knowledge base - provided
that the resulting knowledge base is consistent. Note that we restrict the changes on theargumentation setup to adding knowledge, since we expect the citizen to attribute only
facts on his/her situation. Next, we define future setups, which specify how information
can be added to AS.
Definition 6 (Future setups). The set of future setups F(AS) of an argumentation setup
AS = (L, R, Q, K) consists of all argumentation setups AS0 = (L, R, Q, K0 ) with K ⊆ K0 .
Note that the argumentation setup AS always belongs to the set of future setups
F(AS). Further recall from Definition 1 that K0 must be consistent since AS0 is an argumentation setup. Using the notion of future setups, we now define stability.
Definition 7 (Stability). Let AS = (L, R, Q, K) be an argumentation setup. A literal l ∈ L
is stable in AS iff there is an acceptability status acc ∈ {unsatisfiable, defended, out,
blocked} such that for each AS0 ∈ F(AS), l is acc in AS0 .
Example 3 (Example 2 continued). In our running example, the literal f is stable. By
querying the client agent, we could obtain more information; F(AS) for example contains
an argumentation setup with knowledge base K0 = K ∪ {¬sp} = {sm, b, ¬rp, u,t, ¬sp}.
However, adding information does not influence f ’s acceptability status: for each AS0 in
F(AS), f is blocked in AS0 . Therefore, f is stable in AS.
Proposition 1. Determining stability is CoNP-hard.
This can be shown by a polynomial-time reduction from the CoNP-complete problem UNSAT. The full proof is available on the website with additional material.
CoNP-hard problems are generally considered intractable (unless P = NP). Given theabove results and assuming that P 6= NP, there is no exact polynomial-time algorithm that
determines for an arbitrary argumentation setup AS if a literal is stable in AS. This meansthat an exact algorithm would need exponential time. Since practical applications require
fast computation for arbitrary argumentation setups, we consider a sound polynomialtime approximation algorithm in the next section.

4. Approximating stability
A first approximation algorithm for determining stability in formal argumentation was
proposed in [14]. This algorithm assigns a label to literals and rules that it considers to
be stable. Each label relates to one of the four cases of stability: U (unsatisfiable); D(defended); O (out); or B (blocked). However, the algorithm is not complete: there exist
argumentation setups that are stable but are not labelled as such by the approximation
algorithm. In [14] we gave an example, but no precise specification of argumentation setups for which the algorithm does not recognise stability. In the next subsection, we give
two additional examples which reveal different issues of the method described in [14]. In
Sections 4.2 and 4.3, we present a refined algorithm to solve these issues. Subsequently,
we will show soundness and conditional completeness and study the computational complexity of this refinement in Section 4.4.

July 2020

¬t

t

c
¬a

a

b
D

q2

D
D q1

t

¬b
a
q3

(a) D/B is irrelevant in [14] Case B lit. A.

b(b) Support Cycle. Q = 0,
/ so F(AS) = {AS}.
K = 0,/ so there is no argument for t in Arg(AS).
However, L does not label t.

Figure 3. Examples of incompleteness of the basic algorithm from [14].

4.1. Examples of incompleteness basic algorithm
Figures 3a and 3b illustrate two different issues of the algorithm from [14].
Example 4 (Irrelevant label problem). Figure 3a represents an argumentation setup AS
in which q1 , q2 and q3 are queryable. q1 is in the knowledge base. There is an argument
for t based on a ⇒ t and an argument for ¬t based on b ⇒ ¬t in Arg(AS). So for eachAS0 ∈ F(AS), t is blocked in AS0 . However, t is not recognised as being stable by thealgorithm in [14]. The literal q1 and rules q1 ⇒ a and q1 ⇒ b are correctly labelled D,
but the other literals and rules are not labelled by the algorithm. a and b are not labelled
because they may become either defended (if ¬q2 resp. ¬q3 ∈ K0 ) or blocked (if q2 resp.
q3 ∈ K0 ). As a result, the rules a ⇒ t and b ⇒ ¬t are not labelled because they may
become either defended or blocked. In all future setups in F(AS), the argument for a iseither defended (if q2 6∈ K0 ) or blocked (if q2 ∈ K0 ). Similarly, in every future setup, theargument for b is either defended (if q3 6∈ K0 ) or blocked (if q3 ∈ K0 ). The algorithmin [14] has a labelling rule Case B literal A stating that “l ∈ L is labelled B iff l ∈ Q anda rule for l and a rule for −l are labelled D or B”. However, this rule does not apply:
although a ⇒ t and b ⇒ ¬t will be labelled D or B in a future setup in which we haveinformation about q2 and q3 , we do not know the exact label - which is here irrelevant.
We will refer to the issue illustrated in Figure 3a as the irrelevant label problem. It iscaused by the fact that L only assigns a label if there is exactly one possible acceptancestatus for all future setups, but does not take into account that some acceptability statuses
are impossible in a future setup. The next example reveals another issue of the basic
algorithm, which we will refer to as the support cycle problem.
Example 5 (Support cycle problem). Figure 3b represents an argumentation setup AS in
which a, b, c and t are literals that are not queryable. As a result, there is no other futureargumentation setup than the current setup: F(AS) = {AS}. There is no argument for t
in Arg(AS), hence t is unsatisfiable for every AS0 ∈ F(AS). However, no rule or literal islabelled U since the algorithm in [14] only labels a non-queryable literal U if all rules
for this literal are labelled U; a rule only gets labelled U if at least one antecedent of thatrule is labelled U. Because of this support cycle, there is no place to start labelling.
Due to the irrelevant label problem and the support cycle problem, the algorithm
from [14] fails to recognise the stability of some argumentation setups. We present asolution to these problems in Sections 4.2 and 4.3.

July 2020

4.2. Reasoning with possible future labels
In this section, we present an alternative labelling method that bypasses the irrelevantlabel problem by reasoning with possible future labels. Whereas the approximation algorithm presented in [14] relies on a partial labelling function L that assigns at most one label to each literal in L and rule in R (L : L ∪ R →
7 {U, D, O, B} where →7 denotes a partial
function), we propose a labelling L0 that assigns a quadruple of four booleans hu, d, o, bi
to each literal and rule. Each boolean corresponds to an acceptability status. Intuitively,
the truth value of a boolean belonging to a literal or rule represents the possibility that
this literal or rule may become unsatisfiable (u), defended (d), out (o) or blocked (b) ina future argumentation setup. Similar to the approach in [14], labels of rules depend on
the labels of their antecedent literals and labels of literals depend on the labels of rules
for that literal. Literals and rules are labelled incrementally, starting from queryable literals and literals for which there is no rule and relabelling literals and rules based on the
resulting new labels, until no new label can be added.
Definition 8 (Quadruple labelling L0 ). Let AS = (L, R, Q, K) be an argumentation setup.
The labelling function L0 : L ∪ R → {0, 1} × {0, 1} × {0, 1} × {0, 1} assigns a label
hu, d, o, bi to each literal or rule in L ∪ R. Given a literal or rule x ∈ L ∪ R, we write¬u(x) [resp. ¬d(x), ¬o(x), ¬b(x)] iff the u- [resp. d-, o-, b-] boolean of x’s label is False
and u(x) [resp. d(x), o(x), b(x)] iff the u- [resp. d-, o-, b-] boolean of x’s label is True.
We say that a rule or literal x is labelled stable by L0 iff exactly one of the booleans isTrue: L0 (x) is h1, 0, 0, 0i, h0, 1, 0, 0i, h0, 0, 1, 0i or h0, 0, 0, 1i.
Given a literal l ∈ L, L0 (l) = hu, d, o, bi where:
literal cannot become unsatisfiable: ¬u(l) iff:
L-U-a) l ∈ K; or
L-U-b) there is a rule r for l with ¬u(r).
literal cannot become defended: ¬d(l) iff:
L-D-a) −l ∈ K; or
L-D-b) l 6∈ Q and for each rule r for l: ¬d(r); or
L-D-c) l 6∈ Q and there is a rule r0 for −l with ¬u(r0 ) and ¬o(r0 ).
literal cannot become out: ¬o(l) iff:
L-O-a) l ∈ K; or
L-O-b) for each rule r for l: ¬d(r), ¬o(r) and ¬b(r); or
L-O-c) l 6∈ Q and for each rule r for l: ¬o(r); or
L-O-d) l 6∈ Q and there is a rule r for l with ¬u(r) and ¬o(r).
literal cannot become blocked: ¬b(l) iff:
L-B-a) l ∈ Q; or
L-B-b) for each rule r for l: ¬d(r) and ¬b(r); or
L-B-c) for each rule r for l: ¬b(r) and for each rule r0 for −l: ¬d(r0 ) and ¬b(r0 ).
L-B-d) there is a rule r for l with ¬u(r), ¬o(r) and ¬b(r) and for each rule r0 for −l:¬d(r0 ) and ¬b(r0 ).
Given a rule r ∈ R, L0 (r) = hu, d, o, bi where:
rule cannot become unsatisfiable: ¬u(r) iff:
R-U-a) for each antecedent l of r: ¬u(l).
rule cannot become defended: ¬d(r) iff:
R-D-a) there is an antecedent l of r with ¬d(l).

July 2020

U

D

D/U

D/U/O

¬l2

l2

l3

q3

U

D

U

D/U

l1

q1

¬q1

q2

U

D

U

D/U

D/U

Figure 4. Quadruple labelling example.

rule cannot become out: ¬o(r) iff:
R-O-a) for each antecedent l of r: ¬o(l); or
R-O-b) there is an antecedent l of r with ¬d(l) and ¬o(l) and ¬b(l).
rule cannot become blocked: ¬b(r) iff:
R-B-a) for each antecedent l of r: ¬b(l); or
R-B-b) there is an antecedent l of r with ¬d(l) and ¬b(l).
Example 6. We give some intuition by labelling the AS from Figure 4. Some rules apply
if (the negation of) a literal is in K or Q, e.g. q1 is labelled h0, 1, 0, 0i by Definition 8case L-U-a, L-O-b and L-B-a: there is an observation-based argument for q1 that cannot
be attacked in any future setup. The absence of rules for a literal is informative for theacceptability status as well: e.g. l1 is labelled h1, 0, 0, 0i by L-D-b, L-O-b/c and L-B-b/c.
Other labels are based on the rules for (the negation of) a literal and propagate properties of (attacks on) subarguments. For example, q1 ⇒ l2 is labelled h0, 1, 0, 0i by R-Ua, R-O-a and R-B-a and l2 is labelled h0, 1, 0, 0i by L-U-b, L-O-c/d and L-B-c/d. Some
literals and rules cannot be labelled stable, but still some acceptability status(es) can be
excluded: e.g. the rule q2 ⇒ q3 is labelled h1, 1, 0, 0i by case R-O-a and R-B-a.
Example 7 (Alternative labelling Figure 3a). Consider the L0 labelling for the argumentation setup from Figure 3a. q1 is in the knowledge base, so by Definition 8,
L0 (q1 ) = h0, 1, 0, 0i. Then L0 (q1 ⇒ a) = L0 (q1 ⇒ b) = h0, 1, 0, 0i by R-U-a, R-O-a and
R-B-a. q2 and q3 are queryable but not in the knowledge base and there are no rules
for q2 or q3 , so by Case L-O-b and L-B-a: L0 (q2 ) = L0 (q3 ) = h1, 1, 0, 0i. For the rules
q2 ⇒ ¬a and q3 ⇒ ¬b, only the d- and u-booleans are True by R-O-a and R-B-a. As aresult, for the literals a and b only the d- and b-booleans are True by L-U-b and L-O-c,
which implies by R-U-a and R-O-a that L0 (b ⇒ t) = L0 (a ⇒ t) = h0, 1, 0, 1i. Finally, t islabelled L0 (t) = h0, 0, 0, 1i (by L-U-b, L-D-c and L-O-c/d), so t is labelled stable by L0 .
In Example 7 we saw that t is labelled stable by our labelling function L0 , but its
stability was not detected by [14]’s labelling function L. In general, each literal or rulelabelled stable by L is also labelled stable by L0 , but L0 covers more stable setups than L.
4.3. Preprocessing
The new labelling proposed in the previous section does not solve the support cycle problem: if we would apply the labelling L0 from Definition 8 to the argumentation setup
from Figure 3b, all literals l (including literal t) would be labelled h1, 1, 1, 1i. In orderto solve this issue, we add a preprocessing step, which is specified in Algorithm 1. The

July 2020

Algorithm 1 Preprocessing step
1: procedure P REPROCESS (L, R, Q, K)
2:Label each literal l s.t. l ∈ Q ∧ −l 6∈ K as h1, 1, 1, 1i
3:Label all other literals as h1, 0, 0, 0i
4:
5:
6:
7:
8:
9:

Label each r ∈ R as h1, 0, 0, 0i
while a label changed in the previous loop do
for Rule r in R do
if L(r) = h1, 0, 0, 0i and for each l ∈ ants(r): L(l) 6= h1, 0, 0, 0i thenLabel r as h1, 1, 1, 1iLabel cons(r) as h1, 1, 1, 1iidea of this algorithm is that initially, all literals that cannot be in the knowledge base in
a future setup and all rules are labelled h1, 0, 0, 0i (i.e. unsatisfiable). Then, the algorithm
incrementally removes unsatisfiable labels of rules for which all antecedents are not labelled h1, 0, 0, 0i, and of the consequents of these rules, based on the intuition that there
may be an argument based on these rules in a future setup.
Example 8 (Alternative labelling Example 5). We reconsider Figure 3b, assuming thatthe preprocessing step has been executed. In Line 3, all literals (a, b, c and t) are labelled
h1, 0, 0, 0i. Since the if-statement in Line 7 never returns true, no rule or literal gets
another label, so the while loop is executed only once. After termination of Algorithm 1,
all literals are still (correctly) labelled h1, 0, 0, 0i.
4.4. Properties of the proposed algorithm
In this subsection, we present properties of S TABILITY, our proposed algorithm, whichruns P REPROCESS on the argumentation setup and then labels all literals and rules by
repeatedly applying Definition 8. First, we consider S TABILITY’s soundness.
Proposition 2 (Soundness stability labelling). Given an argumentation setup AS =(L, R, Q, K) and labelling L0 after executing the S TABILITY algorithm, if a literal l ∈ L
is labelled stable in AS, then l is stable in AS.
Soundness can be proven by systematically analysing all argumentation setups inwhich a literal l is labelled stable (e.g. l ∈ K or [l 6∈ Q and there is no rule for l in R]) andproving that l is stable in each of them. Next, we consider completeness. As illustratedin Example 9, S TABILITY is not complete for all argumentation setups.
Example 9 (Example 3 continued). Consider the argumentation setup AS = (L, R, Q, K)
where L, R and Q are as in Figure 2, but K = {¬sm, rm}. S TABILITY does not label fstable: it expects a future argument for f based on sd, ¬rd, d ⇒ f , where the argument forsd is based on sp, ¬b ⇒ sd and the argument for ¬rd is based on ¬rp, b ⇒ rd. However,this argument would require both b and ¬b to be in the knowledge base, which violates
the consistency criterion. In fact, for each AS0 in F(AS) there is no argument for f inArg(AS0 ), so f should be labelled h1, 0, 0, 0i.
Example 9 shows that there are argumentation setups where the S TABILITY algorithm wrongfully takes the possibility into account that there exists an argument for aJuly 2020

literal in a future argumentation setup. Specifically, this issue is caused by inconsistentpotential arguments, which we define next.
Definition 9 (Potential argument). Let AS = (L, R, Q, K) be an argumentation setup. A
potential argument A p inferred from AS is:• c iff c ∈ Q and −c 6∈ K. prem(A p ) = {c}; conc(A p ) = c; and sub(A p ) = {c}.
• A1 , . . . , Am ⇒ c iff there is a rule c1 , . . . , cm ⇒ c in R and for each i ∈ [1 . . m]: Ai is
a potential argument inferred from AS and conc(Ai ) = ci . prem(A p ) = prem(A1 ) ∪. . . ∪ prem(Am ); conc(A p ) = c; and sub(A p ) = sub(A1 ) ∪ . . . ∪ sub(Am ) ∪ {A}.
We denote the set of potential arguments by P(AS). Given some A p , B p ∈ P(AS), A p pattacks B p iff there is a B0 ∈ sub(B p ) s.t. conc(A p ) = −conc(B0 ) and −conc(B0 ) 6∈ K;
A p is inconsistent with B p iff {a, −a} ∈ prem(A p ) ∪ prem(B p ) for some a ∈ L.
Note that, for any argumentation setup AS, each argument inferred from AS or somefuture setup is a potential argument in P(AS). However, there may be a potential argument A p ∈ P(AS) such that there is no AS0 ∈ F(AS) with A p ∈ Arg(AS0 ), but then A p must
be inconsistent with itself, like in Example 9. Example 10 reveals another issue, where
stability is not detected due to an inconsistency of two different potential arguments.
Example 10 (Mutual inconsistency issues). Given the argumentation setup AS illustrated
in Figure 5, for each AS0 = (L, R, Q, K0 ) in F(AS), l1 is blocked in AS0 : if ¬q2 6∈ K0
then there is an argument for l1 based on q2 ⇒ l1 ; otherwise there is an argument for l1
based on ¬q2 ⇒ l1 . However, l1 is not labelled h0, 0, 0, 1i because S TABILITY wrongfully
anticipates a future setup AS0 in which each argument for l1 is attacked by an argument in
G(AS0 ) (thus o(l1 )). For the same reason, ¬l1 is labelled d(¬l1 ) and therefore L0 (¬l1 ) 6=
h0, 0, 0, 1i, although ¬l1 is blocked in each AS0 ∈ F(AS).
The issues illustrated in Examples 9 and 10 can be generalised to the following two
situations. Given an argumentation setup AS = (L, R, Q, K) and a literal l ∈ L:
• l is inconsistently supported in AS iff there are A p , B p ∈ P(AS) such thatconc(A p ) = conc(B p ) = l and A p is inconsistent with B p .
• l is inconsistently attacked in AS iff there is a C p ∈ P(AS) such that conc(C p ) = l
and there are A p , B p ∈ P(AS) such that A p p-attacks C p , B p p-attacks C p and A p isinconsistent with B p .
If a potential argument is inconsistent with itself, its conclusion l can be incorrectly
labelled d(l) or b(l) (e.g. f in Example 9). Similarly, if two potential arguments with thesame conclusion are inconsistent, their conclusion l can be incorrectly labelled o(l) (e.g.
l1 in Example 10). Moreover, if l is inconsistently attacked, l may be incorrectly labelledd(l) (e.g. ¬l1 in Example 10) or b(l). Otherwise, l is labelled stable if it is stable in AS.
Proposition 3 (Conditional completeness stability labelling). Given an argumentation
setup AS = (L, R, Q, K) and a labelling L0 after executing S TABILITY. If l ∈ L is stable
in AS and l is not inconsistently supported or attacked, then l is labelled stable by L0 .
Finally, the proposed algorithm runs in polynomial time, which makes it suitable forpractical applications such as human-computer inquiry dialogues.
Proposition 4. The time complexity of S TABILITY is O(|L|2 · |R| + |L| · |R|2 ).

July 2020

B/O

q1

D

D

¬l1 D/B

l1

D/O

D/U

D

q2

¬q2

q3

D/O

D/U

D

Figure 5. For each AS0 ∈ F(AS): l1 and ¬l1 are blocked in AS0 , but not labelled as such due to inconsistent
support (l1 ) and attack (¬l1 ).

5. Related work
We study stability [14]: given a specific structured argumentation setting, can adding information change the acceptability status of some propositional formula? This is a relatively new task within dynamic argumentation, which studies the acceptability of (sets of)arguments or their conclusions in relation to changes on the argumentation framework.
Research on dynamic argumentation includes work on the impact of a change operation [5,1], enforcement [2,6], resolution [10] and the relation with belief revision [8,13].
Most research on dynamic argumentation, e.g. [2,5,6], only considers the effect ofchanges in the abstract framework, such as adding an argument. This approach does nottake into account dependencies between arguments. For example, adding a new argument
A often introduces more arguments having A as a subargument. Conversely, we study theeffect of changes in the underlying structured argumentation framework.
None of the existing work in structured dynamic argumentation specifically studies
stability. We briefly discuss some related research. [10] study resolutions in structured
argumentation: they show how the acceptability of arguments changes due to a changeof preferences in the underlying structured argumentation framework. Another related
study [13] shows how the acceptability of a specific set of arguments can be altered bya minimal number of changes on the premises and/or rules in an argumentation framework, relating dynamic argumentation to belief revision. However, they do not focus on a
specific task, such as stability; they do not consider computational complexity or provide
an efficient (approximation) algorithm. One of the few papers that take computational
complexity into account is [1]. The authors propose an efficient algorithm to minimise
re-computations after a change in a DeLP program. However, whereas they study acceptability status after a specific change, we study the status after any possible change in the
structured argumentation framework.
Finally, [9] apply a similar strategy to ours for efficiently determining the acceptability status of literals: they create a graph representing (the relation between) literals
and rules and incrementally label its nodes and edges. However, they only determine thecurrent acceptability status without considering changes.

6. Discussion and conclusion
We have studied the task of detecting stability: given a specific structured argumentation
setup, based on a variation on ASPIC+ , can adding information result in a changed acceptability status of a specific literal? We have shown that the task is CoNP-hard. ThisJuly 2020is problematic in practical applications, such as identifying the termination criterion inhuman-computer inquiry dialogue. We proposed an algorithm for estimating stability
that improves on the algorithm in [14]. We have shown that the refined algorithm is soundand runs in polynomial time. Thanks to these properties, the algorithm has been taken
into use as part of an agent handling intake of fraud reports at the Dutch National Police– we provide an English demo that also visualises the agent’s stability component.
There are examples of argumentation setups for which the algorithm does not detectthat a literal is stable; in our application, this can result in the agent asking unnecessary
questions. This issue could be resolved by a further refinement of the algorithm, whichlists the knowledge bases K0 of all future setups and checks that each K0 is consistent.
However, such an algorithm would have exponential time complexity.
In future work, we plan to extend the argumentation framework and the allowed
updates. Furthermore, our demo applies a heuristic to select relevant questions; we plan
to specify this formally. Finally, we will extensively evaluate the fraud intake agent.

References
[1]

[2]

[3]
[4]
[5]

[6]
[7]
[8]
[9]

[10]
[11]
[12]
[13]
[14]

Gianvincenzo Alfano, Sergio Greco, Francesco Parisi, Gerardo Ignacio Simari, and Guillermo Ricardo
Simari. An incremental approach to structured argumentation over dynamic knowledge bases. In Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning, pages 78–87, 2018.
Ringo Baumann and Gerhard Brewka. Expanding argumentation frameworks: Enforcing and monotonicity results. In Proceedings of the 2010 conference on Computational Models of Argument: Proceedings of COMMA 2010, pages 75–86. IOS Press, 2010.
Floris Bex, Joeri Peters, and Bas Testerink. AI for online criminal complaints: From natural dialogues
to structured scenarios. In Artificial Intelligence for Justice Workshop (ECAI 2016), pages 22–29, 2016.
Elizabeth Black and Anthony Hunter. An inquiry dialogue system. Autonomous Agents and Multiagent
Systems, 19(2):173–209, 2009.
Claudette Cayrol, Florence Dupin de Saint-Cyr, and Marie-Christine Lagasquie-Schiex. Change inabstract argumentation frameworks: Adding an argument. Journal of Artificial Intelligence Research,
38:49–84, 2010.
Sylvie Doutre and Jean-Guy Mailly. Constraints and changes: A survey of abstract argumentation dynamics. Argument and Computation, 9:223–248, 11 2018.
Phan Minh Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelligence, 77:321–357, 1995.
Marcelo Alejandro Falappa, Gabriele Kern-Isberner, and Guillermo Ricardo Simari. Belief revision andargumentation theory. Argumentation in Artificial Intelligence, pages 341–360, 2009.
Abdelraouf Hecham, Pierre Bisquert, and Madalina Croitoru. On a flexible representation for defeasible
reasoning variants. In Proceedings of the 17th International Conference on Autonomous Agents andMultiagent Systems, pages 1123–1131, 2018.
Sanjay Modgil and Henry Prakken. Resolutions in structured argumentation. In Proceedings of the 4thInternational Conference on Computational Models of Argument, pages 310–321, 2012.
Henry Prakken. An abstract framework for argumentation with structured arguments. Argument &Computation, 1(2):93–124, 2010.
Marijn Schraagen and Floris Bex. Extraction of semantic relations in noisy user-generated law enforcement data. In 13th International Conference on Semantic Computing, pages 79–86. IEEE, 2019.
Mark Snaith and Chris Reed. Argument revision. Journal of Logic and Computation, 27(7):2089–2134,
2016.
Bas Testerink, Daphne Odekerken, and Floris Bex. A method for efficient argument-based inquiry. In
Proceedings of the 13th International Conference on Flexible Query Answering Systems, 2019.