On the General Epistemic Abstract Argumentation Framework

Abstract

The Epistemic Abstract Argumentation Framework (EAAF) has been recently proposed to extend Dung's framework (AAF) by allowing the representation of epistemic attacks [1]. In this paper, we discuss an intuitive semantics for (general) EAAF, that is a class of frameworks where epistemic attacks may occur in cycles. The EAAF semantics naturally extends that for AAF as well as that for acyclic EAAF. Recent developments in Artificial Intelligence (AI) have shown the necessity to provide new approaches concerning transparency and explanations on how AI systems make decisions. To address this issue, researchers have investigated several directions, including how formal argumentation and ontology techniques can be used together for reasoning about intentions to build complex natural language dialogues to support human decision-making [2]. In this paper, we focus on Dung's Abstract Argumentation Framework (AAF), a simple yet powerful formalism for modeling disputes between two or more agents [3], whcih is applicable in modeling dialogues, negotiation [4], persuasion [5], process mining [6], and all that contexts where controversials occur and reasonable solutions should be found. An AAF consists of a set of arguments and a binary attack relation over the set of arguments that specifies the interactions between arguments: intuitively, if argument attacks argument , then is acceptable only if is not. Hence, arguments are abstract entities whose status is entirely determined by the attack relation. An AAF can be seen as a directed graph, whose nodes represent arguments and edges represent attacks. Several argumentation semantics-e.g. grounded (gr), complete (co), preferred (pr), and stable (st) [3]-have been defined for AAF, leading to the characterization of -extensions, that intuitively consist of the sets of arguments that can be collectively accepted under semantics . Example 1. Consider the AAF Λ1 shown in Figure 1 describing the following planning scenario. A party planner invites Alice (a) and Bob (b) to join a party. Alice replies that she will not join the party if Bob does, whereas Bob replies that he will not join the party if Alice does. An argument x states that “(the person whose initial is) x joins the party”. There are two pr-extensions 1 = {a, ¬b} and 2 = {¬a, b} stating that only Alice or only Bob will attend the party, respectively. Herein, an extension represents a solution and is a set of argument literals, where the occurrence of a positive/negative literal x/¬x means that argument x is accepted/rejected-the remaining arguments, if any, are said to be undecided. Thus,

Keywords

• eol>Formal Argumentation
• Epistemic Argumentation

1. Introduction

b b d a b c d a b c e d f a b f a b the presence of two alternative extensions, namely 1 and 2, suggest that the participation of Alice and Bob to the party is uncertain. □

To deal with uncertain information represented by the presence of multiple extensions, credulous and skeptical reasoning has been introduced. Specifically, an argument is credulously/skeptically true (or accepted) if it is contained in any/all extensions. However, uncertain information in AAF under multiple-status semantics proposed so far cannot be exploited to determine the status of arguments by taking into account the information given by the whole set of extensions, as in the case of credulous and skeptical acceptance. To overcome such a situation, and thus provide a natural and compact way for expressing such kind of conditions, the Epistemic AAF (EAAF) has been recently proposed in [ 1 ], where the concept of epistemic arguments and attacks is introduced. Informally, epistemic attacks allow considering all extensions and not only the current one. Therefore, a strong (resp. weak) epistemic attack from to is such that defeats if occurs in any/all extensions.

Example 2. To illustrate the importance of epistemic attacks in knowledge representation, consider the AAF Λ1 and assume there are two more people: Carol (c) and David (d). Carol’s answer is that she will not attend the party if it is sure (i.e. it is skeptically true) that Alice will, whereas David answers that he will not attend the party if the participation of Bob is possible (i.e. it is credulously true). Intuitively, the party planner should conclude that, as the participation of both Alice and Bob is uncertain, Carol will attend the party, whereas David will not. This situation can be modeled by means of the EAAF Δ1 of Figure 1 where a attacks c with a weak epistemic attack, whereas b attacks d with a strong epistemic attack. Under the preferred semantics, there are two extensions: 1 = {a, ¬b, c, ¬d} modeling the fact that Alice and Carol will attend the party, whereas Bob and David will not; and 2 = {¬a, b, c, ¬d} modeling the fact that Bob and Carol will attend the party, whereas Alice and David will not. □

The semantics of EAAF has been defined only for acyclic EAAF (called well-formed in [ 1, 7 ]), where (weak and strong) epistemic attacks cannot be involved in any cycle (as e.g. Δ1). This is a quite strong limitation as cycles involving epistemic attacks are as natural as those involving standard attacks, which are common in real-life argumentation frameworks—the role and effect of cycles in argumentation have been deeply investigated [ 8, 9, 10, 11, 12, 13 ]. In this paper we illustrate a general framework, recently introduced in [ 14, 15 ], where the presence of cycles is allowed. An example of cyclic EAAF is Δ2, shown in Figure 1. Intuitively, continuing with our example, Δ2 represents a scenario where Bob changes his mind: he will not join the party if Alice or David do. The addition of the standard attack (d,b) leads to the cycle (b, d, b) involving the strong epistemic attack (b, d).

2. General Epistemic AAF

Syntax. An Epistemic AAF is a quadruple Δ = ⟨, Ω, Ψ, Φ⟩ where is a set of arguments, Ω ⊆ × is a set of (standard) attacks, Ψ ⊆ × is a set of weak (epistemic) attacks, and Φ ⊆ × is a set of strong (epistemic) attacks such that Ω ∩ Ψ = Ω ∩ Φ = Ψ ∩ Φ = ∅ and Ω[ 2 ] ∩ (Ψ[ 2 ] ∪ Φ[ 2 ]) = ∅, where [] denotes the projection of relation on the i-th element (with ∈ [ 1, 2 ]). Hence, the set of attacks are pairwise disjoint, and arguments cannot be jointly attacked through standard and epistemic attacks. The latter ensures that epistemic arguments, i.e. arguments attacked through epistemic attacks, are deterministic [ 16 ]. We represent attacks (, ) ∈ Ω by → , (, ) ∈ Ψ by ⇒ , (, ) ∈ Φ by →⇒ . An EAAF ⟨, Ω, Ψ, Φ⟩ can be seen as a directed graph, where denotes the set of nodes and Ω, Ψ, and Φ denotes three different kinds of edges. In the following, we consider the acceptability of (argument) literals, that is either an argument or its negation ¬. We use ¬ to denote the set {¬ | ∈ }, and * to denote ∪ ¬. Moreover, for any set of literals , we use + = { | ∈ }, − = { | ¬ ∈ }, and = { | ∈ A ∖ (+ ∪ − )} to denote the set of arguments that occur as positive, negative, and neither positive nor negative literals in , respectively. For any EAAF Δ = ⟨, Ω, Ψ, Φ⟩, a set of (consistent) sets of literals in * such that all ∈ assign the same status (either true, false, or undefined) to every epistemic argument is called world view of Δ. Intuitively, we can think of a world view as a set of candidate extensions where we take a decision on the status of epistemic arguments. Defeated and Acceptable arguments. The definitions of defeated and acceptable arguments for EAAF extends that of AAF [ 3 ], by taking into account the additional concept of world view that is used to decide if an argument is epistemically defeated/acceptable. Given an EAAF Δ, a world view of Δ, and a (consistent) set ∈ , the sets of arguments defeated/accepted w.r.t. and are: • (, ) = { ∈ | (∃ ∈ . → ) ∨ (∃ ∈ . ∃ ∈ . →⇒ ) ∨ (∀ ∈ . ∃ ∈ . ⇒ )}; • (, ) = { ∈ | ∀ ∈ . (( → ) implies ∈ (, ))∧ (( →⇒ ) implies ∀ ∈ . ∈ (, ))∧ (( ⇒ ) implies ∃ ∈ . ∈ (, )).

Given an EAAF Δ = ⟨, Ω, Ψ, Φ⟩ and a world view of Δ, a set ∈ is said to be -conflict-free if + ∩ (, ) = ∅; -admissible if it is -conflict-free, + ⊆ (, ) and − ⊆ (, ); and -complete if it is -conflict-free, + = (, ) and − = (, ). Moreover, a complete set is said to be W-preferred (resp. W-stable, W-grounded) if + is ⊆ -maximal (resp. if + ∪ − = , if + is ⊆ -minimal). Given a world view for EAAF Δ, we use (or simply if is understood) to denote an assignment of truth values to the epistemic arguments (Δ) of Δ w.r.t. , that is, = ∩ (Δ)* where is any element of .

Reduct. Intuitively, the reduct of an EAAF is an AAF which is determined by a choice of the truth values (i.e. acceptance statuses) of the epistemic arguments. Given an EAAF Δ and a truth value assignment for the epistemic arguments (Δ) of Δ, the reduct of Δ w.r.t. (denoted by Δ ) is the AAF obtained from Δ by i) deleting all epistemic attacks and every argument in − , and ii) adding a self-attack to every argument in .

Semantics. Given an EAAF Δ, a semantics , and a truth assignment for the epistemic arguments (Δ) of Δ, we denote by (Δ, ) = { ∪ | ∈ (Δ )} the set of -extensions of Δ under assignment , where (Δ ) is the set of -extensions of AAF Δ . That is, (Δ, ) extends the -extensions of the reduct Δ with the acceptance status of epistemic arguments. Then, a world view for a given EAAF Δ is a -world view for Δ if for every ∈ there exists a unique set ∈ (Δ, ) such that (, ) = − and (, ) = +, and vice versa. Moreover, for = st, = ∅. Thus, a -world view can be obtained by i) fixing a truth value assignment for the epistemic arguments, ii) determining the set of -extensions entailed by the reduct = (Δ, ), and iii) checking that for every ∈ , the conditions (, ) = − and (, ) = + hold, that is each extension in is confirmed by the defeated and accepted sets.

Example 3. Consider the EAAF Δ3 (Figure 1) and the assignment = {c, ¬d}. The reduct Δ3 is shown in Figure 1. Its preferred extensions are {a, ¬b, c, ¬e, f}, {¬a, b, c, e, ¬f}, and {¬a, b, c, ¬e, f}}. Thus, pr(Δ3, ) = ={1 = {a, ¬b, c, ¬d, ¬e, f}, 2 = {¬a, b, c, ¬d, e, ¬f}, 3 = {¬a, b, c, ¬d, ¬e, f}}. As (, ) = − and (, ) = +, for ∈ [1..3], then is a pr-world view. For ′ = {c, d}, we have that pr(Δ3, ′) = ′ = {1′ = {a, ¬b, c, d, ¬e, ¬f}}. Since c is epistemically attacked by a, we have that c ̸∈ ( ′, 1′) (i.e. 1′ ̸= ( ′, 1)), entailing that ′ is not a pr-world view. □ gr co st pr Complexity of i) verification ( ), credulous acceptance ( ), and skeptical acceptance ( ) problems for AAF; ii) verification ( ) and epistemic acceptance ( ) problems for acyclic EAAF; and iii) possible and necessary verification ( and ) as well as possible and necessary epistemic acceptance ( and ) problems for (general) EAAF. For a class , -c (resp. -h) means -complete (resp. -hard); an interval -h, ′ means -hard and in ′. Complexity.

We discuss the recent complexity analysis for two fundamental reasoning problems for EAAF [ 1, 14, 15 ]: the verification and credulous/skeptical acceptance problems, that are usually considered for analyzing the computational complexity of argumentation frameworks [ 18, 19, 20, 17, 21 ]. To deal with multiple world views, the possible and necessary variants of those problems are recalled in what follows—this is somehow analogous to the approach adopted for instance in incomplete AAF [ 19 ] where multiple completions may exist, each corresponding to a possible materialization of uncertain arguments and attacks. Given an EAAF Δ = ⟨, Ω, Ψ, Φ⟩ and a semantics ∈ {gr, co, pr, st}: every) world view of Δ. • the possible (resp. necessary) verification problem for EAAF, denoted as (resp. ), consists in deciding whether a given set of literals ⊆ * is in any (resp. every) -world view of Δ; • the possible (resp. necessary) credulous acceptance problem, denoted as (resp. ), consists in deciding whether a given goal argument ∈ belongs to any -extension of any (resp. (resp. every) world view of Δ. • the possible (resp. necessary) skeptical acceptance problem, denoted as (resp. ), consists in deciding whether a given goal argument ∈ belongs to every -extension of any Observe that if argument is epistemic, then credulous and skeptical reasoning coincide. In fact, since epistemic arguments are deterministic, their acceptance status does not change in different extensions of a world view (though may change in different world views). Thus, possible (resp. necessary) credulous and skeptical acceptance problems coincide, and we this problem can be simply called possible (resp. necessary) epistemic acceptance, denoted as (resp. ).

The complexity results are summarized in Table 1. While the complexity lower- and upper-bounds provided for are the same of those for (i.e. for acyclic EAAF), the complexity bounds for suggest that necessary verification turns out to be computationally more expensive. This is evident for the grounded and stable semantics, where gr and st become coNP-complete and Π2 -complete, respectively. Moreover, considering the results for the grounded and stable semantics, it turns out that the acceptance problem is harder than in case of acyclic EAAF. Overall, the complexity results confirms the intuition that general EAAF is more expressive than acyclic EAAF.

3. Conclusion

We have discussed a natural, declarative semantics for general (possibly cyclic) EAAFs that extends that of AAF as well as that of acyclic EAAF. Differently from the case of acyclic EAAF, whose semantics prescribes a single world view, an EAAF may have multiple world views. In general, we may have cyclic EAAFs with multiple or single world views. Interesting future work could include the investigation of the computational complexity of canonical argumentation problems in general EAAF, as done for other frameworks extending AAF e.g. [ 1, 22, 16, 23, 24, 25, 20, 18, 21, 19, 26, 27, 28 ].

Acknowledgments

The research reported in the paper has been supported by the PNRR MUR projects PE0000013-FAIR and PE0000014-SERICS, project Tech4You ECS0000009, and MUR project PRIN 2022 EPICA (CUP H53D23003660006).

Declaration on Generative AI

The author(s) have not employed any Generative AI tools. [20] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On acceptance conditions in abstract argumentation frameworks, Inf. Sci. 625 (2023) 757–779. [21] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, Complexity of credulous and skeptical acceptance in epistemic argumentation framework, in: Proc. of AAAI, 2024, pp. 10423–10432. [22] G. Alfano, S. Greco, D. Mandaglio, F. Parisi, I. Trubitsyna, Abstract argumentation frameworks with strong and weak constraints, Artificial Intelligence 336 (2024) 104205. [23] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On preferences and priority rules in abstract argumentation, in: Proc. of IJCAI, 2022, pp. 2517–2524. [24] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, Abstract argumentation framework with conditional preferences, in: Proc. of AAAI, 2023, pp. 6218–6227. [25] G. Alfano, M. Calautti, S. Greco, F. Parisi, I. Trubitsyna, Explainable acceptance in probabilistic and incomplete abstract argumentation frameworks, Artif. Intell. 323 (2023) 103967. [26] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On acceptance conditions in abstract argumentation frameworks, Information Sciences 625 (2023) 757–779. [27] G. Alfano, A. Cohen, S. Gottifredi, S. Greco, F. Parisi, G. R. Simari, Credulous acceptance in high-order argumentation frameworks with necessities: An incremental approach, Artif. Intell. 333 (2024) 104159. [28] G. Alfano, S. Greco, F. Parisi, G. I. Simari, G. R. Simari, Incremental computation for structured argumentation over dynamic delp knowledge bases, Artif. Intell. 300 (2021) 103553.

References

[1] G. Alfano , S. Greco , F. Parisi , I. Trubitsyna , Epistemic abstract argumentation framework: Formal foundations, computation and complexity , in: Proc. of AAMAS , 2023 , pp. 409 - 417 .

[2] D. C. Engelmann , Intentional dialogues in multi-agent systems based on ontologies and argumentation , PhD Thesis , University of Genova, Italy ( 2023 ).

[3] P. M. Dung , On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games , Artif. Intell . 77 ( 1995 ) 321 - 358 .

[4] Y. Dimopoulos , J. Mailly , P. Moraitis , Argumentation-based negotiation with incomplete opponent profiles , in: Proc. AAMAS , 2019 , pp. 1252 - 1260 .

[5] H. Prakken , Models of persuasion dialogue , in: Argumentation in Artificial Intelligence , 2009 , pp. 281 - 300 .

[6] B. Fazzinga , S. Flesca , F. Furfaro , L. Pontieri, Process mining meets argumentation: Explainable interpretations of low-level event logs via abstract argumentation , Inf. Syst . 107 ( 2022 ) 101987 .

[7] G. Alfano , S. Greco , F. Parisi , I. Trubitsyna , Stable semantics for epistemic abstract argumentation framework , in: Proc. of Arg&App@KR , 2023 , pp. 11 - 25 .

[8] P. Baroni , M. Giacomin , Solving semantic problems with odd-length cycles in argumentation , in: Proc. of ECSQARU , 2003 , pp. 440 - 451 .

[9] T. J. M. Bench-Capon , Dilemmas and paradoxes: cycles in argumentation frameworks , J. Log. Comput . 26 ( 2016 ) 1055 - 1064 .

[10] G. A. Bodanza , F. A. Tohmé , G. R. Simari , Beyond admissibility: accepting cycles in argumentation with game protocols for cogency criteria , J. Log. Comput . 26 ( 2016 ) 1235 - 1255 .

[11] R. Baumann , M. Ulbricht , On cycles, attackers and supporters - A contribution to the investigation of dynamics in abstract argumentation , in: Proc. of IJCAI , 2021 , pp. 1780 - 1786 .

[12] W. Dvorák , M. König , S. Woltran , On the complexity of preferred semantics in argumentation frameworks with bounded cycle length , in: Proc. of KR , 2021 , pp. 671 - 675 .

[13] M. Lagasquie-Schiex , Handling support cycles and collective interactions in the logical encoding of higher-order bipolar argumentation frameworks , J. Log. Comput . 33 ( 2023 ) 289 - 318 .

[14] G. Alfano , S. Greco , F. Parisi , I. Trubitsyna, General epistemic abstract argumentation framework: Semantics and complexity , in: Proc. of IJCAI , 2024 , pp. 3206 - 3214 .

[15] G. Alfano , S. Greco , F. Parisi , I. Trubitsyna , On general epistemic abstract argumentation frameworks , in: Proc. of AAMAS , 2024 , pp. 2117 - 2119 .

[16] G. Alfano , S. Greco , F. Parisi , I. Trubitsyna , Incomplete argumentation frameworks: Properties and complexity , in: Proc. of AAAI , 2022 , pp. 5451 - 5460 .

[17] W. Dvorák , P. E. Dunne , Computational problems in formal argumentation and their complexity , FLAP 4 ( 2017 ).

[18] G. Alfano , S. Greco , D. Mandaglio , F. Parisi , I. Trubitsyna , Complexity of verification and existence problems in epistemic argumentation framework , in: Proc. of ECAI , volume 372 , 2023 , pp. 77 - 84 .

[19] D. Baumeister , M. Järvisalo , D. Neugebauer , A. Niskanen , J. Rothe , Acceptance in incomplete argumentation frameworks, Artif . Intell. ( 2021 ) 103470 .