argumentation, Structured argumentation, Uncertainty, Incompleteness 7th Workshop on Advances in Argumentation in Artificial Intelligence (AI 3), November 06-09, 2023, Rome, Italy ∗Corresponding author.
1. Introduction and motivation
Encoding uncertainty about arguments and attacks is key for applying formal argumentation in
several contexts, including strategic ones such as modelling opponents in a debate [
To address this question in more precise terms, we consider argument-incomplete abstract
argumentation frameworks (arg-IAAFs) [
More procedurally, we define rule-incomplete structured argumentation frameworks (rulISAFs) as incomplete extensions of SAFs, and as natural counterparts of arg-IAAFs in abstract argumentation. As a first negative result (Proposition 1), we show that there are rul-ISAFs that cannot be represented abstractly as arg-IAAFs. However, correspondence is retrieved (Theorem 1) if we instead consider a refinement of arg-IAAFs, that we name implicative argumentincomplete abstract argumentation framework (imp-arg-IAAF).
Section 2 provides the necessary formal background on abstract and structured argumentation, as well as the newly defined notions. In Section 3 we prove our main results. Section 4 sketches our current research directions.
A (Dung) abstract argumentation framework (AAF) is a directed graph ⟨Arg, Def⟩ where Arg is a set of arguments and Def ⊆ Arg × Arg is a defeat relation among them.
An argument-incomplete abstract argumentation framework (arg-IAAF) is a tuple ⟨Arg , Arg?, Def⟩ where Arg and Arg? are two pairwise disjoint sets of arguments and Def ⊆ (Arg ∪ Arg?) × (Arg ∪ Arg?).
A completion of ⟨Arg , Arg?, Def⟩ is any AAF ⟨Arg∗, Def∗⟩ s.t.: • Arg ⊆ Arg∗ ⊆ Arg ∪ Arg?.
• Def∗ = Def↾Arg∗.
As announced, arg-IAAFs will fail to be expressive enough for capturing uncertain inference rules. That’s why we need a more refined formalism. An implicative argumentincomplete abstract argumentation framework (imp-arg-IAAF) is ⟨Arg , Arg?, Def, Δ⟩ where ⟨Arg , Arg?, Def⟩ is an argument-incomplete abstract argumentation framework and Δ ⊆ Arg? × Arg? is a set of implicative dependencies. Informally, ⟨, ⟩ ∈ Δ means that appears in a completion whenever does. Formally, a completion of ⟨Arg , Arg?, Def, Δ⟩ is any AAF ⟨Arg∗, Def∗⟩ s.t.: • ⟨Arg∗, Def∗⟩ is a completion of ⟨Arg , Arg?, Def⟩.
• For all ⟨ , ⟩ ∈ Δ if ∈ Arg∗, then ∈ Arg∗.
Note that imp-arg-IAAFs can be seen as a restricted class of constrained incomplete AFs
[
Finally, we introduce the ASPIC+ notions [15] that are relevant to our study. A structured argumentation framework (SAF) is a tuple = ⟨ L, ⋅, R, , K, Arg, Att, ⪯⟩ where each component is defined as follows: • L is a formal language. • ⋅ ∶ L → 2L is a contrary function. We say that: – is contrary of if ∈ but ∉ .
– is contradictory of (noted = − ) if ∈ and ∈ .
Each ∈ L is assumed to have at least one contradictory. • R = R ∪ R with R ∩ R = ∅ is a set of inference rules (sequences of elements of L). R represents strict rules while R represents defeasible rules. • ∶
R
→ L is a partial naming function for defeasible rules. • K ⊆ L is a knowledge base, assumed to be split into two disjoint subsets K (axioms) and K (ordinary premises). • Arg is the set of arguments of
, which is defined inductively together with some auxiliary functions: Sub(⋅) (returns the subarguments of a an argument), Prem(⋅) (returns the premisses of a an argument), Conc(⋅) (returns the conclusion of a an argument), and TopRule(⋅) (returns the last rule employed in the construction of a an argument). We have that ∈
Arg if: – = [] if ∈ K, with Prem() =
Conc() = {} , Sub() = {[]} and TopRule() – – is left undefined.
Sub() = {} ∪ = = [ [ 1, ..., ↠ ] if is an argument for 1 ≤ ≤ (Conc( 1), ..., Conc( ), ) ∈
R , with Prem() =
⋃1≤≤ Prem( ), Conc() = , ⋃1≤≤ Sub( ), TopRule() = ( Conc( 1), ..., Conc( ), ) . 1, ..., ⇒ ] if is an argument for 1 ≤ ≤ and and Sub() = {} ∪
⋃1≤≤ Sub( ), TopRule() = ( Conc( 1), ..., Conc( ), ) . (Conc( 1), ..., Conc( ), ) ∈
R , with Prem() = ⋃1≤≤ Prem( ), Conc() = , • Att ⊆ Arg × Arg is the attack relation of . ASPIC+ allows for three kinds of attacks.
We say that attacks (i.e., ⟨, ⟩ ∈
Att) if undermines, rebuts or undercuts , where: – undermines (on ′) if Conc() ∈ for some ′ = ∈ Prem() and ∈ K . – rebuts (on ′) if Conc() ∈ for some ′ = Sub() of the form 1′, ...., ′ ⇒ . – undercuts (on ′) if Conc() ∈ ( TopRule( ′)) for some ′ = Sub() with
TopRule( ′) ∈ R . • ⪯⊆ Arg × Arg is a preference relation among arguments, with ≺=⪯ ⧵ ⪯−1 its strict counter-part. given associated to
Given = ⟨
L, ⋅, R, , K, Arg, Att, ⪯⟩, we use L() to denote L and apply the same convention for the rest of the components. Let , ∈ Arg() undercuts , or (ii) undermines/rebuts (on ′) and ⊀ , we say that defeats if: (i) ′. The set of all defeats for a is denoted Def() . Finally, given
, the Dung’s argumentation framework is just () = (
Arg(),
Def()) 3. Structured frameworks with uncertain inference rules As mentioned, here we consider the set of rules of a given structured argumentation framework as a source of uncertainty for the presence of arguments. In the same spirit of IAFs, one can define a rule-incomplete structured argumentation framework as a tuple rul- = ⟨L, ⋅, R, , K, Arg, Att, ⪯⟩, where every component is just as in a SAF except from the set of rules R, which is split into four pairwise disjoint subsets R = R ∪R? ∪R ∪R?, representing respectively certain strict rules, uncertain strict rules, certain defeasible rules and uncertain defeasible rules. Then, a rule-completion of rul- is any
∗ = ⟨L, ⋅, R∗, , K, Arg∗, Att∗, ⪯∗⟩ where: • R∗ = R∗ ∪ R∗ is s.t.: – R ⊆ R∗ ⊆ (R ∪ R?); – R ⊆ R∗ ⊆ (R ∪ R?). • ⪯∗=⪯↾Arg∗.
• Arg∗ and Att∗ are the set of arguments and attacks generated by R∗.
We denote by rul-completions() the set of rule-completions of rul-
, it is not necessarily the case that there is arg- Proof. A simple counterexample is provided by considering any rul- where L is the lan
= {(, )} , and R? = {(, )} guage of propositional logic containing atoms , , K = ∅, K = {} , and ⪯= ∅. Then, completions(rul-) and , ⋅ is classical negation, with R = R? = ∅, two members, namely ⟨{[]}, ∅⟩ and ⟨{[], [[] ⇒ ], [[[] ⇒ ] ⇒ ]}, ∅⟩ . Clearly, for basic cardinality reasons, no arg-IAAF has an isomorphic set of completions, since a completion with one argument and a completion with three arguments would force the presence of another completion with two arguments.
As mentioned, one way to interpret this result is that nothing guarantees that the completion of an (arg-)IAAF is subargument closed, e.g., that [[[] ⇒ ] ⇒ ] forces the presence of [[] ⇒ ] , as in the proof of Proposition 1. s.t.: has Theorem 1. Let rul-
be a rul-ISAF, there exists an imp-arg- completions(rul-) = completions(imp-arg-) s.t.
Sketch of the proof. Let rul- = ⟨ its completions in the proof:
L, ⋅, R, , K, Arg, Att, ⪯⟩ be a rul-ISAF, we will use two of • • is the rule-completion whose set of rules is R = R is the rule-completion whose set of rules is R ∪ R .
= R ∪ R ∪ R? ∪ R?.
Now, we are going to build the target imp-arg-IAAF ⟨Arg , Arg?, Def, Δ⟩: • Arg = Arg( • Arg? = Arg( • Def = Def( • Δ = {⟨ , ⟩ ∈ ). ). ) ⧵ Arg(
).
Arg? × Arg? ∣ ∈ Sub( )} .
We show that both directions of the equality completions(rul-) completions(⟨Arg , Arg?, Def, Δ⟩) hold: [⊆] Suppose ⟨Arg∗, Def∗⟩ ∈ completions(rul-) completions to , which amounts by definition of = (H1) ⟨Arg∗, Def∗⟩ = ( ∗) for some ∗ ∈ rul-completions() Hence, we just need to check that ⟨Arg∗, Def∗⟩ satisfies the conditions for being a completion of ⟨Arg , Arg?, Def, Δ⟩, namely: (a) Arg ⊆ Arg∗ ⊆ Arg ∪ Arg?; (b) Def∗ = Def↾Arg∗; and (c) for all ⟨ , ⟩ ∈ Δ if ∈ Arg∗, then ∈ Arg∗.
To do so, we need to establish the following claims, whose proof we omit: Lemma 1. Let and
′ only difer in their set of inference rules. Then: 1. R() ⊆ 2. R() ⊆ 3. Arg()
R( ′) implies Arg() ⊆ Arg( R( ′) implies Def() = Def( is closed under subarguments (i.e., ∈ ′).
′)↾Arg() Arg() . implies Sub( ) ⊆
Arg())
Based on how we defined our target imp-arg-IAAF and H1, condition 1 of Lemma 1 entails (a), since R( ) ⊆ R( ∗) ⊆ R( max). For the same reason, (b) follows from condition 2 by R( ∗) ⊆ R( max). Finally, condition 3 entails (c) by how we set Δ.
[⊇] Suppose ⟨Arg∗, Def∗⟩ ∈ completions(⟨Arg , Arg?, Def, Δ⟩). Then conditions (a)-(c) above are satisfied. We need to show that ⟨Arg∗, Def∗⟩ ∈ completions(rul-) , which means, by definition, that for some ∈ rul-completions() we have () = ⟨ Arg∗, Def∗⟩. Now, let us consider ′ = ⟨L, ⋅, R′, , K, Arg′, Att′, ⪯′⟩ where R′ = {TopRule( ) ∣ ∈ Arg∗}, Arg′ = Arg∗, Att′ = Att↾Arg′ and ⪯′=⪯↾Arg′ (it is easy to check that ′ is actually a SAF). Using conditions (a)-(c) above, one can show that either ′ is the rule-completion of we are looking for, or that there is one rule-completion ∗ with R( ′) ⊆ R( ∗) s.t. ( ∗) = ( ′).
A natural completion of the present work is to investigate whether the existential claim of Theorem 1 holds in the other direction as well, i.e. for every imp-arg-IAAF there is a rul-ISAF with an isomorphic set of completions. Together with Theorem 1, this would amount to a characterization result for the class of rul-ISAFs. We conjecture that this is in fact the case, but the proof is not as direct as that of Theorem 1 and we leave it for future work.
Another task is to investigate the second root of uncertainty mentioned by [11, Section 8.1.]: incomplete defeats based on incomplete preference profiles. Here again, we think a negative result, analogous to Proposition 1, obtains. As for the analogous to Theorem 1, we think that a restricted version of attack-IAAFs ([16]) with correlations could work at the abstract level.
Finally, a third pending task is to accomplish a detailed comparison of our work with the very recent paper [17], where incomplete theories rooted in incomplete knowledge bases for a special instance of ASPIC+ are investigated. Roughly, and besides the clear contrast between uncertain inference rules vs. uncertain knowledge bases, [17] focuses on so-called stability and relevance problems, while our focus is on expressivity of uncertainty, so both approaches can be seen as complementary in these two senses. presence of correlations, in: Z.-H. Zhou (Ed.), International Joint Conference in Artificial Intelligence, IJCAI Organization, 2021, pp. 189–195. doi:10.24963/ijcai.2021/27. [15] S. Modgil, H. Prakken, A general account of argumentation with preferences, Artificial
Intelligence 195 (2013) 361–397. [16] B. Fazzinga, S. Flesca, F. Furfaro, Reasoning over Attack-incomplete AAFs in the Presence of Correlations, in: M. Bienvenu, G. Lakemeyer, E. Erdem (Eds.), Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, 2021, pp. 301–311. doi:10.24963/kr.2021/29. [17] D. Odekerken, T. Lehtonen, A. Borg, J. P. Wallner, M. Järvisalo, Argumentative reasoning in ASPIC+ under incomplete information, in: Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 19, 2023, pp. 531–541.