Dung's Abstract Argumentation Framework (AAF) has emerged as a central formalism in AI for modeling disputes among agents. A recent extension of the Dung's framework is the so-called Epistemic Abstract Argumentation Framework (EAAF), which enhances AAF by allowing the representation of some pieces of epistemic knowledge [1]. EAAF generalizes the concept of attack in AAF, introducing strong and weak epistemic attacks, whose intuitive meaning is that an attacked argument is epistemically accepted only if the attacking argument is possibly or certainly rejected, respectively. The semantics of EAAF has been de ned and studied for several argumentation semantics but not for the stable one, which is arguably one of the most investigated semantics in argumentation. Motivated by this, in this paper, we propose an intuitive stable semantics for EAAF that naturally extends that for AAF and coincides with the preferred semantics in the case of odd-cycle free EAAFs (analogously to what happens in the case of AAF). We analyze the complexity of two argumentation problems: existence, i.e. checking whether there is at least one epistemic extension; and acceptance, i.e. checking whether an argument is epistemically accepted.
In the last decades, Argumentation [
Dung’s Abstract Argumentation Framework (AAF) is a simple yet powerful formalism for
modeling disputes between two or more agents [
Example 1. Consider an AAF = {a, b}, {(a, b), (b, a)} whose corresponding graph is shown in Figure 1(left). describes the following scenario. A party planner invites Alice (a) and Bob (b) to join a party. Due to their old rivalry (i) Alice replies that she will not join the party if Bob does, and (ii) Bob replies that he will not join the party if Alice does. This situation can be modeled by AAF , where an argument x states that “(the person whose initial is) x joins the party”. Under the stable semantics, there are two extensions E1 = {a} and E2 = {b} stating that only Alice or only Bob will attend the party, respectively.
Thus, as prescribed by E1 and E2, in the previous example we have 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.
Speci cally, an argument is credulously true (or accepted) if there exists an extension containing
the argument, whereas an argument is skeptically true if it occurs in all extensions. However,
uncertain information in AAF under multiple-status semantics proposed so far cannot be
exploited to determine the status of arguments (which in turn in uences the status of other
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 use of epistemic
arguments and attacks has been recently proposed in [
This situation can be modeled by means of the Epistemic AAF (EAAF) shown in Figure 1(right)
where a defeats c with a weak epistemic attack, whereas b defeats d with a strong epistemic
attack (we use the two kinds of edges represented in the gure to denote weak and strong
epistemic attacks). Under the stable semantics, there are two extensions: E1 = {a, c} modeling
the fact that Alice and Carol will attend the party, whereas Bob and David will not; and
E2 = {b, c} modeling the fact that Bob and Carol will attend the party, whereas Alice and
David will not. Observe that the epistemic arguments c and d (i.e. the arguments defeated by
an epistemic attack) are deterministic [
Our complexity results are summarized in Table 2 (in Section 4).
We rst review the Dung’s framework and then discuss and an extension of AAF with epistemic constraints.
An Abstract Argumentation Framework (AAF) is a pair A, , where A is a ( nite) set of
arguments and A A is a set of attacks (also called defeats). Di erent argumentation
semantics have been proposed for AAF, leading to the characterization of collectively acceptable
sets of arguments called extensions [
Given an AAF = A, and a set S A of arguments, an argument a A is said to be i) defeated w.r.t. S i b S such that (b, a) ; ii) acceptable w.r.t. S i b A with (b, a) , c S such that (c, b) . The sets of defeated and acceptable arguments w.r.t. S are de ned as follows (where is understood): • Def(S) = {a A | b S . (b, a) }; • Acc(S) = {a A | b A . (b, a) implies b Def(S)}.
To simplify the notation, we will often use S+ to denote Def(S).
Given an AAF A, , a set S • con ict-free i S S+ = ; • admissible i it is con ict-free andS Acc(S).
Given an AAF A, , a set S A is an extension called:
• complete (co) i it is con ict-free andS = Acc(S); • preferred (pr) i it is a -maximal complete extension; • stable (st) i it is a total complete extension, i.e. a complete extension such thatS S+ = A; • grounded (gr) i it is the -smallest complete extension.
The set of complete (resp. preferred, stable, grounded) extensions of an AAF will be denoted by co() (resp. pr() , st() , gr() ). It is well-known that the set of complete extensions forms a complete semilattice w.r.t. , where gr() is the meet element, whereas the greatest elements are the preferred extensions. All the above-mentioned semantics except the stable admit at least one extension. The grounded semantics, that admits exactly one extension, is said to be a unique-status semantics, while the others are said to be multiple-status semantics. With a little abuse of notation, in the following we also use gr() to denote the grounded extension. For any AAF , st() pr() co() and gr() co() .
Example 3. Let = A, be an AAF where A = {a, b, c} and = {(a, b), (b, a), (b, c)}, whose graph is show in Figure 2 (left). The set of complete extensions of is co() = {E0 = , E1 = {a, c}, E2 = {b}}. E0 is the grounded extension, while E1 and E2 are preferred and stable extensions.
Given an AAF = A, and a semantics {gr, co, pr, st}, for g A, the credulous (resp. skeptical) acceptance problem, denoted as CA (resp. SA ) is deciding whether g is credulously (resp. skeptically) accepted, that is deciding whether g belongs to any (resp. every) -extension of . Clearly, CAgr and SAgr coincide.
Recently, a satisfaction problem for AAF called determinism (DS ) has been introduced [
Finally, the existence (resp. non-empty existence) problem denoted as Ex (resp. Ex¬ ) is deciding whether there exists at least one (resp. at least one non-empty) -extension for AAF .
For AAFs, the complexity of the existence and acceptance problems has been investigated
(see [
Considering the AAF obtained from by adding the self-attack (c, c) (see Figure 2 (right)), there are three complete extensions E0 = , E1 = {a} and E2 = {b}. Both E1 and E2 are preferred extensions, but only E2 is stable.
An Epistemic Argumentation Framework (EAF) has been proposed in [
We point out that despite the name Epistemic Argumentation Framework is used, the role of
epistemic formulae is only that of introducing constraints over the set of feasible extensions,
that is it is similar to that of constraints or preferences in AAF [
We augment AAF with epistemic attacks, leading to the concept of Epistemic Abstract Argumentation Framework (EAAF).
De nition 1 (Epistemic AAF). An Epistemic AAF is a quadruple = set of arguments, A A is a set of (standard) attacks, A attacks, and A A is a set of strong (epistemic) attacks such that
A, , , where A is a A is a set of weak (epistemic) = = = .
In the following, we represent attacks (a, b) by a b, (a, b) by a b, (a, b) by a b. An EAAF A, , , can be seen as a directed graph, where A denotes the set of nodes and , , and denotes three di erent kinds of edges. Arguments defeated through epistemic attacks are called epistemic arguments.
We say that there is a path from an argument a A to argument b A if either (i) there exists an attack (a, b) in or (ii) there exists an argument c A and two paths, from a to c and from c to b. We say that an argument b A depends on an argument a A if b is reachable from a in , that is, if there exists a path from a to b in . Moreover, an argument a depends on attack ( ) if there exists a path in that contains and reaches a.
We now introduce well-formed and plain EAAFs.
De nition 2. An EAAF
is said to be: • well-formed if there are no cycles in
with epistemic edges. • in plain form if every epistemic argument is attacked by a single (epistemic) attack. a b c d e f a b a b c a b d e f , and of Example 9.
In the following we assume that our EAAFs are well-formed. The reason for such a restriction is to guarantee that there exists at most one world view (c.f. Theorem 1). In the following we also assume that our EAAFs are in plain form. As it will be clear after introducing EAAF semantics, for well-formed EAAFs in plain form, epistemic arguments are deterministic (c.f. Proposition 2). Example 6. The EAAF = A = {a, b, c, d}, = {(a, b), (b, a)}, = {(a, c)}, = {(b, d} of Example 2, whose graph is shown in Figure 1 (right), is well-formed and in plain form.
The semantics of EAAF is given by relying on the concept of sub-framework (sub-EAAF), which is de ned as follows.
De nition 3. Given two EAAFs and , we say that is a sub-EAAF of (denoted as ) if is obtained from by deleting a subset S of the set of epistemic arguments of and all the arguments depending on an argument in S w.r.t. . Moreover, we write if and = .
Clearly, in De nition3 by deleting arguments we also delete attacks having as a source or target element a deleted argument.
Example 7. Consider the EAAF = {a, b, c, d, e, f}, {(a, b), (b, a), (a, e), (d, f), (e, f), (f, e)}, {(a, c)}, {(b, d)} shown in Figure 3 (left). We have four sub-EAAFs , as shown in the gure: the rst one (from left to right) coincides with , the others are obtained by deleting all arguments depending on: (i) both arguments c and d, (ii) only d, and (iii) only c, respectively.
We rst introduce thestable semantics of EAAF and then present some results concerning properties of the proposed framework.
For any EAAF = A, , , , a set W of sets of arguments in A is called world view of . Informally, a world view can be seen as a set of extensions that are to be used to compute the status of epistemic arguments. Given EAAF = A , , , , we denote by W = {S A | S W } the projection of W over A .
With the aim of providing EAAF semantics by extending AF semantics, we rst extend the de nitions of defeated and acceptable arguments for EAAF by taking into account the additional concept of world view, that is a candidate set of extensions, which is used to decide if an argument is epistemically defeated/acceptable. Given an EAAF , a world view W of , and a set S follows: • Def (W, S) = {b • Acc(W, S) = {b
A | ( a ( T ( T A | a ((a ((a ((a
S . a W . a W . a b)
T . a
T . a A .
b) implies a b) implies b) implies b) b)}.
T T
Def (W, S))
W . a Def (W, T ))
W . a Def (W, T )).
W , the sets of arguments defeated (resp. accepted) w.r.t. S and W are de ned as Example 8. Considering the EAAF of Example 7 and the world view W = {S1 = {c}, S2 = {a, c}, S3 = {b, c}}, we have that: • Def (W, S1) = {d}
and Acc(W, S1) = {c}; • Def (W, S2) = {b, d} and Acc(W, S2) = {a, c}; and • Def (W, S3) = {a, d} and Acc(W, S3) = {b, c}.
Given an EAAF =
A, , , and a world view W of , a set S
W is: • W-con ict-free if S
Def (W, S) = ; • W-admissible if it is W-con ict-free andS
Acc(W, S); • W-complete (W -co) if it is W-con ict-free andS = Acc(W, S).
• W-preferred (W -pr) if S is -maximal; • W-stable (W -st) if S
Def (W, S) = A; • W-grounded (W -gr) if S is -minimal.
We are now ready to de ne EAAF semantics.The meaning of EAAF under the grounded,
complete and preferred semantics has been introduced in [
of EAAF . Then, W is a -world view for {gr, co, pr, st} be a semantics and W a world view
if the following conditions hold: (i) every S
W is a W
- set, and (ii) there is no world view W .
for such that W
W and every S
W is W - for { , {a}, {b}} {{a}, {b}} {{c}, {a, c}, {b, c}} {{a, c}, {b, c}} { , {f}, {a, f}, {b}, {b, e}, {b, f}} {{a, f}, {b, e}, {b, f}} {{c}, {c, f}, {a, c, f}, {b, c}, {b, c, e}, {b, c, f}} {{a, c, f}, {b, c, e}, {b, c, f}}
We now explain De nition4. Given a semantics , a W - set intuitively represents a candidate
set of -extensions for an EAAF. Then, such a set turns out to actually be a set of extensions
if the conditions in De nition4 hold, whose rationale is as follows. Given a world view W
of an EAAF , we check that for all sub-frameworks , every element S W = W is a
W - set (condition i) and W is maximal (condition ii). Intuitively, the rst condition ensures
that the status of an argument is con rmed in all sub-frameworks considered. The second
condition of De nition4 ensures that, if there is a larger -world view for which condition i)
holds, then we prefer to take it. That is, intuitively, we aim at having the whole set of extensions.
In [
It is worth noting that whenever = = , we have that the de nitions of defeated and acceptable arguments coincide with the ones de ned for AAF, that isDef ({S}, S) = Def (S) and Acc({S}, S) = Acc(S). This lead to the following result that states that EAAF semantics extends that of AAF.
Proposition 1. Let = the AAF corresponding to
A, , , be a well-formed EAAF with = = , and = A,
. Then, if st() = then st() is the only stable-world view of .
Clearly, as stable semantics is not guaranteed to exist in AAF, the same holds in EAAF. Indeed, as stated next, any well-formed EAAF has at most one stable world view.
Theorem 1. Any well-formed EAAF admits at most one st-world view.
For any (well-formed) EAAF and semantics {gr, co, pr, st} we use () the -world view of , and will often call its elements -extensions. to denote Example 9. Continuing with Example 7, Table 1 reports the -world view for each EAAF in Figure 3 and {gr, co, pr, st}.
Now, consider the EAAF (shown in Figure 3), the world view W = {S = {a}}, and the stable semantics. If in De nition4 we had only focused on the given EAAF without looking at its sub-frameworks, as S is a W -stable set and W is maximal (i.e., both conditions (i) and (ii) of De nition4 are satis ed if focusing on only), we would have concluded that c is defeated. However, we had expected that c would have been accepted. Indeed, according to De nition4, the only stable-world view of is W = {{a, c}, {b, c}} (cf. Table 1). In fact, considering the sub-framework (cf. Figure 3) obtained from by deleting the epistemic argument c, the only stable-world view of is W = W = {{a}, {b}}, which using De nition4 allows us to discard W = {{a}} from being a stable-world view of .
According to the proposed EAAF semantics, epistemic arguments are deterministic, that is, they have the same “truth assignment” in a world view, that in turn depends on either the credulous or skeptical acceptance of its attackers.
Proposition 2. Let = A, , , be an EAAF, and W the st-world view of . Then, any epistemic argument x A is deterministic, that is, one of the following three conditions hold: i) S W . x Acc(W, S); ii) S W . x Def (W, S); iii) S W . x (Acc(W, S) Def (W, S)).
An alternative way to de nestable extensions for EAAF could be that of choosing among complete extensions those that are total, as it is done for AAF. More in detail, given an EAAF and its complete-world view W = co() , we could have de ned thestable-world view for as st() = {S W | S Def (W, S) = A} ). This is di erent from what is done in De nition4 where to de ne ast-world view we start with a world view W that is not necessarily co() . However, the above-mentioned alternative way to de nestable extensions for EAAF may lead to counter-intuitive solutions, as shown in the following example.
Example 10. Consider the EAAF = {a, b, c, d}, {(a, b), (b, a), (a, c), (b, c)}, {(c, d)}, , shown in Figure 4, and the stable semantics. Intuitively, the strong epistemic attack states that d is accepted if c is skeptically rejected. The stable extensions of , that is, the elements in its st-world view are {a, d} and {b, d}. Thus, we obtain that c is skeptically defeated and, consequently, d is accepted.
However, if we start with the complete-world view co() , we have that there are three complete extensions S1 = , S2 = {a} (with b and c defeated and d undecided) and S3 = {b} (with a and c defeated and d undecided). As there are no total sets in co() , we conclude that under the above-mentioned “alternative” stable semantics there is no stable status for d and c , contradicting our intuition.
As stated next, di erently from AAF,stable extensions are not guaranteed to be complete extensions of EAAF. Related to this, even in AAF credulous and skeptical acceptance may give di erent results under di erent semantics.
Proposition 3. There exists an EAAF such that S st() and S co() .
Particularly, consider the EAAF = {a, b, c, d, e, f}, {(a, b), (b, a), (a, c), (b, c), (c, d)}, {(d, e) (e, f)}, . With a little e ort, it ca be checked thatst() = {S1 = {a, d, f}, S2 = {b, d, f}} and co() = { , {a, d}, {b, d}}, and thus neither S1 co() nor S2 co() .
Finally, stable semantics coincides with preferred semantics in case of odd-cycle free EAAFs. Proposition 4. Let be a well-formed, odd-cycle free EAAF. Then, it holds that st() = pr() .
We investigate the complexity of two fundamental reasoning problems for EAAF under stable semantics. In particular, we study the existence and credulous/skeptical acceptance problems, that are often considered for analyzing the complexity of argumentation frameworks.
We recall the main complexity classes used in this section and, in particular, the de nition
of the classes P, ph, ph and ph, with h 0 (see e.g. [
Given an EAAF = A, , , and a semantics {gr, co, pr, st}: • the existence (resp. non-empty existence) problem for EAAF, denoted as Ex (resp. Ex¬ ) consists in deciding whether there exists at least one (resp. at least one non-empty) -extension S for ; • the credulous (resp. skeptical) acceptance problem, denoted as CA (resp. SA ), consists in deciding whether a given goal argument g A belongs to any (resp. every) -extension of .
Observe that if argument g is epistemic, credulous and skeptical acceptance problems coincide (cf. Proposition 2). Therefore, we call this problem epistemic acceptance and denote it as EA .
The following fact states that the epistemic acceptance problem captures the credulous and skeptical acceptance problems also for non-epistemic arguments under stable semantics. Fact 1. Let =
A, , , be an EAAF, g
A any of its non-epistemic arguments. Then: • CAst( , g) = EAst( , g ) with • SAst( , g) = EAst( , g ) with = A = A {g , g }, {g , g }, {(g, g )}, {(g, g )}, , {(g , g )}, {(g , g )} .
Thus, asking for the credulous and skeptical acceptance of an argument g w.r.t. an EAAF is equivalent to asking for the epistemic acceptance of a fresh epistemic argument g w.r.t. an EAAF , that is obtained from by adding only a pair of attacks.
For this reason and for the fact that epistemic arguments are deterministic (Proposition 2), w.l.o.g. we study the complexity of existence and epistemic acceptance problems in EAAFs (without considering credulous and skeptical acceptance that, as shown above, can be immediately reduced to epistemic acceptance).
The next theorem states the complexity of epistemic acceptance under stable semantics. Theorem 2. EAst is DP-hard.
The following corollary states that for EAAF the existence of at least one extension is not always guaranteed, as for the case of AAF.
Corollary 1. Exst coincides with Ex¬st and it is NP-hard.
The results of this section, along with some related complexity results for AAF, are
summarized in Table 2. We have also reported the results for {gr, co, pr} which are from [
Several proposals have been made to extend Dung’s framework with the aim of better modeling
the knowledge to be represented. The extensions include Bipolar AAF [
We have presented the stable semantics for Epistemic Abstract Argumentation Framework, a generalization of Dung’s framework where epistemic attacks and arguments can be expressed. We also provided complexity bounds for the existence and acceptance problems in EAAF under the well-known stable argumentation semantics. Our complexity analysis shows that the epistemic elements (i.e., epistemic attacks/arguments) impact on the complexity of some of the problems considered. In general, it turns out that EAAF is more expressive than AAF.
The idea of extending logic with epistemic constructs has been investigated also in the eld
of Answer Set Programming (ASP) [
Although our focus is on argumentation, we believe that our results could be of interest
to the logic community. In fact, by exploiting the correspondence between AF and Logic
Programming [
Future work will be devoted to considering other argumentation semantics such as the
semistable semantics. Another interesting direction for future work is exploring EAF in a dynamic
setting [
We acknowledge the support of the PNRR project FAIR - Future AI Research (PE00000013), Spoke 9 - Green-aware AI, under the NRRP MUR program funded by the NextGenerationEU. This work was also funded by the Next Generation EU - Italian NRRP, Mission 4, Component 2, Investment 1.5, call for the creation and strengthening of ‘Innovation Ecosystems’, building ‘Territorial R&D Leaders’ (Directorial Decree n. 2021/3277) - project Tech4You - Technologies for climate change adaptation and quality of life improvement, n. ECS0000009. This work re ects only the authors’ views and opinions, neither the Ministry for University and Research nor the European Commission can be considered responsible for them.