An Efficient Algorithm for Skeptical Preferred Acceptance in Dynamic Argumentation Frameworks

1 Introduction

Abstract argumentation has emerged as one of the major fields in Artificial Intelligence [Bench-Capon and Dunne, 2007; Rahwan and Simari, 2009]. In particular, abstract argumentation frameworks (AFs) [Dung, 1995] are a simple, yet powerful formalism for modelling disputes between two or more agents. The formal meaning of an AF is given in terms of argumentation semantics, which intuitively tell us the sets of arguments (called extensions) that can collectively be used to support a point of view in a discussion.

Although the idea underlying AFs is very simple and intuitive, most of the argumentation semantics proposed so far suffer from a high computational complexity [Dunne and Wooldridge, 2009; Dunne, 2009; Kr¨oll et al., 2017]. In particular, skeptical reasoning under the well-known preferred semantics-one of the most popular semantics [Caminada et al., 2016]-is in the second level of the polynomial hierarchy. Efficient algorithms for AFs have been deeply investigated in the literature, as witnessed by the International Competition on Computational Models of Argumentation (ICCMA) 1 . One of the more challenging tasks of ICCMA is deciding the skeptical preferred acceptance of a given argument (goal).

∗Contact Author

However, ICCMA competition as well as most research have focused on 'static' frameworks, whereas in practice AFs are dynamic systems [Baumann and Brewka, 2010; Baumann, 2011; Falappa et al., 2011; Oikarinen and Woltran, 2011; Charwat et al., 2015]. In fact, an AF often represents a temporary situation, as new arguments and attacks can be added/retracted to take into account new available knowledge. For instance, for disputes among users of online social networks [K¨okciyan et al., 2017], arguments/attacks are continuously added/retracted by users to express their point of view in response to the last moves made by the adversaries.

Recently, the definition of evaluation algorithms taking into account such dynamic aspects has received an increasing attention, as in these situations incremental computation techniques could greatly improve performance [Liao et al., 2011; Baroni et al., 2014; Alfano et al., 2017; Bistarelli et al., 2018a]. In this regard, a new track focusing on solvers processing dynamic AFs have been recently proposed for the next edition of ICCMA competition [Bistarelli et al., 2018b].

In this paper, we propose an algorithm for incrementally solving the following computational task: Given an AF A0, a goal argument g whose skeptical preferred acceptance w.r.t. A0 is known, and an update u, decide whether g is skeptical preferred accepted w.r.t. the updated AF u(A0), that is, decide if g belongs to every preferred extension of u(A0). Thus, we explore how to efficiently and incrementally solve the ICCMA computational task DS-pr [Thimm and Villata, 2017].

Contributions. We make the following contributions:

• Given an update and an argument, we identify a set of arguments, called supporting set, which contains all the arguments whose acceptance status may change after the update and propagate up to the goal argument.
• Given the supporting set, we define the concept of context-based AF that allows us to compute the skeptical preferred acceptance of an argument by focusing on a smaller AF containing the supporting set as well as additional arguments and attacks representing auxiliary information on the external context.

1 http://argumentationcompetition.org

• We introduce SPA, an incremental algorithm for computing the Skeptical Preferred Acceptance of a goal within a dynamic AF. It enables the computation on context-based AFs by means of (non-incremental) stateof-the-art AF solvers. Our solution relies on incrementally maintaining the ideal extension of the given AF. However, to show the relevance of using the ideal extension, we also consider a simpler version of our algorithm (called SPA-base) which does not consider the information provided by the ideal extension.
• We perform a thorough experimental analysis showing the effectiveness of our approach, even in the case of sets of updates applied simultaneously. We compare both SPA and SPA-base with the solver that won the ICCMA'17 competition for the computational task DS-pr as well as between them. Both SPA and SPA-base significantly beat the computation from scratch, and SPA performs better than SPA-base on average.

To the best of our knowledge, this is the first paper addressing the problem of efficiently and incrementally computing skeptical acceptance for dynamic AFs.

2 Preliminaries

We assume the existence of a set Arg of arguments. An (abstract) argumentation framework [Dung, 1995] (AF) is a pair 〈A, S〉, where A ⊆ Arg is a set of arguments, and S ⊆ A×A is a binary relation over A whose elements are called attacks.

Example 1 (Running example). Figure 1(a) shows the graph of the AF AF0 = 〈A0,Σ0〉 where A0 = {a,b,c, . . . ,l} and Σ0 includes, among others, attacks (a,b), (b,a), and (c,d). ■

Given an AF 〈A,S〉 and arguments a,b ∈ A, we say that a attacks b iff (a,b) ∈ S, and that a set S ⊆ A attacks b iff there is a ∈ S attacking b. We use S+ = {b | ∃a ∈ S : (a, b) ∈ S} to denote the set of arguments attacked by S.

Moreover, we say that S ⊆ A defends a iff ∀b ∈ A such that b attacks a, there is c ∈ S such that c attacks b.

A set S ⊆ A of arguments is said to be: (i) conflict-free if there are no a,b ∈ S such that a attacks b; (ii) admissible if it is conflict-free and it defends all its arguments.

An argumentation semantics specifies the criteria for identifying a set of arguments that can be considered "reasonable" together, called extension. A preferred extension of an AF A is a maximal (w.r.t. ⊆) admissible set of A . The ideal extension of A is the biggest (w.r.t. ⊆) admissible set of A which is contained in every preferred extension of A .

It is well-known that every AF admits exactly one ideal extension which is contained in the intersection of the preferred extensions, which are at least one [Dung et al., 2007].

Example 2. The preferred extensions of AF0 are Epr = {a,d,f,h,j,l} and E′pr = {b,d,f,h,k}, while the ideal extension of AF0 is Eid = {d,f,h}. ■

Given an AF A = 〈A,S〉 and an argument g ∈ A, we say that g is skeptically accepted w.r.t. A under the preferred semantics iff for each preferred extension E of A it holds that g ∈ E. In the following, we use SAA (g) to denote the skeptical acceptance (either true or false) of g w.r.t. AF A .

Example 3. For AF AF0 of our running example, we have that the arguments skeptically accepted are d, f, and h. Thus, SAAF0 (d) is true, and so is for SAAF0 (f) and SAAF0 (h), while for any other argument x, SAAF0 (x) =false. ■

Fact 1. Let A be an AF, E the ideal extension of A , and g an argument of A . If g ∈ E then SAA (g) =true. On the other hand, if g ∈ E + then SAA (g) =false.

2.1 Updates

Performing an update on an AF A0 means modifying it into an AF A by adding or removing arguments or attacks.

We use +(a,b), with a,b ∈ A0 and (a,b) ̸∈ S0, (resp. -(a,b), with (a,b) ∈ S0) to denote the addition (resp. deletion) of an attack (a,b), and u(A0) to denote the application of update u = ±(a, b) to AF A0 (where ± means either + or -). Applying an update u to an AF A0 implies that the extensions prescribed by a given semantics, as well as the set of arguments that are skeptical accepted, may change.

Example 4. Continuing with our running example, let u = +(h, d). The ideal extension of u(AF0) is {f, h}, while the preferred extensions are {a, f, h, j, l} and {b, f, h, k}. Thus, only f and h are skeptically accepted w.r.t. u(AF0). ■

As for the addition (resp. deletion) of a set of isolated arguments (i.e., arguments not adjacent to any other argument in the graph), it is easy to see that if A is obtained from A0 through the addition (resp. deletion) of a set S of isolated arguments, then every argument in S is trivially skeptically accepted (resp., not accepted) w.r.t. A . Indeed, if E0 is an extension for A0, then E = E0 ∪S (resp. E = E0 \S) is an extension for A containing every (resp., none) argument in S. Of course, if arguments in S are not isolated, for addition we can first add isolated arguments and then add attacks involving these arguments, while for deletion we can first delete all attacks involving arguments in S. Thus we do not consider these kinds of updates in the following, and focus on the addition and deletions of attacks.

2.2 Notation for reachability and other useful concepts

Given an AF A = 〈A,S〉 and an argument x, we use Reach A (x) to denote the set of arguments that are reachable from x in the AF A . Moreover, we use Reach-1 A (x) to denote the set of arguments from which x is reachable in A . For instance, for the AF AF0 = 〈A0, Σ0〉 of our running example (see Figure 1(a)), we have that ReachAF0 (d)= {d,c,g,h,i}, and Reach-1 AF0 (h) = A0 \ {i, j, k, l}. We write Reach A (x) = /0 and Reach-1 A (x) = /0 if x is not in A .

We use H(A ,u) to denote the larger AF between A and u(A ), that is, H(A ,u) is (i) the updated AF u(A ) if u is an addition update (it includes the attack added through u), (ii) the original AF A if u is a deletion (the removed attack is still considered in H(A,u)). For instance, if u = +(h,d) then H(AF0, u) = 〈A0, Σ0 ∪ {(h, d)}〉, while H(AF0, u) = AF0 for any deletion update u.

We use P(S,A ) to denote the restriction of AF A = 〈A, S〉 to a subset S ⊆ A of its arguments [Baroni et al., 2005], that is P(S,A ) = 〈S, S∩(S×S)〉. For instance, if S = {c, d} then P(S, AF0) = 〈{c, d}, {(c, d), (d, c)}〉.

Finally, given A1 = 〈A1, S1〉 and A2 = 〈A2, S2〉, we denote as A1 ⊔A2 = 〈A1 ∪A2,S1 ∪S2〉 the union of the two AFs.

3 Supporting Set

In this section, we introduce the novel concept of supporting set which intuitively consists of the set of arguments that needs to be taken into account in order to determine the skeptical acceptance of an argument of interest after performing an update. We provide a parametric definition of supporting set that will enable the characterization of different portions of a given AF, called context-based AFs, that will be used for two different purposes: (i) recompute the skeptical acceptance of a goal w.r.t. the updated AF, and (ii) recompute the ideal extension of the updated AF.

Before defining the supporting set, we introduce the auxiliary notion of steadiness of an argument. Given an AF A = 〈A,S〉, the ideal extension E of A , and an update u = ±(a, b), we first define E(u) as the subset of E consisting of the arguments which are not reachable from b in A , i.e., E(u) = {z | z ∈ E, z ̸∈ Reach A (b)}. Intuitively, the acceptance status of the arguments in E(u) is not affected by u as they are not reachable from it. Then, the set of steady arguments for u = ±(a, b) w.r.t. A is defined as StdA (u) = (E(u))+ \ {b}, i.e., the arguments attacked by E(u) in A and that will be still attacked by E(u) in u(A ). Argument b is not included in StdA (u) as it may be no longer attacked by a ∈ E(u) after performing u = -(a,b); however, it will be considered for positive updates in Definition 1. For the AF AF0 of our running example, where Eid = {d,f,h}, if u =+(h,d) then Eid (u) = {f} and StdAF0 (u) = {e, g} ⊆ E + id = {c,e,g,i}.

Thus, if an argument is steady for update u w.r.t. AF A then its acceptance status does not depend on u, though it is reachable from an argument of u. Steady arguments limit the portion of the AF to be examined to define the supporting set. Definition 1 (Supporting set). Let A = 〈A,S〉 be an AF, u = ±(a,b) an update, E the ideal extension of A , and g an argument in A. Let

Let n be the natural number such that Supn(u,A ,E,g) = Supn+1(u,A ,E,g). The supporting set Sup(u,A ,E,g) is:

where G=P(Supn(u,A ,E,g),H(A ,u)) is the restriction of H(A ,u) to Supn(u,A ,E,g).

Finally, when g is not specified, the supporting set, denoted as Sup(u,A ,E,⋆), is defined as Sup(u,A ,E,g) except that all the checks concerning Reach-1 are omitted.

Intuitively, Sup(u,A ,E,g) consists of the arguments whose status may change after performing an update u and such that their change can imply a change of the status of g.

The supporting set is iteratively defined by n+1 steps (n ≤ |A|), each of them consisting of the addition of at least a non-steady argument attacked by the set built at the previous step and allowing to reach the goal g (if specified). More in detail, Sup(u,A ,E,g) for u = ±(a,b) and g consists of the arguments that (i) can be reached from b without using any steady argument y; and (ii) allow to reach g in H(A ,u) by using only the arguments in Supn(u,A ,E,g). In fact, Equation (1) entails that an argument of Supn(u,A , E, g) will be in Sup(u,A ,E,g) only if it can reach g in the restriction of H(A ,u) to Supn(u,A ,E,g)-the other arguments in Supn(u,A ,E,g) are not needed to determine the acceptance status of g, and thus they are pruned by Equation (1).

When no argument g is specified, the set Sup(u,A ,E,⋆) is built by ignoring condition (ii) above. It is easy to see that, for any argument g, Sup(u,A , E, g) ⊆ Sup(u,A , E, ⋆) ⊆ Reach A (b), where b is the argument in the update u = ±(a, b). Moreover, Sup(u,A , E, g) may be empty even if g ∈ Reach A (b). Finally, if Sup(u,A ,E,g) ̸= /0 then the arguments of at least one path from b to g belong to Sup(u,A ,E,g).

Example 5 (Supporting set for u = +(h,d)). For the goal c, we have that Sup0(u,AF0,Eid,c) = {d}, Sup1(u,AF0,Eid,c) = {c,d}, and Sup2(u,AF0,Eid,c) = {c,d} (the latter does not contain g since g ∈ StdAF0 (u)). Thus, Sup(u,AF0,Eid,c) = {c,d} as both c and d allow to reach c in the restriction of the updated AF to {c, d}. Reasoning analogously, we have that Sup(u, AF0, Eid , ⋆) = {c, d}.

Consider now what happens for the goal h. Again Sup0(u,AF0,Eid,h) = {d}, and Sup1(u,AF0,Eid,h) = Sup2(u,AF0,Eid,h) = {c,d}. However, Sup(u,AF0,Eid,h) = /0 as {c,d}∩Reach-1 G (h) = /0, where G=P({c,d},u(AF0)). Also for the goal a, we have that Sup(u,AF0,Eid,a) = /0. ■

Theorem 1. Let A0 = 〈A0,S0〉 be an AF, E0 the ideal extension of A0, u =±(a,b) an update, A = u(A0) the updated AF, and x an argument in A0. Therefore, if Sup(u,A0,E0, x) = /0 then SAA (x) = SAA0 (x).

Example 6. Continuing with Example 5, since Sup(u,AF0,Eid,h) = /0 we can conclude that SAu(AF0)(h) = SAAF0 (h) =true. Similarly, since Sup(u,AF0,Eid,a) = /0 then SAu(AF0)(a) = SAAF0 (a) =false. ■

4 Context-Based Argumentation Frameworks

The supporting set has been used so far to determine whether the status of the goal does not need to be recomputed. In this section, starting from the supporting set, we define a restriction of the AF which will be used to compute the status of the goal after an update. More specifically, given the supporting set Sup(u,A ,E,g) (resp. Sup(u,A ,E,⋆)), we define the context-based AF CBAF(u,A ,E,g) (resp.

CBAF(u,A ,E,⋆)). Moreover, while CBAF(u,A ,E,⋆) will be used to incrementally compute the ideal extension of the updated AF (with the aim of checking if one of the conditions of Fact 1 holds), CBAF(u,A ,E,g) will be used to compute the skeptical acceptance SAu(A )(g) w.r.t. the updated AF.

Given an AF A = 〈A,S〉, its ideal extension E, and a set S ⊆ A, we use Nodes(A ,S,E) to denote the set of the nodes x ∈ A such that there are a node y ∈ S and a path from x to y in A such that all nodes in the path except y do not belong to E ∪E + (i.e., they are undecided, using the labelling terminology [Baroni et al., 2011]). Analogously, Edges(A ,S,E) is the set of edges (x,z) ∈ S such that there are y ∈ S and a path from x to y in A containing (x,z) such that all nodes in the path except y do not belong to E ∪E +. Essentially, if S is the supporting set, to determine the status of nodes in S we must also consider all nodes and attacks occurring in paths (of any length) ending in S whose nodes outside S are undecided. The motivation to also consider "undecided" paths is that some of the undecided arguments occurring in such paths could belong to (or be attacked by) some preferred extension and, therefore, together they could determine a change in the status of nodes in S.

Definition 2 (Context-Based AF). Let A = 〈A,S〉 be an AF, u =±(a,b), E the ideal extension of A , and x either an argument in A or the symbol ⋆. Let S = Sup(u,A ,E,x). The context-based AF of A w.r.t. u and x is CBAF(u,A ,E, x) = P(Sup(u, A , E, x), u(A )) ⊔ T1 ⊔ T2 where:

• T1 is the union of the AFs 〈{c,d},{(c,d)}〉 s.t. (c,d) is an attack of u(A ) and c ̸∈ Sup(u,A ,E,x), c ∈ E, and d ∈ Sup(u,A , E, x);
• T2 = 〈Nodes(u(A ),S,E), Edges(u(A ),S,E)〉.

Example 7. For AF0, where Eid = {d,f,h}, and u =+(h,d), we have seen in Example 5 that Sup(u,AF0,Eid,c) = {c,d}. Thus CBAF(u, AF0, Eid , c) = 〈{c, d}, {(c, d), (d, c)}〉 ⊔ T1 ⊔ T2 where: T1 = 〈{h,d},{(h,d)}〉 since h ∈ Eid does not belong to Sup(u,AF0,Eid,c) while d ∈ Sup(u,AF0,Eid,c); and T2 = 〈{a,b,c},{(a,b), (b,a),(a,c),(b,c)}〉 since there are paths starting from the undecided arguments a and b ({a, b} ̸⊆ (Eid ∪ E + id )) and ending in c ∈ Sup(u,AF0,Eid,c). Thus, CBAF(u,AF0,Eid,c) is the AF shown in Figure 1(b).

In general, CBAF(u,A ,E,g) is a subgraph of CBAF(u,A , E, ⋆) since Sup(u,A , E, g) ⊆ Sup(u,A , E, ⋆).

Theorem 2. Let A0 = 〈A0,S0〉 be an AF, E0 the ideal extension of A0, u =±(a,b) an update, A = u(A0) the updated AF, and x an argument in A0. Thus, if Sup(u,A0,E0,x) ̸= /0 then x is skeptically accepted w.r.t. A iff it is skeptically accepted w.r.t. the context-based AF CBAF(u,A0,E0, x).

Example 8. Continuing from Example 7, we can conclude that argument c is not skeptically accepted w.r.t. the updated AF u(AF0) because it is not skeptically accepted w.r.t. the context-based AF CBAF(u,AF0,Eid,c) of Figure 1(b) whose preferred extensions are {a,h} and {b,h} (only h is sceptically accepted w.r.t. the context-based AF). ■

Theorem 3. Let A0 = 〈A0,S0〉 be an AF, E0 the ideal extension of A0, u = ±(a,b) an update, and A = u(A0) the updated AF. Then, the ideal extension E of A is such that E = (E0 \Sup(u,A0,E0,⋆))∪E ′ , where E ′ is the ideal extension of the context-based AF CBAF(u,A0,E0,⋆).

Example 9. Continuing from Example 7, the ideal extension {f,h} of u(AF0) is equal to ({d,f,h}\{c,d})∪{h} where {h} is the ideal extension of CBAF(u,AF0,Eid,⋆). ■

5 Incremental Computation

The results of Theorems 1 and 2, along with those of Theorem 3 and Fact 1, allow us to define SPA (see Algorithm 1) to decide the skeptical acceptance of a goal g w.r.t. an AF A0 updated by u = ±(a,b). Given the initial skeptical acceptance SAA0 (g) of g and the ideal extension E0 of A0, both SAu(A0)(g) and the ideal extension E of the updated AF u(A0) are incrementally computed, thus enabling consecutive invocations of the algorithm to perform sequences of updates.

Algorithm SPA works as follows. First, the supporting set S⋆ = Sup(u,A0, E0, ⋆) is computed at Line 1, and using Theorem 3 the ideal extension E of the updated AF is computed by invoking an external solver ID-Solver(Aid), computing the ideal extension of the context-based AF CBAF(u,A0,E0,⋆) (Line 3). Then, using Fact 1, if g belongs to E, then g is skeptically accepted and the algorithm returns true along with the ideal extension of the updated AF (Line 5). Similarly, if g belongs to the set of arguments attacked by an argument in E, then g is not skeptically accepted and the algorithm returns false along with E (Line 7). Otherwise, the set Sg = Sup(u,A0,E0,g) is built (it can be efficiently done by starting from S⋆), and it is checked if it is empty. If this is the case, using Theorem 1, we can conclude that the acceptance status of g does not change after the update (Line 10). Otherwise, the context-based AF is built at Line 11 and, using Theorem 2, the skeptical acceptance of g is recomputed by invoking an external solver SA-Solver(Asa, g) which tells us if g is skeptically accepted w.r.t. the context-based AF CBAF(u,A0,E0,g) (Line 12).

Theorem 4. If ID-Solver and SA-Solver are sound and complete, for any goal g Algorithm 1 computes SAu(A0)(g) w.r.t. the updated AF u(A0) and the ideal extension of u(A0).

SPA-base: A version of SPA not using the ideal extension. SPA-base is obtained fromSPA by skipping lines 17 of Algorithm 1 and assuming E0 = /0 at lines 8 and 11 to compute Sg and Asa respectively. Also, no ideal extension is returned (i.e., E =⊥). Notice that, similarly to SPA-base, SPA does not use the information provided by the initial ideal extension when E0 = /0, though SPA always incrementally computes the ideal extension of the updated AF.

Multiple Updates

The application of a set U of updates can be reduced to performing a single attack update as follows. Let A = 〈A,S〉 be an AF, and

• S+ ={(a1,b1), ...,(an,bn)}⊆ (A×A)\S, and
• S- ={(a′1 ,b′1 ), ...,(a′m,b′m)}⊆S

such that S+ ∩ S- = /0 be two sets of attacks. Let U = {+(ai,bi) |(ai,bi) ∈S+}∪{-(aj,bj) |(aj,bj) ∈S-} be a set of updates. We define A U = 〈A U , S U 〉 where:

Algorithm 1 SPA(A0, g, SAA0 (g), u, E0)

Input: AF A0 = 〈A0,S0〉, argument g ∈A0, skeptical acceptance SAA0 (g) of g w.r.t. A0, update u =±(a,b), ideal extension E0 of A0. Output: skeptical acceptance SAu(A0)(g) of g w.r.t. u(A0), ideal extension E of u(A0). 1: Let S⋆ =Sup(u,A0,E0,⋆) 2: Let Aid =CBAF(u,A0,E0,⋆) 3: Let E = (E0 \S⋆)∪ID-Solver(Aid) 4: if g ∈E then 5: return 〈true, E〉 6: if g ∈E + then 7: return 〈false, E〉 8: Let Sg =Sup(u,A0,E0,g) 9: if Sg is empty then 10: return 〈SAA0 (g),E〉 11: Let Asa =CBAF(u,A0,E0,g) 12: return 〈SA-Solver(Asa,g), E〉

• A U =A ∪ {xi,yi | +(ai,bi) ∈U} ∪{x′j ,y′j | -(aj,bj) ∈ U} ∪{v,w,w′}, where all xi,yi, x′j ,y′j , w, w′ , and v are new arguments not occurring in A, and
• S U =(S\S-)∪{(ai,xi),(xi,yi),(yi,bi)| +(ai,bi)∈U}∪ {(aj,x′j ),(x′j ,y′j ),(y′j ,bj) | -(aj,bj) ∈U}∪{(w,yi) | + (ai,bi) ∈U}∪{(w′ ,y′j ) | -(aj,bj) ∈U} ∪{(w,w′ )}.

Proposition 1. Let A0 = 〈A0,S0〉 be an AF, and U a set of updates. Let A be the AF obtained from A0 by performing all updates inU on it. Then,

• E = E U ∩A0 is the ideal extension of A iff E U is the ideal extension of +(v,w)(A U ).
• Given an argument g of A0, SAA (g) = SA+(v,w)(A U ) (g).

6 Implementation and Experiments

We have implemented a C++ prototype and compared our incremental technique with ArgSemSAT [Cerutti et al., 2014], the solver that won the last ICCMA competition for the task DS-pr of determining the skeptical preferred acceptance.

Datasets and Methodology

We used benchmarks from the DS-pr track of ICCMA'17, that is, the dataset A2 consisting of 50 AFs with a number of arguments |A| ∈ [61, 20K] and a number of attacks |S| ∈ [97, 358K], and the dataset A3 consisting of 100 AFs with |A| ∈ [39, 100K] and |S| ∈ [72, 1.26M].

For each AF A0 in the dataset, we randomly selected an update u (or a set U of updates), and an argument g. Then, we computed SAu(A0)(g) by using 1) SPA, that is Algorithm 1 where ID-Solver is pyglaf [Alviano, 2017] and SA-Solver is ArgSemSAT; 2) SPA-base where only ArgSemSAT is used; and 3) ArgSemSAT (from scratch).

For AF A0, update u, and argument g, let tA and tB be the amount of time required by SPA and SPA-base, respectively, to compute SAu(A0)(g). Let tS be the time required by ArgSemSAT to compute SAu(A0)(g) from scratch. Then, the improvements of SPA and SPA-base over ArgSemSAT are defined as tS tA and tS tB , respectively. Thus, an improvement equal to x means that the incremental computation is x times faster than the computation from scratch.

In the figures, each data-point is the average of 10 runs, and solid lines are obtained by linear regression.

Experiment 1. Figure 2 reports the improvement (log scale) of SPA and SPA-base over ArgSemSAT on datasets A2 (LHS) and A3 (RHS) for single updates versus the size of the AFs, i.e., the number of attacks. Both SPA and SPAbase significantly outperform the computation from scratch, though the improvement decreases as the number of attacks increases. This behavior, which is in line with that of algorithms for computing argumentation semantics in the static setting [Liao, 2013; Liao and Huang, 2013; Alfano et al.,

2019], is analysed in Experiment 2. Considering the averages of the improvements, SPA and SPA-base turn out to be 5 and 4 orders of magnitude faster than ArgSemSAT, respectively. However, as this can be skewed by extremely large values of improvements (e.g. 10 6 ), we also considered the medians of improvements for SPA (32 on A2, 134 on A3) and SPA-base (27 on A2, 40 on A3) (see dashed line in Figure 2), which confirm the significance of the gain in efficiency. The experiments show that SPA is generally faster than SPA-base, except for a few AFs whose initial ideal extension is empty.

Experiment 2. We analysed the performances of SPA and SPA-base by varying the number of attacks and keeping almost constant either the number of arguments or the average degree (i.e., N. of attacks / N. of arguments). To this end, we selected as many AFs as possible from the two datasets having these properties. Figure 3 reports the improvement for AFs having (a) a number of arguments in [160,200] and (b) an average degree in [5,10]. Figure 3(a) shows that the performance gets worse when the increasing of the number of attacks is mainly due to the increasing of nodes' degree (in our experiment it varies from 1.5 to 40) and the AFs become more and more dense. Figure 3(b) shows that when the average degree does not change significantly and the increasing of the number of attacks is mainly caused by the increasing of the number of arguments (in our experiment it has more than doubled, from 2.4K to 5.4K), the improvement does not decrease. This can be explained by looking at the ratio r between the size of the context-based AF and that of the initial AF. Indeed, r increases from 4% to 95% when the average degree of the input AFs varies from 2 to 40 in Figure 3(a). On the other hand, for Figure 3(b), r is almost constant (i.e., in [60%,65%]). Thus, the performance gets worse when the ratio between the size of the context-based AF and that of the initial AF becomes very large because of the increasing density of the initial AFs.

Experiment 3. Figure 4 reports the improvement of SPA over ArgSemSAT on datasets A2 (LHS) and A3 (RHS) for 10 and 100 updates performed simultaneously. To preserve the structure of the AFs in the datasets, we changed at most 1% (resp., 10%) of the number of attacks for the AFs of A2 (resp., A3), that is, we considered AFs whose size is greater than 1K. Figure 4 also reports the improvement for 1 update, as well as for 10 and 100 updates applied sequentially, i.e., one after another (see dashed lines). The results show that SPA remains faster than the competitor even when 10 or 100 updates are performed simultaneously. Moreover, despite the overhead of the construction given before Proposition 1, applying updates simultaneously is faster than applying them sequentially.

7 Conclusions and FutureWork

There has been an extensive body of work on managing changes in argumentation (a recent survey can be found in [Doutre and Mailly, 2018]). Besides the works cited in the introduction, other significant efforts coping with dynamics aspects of AFs include [Baroni et al., 2005; Boella et al., 2009; Cayrol et al., 2008; Amgoud and Vesic, 2012; Bisquert et al., 2013]. Similarly to what is done in this paper, some approaches focused on local computation in dynamic AFs [Liao et al., 2011; Baroni et al., 2014; Greco and Parisi, 2016a; 2016b; Alfano et al., 2017] but with the aim of recomputing extensions. To the best our knowledge, this is the first paper proposing an efficient technique for the incremental computation of skeptical acceptance in dynamic AFs.

We have proposed a new algorithm, called SPA, which incrementally computes the skeptical preferred acceptance by maintaining the ideal extension (that can be considered the best available short-cut to compute preferred extensions when it is known [Dunne et al., 2016]). For a better understanding of the relevance of computing the ideal extension, we have also considered its simpler variant SPA-base which does not rely on the ideal extension. Both algorithms outperform the computation from scratch, and SPA is generally faster than SPA-base. However, as the experiments showed, SPA may be slower than SPA-base when the initial ideal extension is empty. Thus, a first direction for future work is devising heuristics to take advantages of both algorithms.

Analogously to classical AF solvers, our approach allows us to determine the skeptical acceptance of a single argument. However, the definition of supporting set and context-based AF can be extended to sets of arguments-a way to do it is using the union of the supporting sets to compute the contextbased AF. As a further line for future work, we plan to extend our algorithm to take as input a set of arguments. In this direction, SPA always computes the ideal extension, which being contained in every preferred extension, already provides additional skeptical preferred arguments other than the goal.

Finally, we plan to extend our technique to other argumentation semantics. In this regard, we point out that our technique can be used as it is for skeptical acceptance under the semi-stable semantics, but a deeper investigation is needed for extending the technique to deal with the stable semantics.