Robustness in Single-Audience Value-based Abstract Argumentation: Complexity Results

1 Introduction

The well-known Abstract Argumentation Framework (AAF) [Dung, 1995], largely employed for reasoning over disputes and solving problems that can be translated into them [Alfano et al., 2024a; Fazzinga et al., 2022b; Fazzinga et al., 2022a; Fazzinga et al., 2021b] has been extended in a number of ways. Specifically, several efforts have been made in the direction of taking into account the 'strength' of the arguments of the dispute. In particular, in Preference-based Argumentation Framework (PAF) [Amgoud and Cayrol, 2002], the fact that some arguments are perceived as stronger than others by the audience to which the arguments are addressed is encoded with a set of preferences, whose effect on the reasoning is the deactivation of any attack where the attacked is preferred to the attacker. Then, in (single-Audience) Value-based Argumentation Frameworks (AVAFs) [Bench-Capon, 2003], the difference in strength between the arguments is modeled as a consequence of the fact that the arguments may promote different social values, and the audience has preferences between these social values, as illustrated in the following example.

∗Contact Author

Example 1 An analyst is reasoning on a dispute whose arguments promote the following social values: "Generosity (G)", "Fairness (F)", "Accountability (A)". The arguments are:

• a (promoting G): "John is unemployed, and he is not been searching for a job for some years. His family is very poor, so we should donate some money to him";
• b (promoting F): "Redistributing wealth without considering who contributed to its creation fosters laziness and leads to impoverishment. So, grant no compensation to people who made no effort to improve their circumstances";
• c (promoting A): "John did not allow us to verify his family's income, so it is not appropriate to make any decision based on the assumption that his family is poor".

Independently from the values promoted by the arguments, it is easy to detect, by looking into the meaning of the arguments, that a and b attack each other, and that c attacks a. So, by encoding the dispute in a classical AAF with the above arguments and attacks, the analyst would conclude that {b}, {c}, and {b, c} are admissible extensions, while {a} is not, and that c and b are accepted arguments, while a is not.

Now, the analyst wants to take into account the standpoint of a specific audience, whose perception of the existence of the attacks is implied not only by the meaning of the arguments, but also by the "strength" that the audience attributes to the arguments. So, the analyst turns the AAF into an AVAF, where the audience profile is described by the following preferences between values: G>F and G>A, where the meaning of X > Y is: "the audience will always consider any argument x promoting X stronger than any y promoting Y , and thus any attack from y to x ineffective".

Thus, in the AVAF obtained this way, the attacks from b to a and from c to a are inactive and are excluded from the reasoning, so the analyst will conclude that, from the standpoint of the audience, b is not an accepted argument, while a is, and {a}, {c} and {a, c} are admissible extensions.

Example 1 suggests the reason why AVAFs have proved effective in several scenarios, such as promotional campaigns and trials: they allow the analyst to simulate the subjective views of the people to which the arguments are addressed

(e.g. the target population, in the case of promotional campaigns, or the jury, in the case of trials) and then to reason on how the audience will perceive the status of the arguments.

However, the outcome of the reasoning performed over an AVAF could be affected by reliability issues, since:

1) the audience profile may not be accurate, as the beliefs and social convictions of the involved individuals are not always easy to predict; so, some preferences put in the audience profile by the analyst may be wrong and/or some preferences actually characterizing the audience may be missing;

2) even if, initially, the audience profile is accurately modeled, the audience may change their opinions over time and, therefore, the importance they attribute to values.

A possible way for assessing the reliability of the result of the reasoning is studying its "robustness": once the status of a set of arguments (is it an extension or not?) or of a single argument (is it accepted or not?) has been determined over an AVAF, its "robustness degree" is the maximum number of changes to the audience profile that are tolerated, in the sense that no modification of the status would be observed if any set of changes of this cardinality were performed.

Intuitively, the higher the degree of robustness, the greater the reliability of the result of the reasoning: if many changes to the profile are required to alter the outcome, it means that, even if there were errors in defining the profile or changes occurred since it was defined, it is unlikely that such errors and changes would be numerous enough to affect the result.

Example 2 (continuing Example 1) There are tenmore arguments x1, · · · , x10, where: x10 attacks and is attacked by c; each xi promotes a distinguished value vi, and attacks and is attacked by a. Figure 1 (a) shows the AVAF modeling this situation, when the audience profile has not been defined yet, so all the attacks are active. Suppose that now the analyst models the audience profile as follows: F>G, A>G, A> v10 and, for each i ∈ [1..10], vi >G. Since all the attacks stemming from a and the attack from x10 to c are deactivated by the preferences, the active attacks become those in Figure 1(b).

Reasoning on this AVAF, the analyst (who adopts the admissible semantics) concludes that b and c are both (credulously) accepted. However, by looking into the robustness of the acceptance of b and c, an evident difference emerges: b's acceptance is way more robust that c's. In fact, making b unaccepted requires at least 23 changes to the set of preferences, while two changes suffice to make c unaccepted. The reason is that invalidating b's acceptance requires deactivating the attack (b, a), activating (a, b), and deactivating all the defenses against a; this can be done by deleting all the preferences except A> v10, and then adding the 'opposite' preferences G>F, G>A and G> vi, for each i ∈ [1..9] (note that, this way, G> v10 is implied). This means 12 deletions and 11 insertions of preferences, which yield the AVAF in Figure 1(c). On the other hand, simply inactivating the attack (c, x10) and activating (x10, c) makes c unaccepted, and this requires deleting A> v10 and adding v10 > A (that are 2 changes in total). It is easy to see that it is not possible to change the status of b and c with less than 23 and 2 insertions/deletions, respectively. Hence, the robustness degrees of b's and c's acceptance are 22 and 1, respectively.

Given this, based on the different robustness degrees, the analyst may conclude that, in light of the risk that the audience profile might contain inaccuracies, relying on the acceptance of b is much more cautious than on the acceptance of c.

Using the same reasoning, it is easy to see that both x10 and a are unaccepted in the AVAF in Figure 1(b), but these non-acceptance statuses have different robustness (0 for x10 and 12 for a): only one change to the profile (the deletion of A> v10) makes x10 accepted, while making a accepted requires at least 13 changes: deleting all the preferences but A > v10, and adding G>A. These different robustness degrees suggest to the analyst that, even if the audience turns out to be somewhat different from what was specified in the model, it is unlikely that the status of a returned by the AVAF would differ significantly from what is perceived by the real audience, because that would mean the real audience is much different from what was modeled. On the other hand, with x10, this risk is much more real.

The notion of robustness can be applied also to extensions and non-extensions: for instance, S1 = {c} and S2 = {b, x1, . . . , x9} are admissible extensions in the AVAF of Figure 1(b), and their robustness degrees are 1 and 19, respectively (deleting A > v10 and inserting v10 > A makes S1 a non-extension, while performing the 20 updates needed to invert the preference F > G and every vi > G, with i ∈ [1..9], makes S2 a non-extension).

The contribution of this paper is the introduction of a new paradigm for reasoning on the robustness of the status of (sets of) arguments, which is a relevant issue since, as shown in Example 2, it can effectively help assess the reliability of the outcome of the reasoning over AVAFs. In particular, we introduce the decision problems underlying the computation of the degree of robustness, and thoroughly investigate their computational complexity. The novelty of the contribution lies in the fact that robustness has never been studied in the literature of abstract argumentation with regard to audience profiling. In fact, it was addressed only in the case of standard AAFs (thus disregarding values and preferences): specifically, in [Rienstra et al., 2020], where the resilience of the acceptance status w.r.t. the addition/removal of attacks has been used as a principle for comparing different admissibility-based semantics;

in [Rapberger and Toni, 2024], in terms of the property of explanations of being still valid after changes of the argumentation graph; as well as, indirectly, in the framework of enforcement of extensions and of acceptability constraints [Doutre and Mailly, 2018].

2 Preliminaries

Abstract Argumentation Frameworks (AAFs). An abstract argumentation framework (AAF) is a pair F = ⟨A, D⟩, where A is a finite set of arguments and D ⊆ A × A is a binary relation, whose elements are called attacks. Given a set of arguments S and an argument a, we say that "S attacks a" if there is b in S such that b attacks a, and that "a attacks S" if there is b ∈ S such that a attacks b. We say that an argument a (resp., a set of arguments S) "defends b against c's attack" if c attacks b, while a (resp., S) attacks c, and that a is acceptable w.r.t. S if S defends a against every attack. The "argumentation graph" of F is the directed graph whose nodes and edges are the arguments and the attacks of F .

Several semantics for AAFs have been proposed to identify "reasonable" sets of arguments, called extensions [Dung, 1995]. A set S ⊆ A is an extension of type: conflict-free (cf) if there is no attack between its arguments; admissible (ad) if S is conflict-free and its arguments are acceptable w.r.t. S; stable (st) if S is conflict-free and S attacks every a ∈ A\S; complete (co) if S is admissible and contains all the arguments acceptable w.r.t. S; grounded (gr) if S is a minimal (w.r.t. ⊆) complete extension; preferred (pr) if S is a maximal (w.r.t. ⊆) complete extension. cf, ad, st, gr, co, pr will be referred to as Dungean semantics. Arguments belonging to at least one (resp., every) extension are said to be Credulously (Cr-) accepted (resp., Skeptically (Sk-) accepted). The fundamental problems supporting the reasoning over AAFs are the verification and the acceptance problems VERσ (F, S) and ACCσ (F, a, X), asking if S is an extension and if a is Xaccepted, with X ∈ {Cr, Sk}, respectively.

Preferences, Preference Relation, and Preference-based Argumentation Framework (PAF). A preference between two elements x1, x2 of a set X is an expression "x1 > x2", to be read as "x1 is preferred to x2". A (strict) preference relation on a set X is a partial, transitive, asymmetric, irreflexive relation P ⊂ X ×X. Each (x1, x2) ∈ P is interpreted as a preference x1 > x2. If (x1, x2) ̸∈ P , we write x1 ̸> x2.

A PAF [Amgoud and Cayrol, 2002] is a triplet PF = ⟨A,D, P⟩, where ⟨A,D⟩ is an AAF and P is a (strict) preference relation on A. The effect of preferences is the inactivation of any attack (a, b) where b > a. Thus, the extensions and the accepted arguments of PF = ⟨A,D, P⟩ are those of the "implied" AAF F = ⟨A, D′ ⟩, where D′ is the subset of D containing only its active attacks, i.e. the attacks (a, b) with b ̸> a.

Single-Audience Value-based Argumentation Framework (AVAF). AVAF [Bench-Capon, 2003] extends the traditional reasoning paradigm over AAF by taking into account the audience profile. This profile is a set of preferences on the set of social values involved in the dispute to be modeled, and implies a set of preferences on the arguments, so that reasoning on an AVAF reduces to reasoning over the PAF where the preference relation over the arguments is that implied by the preferences specified in the AVAF.

Formally, given a set of values V , an (audience) profile (or preference specification) π over V is a set of preferences of the form v1 > v2, with v1, v2 ∈ V . In graph terms, π is represented by the digraph, called preference graph, having V and {(v1, v2)|v1 > v2} as sets of nodes and arcs. We denote as π∗ the transitive closure of π. A profile π is said to be consistent iff it is acyclic, meaning that π∗ is a (strict) preference relation over V . For instance, the profile {v1 > v2, v2 > v3, v3 > v1} is not consistent: observe that its transitive closure is not a strict preference relation, since it contains the preferences v1 > v3 and v3 > v1 (thus violating the asymmetry).

An AVAF is a tuple VF = ⟨A, D, V, val, π⟩, where ⟨A, D⟩ is an AAF, V a set of values, π a consistent preference specification over V , and val : A→ V a total function associating arguments with values. The semantics of an AVAF VF = ⟨A,D, V, val, π⟩ is given by the PAF PF = ⟨A,D, P(π)⟩, where P(π) is the strict preference relation implied by π, i.e. P(π) = {(a, b)|(val(a) > val(b)) ∈ π∗ }. Thus, the extensions and the accepted arguments of VF are those of PF, or, equivalently, of the AAF implied by PF, that are called the PAF and the AAF "implied" by VF, respectively.

2.1 Further Notions and Notations

Given a preference specification π over a set of values V , we consider two primitive update operations over π: the insertion ins(v1 > v2) and the deletion del(v1 > v2), which inserts and removes the preference v1 > v2 into and from π, respectively. In turn, we call "preference update" any set U of primitive update operations, and define the application of U to π as U(π) = π ∪ {v1 > v2|ins(v1 > v2) ∈ U} \ {v1 > v2|del(v1 > v2) ∈ U}. In turn, we define the application of a preference update U to an AVAF VF = ⟨A, D, V, val, π⟩ as the AVAF U(VF) = ⟨A, D, V, val, U(π)⟩.

A preference update U over π is said to be consistent if U(π) is consistent. U is said to be "del-only" (resp., "insonly") if it contains only deletions (resp., insertions). Obviously, a del-only preference update over a consistent profile is always consistent.

3 Problem Statement: Reasoning on the Robustness over AVAFs

We now introduce the fundamental problems that support the analysis on the "robustness" of the outcome of the reasoning over an AVAF. We address the case where an AVAF has been already defined, and the analyst wants to investigate the consequences of some modifications of the audience profile, due to changes in mind of the audience or to the need of fixing inaccuracies w.r.t. the actual subjective view of the audience. Herein, for a set of arguments S and an argument a, "robustness" means the number of changes to the audience profile that have no impact on the status of S and a, in terms of being or not an extension and accepted, respectively.

Definition 1 (k-robustness problems) REσ (VF, S, k) (resp., RNEσ (VF, S, k)) is the problem of checking if the set S, that is (resp., is not) an extension of the AVAF VF under σ, is still (resp., is still not) an extension of U(VF) under σ for every consistent preference update U over π with |U| ≤ k.

RAσ (VF, a,X, k) (resp., RNAσ (VF, a,X, k)), where X ∈ {Cr, Sk}, is the problem of checking if the argument a, that is (resp., is not) X-accepted for the AVAF VF under σ, is still (resp., is still not) X-accepted for U(VF) under σ for every consistent preference update U over π with |U| ≤ k.

The suffixes -IO and -DO will denote the variants of the robustness problems restricted to ins-only and del-only preference updates. Restricting to ins-only (resp., del-only) updates means assessing the robustness in the case where the audience profile may be strictly more specific (resp., strictly more general) than what initially specified by the analyst.

Remark 1: on the encoding of the audience. It is worth noting that reasoning on the robustness over AVAFs has required a modification of the definition of AVAF introduced in [Bench-Capon, 2003], where the subjective view of the audience is encoded in terms of a (strict) preference relation, while, in our framework, it is encoded in terms of a (consistent) set of preferences. In fact, the preference relation in [Bench-Capon, 2003] is the transitive closure of the preference specification occurring in "our" AVAF. The point is that these two encodings are equally suitable when no change of preference occurs, as in [Bench-Capon, 2003]. But the encoding based on a set of preferences is more suitable for measuring the extents of the modifications of what is believed about the subjective view of the audience. The reason is that two sets of preferences π1, π2 may correspond to the same preference relation (that is, π∗ 1 and π∗ 2 coincide), but they may not coincide. For instance, consider π1 = {v1 > v2, v2 > v3} and π2 = {v1 > v2, v2 > v3, v1 > v3}. Since preferences are implied by transitivity, we have π∗ 1 = π∗ 2 , but the fact that v1 > v3 occurs in π2 means that the analyst who models the audience with π2 explicitly believes that the audience prefers value v1 to v3. Thus, when counting the changes to the profile of the audience needed to remove v1 > v3, if π1 is adopted, we obtain that only one deletion is necessary (either del(v1 > v2) or del(v2 > v3), since this way v1 > v3 is no more implied), while if π2 is adopted, at least two deletions are needed, since also del(v1, v3) should be performed. And this difference reflects the fact that in π2 the preference v1 > v3 is explicitly stated, while in π1 it is a consequence of what is believed. Given this, if the audience profile were encoded in terms of the preference relation, it would be impos-

sible to distinguish the scenarios corresponding to π1 and π2.

Remark 2: on assuming the initial status known. In Definition 1, the "initial" status of S and a is assumed known. In fact, from a practical perspective, it is natural that the analyst starts to reason on the robustness of the status of (a set of) arguments after the initial status has been determined. From a technical perspective, this has no impact on the importance of our results on the computational complexity presented in the following section. On the one hand, Definition 1 allows us to "isolate" the source of complexity related to assessing the initial status from the complexity of reasoning on the effects of changing the audience profile. On the other hand, the computational complexity of the variant of the k-robustness problems where the initial status is not known can be obtained

Skeptical acceptance

by properly combining the complexities of the standard verification and acceptance problems VER and ACC with those of the k-robustness problems studied in this paper.

4 The Complexity of the k-Robustness Problems

We here present the main technical contribution of this paper, that is the characterization of the computational complexity of the k-robustness problems. The results are summarized in Table 1, which also reports the complexity of the classical verification and acceptance problems over AAFs, PAFs, and AVAFs (obviously, the semantics cf is not considered for the acceptance and the related robustness problems, and ad is not considered for the skeptical acceptance and the related robustness problems, since these cases are trivial).

We start with a preliminary result: verifying if a specific attack can be deactivated by a certain number of preference deletions is in P. This result is used for proving the tractability of the polynomial-time cases of the k-robustness problems.

Lemma 1 The problem SINGLEATTACKACTIVATIONDO(VF, (a, b), k), where VF = ⟨A, D, V, val, π⟩ is an AVAF, (a, b) an attack in D, k ≥ 0 an integer, of checking if there is a consistent del-only preference update U with |U| ≤ k such that the attack (a, b) is active in U(VF) is in P.

Lemma 1 is implied by the fact that the deactivation of an attack (a, b) via del-only updates is equivalent to making, in the preference graph, the node val(b) unreachable from val(a) via edge removals. In turn, this check is a particular instance of the well-known DIRECTEDCUT problem: "Given a directed graph G and a set of pairs of nodes T , check if there are no more than k edges whose removal from G makes, for every pair (n1, n2) in T , n2 unreachable from n1". Now, although DIRECTEDCUT is NP-hard in general, it is in P if |T | = 1 (see Theorem 3.1 in [Bang-Jensen and Yeo, 2014]). This also explains why Lemma 1 cannot be extended to the deactivation of multiple attacks.

Theorem 1 The computational complexity of RE, RNE, RA and RNA are reported in Table 1.

Proof. Memberships: cases beyond P. The memberships in classes beyond P can be all proved with a similar scheme. As for RE, RNE, credulous RA and skeptical RNA, the scheme for the complement of these problems is: guess a preference update U with |U| ≤ k and then check if S is an extension (for RE and RNE) or a is accepted (for RA and or RNA) in U(VF). An exception is the case RE under σ = pr: the guess must also contain a set of arguments S′ ⊃ S, and the check consists in verifying whether S and S′ are admissible extensions. In every case, the final complexity class is coNPC , where C is the complexity class of the verification or acceptance problem over AVAFs solved in the checking phase.

As for credulous RNA and skeptical RA, the scheme for the complement of these problems is: guess a preference update U with |U| ≤ k and a set of arguments S such that a ̸∈ S; then, check if S is an extension of U(VF) (under σ = pr the verification is done under the admissible semantics). Hence, the final complexity class is coNPC , where C is the class characterizing the verification problem over AVAFs solved in the check.

Memberships: trivial cases. RNE-DO (resp., RE-IO) is trivial since del-only (resp., ins-only) updates cannot deactivate (resp., activate) attacks, thus they cannot make conflict-free (resp., conflicting) a set of arguments that is conflicting (resp., conflict-free).

Memberships: polynomial-time cases. RE-DOσ (VF, S, k) is in P under σ ∈ {cf, ad, st}, where VF = ⟨A, D, V, val, π⟩.

Under σ = cf, let DS = D∩S×S be the set of (inactive) attacks between nodes in S. If DS = ∅, the answer to REDOσ (VF, S, k) is trivially TRUE, as no attack can be created (implying conflicts inside S) by modifying the preferences. Otherwise, if DS ̸= ∅, in order to make S non conflict-free it is necessary and sufficient to make at least one attack in DS active. Therefore, RE-DOσ (VF, S, k) is TRUE iff there is at least one attack α in Ds such that SINGLEATTACKACTIVATION(VF, αi, k) is TRUE. Performing this check requires solving at most |DS| instances of SINGLEATTACKACTIVATION, so Lemma 1 implies that RE-DO is in P.

Under σ = st, RE-DO coincides with the case σ = cf, as preference deletions cannot inactivate attacks from S against nodes outside S (so del-only updates can invalidate a stable extension only by making it conflicting).

Under σ = ad, solving RE-DO means deciding if either Property 1: "there is a del-only preference update U with |U| ≤ k making S non conflict-free", or Property 2: "there is a del-only preference update U with |U| ≤ k making S undefended against attacks from outside S", or both. Now, checking Property 1 is in P, as it means solving RE-DOσ (VF, S, k)

under σ = cf. We show that also checking Property 2 is in P, thus concluding the proof. Since S is an extension of VF, every attack α = (a, s) towards S with a ̸∈ S satisfies one of the two conditions:

• C1 : α is inactive and no attack from S to a is active, or

C2 : α is either active or inactive, and at least one attack from S to a is active.

In fact, the combination "α is active and no attack from S to a is active" is not possible, as S is an extension in VF. Let D1 and D2 be the disjoint subsets of D consisting of the attacks α satisfying C1 and C2, respectively.

Applying any del-only update over VF keeps S defended against the attacks in D2, since removing preferences cannot inactivate active attacks from S. So, checking Property 2 means checking if there is a del-only preference update U with |U| ≤ k such that, for at least one attack α = (a, s) in D1: i. U makes α active (i.e. (val(s) > val(a)) ̸∈ U(π)∗ ), and ii. U leaves S undefended against α. We now prove that the existence of a preference update U with |U| ≤ k satisfying i. implies the existence of a preference update U ′ with |U ′ | ≤ k satisfying both i. and ii.. By contradiction, if this were false, every del-only preference update U with |U| ≤ k activating α would also activate some attack from some b ∈ S to a; thus, some edges removed by U from the preference graph encoding π∗ to make val(a) unreachable from val(s) would also make val(b) unreachable from val(a). This means that, in the preference graph encoding π∗ , there is at least a path psa from val(s) to val(a) containing an edge e = (val(x), val(y)) in common with a path pab from val(a) to val(b). Thus, psa and pab are of the form psa = psx · e · pya and pab = pax · e · pya, where pwz denotes a path from val(w) to val(z). This implies that π∗ contains the path pax · e · pya, which contradicts that π is consistent.

What said so far allows us to check Property 2 by merely checking the existence of a del-only preference update U with |U| ≤ k satisfying i. In turn, this means solving SINGLEATTACKACTIVATION(VF, (a, s), k), so Lemma 1 implies that checking Property 2 is in P.

Hardness: RNE-DO with σ ∈ {ad, st, co, gr}. Under σ = ad, we show a reduction from the NP-hard problem 2-SKEWMULTICUT (a special case of SKEWMULTICUT [Kratsch et al., 2015]) to the complement of RNEDO. An instance of SKEWMULTICUT is a tuple (G, k, T ), where G = ⟨N,E⟩ is a directed acyclic graph, k ≥ 0 is an integer, and T a set of pairs of nodes of the following form: there are two disjoint subsets V = {v1, . . . , vm} and W = {w1, . . . , wm} of N (with |V| = |W| = m), such that T = {(vi, wj) ∈ V ×W | i ≤ j}. Without loss of generality, it is assumed that for each (vi, wj) ∈ T , wj is reachable from vi in G. The answer of SKEWMULTICUT(G, k, T ) is Yes if there is a set of edges E′ of G with |E′ | ≤ k such that, for every (v, w) ∈ T , w is not reachable from v in G \ E′ .

2-SKEWMULTICUT is SKEWMULTICUT where m = 2, i.e. T has the specific form: T = {(v1,w1), (v1,w2), (v2,w2)}. Given an instance 2-SKEWMULTICUT(G, k, T ), where we denote the sets of nodes and arcs of G as N and E, respectively, we build the AVAF VF = ⟨A, D, V, val, π⟩, where:

- V = N ∪ {vb}, where vb is a fresh value and π = E;

The argumentation graph (the arguments are depicted along with their values)

The set of preferences that must be removed to make S={aw1, aw2, b} an extension

• A = {av′1 , av′′ 1 , av2, aw1, aw2, b};
• D = {(av′1 , av′1 ), (av′′ 1 , av′′ 1 ), (av2, av2), (av′1 , b), (av′′ 1 , b), (av2, b), (aw1, av′1 ), (aw1, av′′ 1 ), (aw2, av2)};
• val is defined as follows: val(aw1) = w1, val(aw2) = w2, val(av′1 ) = val(av′′ 1 ) = v1, val(av2) = v2, val(b) = vb.

The argumentation graph and the graph of preferences underlying VF are depicted in Figure 2.

We set S = {aw1, aw2, b}. Observe that, in VF, the attacks from aw1 and aw2 are inactive (by hypothesis, every pair in T denotes the existence of a path in G, so every pair in T is also a preference in π∗ ). Hence, S is not an extension of VF.

Therefore, the problem RNE-DOσ (VF, S, k) makes sense, and we conclude the proof by showing the following equivalence: "The answer of 2-SKEWMULTICUT(G, k, T ) is Yes" ⇔ "The answer of RNE-DOσ (VF, S, k) is No"

⇒: Let E′ be a set of edges with |E′ | ≤ k such that, for every pair (vi,wj) ∈ T , wj is not reachable from vi in G \ E′ . Consider the update: U = {del(x > y)|(x, y) ∈ E′ }. As the preference graph of U(π) (after removing the node vb) coincides with G \ E′ , we have that, for every pair (vi, wj) ∈ T , (vi,wj) ̸∈ π∗ . Hence, the attacks from aw1, aw2 to av′1 , av′′ 1 , av2 are active in U(VF), so S is an extension of U(VF), and this proves the implication, as |U| = |E′ | ≤ k. ⇐: Let U be a del-only update over VF such that |U| ≤ k and S is an extension of U(VF). As the value vb is involved in no preference in VF, it is still involved in no preference in U(VF), so the attacks towards b are active in both VF and U(VF), as deleting preferences cannot inactivate attacks. Hence, the fact that S is not an extension of VF but is an extension of U(VF) means that the attacks from aw1 and aw2 are inactive in VF but active in U(VF). This means that, for every pair (vi,wj) ∈ T , we have that (vi,wj) ̸∈ U(π)∗ . It is straightforward to see that this is the same as saying that the set of edges E′ consisting of the same pairs as U is such that, for every pair (vi,wj) ∈ T , wj is not reachable from vi in G \ E′ , that proves the implication, as |E′ | = |U| ≤ k.

The proof used in the case σ = ad trivially extends to σ ∈ {st, co, gr}, as, for any consistent preference update U, S = {aw1, aw2, b} is an admissible extension of U(VF) iff S is an extension of U(VF) under any σ ∈ {st, co, gr}.

Hardness: RE-DO under σ ∈ {co, gr, pr}. We show a reduction from 2-SKEWMULTICUT. Given an instance 2SKEWMULTICUT(G, k, T ), we consider the instance REDO(VF, S′ , k), where VF is the same AVAF defined in the reduction used above to prove the coNP-hardness of RNE- DO under σ = ad, while S′ = {aw1, aw2}. The same reasoning used above proves the following equivalence, that proves the correctness of the reduction: "The answer of 2SKEWMULTICUT(G, k, T ) is Yes" ⇔ "The answer of REDO(VF, S′ , k) is No". The difference, here, is that S′ is complete in VF, and activating the attacks from aw1, aw2 against av′1 , av′′ 1 , av2 makes it no longer complete.

Hardness: other cases. (Sketch) As for RNE-IO under σ ∈ {cf, ad, st, co, gr, pr}, it is easy to see that the complement of RNE-IO is more general than checking the existence of an update consisting of no more than k insertions that inactivates a given set of attacks in an AVAF. In turn, this problem can be shown to be able to encode any instance of the well-known NP-hard problem SET-COVER.

As for RNE (only under σ = pr), RNA-IO and RNA-DO, reductions from verification or acceptance problems in attack incomplete AAFs (aiAAFs) can be defined (the relationship with aiAAFs is also discussed in Section 5).

As for RA with σ ∈ {ad, st, co, gr, pr} and X = Cr, reductions from the satisfiability problem over (quantified) propositional formulas can be defined.

As for RA with σ ∈ {st, pr} and X = Sk, reductions from the skeptical acceptance problem over AAFs can be defined. The hardness for RA with σ ∈ {co, gr} and X = Sk follows from the case of RA with σ = gr and X = Cr. ✷

The following proposition states that, if the number of values is constant w.r.t. the size of the AVAF, several k-robustness problems become solvable in polynomial time, i.e. they are fixed parameter tractable w.r.t. the number of values.

Proposition 1 RE, RNE under σ ∈ {cf, ad, st, co, gr}, as well as RA and RNA under σ = gr and X ∈ {Cr, Sk} or σ = co and X = Sk are fixed parameter tractable w.r.t the size of the set of values.

Proof. Let VF = ⟨A,D, V, val, π⟩ be an AVAF. The krobustness problems can be solved by generating all the preference updates U and checking the verification or the acceptance over U(VF). Since: i. the number of preference updates is bounded by 2|V |×|V | , ii. the cost of applying an update is polynomial in the size of the update and the AVAF, iii. the verification or acceptance test over the implied AAF are in P for the cases in the statement, the overall cost is O(g(|V |)·f(|A|+|D|)), where f is a polynomial function. ✷

5 Discussion of the Results and RelatedWork

This study is related to the works investigating how the outcome of the reasoning over AAFs changes when attacks are inserted/removed. In this research context, the following two topics are particularly related:

• attack-incomplete AAFs (aiAAFs) [Baumeister et al., 2018], i.e. AAFs where some attacks are uncertain, so the reasoning takes into account all the alternative "completions", i.e. the alternative AAFs containing all the arguments and the certain attacks, along with a subset of the set of uncertain attacks;
• the strict (resp., non-strict) argument-fixed extension enforcement problem over AAFs, that asks for minimizing the number of local updates (i.e. insertions/deletions

into/from the set of attacks) needed to make a set an extension (resp., a subset of an extension) [Baumann et al., 2021; Coste-Marquis et al., 2015; Wallner et al., 2017].

As for the relationship with aiAAFs, the problems RNE and RNA resemble the complements of the problems IVER and IACC of deciding if a set is an extension and an argument is accepted in a completion of an aiAAF, studied in [Fazzinga et al., 2020; Baumeister et al., 2021]. However, compared with IVER and IACC, RNE and RNA exhibit two further sources of complexity: the necessity for counting (as in RNE and RNA a condition is specified on the number of preference updates) and the fact that the preferences between values encode correlations between activations/deactivations of distinct attacks, thus making these problems more similar to the variants of IVER and IACC addressed in [Fazzinga et al., 2021a], where correlations can be expressed over the uncertain attacks. Indeed, the correlations expressible via preferences between values do not coincide with any of the single forms of dependencies in [Fazzinga et al., 2021a]. From a computational complexity standpoint, it is interesting to observe that, for the semantics under which IVER and IACC are hard for some class C beyond P, the problems RNE and RNA are complete (both in the ins-only and del-only variants) for the complement of C; on the other hand, when IVER is in P (i.e. under σ ∈ {cf, ad, st, co, gr}), RNE is coNP-complete (except for the trivial case of del-only updates under σ = cf).

As for the relationship with the enforcement problems above, RNE and RNA are close to (the complements of) the strict and the non-strict enforcement problems. However, analogously to what was said for aiAAFs, the enforcement problem imposes no constraint on which attacks can be added/deleted. On the contrary, when assessing the robustness, it is not possible to consider inconsistent updates, so, for instance, it is not possible to simultaneously deactivate two attacks of the form (a, b), (b, a) to make {a, b} conflict-free (the removal of (a, b), (b, a) is instead allowed when enforcing the conflict-freeness of {a, b}). Comparing our results on RNE and RNA with those on the enforcement in [Wallner et al., 2017], the main difference is in the cases where the enforcement is decidable in P (i.e. under σ ∈ {cf, ad, st}), as in these cases RNE is harder (coNP-complete), while in the other cases the complexity classes are complementary.

Observe also that our fine-grained study of the computational complexity, where we separately consider the cases of ins-only and del-only updates, has no counterpart in the literature of aiAAFs and argument-fixed enforcements, where it was not investigated what happens when attacks can be only added or only removed (for instance, the reductions in [Wallner et al., 2017] proving the NP-hardness of the strict enforcement under σ ∈ {co, gr, pr} simultaneously exploit the insertions and deletions of attacks).

As for the other two k-robustness problems studied in this paper, RE and RA, they are in some sense analogous to enforcement of general acceptability constraints [Doutre and Mailly, 2018] (however, the setting where this enforcement was studied disregards values and preferences).

This work is also closely related to the generalizations of AAFs where preferences are used for filtering the extensions [Alfano et al., 2023; Amgoud and Vesic, 2011] (similarly to what done in [Alfano et al., 2024b; Alfano et al., 2024c] by means of constraints) or for "revising" the attacks (as done in PAFs [Amgoud and Cayrol, 2002], that underlie the semantics of AVAFs, or in [Kaci and Labreuche, 2014], where preferences are valued and are used to obtain varied-strength attacks) or for both these aspects [Amgoud and Vesic, 2014]. Preferences have been employed also in other forms of argument systems: they are specified over arguments to extend Claim-augmented AAFs in [Bernreiter et al., 2024], over structured arguments in ASPIC+ [S. Mogdil, 2013], and over assumptions to extend Assumption Based Argumentation [Cyras and Toni, 2016]. In [Modgil, 2009], a framework integrating metalevel argumentation that encodes the reasoning over preferences and generalizes PAFs and AVAFs has been introduced. In [Kaci et al., 2018; Amgoud and Vesic, 2014], three translations from PAFs to AAFs alternative to the one used in this paper (that was defined in [Amgoud and Cayrol, 2002]) have been introduced. The notion of robustness and the definitions of the related problems studied in this paper are orthogonal to the specific translation used. As for the complexity results, it is easy to see that the memberships in classes beyond P in Table 1 hold for the other translations; the same is true, up to minor changes, for most of the reductions proving the hardness results. However, formally proving the correctness of the modified reductions and extending the tractability results of Table 1 to the other translations is a matter of future work.

As robustness deals with the uncertainty of the audience profile, our work is related with the literature on uncertainty in abstract argumentation such as incomplete AAFs [Fazzinga et al., 2020] (generalizing aiAAFs, as they also consider uncertain arguments), Control Argumentation Frameworks [Dimopoulos et al., 2018], and probabilistic AAFs (following the constellations [Li et al., 2011; Fazzinga et al., 2018; Fazzinga et al., 2019; Polberg and Hunter, 2018] or the epistemic [Hunter and Thimm, 2014; Thimm, 2012] approach), where the uncertainty is expressed probabilistically.

6 Conclusions and FutureWork

In the context of AVAF, we have introduced a framework for reasoning on the robustness of the status of sets of arguments and of single arguments with respect to changes of the audience profile. This profile is a set of preferences over the social valued promoted by the arguments, and its modifications cause the activation/deactivation of the attacks. We have characterized the computational complexity of the decision problems at the core of the reasoning paradigm. Future work will be devoted to addressing the following extensions of the framework: 1) modeling arguments promoting multiple values, as done in [Kaci and van der Torre, 2008]; 2) simultaneously considering multiple audiences, and reasoning on the robustness of the status of the arguments for at least one or all the audiences; 3) introducing a weighted model for the preferences, so that it can be taken into account that a preference insertion/deletion/inversion is more or less likely than another; 4) defining new gradual semantics for AVAFs, where the acceptability degrees of the arguments are defined in terms of their robustness degrees.

Acknowledgments

We acknowledge financial support from PNRR MUR project PE0000013-FAIR and project Tech4You ECS0000009, and MUR project PRIN 2022 EPICA (CUP H53D23003660006).