A Fully Rational Account of Structured Argumentation Under Resource Bounds

1 Introduction

Context. Dung's seminal argumentation theory [Dung, 1995] enables formalisation of single agent, and distributed (dialogical), non-monotonic reasoning in terms of the exchange of arguments. ASPIC+ is a widely used general framework for defining the arguments and defeats that comprise a Dung Argumentation Framework (AF) [Modgil and Prakken, 2013]. Arguments are constructed from a knowledge base (KB) of formulae in some logical language, and defeasible and strict inference rules; the latter typically encoding inference in a deductive logic. Attacks are defined between arguments, and a preference relation over arguments decides which attacks succeed as defeats. The claims of the winning (justified) arguments (under Dung's semantics) define the non-monotonic inferences from the underlying KB. ASPIC+ allows considerable degrees of freedom in the choice of the logical language, the defeasible and strict inference rules, and how preferences are defined. Hence it is shown (see review in [Modgil and Prakken, 2018]) to capture other argumentation formalisms, provide dialectical characterisations of well known non-monotonic logics (e.g., (Prioritised) Default Logic and Preferred Subtheories), and enable formulation of novel nonmonotonic logics (e.g., [Dong et al., 2019]).

ASPIC+ specifies guidelines that constrain the above choices, so guaranteeing rational outcomes when evaluating justified arguments; in particular consistency and closure [Caminada and Amgoud, 2007]. However, two key limitations of ASPIC+preclude its use in providing dialectical characterisations of non-monotonic reasoning for real world agents reasoning as individuals or via dialogue. Firstly, consistency is satisfied under the tacit assumption that agents have unbounded resources (logical omniscience is assumed in that all deductive inferences are assumed to be generated). Secondly, guidelines for satisfying the 'non-contamination' postulates [Caminada et al., 2012] are not specified. Hence, inferences (the claims of justified arguments) may be invalidated by adding syntactically disjoint information to the premises. This is particularly problematic when evaluating arguments under the computationally feasible grounded semantics which (sceptically) identifies a unique set of nonmonotonic inferences.

Contributions. This paper is the first to provide a formalisation of ASPIC+ - Dialectical ASPIC+ (D-ASPIC+) - that is fully rational under resource bounds: consistency, closure and non-contamination are satisfied, while making only minimal (i.e., relatively undemanding) assumptions as to the resources available for constructing arguments. Hence, DASPIC+represents an important step towards enabling deployment of argumentation formalisms and non-monotonic logics in real-world settings by resource bounded agents, while satisfying the full gamut of rationality criteria.

Outline of Paper. In Section 3we formalise the D-ASPIC+ framework for structured argumentation. We adapt the approach in [D'Agostino and Modgil, 2018], which establishes rationality under resource bounds for classical logic argumentation. D-ASPIC+refines an argument's ontology to reflect the distinction in real-world dialectical uses of argument, between arguments that an agent commits to, and those that are supposed (conceded) for the sake of argument (and that an interlocutor may commit to in dialogical contexts). Unlike ASPIC+, consistency and closure hold without assuming full deductive inferential capabilities, or assuming that preference relations satisfy any properties. Moreover, D-ASPIC+ solves the foreign commitment problem [Caminada et al., 2014]. Section 4 then identifies the conditions - properties of preferences relations and assumptions on available resources for constructing arguments - under which D-ASPIC+ satisfies non-contamination. Section 5 highlights other works aiming at full rationality for restricted versions of ASPIC+. We also point to future work: we propose that strict inferences in arguments be generated by proof theories which do not licence use of 'redundant' (syntactically disjoint) premises (e.g., the natural deduction system in [D'Agostino et al., 2019]). In so doing, non-contamination is then satisfied irrespective of the properties of preference relations.

2 ASPIC+and its Limitations.

An ASPIC+ argumentation system (AS) 〈L, -, R, n〉 consists of some logical language L that includes the constant symbol ⊥ (falsum), and a function - : L ↦→ 2L specifying when formulae are in conflict:

• ϕ is a contrary of ψ if ϕ ∈ ψ, ψ /∈ ϕ (e.g., ∀φ ∈ L, ϕ is a contrary of NOT ϕ, where NOT is 'negation as failure');
• ϕ is a contradictory of ψ (denoted by 'ϕ = -ψ'), if ϕ ∈ ψ, ψ ∈ ϕ (e.g., ∀ϕ ∈ L, ϕ and ¬ϕ are contradictories). R = Rs ∪ Rd is a set of strict (Rs) and defeasible (Rd) inference rules of the form ϕ1, . . . , ϕn → ϕ, respectively ϕ1, . . . , ϕn ⇒ ϕ (ϕ ̸= ⊥) where ϕi, ϕ are meta-variables ranging over wff in L. Typically, strict rules encode inference in some deductive logic, e.g.,

ϕ1, . . . , ϕn → ϕ ∈ Rs iff ϕ1, . . . , ϕn ⊢CL ϕ, in which case we may simply write Rs = ⊢CL (⊢CL is the consequence relation of classical logic).

Defeasible rules typically specify domain-specific defeasible (default) inferences (e.g., bird(X) ⇒ fly(X)). n is a partial function assigning names (formulae in L) to defeasible inference rules. Then, any argument concluding a contrary or contradictory of α, invalidates use of the defeasible rule r named α (and so attacks an argument X that uses r).

An ASPIC+ theory T = (AS, K) consists of an argumentation system and a knowledge base K ⊆ L \ {⊥} consisting of two disjoint subsets Kn (the axiom premises) and Kp (the ordinary premises). Kn represents infallible information and/or axioms in some deductive logic, and Kp fallible information. In this paper we assume any T satisfies only two of the five conditions identifying 'well defined' theories in [Modgil and Prakken, 2013]: 1) the axiom premises are consistent, and 2) whenever ϕ is a contrary of ψ then ψ /∈ Kn and ψ is not the consequent of a strict rule (e.g., NOTϕ cannot be an axiom or conclusion of a strict rule). We additionally assume that the following is satisfied by Rs:

ASPIC+ arguments are upside down trees, whose leaves are premises, yielding the argument's claim (the root node) via application of strict and/or defeasible rules. In this paper, the defeasible, but not strict, rules are explicitly represented as nodes. Figures 1i-iii show such arguments. (In each case Rs = ⊢CL and Kn = ∅.). Application of defeasible rules is indicated by dashed lines (note that '⊃' denotes material implication). Application of strict rules is indicated by unbroken lines linking the rule's conclusion to its antecedents. In i), we assume arguments built from Kp = {k, r, ¬p, q ⊃ ¬s, t} and Rd = {k, r ⇒ p; t ⇒ s}). In ii) and iii), Kp = {e, s}, Rd = {e ⇒ ¬s} and Kp = {g, e, s}, Rd = {g ⇒ p; e ⇒ ¬s} respectively. We may write arguments as lists of premises and defeasible rules preceding a claim (e.g., A = [k; r; k, r ⇒ p; ¬p; q ⊃ ¬s] : ¬s in Fig. 1i.

The sub-arguments of an argument X (denoted Sub(X)) are the sub-trees of X, each of whose root node is a node in X other than a defeasible rule. In Fig. 1i, Sub(A) = A,A1...6, and the proper sub-arguments of A are A1...6. Note that we may also represent an argument by its top rule (the last rule applied to obtain the argument's claim), and with its immediate proper sub-arguments substituing for the rule's antecedents; e.g., A = A1,A2,A3 → ¬s. Also, any X′ ∈ Sub(X) such that X′ 's top rule is defeasible or X′ is an ordinary premise, is said to be a fallible sub-argument of X.

An argument X attacks Y on Y ′ ∈ Sub(Y ), if the claim α of X is a contrary or contradictory of: i) an ordinary premise Y ′ (an undermine attack), or ii) conclusion of a defeasible rule that is the top rule of Y ′ (a rebut attack), or iii) the name (n(r)) of the defeasible rule r that is the top rule of Y ′ (an undercut attack). If X undermine or rebut attacks Y on Y ′ , then in the case that the claim α is a contradictory of its target, X defeats Y on Y ′ only if X ⊀ Y ′ , where ≺ is a strict partial preference ordering over arguments. Else undercut attacks and attacks targeting contraries, succeed as defeats irrespective of preferences (e.g., when X claims α, the contrary of an ordinary premise Y ′ = [NOTα] : α ∈ Sub(Y )).

One can then define the extensions of a Dung AF (A,⇝) consisting of an ASPIC+theory's arguments A and defeats (⇝⊆ A×A). A set S of arguments is admissible if it is conflict free (∀X, Y ∈ S: X ̸⇝ Y ) and defends all its arguments (∀X ∈ S, ∀Y s.t. Y ⇝ X, ∃Z ∈ S s.t. Z ⇝ Y ). An admissible set S is: complete if every argument defended by S is in S; grounded/preferred if it is the smallest, respectively a largest (under set inclusion), complete extension; stable if ∀X /∈ S, ∃Y ∈ S s.t. Y ⇝X.

Limitations of ASPIC+. The consistency postulate [Caminada and Amgoud, 2007] states that no complete extension should contain arguments with claims ϕ and ψ such that ϕ ∈ ψ. ASPIC+is shown to satisfy consistency ([Modgil and Prakken, 2013]) if ≺ is 'reasonable' (i.e., ≺ satisfies certain properties as illustrated below), and under the tacit assumption that arguments are constructed given unlimited resources for generating all deductive inferences encoded in the strict rules. For example, if Rs = ⊢CL, then in general there will be an infinite number of arguments. Moreover first order classical logic is undecidable; even in the propositional case deciding whether ∆ ⊢CL α is in general NP-hard, and therefore most likely intractable. This is clearly unfeasible for agents with limited resources. To illustrate, suppose Rs = ⊢CL and Kp = {p, p ⊃ ¬q, p ⊃ q}. Note that attacks cannot target conclusions of strict rules (else this would result in violation of strict closure and indirect consistency rationality postulates [Caminada and Amgoud, 2007]). Hence, to ensure that no complete extension E contains X and Y in Fig.1iv, one needs to assume resources suffice to additionally construct A and B and C. Then, if ≺ is reasonable (i.e., A ⊀ [p ⊃ ¬q] : p ⊃ ¬q or B ⊀ [p ⊃ q] : p ⊃ q or C ⊀ [p] : p), at least one of the attacks from A, B or C succeeds as a defeat. Hence, defending against any such defeat requires some Z ∈ E that defeats A or B or C, which necessarily implies that Z defeats either X or Y , contradicting E is conflict free and so complete.

Non-contamination [Caminada et al., 2012] may be violated by ASPIC+ if an argument makes use of inconsistent premises and/or rules, or premises/rules that are redundantly used in deriving a claim.

Firstly, suppose Rs = ⊢CL, Kp = {q ⊃ ¬s, t} and Rd = {t ⇒ s}. Clearly B in Fig. 1i is in the grounded extension. But upon adding {k, r, ¬p} and {k, r ⇒ p} to Kp and Rd, which intuitively are irrelevant to deciding the status of B (by virtue of being syntactically disjoint from t and t ⇒ s), then A in (Fig. 1i) attacks B. Assuming ≺ = ∅, A defeats B. One can easily verify that B is now no longer in the grounded extension. The 'inconsistent' A is said to be 'contaminating'.

Secondly, suppose in Fig. 1ii that C ≺ F so that F defeats C but not vice versa. F = [s] : s is in the grounded extension. Suppose one adds to the underlying theory the irrelevant (syntactically disjoint) g and g ⇒ p, additionally yielding D in Fig. 1iii. If D ⊀ F, then although F still defeats C, D and F defeat each other. F is no longer in the grounded extension. C has been contaminated by the redundant g and g ⇒ p, by virtue of the classical inference p, e ⊢CL e.

3 Dialectical ASPIC+

In providing a resource bounded fully rational account of ASPIC+, we begin by observing that a common dialectical move is to commit to some arguments and their claims, arguing that if one supposes for the sake of argument the arguments and claims of an interlocutor, then α is necessarily (strictly) entailed. Hence, a D-ASPIC+ argument differentially labels the 'maximal fallible subarguments' (mfs) of an ASPIC+argument A, according to whether they are committed or supposed for the sake of argument:

Definition 1. An ASPIC+argument A is a D-ASPIC+ argument iff exactly one of L1. . .L4 hold:

L1: A = [φ] : φ, φ ∈ Kp and A is exclusively labelled with either c© (for 'committed') or s© (for 'supposed')

L2: A = [φ] : φ, φ ∈ Kn

L3 A = A1, . . . , An ⇒ ϕ and A is exclusively labelled with either c©or s©

L4: A = A1, . . . , An → ϕ and each Ai is a D-ASPIC+ argument, 1 and:

1 That is, traversing each path from the root (conclusion) to a leaf of an ASPIC+argument A, assign label c©or s©when first encountering either an ordinary premise or conclusion of a defeasible inference rule. Once a label is assigned, traversal is terminated.

C2 ∀A′ ∈ Sub(A), if A′ is labelled s© , then ¬∃A′′ ∈ Sub(A) such that A′′ is labelled c©and A′ ∈ Sub(A′′ ).

We may write (∆, Γ, φ)A to denote a D-ASPIC+argument A, where A′ ∈ ∆ iff A′ is labelled c© , A′ ∈ Γ iff A′ is labelled s© in A. Then com(A) = ∆ and sup(A) = Γ are the committed, respectively supposed, mfs of A. C2 then states that no supposed X ∈ Γ is a proper sub-argument of some committed Y ∈ ∆, since commitment to Y implies commitment to all sub-arguments of Y . Also, for any set S:

denotes the sub-arguments of committed arguments in S.

Example 1. Let Rs = ⊢CL, Kn = {accA, accB}, Kp = {bgt}, Rd = {accA ⇒ attA; accB ⇒ attB; bgt ⇒ ¬(attA ∧ attB)}, where (letting X stand for A or B):

accX and attX respectively denote 'paper accepted at conference X' and 'will attend conference X', and bgt denotes 'budget'.

({A1,B1}, ∅, attA ∧ attB)D in Fig. 2-i claims the intention to attend A and B. ({C3}, {A1}, ¬attB)C1 and ({C3}, {B1}, ¬attA)C2 , argue that the budget is insufficient to attend both conferences, and supposing attendance at A (respectively B), then one cannot attend B ( respectively A).

Definition 2. Let (∆, Γ, α)X and (Π,Σ, β)Y be D-ASPIC+ arguments.

1) if α ̸= ⊥, then X attacks Y if X undercuts, rebuts or undermines some Y ′ ∈ Π on Y ′′ ∈ Sub(Y ′ ) (one can only target committed arguments). X defeats Y iff X attacks Y and if the attack rebuts/undermines a contradictory then X ⊀ Y ′′ .

2) if α = ⊥ (X is a 'falsum argument') then X attacks Y on any Y ′ ∈ Γ∩ Sub(Π). If ∆ = ∅, then X defeats Y . If ∆ ̸= ∅ then X defeats Y only if ∃Y ′ ∈ Γ ∩ Sub(Π), X ⊀ Y ′ .

Intuitively, attacks and defeats of type 1 are defined as for ASPIC+ arguments, except that the attack must target a fallible committed sub-argument of the attackee. In Example 1, C1 attacks D on B1, and defeats D on B1 only if C1 ⊀ B1. Likewise, C2 attacks D on A1, and defeats D on A1 only if C2 ⊀ A1. Notice that C1 (C2) does not attack C2 (C1) on the supposed B1 (A1). For attacks from falsum arguments, if ∆ = ∅ then the attack amounts to a dialectical demonstration that the supposed Γ are inconsistent, and so succeeds as a defeat independently of preferences; else success is contingent on X ⊀ Y ′ for some Y ′ ∈ Γ ∩ Sub(Π). Also, note that the mfs of any given constructed argument can be differentially labelled; this does not affect the strength of the argument:

Definition 3. Let ≺ be a strict partial ordering over some set A of D-ASPIC+ arguments. Let (∆, Γ, α)X ∈ A. Then:

• [X] = {(∆′ , Γ′ , α)X′ |∆′ ∪Γ′ =∆∪Γ, and Sub(X′ ) = Sub(X) }. ∀Y,Z ∈ [X] we say that Y and Z are logically equivalent.
• Henceforth we assume that ≺ satisfies the following: ∀Y ′ ∈ [Y ], ∀X′ ∈ [X] : Y ≺X iff Y ′ ≺X′

In general, when establishing whether Y is defended by a set E of arguments (i.e., whether Y is acceptable w.r.t. E), one commits to fallible arguments in E and Y . Hence (∆, Γ, α)X can then challenge (i.e., defeat) Y if X supposes/concedes a subset Γ of these fallible arguments, arguing that together with ∆, Γ neccessarily entails a claim that conflicts with some fallible element in Y . Then, a defeat by (∆, Γ, ⊥)X indicates that the fallible arguments Γ committed in E∪{Y }, together with ∆, are inconsistent. Y should only then be targeted if at least one of the committed arguments in Y contributes to the inconsistency (i.e., is in Γ). Only if ∆ = ∅ does the attack by X dialectically demonstrate that E ∪ {Y } has necessarily committed to (strictly entails) an inconsistency, and so succeeds as a defeat independently of preferences. As for arguments (X) deployed in challenging Y , these are not required to define an admissible set; they are countered on an individual basis. Hence Z ∈ E can defend Y if Z defeats X, while conceding only fallible arguments that X commits to (i.e., sub-arguments of ∆).

Definition 4. Let (A,D) be a dialectical AF (DAF) defined by a theory T = (AS,K), where A is a set of DASPIC+arguments, and D ⊆ A × A is the set of defeats.

Then X defeats Y with respect to S ⊆ A, denoted X ⇝S Y , if (X, Y ) ∈ D and sup(X) ⊆ SubCom(S ∪ {Y }).

• S is conflict free if ∀Z, Y ∈ S, Z ̸⇝S Y .
• Y is acceptable w.r.t. S if ∀X s.t. X ⇝S Y , ∃Z ∈ S s.t. Z ⇒{X} X.

The extensions of (A,D) are then defined as in Section 2, except in the case that S is stable, in which case we stipulate that ∀X /∈ S.∃Y ∈ S s.t. Y ⇝{X} X.

Consider Example 1, and suppose a dialogue in which the acceptablity of D w.r.t. some set E, is challenged by a defeat from either C1 or C2. Then C1 ⇝E D and C2 ⇝E D, where C1 (C2) need not commit to A1 (B1), but rather supposes A1 (B1) only for the sake of argument, given A1 (B1) is committed in D. The corresponding ASPIC+arguments, which do not distinguish commitments from suppositions, illustrate the foreign commitment problem [Caminada et al., 2014]: they unnaturally have to commit to attendance at one of the conferences (i.e., A1 or B1) in order to challenge the argument D which claims that both conferences cannot be attended.

Let Rs = ⊢CL, Kp = {p, p ⊃ ¬q, p ⊃ q} and A include the D-ASPIC+arguments in Fig.2ii, as well as ({p}, ∅, p)F , ({p ⊃ ¬q}, ∅, p ⊃ ¬q)G, ({p ⊃ q}, ∅, p ⊃ q)H. Now, E cannot be admissible. This is because the inconsistency of the premises p, p ⊃ ¬q, p ⊃ q is recognised by virtue of constructing arguments with conflicting claims (X and Y ). Then, intuitively, a minimal assumption on available resources would be that resources suffice to combine the mfs of these arguments to yield the falsum argument Z2 in Fig.2ii. Then Z2 ⇝E X on F and G (since sup(Z2) ⊆ SubCom(E ∪ {X})), and Z2 ⇝E Y on F and H; Z2 is moved to dialectically demonstrate that E commits to mfs that strictly entail ⊥. These defeats succeed independently of preferences. Z2 cannot be defeated as it has not committed to any arguments. Hence neither X or Y can be defended and E cannot be admissible. Observe that unlike ASPIC+, satisfaction of consistency in D-ASPIC+ does not: 1) assume resources suffice to construct A, B and C (in Fig.1iv); 2) require that ≺ satisfy the property of being reasonable.

Definition 5. Let (A,D) be a DAF. We define properties that A may satisfy:

P1, P2 and P3 encode the assumption that resources suffice to: (P1) construct all sub-arguments of a given argument X; (P2) differentially label the mfs of a given argument X; (P3) combine the mfs of arguments with contradictory claims, to construct a falsum argument that strictly entails ⊥.

We now state satisfaction of the consistency and closure postulates, having first defined the claims of arguments in an extension E as the conclusions of arguments in E that make no suppositions (intuitively, the argumentation defined inferences are the conclusions only of arguments one commits to):

Theorem 1. Direct Consistency: Let E be an admissible extension 3 of a DAF (A, D). If A satisfies P1, P2 and P3, then ∀α, β ∈ claims(E), α ̸= ⊥ and α /∈ β.

Assuming only that A satsifies P1, one can also show that for any complete extension E:

Closure under Strict Rules: If E contains arguments A1 . . .An with respective claims φ1 . . . φn, and r = φ1, .. .., φn → φ ∈ Rs, and A includes an argument A that extends A1 . . . An with r so as to strictly claim φ, then A ∈ E;

2 Which given P2 implies that (∅, ∆ ∪ Γ, ⊥)Z′ ∈ A.

3 Note: ASPIC+ only shows consistency for complete extensions.

Sub-argument Closure: ∀X ∈ SubCom(E), X ∈ E (every sub-argument of a committed argument in E, is also in E).

The following key results that hold for Dung AFs, also hold for DAFs: 1) Every admissible extension of a DAF is a subset of a preferred extension; 2) Letting F(A,D) : 2A ↦→ 2A be the characteristic function of a DAF (A,D), defined as F(A,D)(E) = {X ∈ A|X is acceptable w.r.t. E }, then there exists a unique least fixed point of F(A,D) (the grounded extension of (A, D)).

4 Non-Contamination

Contamination may occur when the argumentation defined inferences (the claims of justified arguments) of a theory T are invalidated when 'expanding' the theory with syntactically disjoint domain specific information. That is, when the defeasible rules Rd and premises (ordinary or axiom) K in T are expanded to include premises R′d K′ and that are syntactically disjloint from Rd and K. We now specify the notions of syntactic disjointness and the expansion of a theory.

For any set of wff ∆ in a language L, sym(∆) denotes the set of predicate, function and constant symbols in ∆. 4 Henceforth, for any ∆1, ∆2:

When specifying the symbols appearing in premises and defeasible rules, we need to account for the names assigned (by n) to these rules, as well as formulae declared to be in conflict (by -). To illustrate the latter, suppose an argument X constructed from T , where X includes the ordinary premise married. Then, if bachelor = -married, bachelor should be considered to be in the symbols of T , since an additional argument claiming bachelor, constructed using K′ and R′d , may attack X and so legitimately challenge the justified status of X. Henceforth, we write α ∈ r to denote that α appears in the antecedent, or is the consequent, of a defeasible rule r.

Definition 6. Let con dr(r) = {n(r)} ∪ n(r)∪⋃α∈r α, and;

• conset(Rd ∪ K) = ⋃r∈Rd con dr(r) ∪ ⋃α∈K α;
• base(Rd ∪ K) = ⋃α∈r,r∈Rd ∪ K ∪ conset(Rd ∪ K)

Let T ′ be a D-ASPIC+ theory (AS′ , K′ ), where

• AS′ = 〈L, -,R=Rs ∪Rd1 ∪Rd2 , n′ 〉;
• K′ = K1 ∪K2

Then T = (〈L, -, R = Rs ∪ Rd1 , n〉, K1) is said to be 'expanded by the syntactically disjoint (Rd2 ,K2) to obtain T ′ ', denoted T ′ = T ⊕ (Rd2 ,K2), iff ∀r ∈ Rd1 , n(r) = n′ (r), and:

Henceforth, we let A be the arguments constructed from T and the preference relation ≺ over A, and A′ the arguments constructed from T ′ and the preference relation ≺′ over A′ . It is straightforward to see that A ⊆ A′ . Moreover, we assume that preferences over arguments in A are unchanged when incorporating Rd2 and K2 (i.e., ≺=≺′ ∩ A×A). Let us now revisit the example illustrating contamination in Fig. 1i):

4 As usual, propositional atomic formulae are interpreted as predicate symbols of arity 0.

Example 2. Let T be a theory s.t. L is a propositional language, ∀φ ∈ L, φ is a contradictory of ¬φ, Rs = ⊢CL (T is said to be a 'classical propositional theory'), and:

• Rd1 = {t ⇒ s}, n(t ⇒ s) = r1, K1 = Kp1 = {q ⊃ ¬s, t}, and ≺= ∅.
• Let T ′ = T ⊕ (Rd2 = {k, r ⇒ p}, K2 = Kp2 = {k, r, ¬p}), where n′ (t ⇒ s) = r1, n′ (k, r ⇒ p) = r2, ≺′= ∅. Note that base(Rd1 ,K1)‖base(Rd2 ,K2). However, suppose Kp2 had also included g, and g ∈ r1. Then the respective symbol bases would not be syntactically disjoint (the argument [g] : g would undercut an argument that uses t ⇒ s).
• Fig. 2iii shows arguments A and A′ respectively constructed

from T and T ′ (note, we do not show these arguments with all their differential labellings - i.e., their logical equivalents).

Observe that B is in the grounded extension of (A,D). Now notice that A ∈ A′ defeats B ∈ A′ . However, unlike ASPIC+, B is still in the grounded extension E of (A′ ,D′ ). Intuitively, given that resources suffice to strictly extend A1 and A6 so as to explosively entail q, then resources suffice to construct the corresponding falsum argument F = (∅, {A1,A6},⊥). Since F has empty commitments, it cannot be defeated, and so F ∈ E. Moreover, F defends B ∈ E since F ⇒{A} A independently of preferences. Intuitively, F dialectically demonstrates that A is a contaminating argument by stint of committing to inconsistent fallible information (A1 and A6).

Example 3. Let T be a classical propositional theory, and:

• Rd1 = {e ⇒ ¬s}, n(e ⇒ ¬s) = r1, K1 = Kp1 = {e, s}. Fig. 2iv shows arguments C, C1 and F . Let C ≺ F .
• Let T ′ = T ⊕ (Rd2 = {g ⇒ p}, K2 = Kp2 = {g}), where n′ (e ⇒ ¬s) = r1, n′ (g ⇒ p) = r2. Fig. 2iv) shows the additional arguments D, C2 and C3. Let C ≺′ F , D ⊀′ F .

Adding the syntactically disjoint (Rd2 ,K2) results in contamination, since (as in ASPIC+) F is in the grounded extension of (A, D) but not (A′ , D′ ). However, non-contamination would be satisfied if adding syntactically disjoint information to an argument does not change the strength of the argument. Then one would have that D ≺ F, hence D ̸⇝E F, and so F would be in the grounded extension.

Let us now more formally set out the conditions for satisfaction of non-contamination. Firstly, the following can be shown (in what follows we write DP(A) to denote the defeasible rules and premises in an argument A):

Definition 7. ⊢ is a regular logic if it satisfies the following:

Note, it is easy to show that classical logic is regular (see Proposition 30 in [D'Agostino and Modgil, 2018]).

Proposition 1. Let A be the arguments defined by a theory (AS,K) such that Rs in AS encodes a regular logic ⊢. Let X ∈ A such that conc(X) = α and Γ = DP(X), ∅ ̸= ∆ ⊆ Γ and ∆‖Γ \ ∆ ∪ {α}. Then

Henceforth we assume Rs is regular and that P4 is satisfied by the arguments constructed from a theory. That is to say, given an argument of the form X in Proposition 1, resources suffice to:

(i) construct the required X′ with conc(X′ ) = ⊥, if ∆ is inconsistent (in Example 3, A includes 'inconsistent components A1 and A6' and so F ∈ A′ ); or else

(ii) to construct X′ with conc(X′ ) = α. In this case X′ is said to be the 'non-redundant counterpart' of X (in Example 3, D ∈ A′ and so resources suffice to construct its nonredundant counterpart, i.e., C ∈ A′ ).

In general, non-contamination is then satisfied if a nonredundant counterpart X′ is neither weakened or strengthened when adding syntactically disjoint information, to yield the argument X (see Definition 8). However, if T contains no defeasible rules 5 - i.e., T is a strict theory - then it suffices that arguments are not strengthened. In general, whether or not P4 can be satisfied with bounded resources, depends on whether the proof-theoretical means used to obtain strict inferences is such that given a proof of a conclusion that is syntactically disjoint from the premises, we can feasibly (with virtually no computational cost) turn it into a proof of ⊥ from the same premises. A classical natural deduction system satisfying this requirement is presented in [D'Agostino and Modgil, 2018] and [D'Agostino et al., 2019].

Definition 8. ∀X, Y, Y ′ such that:

conc(Y ′ ) = conc(Y ) = α, and ∀r, r′ ∈ Γ, r′ is a child of r in Y ′ iff r′ is a child of r in Y 6

• ≺ is said to be non-strengthening if:
• Y ′ ≺ X implies Y ≺ X and X ⊀ Y ′ implies X ⊀ Y , and
• ≺ is said to be non-weakening if:

Now, let the consequences of a theory T = (AS,K) be defined as Cn(T ) = {claims(E1), . . . , claims(En)}, where E1, . . . ,En are the complete extensions of the DAF (A,D) defined by T . Also, let Cn(T )Sy denote the formulae in Cn(T ) whose symbols are also in the set Sy. We now state satisfaction of the first of the non-contamination postulates - non-interference - studied in [Caminada et al., 2012].

Theorem 2. Non-Interference. Let T ′ = T ⊕ (Rd2 ,K2). Assume that: 1) preferences are non-strengthening in the case of strict theories, and both non-strengthening and non-weakening in the case that theories include defeasible rules; 2) the arguments A and A′ respectively constructed from T and T ′ , satisfy P1-P4. Then:

Intuitively, the above result follows from the result that whenever (A,D) is defined by T and (A′ ,D′ ) is defined by T ′ , and T ′ = T ⊕(Rd2 , K2), then E is a complete extension of (A,D) iff E′ is a complete extension of (A′ ,D′ ), where E = E′ ∩ A. For brevity, we omit here the second noncontamination postulate - crash resistance - which follows straightforwardly from non-interference.

5 E.g., when D-ASPIC+formalises classical logic argumentation with preferences as in [D'Agostino and Modgil, 2018].

6 r′ is a child of r in X iff r′ is the top rule of some X′ ∈ Sub(X) that is a proper sub-argument of an X′′ ∈ Sub(X) with top rule r.

5 Conclusions

This paper is the first to study rationality under resource bounds, in the context of general frameworks for structured argumentation. A number of works show satisfaction of non-contamination for specific instances of ASPIC+. In [Caminada et al., 2012], propositional logic programming and Default Logic instantiations of Dung frameworks are shown to satisfy these postulates, but only under the semi-stable semantics. In [Wu and Podlaszewski, 2015], non-contamination is shown assuming syntactically restricted strict inference rules, no preferences, and frameworks 'cleansed of' (excluding) inconsistent arguments. [Heyninck and Straßer, 2017] prove all rationality postulates, only for the grounded semantics, and for a version of ASPIC+ restricted to axiom premises, without undercuts, and with preferences specifically defined by a weakest linking lifting of a total ordering over defeasible rules (generalised to preorders and a different lifting principle in [Heyninck and Straßer, 2019]). [Borg and Straßer, 2018] study approaches to structured argumentation that do not make use of preferences, and that assume a single set of premises. In particular, they identify strict rules encoding 'pre-relevant' logics as a sufficient condition for satisfying non-contamination (note that classical logic is not pre-relevant, so that noncontamination is only satisfied by cleansed frameworks). Finally, [D'Agostino and Modgil, 2018] distinguish between commitments and suppositions in the context of classical logic argumentation with preferences. Full rationality is shown under conditions analogous to P1-P4 (and without requiring that one check that the premises of arguments are consistent and subset minimal). Moreover, they consider the use of a recently proposed natural deduction proof theory for propositional classical logic [D'Agostino et al., 2019], which does not yield arguments that redundantly use syntactically disjoint information. The use of such a proof theory means that satisfaction of non-contamination is not contingent on preference relations for strict theories being non-strengthening. We believe it is straightforward to then show that in the context of D-ASPIC+, if Rs is defined in terms of the inferences licensed by such 'non-contaminating proof systems', satisfaction of non-contamination can then be shown assuming any preference relation.

To conclude, the D-ASPIC+framework for structured argumentation is the first to establish: 1) conditions under which non-contamination is satisfied for all complete semantics and without compromising the generality of ASPIC+; 2) minimally demanding requirements as to the resources available for constructing arguments, that suffice to guarantee satisfaction of all rationality postulates. This has significant implications for a wide range of existing and novel argumentation formalisms and non-monotonic logics that can be formalised in ASPIC+, rendering them more suitable for use by resource bounded real-world agents engaging in epistemic reasoning and decision making, either as individuals or via dialogue.