# admissibility_in_probabilistic_argumentation__5983cb32.pdf

Journal of Artiﬁcial Intelligence Research 74 (2022) 957 1009 Submitted 12/2021; published 06/2022

Admissibility in Probabilistic Argumentation

Nikolai K afer nikolai.kaefer@tu-dresden.de Christel Baier christel.baier@tu-dresden.de Martin Diller martin.diller@tu-dresden.de Clemens Dubslaﬀ clemens.dubslaff@tu-dresden.de Sarah Alice Gaggl sarah.gaggl@tu-dresden.de Faculty of Computer Science Technische Universit at Dresden Dresden, Germany

Holger Hermanns hermanns@cs.uni-saarland.de Saarland Informatics Campus Saarland University Saarbr ucken, Germany

Institute of Intelligent Software Guangzhou, China

Abstract argumentation is a prominent reasoning framework. It comes with a variety of semantics and has lately been enhanced by probabilities to enable a quantitative treatment of argumentation. While admissibility is a fundamental notion for classical reasoning in abstract argumentation frameworks, it has barely been reﬂected so far in the probabilistic setting. In this paper, we address the quantitative treatment of abstract argumentation based on probabilistic notions of admissibility. Our approach follows the natural idea of deﬁning probabilistic semantics for abstract argumentation by systematically imposing constraints on the joint probability distribution on the sets of arguments, rather than on probabilities of single arguments. As a result, there might be either a uniquely deﬁned distribution satisfying the constraints, but also none, many, or even an inﬁnite number of satisfying distributions are possible. We provide probabilistic semantics corresponding to the classical complete and stable semantics and show how labeling schemes provide a bridge from distributions back to argument labelings. In relation to existing work on probabilistic argumentation, we present a taxonomy of semantic notions. Enabled by the constraintbased approach, standard reasoning problems for probabilistic semantics can be tackled by SMT solvers, as we demonstrate by a proof-of-concept implementation.

1. Introduction

In its basic form, an abstract argumentation framework (AF) (Dung, 1995) consists of a set of abstract arguments together with a binary relation that represent conﬂicts between arguments, the so-called attack relation. AFs are popular to describe contentious information and draw conclusions from it using formalized arguments. The popularity of the AF concept has led to a variety of extensions like notions to handle preferences and values on arguments (Amgoud & Cayrol, 2002; Bench-Capon, 2003), weights (Dunne et al., 2011), probabilities (Li, Oren, & Norman, 2011; Thimm, 2012; Hunter, 2013) or introducing a positive inﬂuence relation between arguments, so-called supports (Amgoud et al., 2008;

2022 AI Access Foundation. All rights reserved.

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

Figure 1: Exemplary sensor layout of a semi-autonomous vehicle

Nouioua & Risch, 2011). Furthermore, abstract dialectical frameworks (ADFs) as a powerful generalization of Dung s framework have been introduced (Brewka & Woltran, 2010; Brewka et al., 2013; Straß & Wallner, 2015; Gaggl et al., 2021), which also allow to handle probabilities (Polberg & Doder, 2014). In this paper, we focus on the emerging ﬁeld of AFs in the probabilistic setting. As a concrete example to ground our discussion, we consider an argumentation-based decision framework for a semi-autonomous vehicle as depicted in Figure 1. Here, a central decision entity (the supervisor , see Faqeh et al., 2020) has access to possibly conﬂicting information from several sensors (left/right camera, lidar sensor) with overlapping sensing areas in front of the vehicle. The sensor values are assumed to be of a Boolean nature and indicate whether an obstacle is detected. They together induce reasons to assume that there is or is not an obstacle in some speciﬁc area in front of the vehicle. The supervisor aggregates this information in order to decide whether to continue moving forward. We translate this scenario into an argumentation setting as follows. We use literals cl and cl to denote arguments expressing that the left camera has detected an obstacle or not, and similar for the right camera (cr and cr) and for the lidar sensor (ld and ld). Slightly more complex arguments represent reasons for and against an obstacle being either on the left (l and l), the right (r and r), or in the middle (m and m) of the area ahead of the vehicle. For example, the argument cl l expresses that a silent left camera sensor backs the conclusion that there is no obstacle on the left. The literals ct and st indicate that the vehicle should continue ahead or stop respectively. The resulting argument graph is depicted in Figure 2, with nodes representing arguments and directed edges representing attacks. In particular, we see ﬁrst of all that contrary sensor readings attack each other (e.g., cr and cr). Also, arguments about sensors can undermine arguments about the location of obstacles (e.g., cl undermines cl l) while arguments about the location can rebut each other when they make contradictory claims (e.g., cl m and ld m rebut each other). Moreover, arguments for an obstacle being in the middle can counter the decision to continue (e.g., ld m attacks ct), while the decision to continue invalidates the decision to stop (ct attacks st). This reﬂects that if there is no reason to

Admissibility in Probabilistic Argumentation

Figure 2: Argument graph for the vehicle example

assume that there is an obstacle in the middle, the vehicle will continue driving. Otherwise, it will need to stop1. We are now interested in the situation where the degree of acceptance of arguments lies on a continuum. For instance, object detection by the right camera might fail with some probability (false negatives), spurious detections may be possible (false positives), and the spatial layout of the overlapping camera views may give quantitative information where to expect an object, albeit the information provided may not be clear-cut. This implies that there will be diﬀerent degrees of uncertainty whether to continue moving forward or not. This motivation helps to understand why there is a growing body of inspiring research on probabilistic abstract argumentation frameworks (Pr AFs). In this paper, we contribute to this research spectrum taking a probability-theoretic perspective based on the epistemic approach (see Section 4 for an overview). We start oﬀfrom the idea that a Pr AF induces probability distributions over various arguments being accepted or not. Just like classical AFs can induce potentially multiple valid interpretations (called extensions2 in the literature), a Pr AF can induce multiple such distributions. We embark on extending the basic notions of classical argumentation theory to the probabilistic setting in a conservative manner. In this, we take the fairly natural view that no argument and its attackers may be accepted at the same time. This does not mean that both views on an argument and its attacker cannot have non-zero probability, but simply that the probability of an argument

1. To model the arguments and obtain the argument graph we base ourselves on the ASPIC+ framework (Modgil & Prakken, 2018). Speciﬁcally, we use ASPIC+ with possibly non-symmetric negation. Then the ASPIC+ framework underlying our example consists of the ordinary premises {cl, cr, ld, cl, cr, ld, ct, st} (i.e., these are uncertain and can be attacked) and defeasible rules {cl l, cl m, cl l, cl m, cr r, cr m, cr r, cr m, ld m, ld m}. Note that in our example we use the same notation for arguments as for the rules underlying them. There are no axiom premises nor are there strict rules in our example. Dual literals (e.g., cl and cl as well as m and m) are contradictories of each other while m is the contrary of ct and ct is the contrary of st. 2. In this paper, we avoid using extension in this sense, and instead use this term to identify probabilistic semantics that are conservative extensions of classical AF semantics, see Deﬁnition 5.

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

and its attacker being simultaneously accepted is zero by construction. Similarly, we would like to ensure that accepted arguments are defended, meaning that each of their attackers are attacked with a probability of one. This is indeed needed for making sense of scenarios like the vehicle example above, but is in contrast to earlier work on Pr AFs (Hunter & Thimm, 2017) where probabilities of single arguments were put in focus. When lifting the classical concepts from AFs to Pr AFs, especially the notion of admissibility gives rise to a hierarchy of diﬀerent interpretations and leads to an entire taxonomy of semantics. Along this discussion, it becomes apparent that each lifted semantics concept imposes a set of constraints on the joint probability distributions of arguments to be accepted or not. We will show in this paper that, with one exception, all these sets of constraints we consider are linear, i.e., they are expressible in the linear arithmetic theory of the reals. Among others, this gives us decidability and bridges to the world of SMT solvers, which are nowadays well capable of handling large sets of linear and even non-linear constraints. Indeed, we present a prototypical tool for studying a variety of questions arising in a Pr AF. Speciﬁcally, we apply the tool to the above vehicle example to pinpoint some ﬁne details that help to understand our contribution as well as getting an impression of practical relevance. For example, the tool can compute a distribution maximizing the value of ct assuming that cl and ld are accepted almost surely with additional constraints on the rate of false positives for the sensors, while satisfying a particular semantics (or even sets thereof). The tool and all experimental data are publicly available at https://www.perspicuous-computing.science/cpraa

In summary, our contribution is fourfold:

(i) We provide a profound study of admissibility as well as complete and stable semantics in a probability-theoretic approach to abstract argumentation,

(ii) discuss a hierarchy of resulting semantics in the context of earlier work,

(iii) investigate the complexity of established computational problems lifted to the probabilistic setting, and

(iv) present prototypical tool support for experimenting with these semantics and further context-speciﬁc constraints.

We structured the paper as follows. In Section 2 we introduce the necessary background on abstract argumentation, as well as notations needed for the probabilistic setting such as assignments and distributions. Our probabilistic argumentation framework is presented in Section 3, where we lift classical argumentation semantics to the probabilistic setting and discuss our probabilistic notions of admissibility, complete semantics, saturation, and labeling schemes. We relate our semantics to the existing (probabilistic) semantics and further related work in Section 4 before we discuss the complexities of various probabilistic argumentation decision problems in Section 5. Details about our implementation and experimental studies on the vehicle example are provided in Section 6. We close the paper with concluding remarks and further work (Section 7). This paper is the journal version of the conference publication (Baier, Diller, Dubslaﬀ, Gaggl, Hermanns, & K afer, 2021), containing full proofs and enhancing our framework by saturation semantics, labeling schemes, and complexity-theoretic considerations.

Admissibility in Probabilistic Argumentation

2. Preliminaries

In this section, we introduce the basics of abstract argumentation along with classical argumentation semantics on which we base our probabilistic abstract argumentation framework. We start with a deﬁnition of abstract argumentation frameworks following (Dung, 1995). For a detailed discussion on argumentation semantics we refer to (Baroni, Caminada, & Giacomin, 2011).

Deﬁnition 1. An abstract argumentation framework (AF) is a pair F = Arg, Att where Arg is a ﬁnite set of arguments and Att Arg Arg an attack relation.

A pair (A, B) Att means that argument A attacks argument B. We denote the set of attackers of A by A := {B Arg : (B, A) Att} and the set of A s attackees by A := {B Arg : (A, B) Att}. A is called initial if it has no attackers, i.e., if A is empty. These notions naturally extend to sets of arguments S Arg by S := S A S A and S := S A S A . Two arguments A and B are in conﬂict if (A, B) Att or (B, A) Att, i.e., either one is attacking the other. S defeats an argument B if B S , i.e., at least one argument in S attacks B. An argument C is defended by S if S defeats all attackers B C. The set of all arguments defended by S is thus given by

Defend(S) := {C Arg : B S for each B C}.

2.1 Classical Argumentation Semantics

Semantics for AFs are given by collections of argument sets that do not exhibit conﬂicts.

Deﬁnition 2. For an AF F = Arg, Att , a set S Arg is said to be conﬂict-free (Cf) if (A, B) / Att for all arguments A, B S. A conﬂict-free argument set S is

(St) stable if S S = Arg,

(Adm) admissible if S Defend(S),

(Cmp) complete if S = Defend(S),

(Gr) grounded if there is no complete T Arg with T S, and

(Prf) preferred if there is no complete T Arg with T S.

The classical argumentation semantics σ for F with σ {Cf, St, Adm, Cmp, Gr, Prf} is the set [F]σ of all argument sets S Arg where condition σ as above holds.

Classical argumentation semantics thus require the absence of conﬂicts in their contained argument sets, a property that takes over to the set of defended arguments.

Lemma 3 (Dung, 1995). Let F = Arg, Att be an AF. If a set S Arg is conﬂict-free, then so is Defend(S).

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

2.2 Assignments

In the probabilistic setting, each argument A of a given AF F = Arg, Att is treated as a Boolean random variable with the same name. An assignment is a function β : Arg {T, F} that determines for each variable, whether the argument is accepted (T) or not (F). The set of all assignments for Arg is denoted by Asg(Arg). An event φ is a set of assignments, i.e., φ Asg(Arg). There exists a straight-forward one-to-one correspondence between argument sets and assignments: Given an argument set S Arg, the corresponding assignment is given by its characteristic function id S deﬁned by id S(A) := T if A S and id S(A) := F otherwise. Conversely, each assignment β Asg(Arg) naturally induces an argument set Argβ := {A Arg : β(A) = T}. The switch between argument sets and assignments is thus merely of syntactic nature, and we may use both representations interchangeably. In the same vein an assignment is admissible (or complete, stable, . . . ) if the corresponding argument set is admissible (or complete, stable, . . . ). Further, we use propositional logic formulas over arguments to specify sets of assignments, e.g., we write A B with A, B Arg for the set of assignments φ Asg(Arg) where φ = {β Asg(Arg) : β(A)=T, β(B)=F}. Using such kind of notation, we deﬁne the set of assignments whose corresponding argument sets defend an argument C Arg by

Note that as usual, empty conjunctions stand for T and empty disjunctions for F. To this end, e.g., in case B is empty, (C) necessarily is the empty set.

2.3 Distributions

A probability distribution over a set X is a function µ: X [0, 1] where P β X µ(β) = 1. The set of all distributions over X is denoted by Distr(X). The support of a distribution µ is deﬁned by Supp(µ) := {β : µ(β) > 0}. µ is a Dirac distribution if µ(β) {0, 1} for all β Asg(Arg), or, equivalently, if Supp(µ) is a singleton. For a ﬁxed β X, we write Diracβ for the uniquely deﬁned Dirac distribution where Diracβ(β) = 1. In the following, we are only concerned with distributions over the set of assignments Asg(Arg). For brevity, we write Distr(F) for Distr(Asg(Arg)), the set of all possible distributions for an AF F. Each distribution µ Distr(F) induces a probability measure over events, denoted by µ as well, i.e., a function µ: 2Asg(Arg) [0, 1] with µ(φ) := P β φ µ(β) for events φ Asg(Arg). Note that (C) is an event for any argument C Arg. As usual, we say that µ has outcome φ almost surely in case µ(φ) = 1. For argument sets S Arg, we use Dirac S as a short form for Diracid S. Finally, for two events φ, ψ Asg(Arg) with µ(ψ) > 0, the conditional probability of φ given ψ is deﬁned as

µ(φ | ψ) := µ(φ ψ)

Admissibility in Probabilistic Argumentation

3. Probabilistic Argumentation Semantics

A probabilistic argumentation semantics ρ assigns to each AF F = Arg, Att a subset JFKρ of Distr(F). While for any classical argumentation semantics σ the argument sets in [F]σ only specify which arguments can be jointly accepted, distributions in JFKρ give rise to a probabilistic interpretation of the arguments, e.g., to specify the belief in, the acceptance of, or the frequency of arguments to be accepted.

Deﬁnition 4 (Likelihood of arguments). For an AF F = Arg, Att , a distribution µ Distr(F), and an argument A Arg, we refer to µ(A) as the µ-likelihood of A.

We denote by Argµ := {A Arg : µ(A) = 1} the set of almost-surely accepted arguments, i.e., arguments with a µ-likelihood of one. Note that here, A stands for a (basic) propositional logic formula over arguments that speciﬁes the set of all events β where β(A)=T. Classical semantics for AFs can be lifted naturally to the probabilistic setting by Dirac distributions corresponding to the semantics argument sets. Likewise, probabilistic semantics can be restricted to the classical case by considering the argument sets corresponding to the Dirac distributions induced by the semantics. Under this view, a probabilistic semantics where all induced Dirac distributions agree with the Dirac distributions of the argument sets of a classical semantics is called a conservative extension.

Deﬁnition 5 (Conservative extension). A probabilistic argumentation semantics ρ is a conservative extension of a classical argumentation semantics σ if for all AFs F = Arg, Att and argument sets S Arg, we have

S [F]σ iﬀ Dirac S JFKρ.

When looking for a probabilistic semantics that reﬂects one of the classical notions, constituting a conservative extension is by itself clearly not suﬃcient. However, we deem it a necessary criterion, and will show that all probabilistic semantics introduced later on are conservative extensions of their corresponding classical semantics. As a basic instance of a conservative extension, we present the element-wise lifting of classical argumentation semantics, ﬁrst introduced by (Thimm, Baroni, Giacomin, & Vicig, 2017).

Deﬁnition 6 (Element-wise lifting). Let F = Arg, Att be an AF. Then, for a classical argumentation semantics σ, the element-wise-σ semantics Elm-σ is deﬁned by

JFKElm-σ := µ Distr(F) : Argβ [F]σ for all β Supp(µ) .

For instance, JFKElm-Adm comprises exactly those distributions where only the assignments corresponding to the admissible sets of F may have positive probability. Conversely, Elm-σ semantics enforce µ(βS) = 0 for all argument sets S 2Arg\[F]σ that are not part of the classical argumentation semantics σ.

Lemma 7. Element-wise lifting of classical semantics yields conservative extensions.

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

Proof. Let σ be a classical semantics and S Arg. According to Deﬁnition 5, we have to show that S [F]σ iﬀDirac S JFKElm-σ. ( ): Let S [F]σ. We have to show Argβ [F]σ for all assignments β Supp(Dirac S). This holds as the support of Dirac S only contains the characteristic function id S of S with Argid S = S and thus Argid S [F]σ by assumption. ( ): Let Dirac S JFKElm-σ. Then, Argid S [F]σ since Supp(Dirac S) = {id S} and thus, by Argid S = S we obtain S [F]σ.

The converse of Lemma 7 does not hold, i.e., the notion of conservative extension is more liberal than element-wise lifting.

3.1 Assignment Distribution Properties

Before we discuss probabilistic extensions of admissible and complete semantics, we deﬁne the notions of conﬂict-freeness and defense in the probabilistic setting.

3.1.1 Almost-surely Conflict-free

Recall that a set of arguments S is said to be conﬂict-free if there is no attack (A, B) Att for all A, B S. By the one-to-one correspondence of argument sets to assignments, an assignment β is thus conﬂict-free if there is no (A, B) Att with β(A) = β(B) = T. This notion of conﬂict-freeness naturally transfers to distributions over assignments.

Deﬁnition 8 (Almost-surely conﬂict-free). Let F = Arg, Att be an AF. A distribution µ Distr(F) is called almost-surely conﬂict-free iﬀ

µ(A B) = 0 for all (A, B) Att. (as Cf)

Notably, as Cf does not imply that attacker and attackee cannot both have nonzero µlikelihood. However, the probability of both being jointly accepted (constituting a classical conﬂict) is zero. As it turns out, this deﬁnition of almost-sure conﬂict-freeness coincides with the element-wise lifting of conﬂict-free argument sets.

Lemma 9 (as Cf Elm-Cf). For an AF F = Arg, Att , a distribution µ Distr(F) is almost-surely conﬂict-free iﬀthe set Argβ is conﬂict-free for each assignment β Supp(µ).

Proof. ( ): Suppose µ is almost-surely conﬂict-free and assume by contradiction that there is some assignment β Supp(µ) that is not conﬂict-free. Then, there are arguments A, B Argβ such that A attacks B and β(A) = β(B) = T. As µ satisﬁes as Cf, we have µ(A B) = 0. The assignment β satisﬁes A B, so µ(A B) µ(β) holds. However, by β Supp(µ), we have µ(β) > 0, which directly leads to a contradiction:

0 = µ(A B) µ(β) > 0.

( ): We now assume that each β Supp(µ) is conﬂict-free but µ is not almost-surely conﬂict-free. Then there is some pair (A, B) Att with µ(A B) > 0, and thus an assignment β with β (A) = β (B) = T and µ(β ) > 0. However, then β Supp(µ) but β

is not conﬂict-free, a contradiction.

By Lemma 7 and 9, the set of almost-surely conﬂict-free distributions conservatively extends the set of conﬂict-free argument sets.

Admissibility in Probabilistic Argumentation

Figure 3: AF fragment for an argument C with attackers Bi and defenders Ai

3.1.2 Almost-sure Defense

In the classical setting, an argument is defended by defeating each of its attackers. Likewise, we say that a distribution almost-surely defends an argument if all attackers are in turn attacked with probability one.

Deﬁnition 10 (Almost-sure defense). For F = Arg, Att an AF, a distribution µ Distr(F) almost-surely defends an argument C Arg iﬀ

The set of all arguments defended almost surely by µ is denoted by as Defend(µ).

Example 11. In the AF from Figure 3, argument C is almost-surely defended by a distribution µ if the following constraint holds:

A B A = µ (A1 A2) A3 = 1.

That is, the event where argument A3 as well as arguments A1 or A2 are accepted needs to occur almost-surely. This entails that µ(A3) = 1 is required for C to be almost-surely defended by µ. Argument B1 is attacked but has no defenders. Recalling that an empty disjunction stands for F, this yields

D A D = µ(F F) = 0 = 1.

Thus, B1 (and likewise B2) cannot be almost-surely defended by any distribution. Finally, for unattacked arguments like A1, we always get

µ (A1) = µ(T) = 1.

Initial arguments are thus almost-surely defended by any distribution.

Equivalently, the set as Defend(µ) is also characterized by the arguments that are defended by each assignment in the support of µ.

Lemma 12. Let F = Arg, Att be an AF and µ Distr(F). Then:

as Defend(µ) = \

β Supp(µ) Defend(Argβ).

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

Proof. ( ): Let C as Defend(µ) and β Supp(µ). To prove C Defend(Argβ), we pick an attacker B of C and show B Argβ . By deﬁnition of the almost-surely defended sets, we have µ (C) = 1. This implies β(A) = T for at least one attacker A of B. Thus, A Argβ and B Argβ . ( ): Let C be an argument such that C Defend(Argβ) for all β Supp(µ). Then for each attacker B C and each β Supp(µ) there is at least one argument A B such that β(A) = T. This yields µ (C) = 1 for each B C and thus, C as Defend(µ).

Corollary 13. For any AF F = Arg, Att and distribution µ Distr(F):

(a) as Defend(µ) is conﬂict-free if µ is almost-surely conﬂict-free;

(b) as Defend(Dirac S) = Defend(S) for each S Arg.

Proof. (a): If µ is almost-surely conﬂict-free, then each assignment in Supp(µ) is conﬂict-free (Lemma 9). But then the claim follows from Lemma 12 and the facts that (1) Defend(Argβ) is conﬂict-free if β is conﬂict-free (cf. Lemma 3) and (2) the intersection of conﬂict-free argument sets is conﬂict-free. (b): Let µ = Dirac S and β = id S. Thus, β is the unique assignment with Argβ = S and µ is the (unique) Dirac distribution with Supp(µ) = {β}. But then Lemma 12 directly yields as Defend(µ) = Defend(S).

In other words, an argument set S defends an argument C if and only if Dirac S almost-surely defends C.

3.1.3 Relative Defense Constraint

Several of the semantics proposed in the next sections will impose constraints relating the probability of an argument to the probability of the argument being almost-surely defended. For a distribution µ and a comparison relation { , =, }, we deﬁne the relative defense constraint ( µ ) as the set of constraints

for all arguments C Arg. For example, the constraint ( µ ) is satisﬁed if for all arguments the probability that the argument is defended is at least as high as the likelihood of the argument itself.

3.2 Admissibility

Recall that a set of arguments S is called admissible if and only if S is conﬂict-free and defends all its elements. In this section, we provide several notions of admissibility in the probabilistic setting. They all have in common to require almost-surely conﬂict-free distributions but have diﬀerent approaches to capture the self-defense aspect of admissibility. The ﬁrst one directly reﬂects the classical deﬁnition and states that almost-surely accepted arguments need to be defended almost-surely.

Deﬁnition 14 (w Adm). Let F = Arg, Att be an AF and µ Distr(F) an almost-surely conﬂict-free distribution. Then µ is called weakly admissibleiﬀ

Argµ as Defend(µ).

Admissibility in Probabilistic Argumentation

In other words, an almost-surely conﬂict-free distribution µ is weakly admissible iﬀfor all arguments C, we have that

µ(C) = 1 implies µ (C) = 1.

The semantics is weak in the sense that all distributions where no argument has a likelihood of one are trivially weakly admissible. As such, weak admissibility is more of a basic requirement like almost-sure conﬂict-freeness and also weak in the sense that it is implied by all our other probabilistic notions of admissibility (which we show in the following). Our notion of weak admissibility should hence not be confused with the recent notion of weak admissibility in the non-probabilistic setting (Baumann, Brewka, & Ulbricht, 2020). This non-probabilistic notion focuses on relaxing requirements on defense, e.g., to not require self-attacking arguments to be defended in case they also attack the set of arguments under consideration.

Towards a stronger probabilistic notion of admissibility, we relate the likelihood of each argument to the probability of its strongest attacker, or, equivalently, the attacker against which the defense is weakest.

Deﬁnition 15 (min Adm). Let F = Arg, Att be an AF and µ Distr(F) an almost-surely conﬂict-free distribution. Then µ is called min-admissible iﬀfor all C Arg, we have

µ(C) min B C µ _

That is, for every argument C the probability of being accepted is bounded from above by the lowest probability of C being defended against any of its attackers. Equivalently,

needs to hold for each attacker B C.

Example 16. Consider the AF from Figure 3 and assume we have an almost-surely conﬂictfree distribution µ with µ(A1 A2) = 0.7 and µ(A3) = 0.4. Then min-admissibility requires µ(C) 0.4 as this is the probability with which C is defended against its strongest attacker, B2. This entails µ(C) 0.7 = µ(A1 A2) also for the remaining attacker B1.

Next, instead of considering each attacker separately, we require that the probability of defense against the joint attacks is an upper bound on each argument s likelihood. This is a ﬁrst instance of the relative defense constraint introduced in Section 3.1.3.

Deﬁnition 17 (jnt Adm). Let F = Arg, Att be an AF. A distribution µ Distr(F) is called joint-attack admissible iﬀµ is almost-surely conﬂict-free and ( µ ) holds, i.e., for all C Arg, we have µ(C) µ (C) .

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

Figure 4: Under pr Adm, µ(C1 C2) µ(A1 A2) needs to hold

Example 18. Continuing Example 11, joint-admissibility requires for argument C that

µ(C) µ (A1 A2) A3 .

For arguments B1 and B2, we have µ (B1) = µ (B2) = 0, so µ(B1) = µ(B2) = 0 needs to hold for all joint-admissible distributions. Note that for initial arguments like A1, the resulting constraint µ(A1) µ (A1) = 1

is trivially fulﬁlled by every distribution.

For our last notion of admissibility we shift the view from arguments C that need to be defended to arguments B which are attackers of such arguments.

Deﬁnition 19 (pr Adm). Let F = Arg, Att be an AF. A distribution µ Distr(F) is called probabilistically admissible iﬀµ is almost-surely conﬂict-free and for all B Arg, we have µ _

Recall that if an argument set S is admissible, then each argument B attacking arguments in S is itself attacked by some argument in S. Likewise, if B attacks arguments that are almost-surely accepted, we would expect that B is attacked with likelihood one, which is implied by weak admissibility. Now pr Adm further generalizes this relation and requires for each argument B that the probability of accepting arguments attacked by B is bounded by the probability of accepting the arguments which themselves attack B.

Example 20. On the AF from Figure 3, pr Adm yields the same constraints as jnt Adm (see Example 18). This changes when considering the AF from Figure 4 where argument B attacks two arguments C1 and C2. For probabilistically admissible distributions µ, we get for B the constraint µ(C1 C2) µ(A1 A2),

whereas joint-attack admissible distributions need to satisfy both µ(C1) µ(A1 A2) and µ(C2) µ(A1 A2).

Finally, Deﬁnition 6 provides the notion of element-wise admissibility, which requires that all assignments in the support of a distribution µ are admissible. This can be rephrased as a conditional probability constraint: For each argument C with positive µ-likelihood, the probability of assignments defending C must equal one when conditioned on the event that C is accepted.

Admissibility in Probabilistic Argumentation

Lemma 21. Let F = Arg, Att and µ Distr(F). Then µ is element-wise admissible iﬀ µ is almost-surely conﬂict-free and for each argument C Arg with µ(C) > 0, it holds

µ (C) C = 1.

Proof. As µ(C) > 0, the constraint µ (C) C = 1 is equivalent to µ (C) C = µ(C), so it suﬃces to show that (C) C and C describe the same event iﬀµ is element-wise admissible. ( ): Let µ be element-wise admissible and C Arg. Then for all assignments β Supp(µ) we have Argβ Defend(Argβ). For those β with β(C) = T, we thus have C Defend(Argβ). Recall that (C) is the set of all assignments whose argument sets defend C, so we have β (C). ( ): Let µ (C) C = µ(C) for all C Arg and assume by contradiction there exists a β Supp(µ) with Argβ being not admissible. Then either Argβ is not conﬂict-free (contradiction) or Argβ Defend(Argβ), i.e., there is a C Argβ that is not defended by Argβ. But then β (C ), which contradicts µ (C ) C = µ(C ).

All ﬁve presented admissibility notions for distributions are conservative extensions of the non-probabilistic notion of admissibility, as stated in the following lemma.

Lemma 22 (Conservative extension Adm). Let F = Arg, Att be an AF and S Arg be conﬂict-free. Then, S is admissible iﬀDirac S is κ admissible for κ {element-wise, probabilistically, joint-attack, min-, weakly}.

Proof. As weak admissibility is the weakest notion and element-wise admissibility the strongest one (in anticipation of Lemma 23, 24, and 25), it suﬃces to show the implications Adm Elm-Adm and w Adm Adm. The ﬁrst implication is obvious by Lemma 7. For the second implication we suppose that Dirac S is weakly admissible. Hence:

S = Arg Dirac S as Defend(Dirac S).

Corollary 13 yields: as Defend(Dirac S) = Defend(S).

Thus, S Defend(S) holds and S is admissible.

3.2.1 Relationships

We now investigate how our probabilistic notions of admissibility relate to each other. First, we provide implications that hold between the diﬀerent semantics and then give concrete examples that show these implications to be strict. Element-wise admissibility is the most restricted variant, i.e., each distribution that satisﬁes Elm-Adm also satisﬁes the other notions of admissibility. Exemplarily, for an attack (B, C) Att, whenever β(C) = T for some admissible assignment β, there must be some attacker A of B with β(A) = T as well. Thus, all admissible assignments that contribute to the probability on the left-hand side of the pr Adm constraint also appear on the right, so all element-wise admissible distributions are also probabilistically admissible.

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

Lemma 23 (Elm-Adm pr Adm, Elm-Adm jnt Adm). Let F be an AF and µ Distr(F). If µ is element-wise admissible, then µ is probabilistically and joint-attack admissible.

Proof. (Elm-Adm pr Adm): Let µ be element-wise admissible. Then each assignment β Supp(µ) is admissible, so given an attack (B, C) Att, we have:

If β(C) = T then β(A) = T for some attacker A of B.

Thus, if β is an assignment satisfying W C B C, then β also satisﬁes W A B A. Hence, pr Adm holds, which shows that µ is probabilistically admissible. (Elm-Adm jnt Adm): Since all assignments β Supp(µ) are admissible, it suﬃces to show that for each admissible β and C Arg, we have:

If β(C) = T then for each B C there is some A B s.t. β(A) = T.

This, however, is clear as the argument set Argβ = {C Arg : β(C) = T} defends all its arguments. So, β(C) = T implies that for each attacker B of C (i.e., each argument B C) there is an attacker of B in Argβ (i.e., there is some argument A B with β(A) = T).

Lemma 24 (pr Adm min Adm, jnt Adm min Adm). Let F be an AF and µ Distr(F). If µ is probabilistically or joint-attack admissible, then µ is min-admissible.

Proof. (pr Adm min Adm): Let µ be probabilistically admissible. For any argument C, we have to show µ(C) min B C µ _

For this it suﬃces to pick any attacker B C and show that µ(C) µ W A B A . But this follows directly from pr Adm as C B , which yields:

(jnt Adm min Adm): Let µ be joint-attack admissible, i.e., the relative defense constraint ( µ ) is satisﬁed. Then we have

µ(C) µ (C) = µ

A B A min B C µ _

because each assignment β which satisﬁes (C) also satisﬁes W A B A for all B C.

Note that the notions joint-attack and min-admissibility collapse in AFs where each argument has at most one attacker. As weak admissibility only imposes constraints on the likelihood of arguments belonging to Argµ, it is strictly weaker than min-admissibility, and hence the most liberal of the considered admissibility notions.

Lemma 25 (min Adm w Adm). Let F = Arg, Att be an AF and µ Distr(F). If µ is min-admissible, then µ almost-surely defends all arguments in Argµ.

Admissibility in Probabilistic Argumentation

min Adm w Adm Elm-Adm

min Adm w Adm

Figure 5: Hierarchy of the admissible semantics from Deﬁnitions 14, 15, 17, and 19

Proof. Suppose C Argµ. Then, µ(C) = 1. The task is to show that each attacker of C is attacked almost surely. Pick an attacker B of C. As µ(C) = 1, the constraint min Adm directly yields µ _

Thus, µ almost-surely defends C.

The results so far establish a hierarchy of the ﬁve notions of admissibility for distributions as illustrated in Figure 5. The following examples show the inclusions within this hierarchy to be strict.

Example 26 (min Adm pr Adm, min Adm jnt Adm). As an example for a minadmissible distribution that is not element-wise admissible and neither joint-attack nor probabilistically admissible, let µ be the distribution for the AF depicted on the right with the probabilities given on the left:

µ( A B C D) = 1/3 µ( A B C D) = 1/4 µ( A B C D) = 1/6 µ( A B C D) = 1/4

That is, µ(β) = 0 for all other assignments β. Then µ is almost-surely conﬂict-free (since all assignments in its support are conﬂict-free, cf. Deﬁnition 8) and satisﬁes min Adm:

Argument C has likelihood µ(C) = 1/3 + 1/4 = 7/12 and a single attacker B, which is attacked by A and D with probability 1/4 + 1/3 = 7/12.

Argument B has likelihood µ(B) = 1/6. Its attackers A and D are attacked with probability 1/3 resp. 1/4.

Argument D has likelihood µ(D) = 1/3, and so is the probability for its attacker A to be attacked. The analogous statement holds for A.

So, µ is min-admissible, but µ is not element-wise admissible as A B C D and A B C D induce the non-admissible argument sets {C} and {B}, respectively, that do not defend their arguments. Further, µ is not joint-attack admissible, since the argument B has no joint attack of its attackers A and D:

6 0 = µ(A D) = µ (B) .

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

Indeed, in this example there is no admissible argument set containing B, since B s attackers A and D attack each other. To see why µ is not probabilistically admissible, consider argument D. We have D = {A, B} and D = {A}. But then

C D C = µ(A B) = 1

6 1 4 = µ(A) = µ _

Thus, the constraint pr Adm is violated for argument D. Analogously, pr Adm does not hold for A.

The following two examples illustrate that probabilistic admissibility and joint-attack admissibility are incomparable.

Example 27 (jnt Adm pr Adm). Consider the AF depicted on the right below and the distribution µ with the following probabilities for assignments in its support:

µ( A B C D) = 1/3 µ( A B C D) = 1/3 µ( A B C D) = 1/3

µ obviously is almost-surely conﬂict-free and the µ-likelihood of all four arguments is 1/3. As each argument has exactly one attacker, µ is joint-attack admissible: For example, the jnt Adm constraint is satisﬁed for argument C since C = {B}, B = {A}, and

3 1 3 = µ(A) = µ( _

A B A ) = µ (C) .

However, µ does not satisfy the constraint pr Adm for argument B:

C B C = µ(C D) = 1

3 1 3 = µ(A) = µ _

Hence, µ is not probabilistically admissible.

Example 28 (pr Adm jnt Adm). Consider the following almost-surely conﬂict-free distribution µ for the AF depicted on the right:

µ( A B C D) = 1/4 µ( A B C D) = 1/4 µ( A B C D) = 1/4 µ( A B C D) = 1/4

We have µ(A) = µ(B) = µ(D) = 1/4, and µ(C) = 1/2. This implies that Argµ is empty, such we can immediately infer that µ is weakly admissible. To see why µ is probabilistically admissible, we have to check that µ satisﬁes pr Adm for all arguments:

Admissibility in Probabilistic Argumentation

For argument A, we have A = {B, D} and A = {C}, such that µ(B D) µ(C) has to hold. This is in fact the case due to µ(B D) = µ(C) = 1/2.

For argument B, we have B = {C, D}, B = {A, D}, and µ(C D) = 1/2 1/2 = µ(A D).

For argument C, we have C = {A}, C = {B}, and µ(A) = 1/4 1/4 = µ(B).

For argument D, we have D = {B}, D = {A, B}, and µ(B) = 1/4 1/2 = µ(A B).

Thus, µ is probabilistically admissible. To see why µ is not joint-attack admissible, we observe that the µ-likelihood of argument B is positive, but there is no joint attack on B s attackers A and D. More precisely:

4 0 = µ C (A B) = µ (B) .

Here, C stands for the attacks on A, and A B for the attacks on D. This shows that µ violates the constraint jnt Adm for argument B.

3.3 Complete Semantics

In the non-probabilistic setting, complete semantics imposes stronger constraints than admissibility, as it additionally requires that all arguments defended by a set S Arg are contained in S, i.e., S = Defend(S). Based on the notions of admissibility for distributions from the previous section, we now extend complete semantics towards ﬁve notions in the probabilistic setting. Again, Elm-Cmp is an instantiation of Deﬁnition 6.

Deﬁnition 29. Let F = Arg, Att be an AF and µ Distr(F) an almost-surely conﬂictfree distribution. Then µ is called

(w Cmp) weakly complete iﬀArgµ = as Defend(µ),

(min Cmp) min-complete iﬀµ satisﬁes min Adm and ( µ ),

(jnt Cmp) joint-attack complete iﬀµ satisﬁes (=µ ),

(pr Cmp) probabilistically complete iﬀµ satisﬁes pr Adm and ( µ ), and

(Elm-Cmp) element-wise complete iﬀµ JFKElm-Cmp.

It is clear that each of the ﬁve notions of complete semantics imposes stricter constraints than the corresponding notion of admissibility, so each κ complete distribution is also κ admissible for κ {element-wise, weakly, probabilistically, min-, joint-attack}. Before we establish the relationships between the ﬁve semantics, we remark on the particular choice of constraints for minand probabilistically complete semantics.

Remark 30. Joint-attack and weakly complete semantics have been deﬁned by requiring, respectively, the joint-attack admissibility constraint ( µ ) and the weak admissibility contraint Argµ as Defend(µ), plus the analogous reverse condition , namely ( µ ) and

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

Argµ as Defend(µ), resulting in the equality constraints as stated in Deﬁnition 29. One might wonder why minand probabilistically complete semantics are not deﬁned in an analogous way. We argue that the resulting notions would be too strong. For probabilistically complete semantics, the requirement

C B C = µ _

would imply for arguments B which do not attack other arguments (i.e., B = ) that all their attackers C B are unacceptable under µ, as for those µ(W A B A) = 0 would need to hold. This condition appears very strong and lacks an intuitive meaning in the spirit of the non-probabilistic complete semantics. Likewise, for min-complete semantics the condition µ(C) = min B C µ _

also appears questionable as a criterion for complete semantics as it implies that each argument C with likelihood 0 has at least one attacker B that is not attacked under µ (in the sense that µ(W A B A) = 0 holds). This needlessly excludes cases where more than one argument contributes to the attack on C, but none of them is completely unattacked under µ.

Analogous to Lemma 21, element-wise complete semantics can be characterized by element-wise admissibility and the constraint that any defended argument has a conditional likelihood of one.

Lemma 31. Let F = Arg, Att and µ Distr(F). Then µ is element-wise complete iﬀµ is element-wise admissible and for all arguments C Arg where event (C) has positive probability under µ we have µ C | (C) = 1.

Proof. As µ (C) > 0, the conditional probability constraint µ C | (C) = 1 is equivalent to µ C (C) = µ (C) . Thus it suﬃces to show that C (C) and (C) describe the same assignments iﬀµ is element-wise complete. ( ): Let µ be element-wise complete and C Arg. Then for all assignments β Supp(µ), we have Argβ = Defend(Argβ). Now if β (C), then C Defend(Argβ) and hence C Argβ, leading to β also satisfying C (C). ( ): Let µ be element-wise admissible, µ C (C) = µ (C) for all C Arg, and assume by contradiction there exists a β Supp(µ) such that Argβ is not complete, i.e., Argβ = Defend(Argβ). Since β is admissible, we have Argβ Defend(Argβ), i.e., there is an argument C which is defended by Argβ but not element of the set. But then β only satisﬁes (C ) but not C (C ), which contradicts µ C (C ) = µ (C ) because µ(β) > 0 due to β Supp(µ).

All ﬁve complete semantics from Deﬁnition 29 are conservative extensions of the nonprobabilistic complete semantics for argument sets.

Admissibility in Probabilistic Argumentation

Lemma 32 (Conservative extension Cmp). Let F = Arg, Att be an AF and S Arg. Then, S is complete iﬀDirac S is κ complete for κ {element-wise, weakly, probabilistically, min-, joint-attack}.

Proof. By the relationship results between the diﬀerent complete semantics established in Section 3.3.1, it suﬃces to prove the following two implications:

S is complete Dirac S is element-wise complete and

Dirac S is weakly complete S is complete.

The ﬁrst implication is obvious as Dirac S is element-wise complete iﬀid S is a complete assignment, which again is equivalent to S being a complete argument set. For the second implication, suppose that Dirac S is weakly complete. Using Corollary 13 we obtain:

Defend(S) = as Defend(Dirac S) = Arg Dirac S = S.

This directly yields that S is complete.

Recall that Argµ denotes the set of arguments that are accepted almost-surely under a distribution µ. Given a probabilistic semantics ρ, one may ask if there are arguments that are almost-surely accepted under all ρ-distributions. For the various admissibility semantics, the answer is negative as the Dirac distribution corresponding to the empty argument set is always part of the semantics and no argument is almost-surely accepted under it. This is no longer the case when turning to the complete semantics from Deﬁnition 29: Here, it turns out that the arguments almost-surely accepted under all distributions from one of the semantics are exactly those arguments in the grounded argument set of the AF.

Lemma 33. Let F = Arg, Att be an AF with grounded argument set SGr and let ρ be any of the complete semantics from Deﬁnition 29. Then: \

µ JFKρ Argµ = SGr.

Proof. ( ): If A / SGr, then Dirac SGr(A) = 0. As SGr is complete, Dirac SGr is contained in JFKρ for every semantics ρ by Lemma 32. Thus, A is not in T µ JFKρ Argµ. ( ): Now let A SGr. We consider the constructive characterization of the grounded semantics from (Dung, 1995) as the least ﬁxed-point of the Defend( ) function, i.e., S0 Gr = Defend( ), Si Gr = Defend(Si 1 Gr ) for i > 0, and SGr = Sj Gr s.t. Sj Gr = Sj+1 Gr . We show inductively that for every weakly complete distribution µ, we have µ(A) = 1 for each A Si Gr. Base case: Let A S0 Gr = Defend( ). As A is defended by the empty set, it must be initial. Then A is also almost-surely defended by µ, which implies µ(A) = 1 as µ is weakly complete. Step of induction: Let A Si Gr = Defend(Si 1 Gr ) for i > 0. We can assume µ(C) = 1 for all C Si 1 Gr . Now consider µ (A) = µ V B A W C B C . As A Defend(Si 1 Gr ), we know that for each attacker B of A, there is a defender C Si 1 Gr with µ(C) = 1. Therefore, µ (A) = 1 which again implies µ(A) = 1. Thus, for A SGr, we have µ(A) = 1 for all weakly complete distributions. As we will see all other notions of completeness imply w Cmp, which concludes the proof.

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

3.3.1 Relationships

Similar as for the notions of admissibility, we draw relationships between the ﬁve complete semantics introduced in Deﬁnition 29. This yields connections between them analogously to the case of admissibility (cf. Figure 5).

Lemma 34 (Elm-Cmp jnt Cmp, Elm-Cmp pr Cmp). Let F be an AF and µ Distr(F). If µ is element-wise complete, then µ is joint-attack and probabilistically complete.

Proof. Let us ﬁrst observe that each conﬂict-free assignment β Asg(Arg) is complete iﬀ

C Arg. β(C) = T B C. A B. β(A) = T

In other words, C is assigned value T under β iﬀC is defended in β: β(C) = T iﬀβ (C). (Elm-Cmp jnt Cmp): Now let µ be element-wise conﬂict free and C Arg. Then all assignments in the support of µ are complete, so we have

β (C) µ(β) = µ (C) .

Thus, all arguments C satisfy the constraint (=µ ) and hence µ is joint-attack complete. (Elm-Cmp pr Cmp): We have to show that µ is probabilistically admissible and satisﬁes ( µ ). The latter is clearly implied by µ being joint-attack complete as established above. For the former, recall that element-wise complete semantics implies element-wise admissibility. By Lemma 23, this implies probabilistic admissibility, so µ is probabilistically complete.

Lemma 35 (pr Cmp min Cmp, jnt Cmp min Cmp). Let F be an AF and µ Distr(F). If µ is probabilistically or joint-attack complete, then µ is min-complete.

Proof. Recall that min-complete semantics requires min-admissibility and that the constraint ( µ ) holds. For the case where µ is joint-attack complete, the statement is obvious, since jnt Cmp directly implies min Adm and ( µ ). Let us suppose now that µ is probabilistically complete. Then, µ is probabilistically admissible and therefore min-admissible by Lemma 24. Furthermore, by deﬁnition of pr Cmp, µ also satisﬁes ( µ ). Thus, µ is min-complete.

Lemma 36 (min Cmp w Cmp). Let F be an AF and µ Distr(F). If µ is min-complete, then µ is weakly complete.

Proof. Let µ be min-complete, i.e., µ satisﬁes min Adm and ( µ ). Lemma 25 yields Argµ as Defend(µ) and it remains to show that as Defend(µ) Argµ. Let C as Defend(µ). Then µ attacks each attacker B of C with probability 1, which is equivalent to µ (C) = 1. Then ( µ ) yields µ(C) = 1 and hence C Argµ.

We now provide an examples illustrating that the implications between the diﬀerent complete semantics are strict.

Admissibility in Probabilistic Argumentation

Example 37. An example for a distribution that is both joint-attack and probabilistically complete, but without being element-wise complete, is a distribution µ that assigns probability 1

3 to the assignments id{A}, id{B}, and id{C} for the simple odd-length cycle AF on the right below. Neither {A}, {B}, nor {C} are complete sets, so µ is not element-wise complete. Because A, B, and C are isomorphic in the AF under µ, for all constraints imposed by pr Cmp and jnt Cmp the left-hand side equals the right-hand side, so µ is probabilistically and joint-attack complete. For an example of a weakly complete distribution that is not complete w.r.t. any of the other four complete semantics, consider the distribution ν provided through the following probabilities of the assignments in its support:

ν( A B C) = 1/2 ν( A B C) = 1/3 ν( A B C) = 1/6

Then Argν = = as Defend(ν) and hence ν is weakly complete. However,

2 1 6 = ν(B) = min C A ν _

and thus the min Adm constraint is violated for argument A. To this end, ν is not mincomplete and thereby not probabilistically, joint-attack, or element-wise complete. The distribution of Example 27 is joint-attack complete, but not probabilistically admissible, and therefore not probabilistically complete. Vice versa, the distribution µ of Example 28 is probabilistically complete, but not joint-attack admissible, and therefore not joint-attack complete. Note that µ satisﬁes the jnt Cmp constraint for the arguments A, C, and D but not for B, since jnt Adm is violated due to µ(B) = 1/4 > 0 = µ (B) . However, the latter inequation also implies that µ satisﬁes pr Cmp for B and together with pr Adm holding for A, C, and D, µ satisﬁes pr Cmp for all arguments.

3.4 Saturation

We recall that in the non-probabilistic setting an argument set S Arg is called stable if S is conﬂict-free and S S = Arg. Equivalently, S is conﬂict-free and each B Arg\S is attacked by S: S B = . Stable sets S can thus be thought of as perfectly saturated in the sense that an argument is either in S or attacked by S. This is a quite strong constraint, and the existence of stable sets and thus also element-wise stable distributions is not guaranteed. In particular, this is the case for AFs where the underlying graph structure constitutes a simple cycle of odd length, e.g., as in the graph of Example 37. In the classical setting, the semi-stable semantics (Caminada, Carnielli, & Dunne, 2006) addresses this issue, being deﬁned as all complete argument sets S where S S is maximal w.r.t. set inclusion. This entails that if stable argument sets exist, they coincide with the semi-stable sets, and that semi-stable sets always exist even when there is no stable set. However, for distributions such a maximization criterion is not readily expressible as a polynomial constraint. In the following, we provide a diﬀerent approach of carefully weakening the strong notion of perfect saturation .

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

The idea is to require probabilistic justiﬁcations for µ(B) = 0 or µ(B) < 1. 0-saturation requires that if argument B is accepted with likelihood 0, then B is attacked almost surely, i.e., µ(W A B A) = 1. Likewise, 1-saturation imposes the constraint that all arguments B where µ(B) < 1 are attacked with positive probability.

Deﬁnition 38 (0and 1-saturated distributions). Let F = Arg, Att be an AF and µ Distr(F) be almost-surely conﬂict-free. Then µ is called

(Elm-St) element-wise stable iﬀµ JFKElm-St,

(0-Sat) 0-saturated iﬀµ(W A B A) = 1 for each B Arg with µ(B) = 0,

(1-Sat) 1-saturated iﬀµ(W A B A) > 0 for each B Arg with µ(B) < 1, and

(0/1-Sat) 0/1-saturated iﬀµ is 0-saturated and 1-saturated.

We ﬁrst note that element-wise stable distributions are both 0and 1-saturated.

Lemma 39 (Elm-St 0/1-Sat). Let F = Arg, Att be an AF and µ Distr(F). If µ is element-wise stable then µ is 0/1-saturated.

Proof. Let µ be element-wise stable. This implies that µ is almost-surely conﬂict-free. By contradiction, assume µ is not 0/1-saturated. Then there is a B Arg such that either µ(B) = 0 but µ(W A B) = 1, or µ(B) < 1 but µ(W A B) > 0. In both cases, there is an assignment β Supp(µ) with β(B) = F and β(A) = F for all attackers A B. But then Argβ B = , which contradicts β being a stable assignment.

On the other hand, 0/1-saturated distributions are not necessarily element-wise stable as the following example shows.

Example 40 (0/1-Sat Elm-St). As mentioned before any AF F where the underlying graph constitutes a simple cycle of odd length n 3 (for instance the AF from Example 37) does not have stable argument sets and hence no element-wise stable distributions. However, the distribution that assigns probability 1/n to each assignment id A for every A Arg is 0/1saturated because the likelihood of each argument is then strictly between 0 and 1.

Nevertheless, the deﬁnitions of element-wise stable, 0-saturated, and 1-saturated distributions agree for Dirac distributions. This implies, in particular, that 0-saturation as well as 1-saturation are conservative extensions of the non-probabilistic stable semantics.

Lemma 41 (Conservative extension St). If S Arg is conﬂict-free then the following statements are equivalent:

(a) S is stable.

(b) Dirac S is element-wise stable.

(c) Dirac S is 0-saturated.

(d) Dirac S is 1-saturated.

(e) Dirac S is 0/1-saturated.

Admissibility in Probabilistic Argumentation

Proof. The equivalence of statements (a) and (b) is trivial. The conditions required for 0-saturation and 1-saturation of the Dirac distribution µ = Dirac S collapse to the following requirement: If B / S then S B = .

This yields the equivalence of (a) to statements (c), (d), and (e).

3.4.1 Existence of 0/1-saturated Distributions

As mentioned above there are AFs that do not have stable argument sets and thus no element-wise stable distributions, so no guarantee can be given for the existence of 0or 1-saturated Dirac distributions. Nevertheless, 0/1-saturated distributions always exist provided there are no self-attacks in the AF. Speciﬁcally, we show how in those cases the grounded argument set can be extended to a 0/1-saturated distribution.

Lemma 42 (Existence of 0/1-saturated distributions). For every argumentation framework F = Arg, Att where Att is irreﬂexive, there is at least one 0/1-saturated distribution.

Proof. We partition the set Arg of all arguments as follows: SGr Arg is the unique grounded argument set, i.e., [F]Gr = {SGr}, SGr is the set of all arguments attacked by the grounded set, and H = Arg \(SGr SGr ) contains the remaining arguments. Note that if H is not empty, then it contains at least two arguments: A single argument in H would either be initial or attacked from within SGr , but in both cases it would be defended by SGr. However, the grounded set is complete, so the argument would need to be contained in SGr. By the same reasoning we get that all arguments in H are non-initial and have at least one attacker that is also in H. The assumption that F has no self-attacks then yields the existence of a subset C of 2H

such that (1) all argument sets in C are conﬂict-free, (2) each argument B H is contained in at least one S C, (3) for each argument B H there is at least one set S C with B / S. For example, the set C = { } {B} : B H satisﬁes (1) (3). We now consider an arbitrary distribution µ such that Supp(µ) = {id S SGr : S C}. Each assignment id S SGr is conﬂict-free as both S and SGr are conﬂict-free, S SGr = holds as S H, and S SGr = as SGr is admissible. Thus, µ is almost-surely conﬂict-free by Lemma 9. We conclude the proof by checking the constraints imposed by 0/1-saturation for each argument B Arg:

B SGr: Then by the construction of µ, we have µ(B) = 1 and are done.

B SGr : Then µ(B) = 0, but also µ(W A B) = 1.

B H: Then 0 < µ(B) < 1 by (2) and (3). As noted before, B is non-initial and has at least one attacker A H, so µ(W A B) > 0.

Example 43 (AFs with self-attacks). To illustrate why the restriction to AFs without selfattacks can be necessary to ensure the existence of 0/1-saturated distributions, consider an AF containing an argument B with B = {B}, i.e., B is self-attacking and has no other attackers. Then B is not contained in any conﬂict-free argument set, so µ(B) = 0 holds for each almost-surely conﬂict-free distribution µ. Subsequently, µ(W A B A) = µ(B) = 0

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

and thus no 0-saturated distribution exists. For the same reason there is no 1-saturated distribution since µ(B) < 1 holds but the attack probability of B is not positive. However, the existence of a self-attacking argument is not suﬃcient to prevent the existence of 0/1-saturated distribution. Consider the following AF:

Then the unique distribution µ with µ(A) = 1 and µ(B) = 0 is almost-surely conﬂict-free. As µ(W A B A) = 1 and µ(W B A B) = 0, µ is 0/1-saturated. In fact, µ is also elementwise stable because {A} is a stable argument set. An example for an AF with a self-loop that has no stable argument set but still a 0/1-saturated distribution is readily constructed by adding a three-node cycle to the example above.

An algorithm to decide whether a 1-saturated distribution exists for a given AF is detailed in Section 5.3.3.

3.4.2 Relationships

We now consider the relationships between the saturation semantics from Deﬁnition 38 and the admissible and complete semantics from Sections 3.2 and 3.3. As shown by Example 43, existence of saturated distributions is not guaranteed. This indicates that none of the admissible and complete semantics are subsumed by any of the saturation semantics. In the other direction, we obtain the following lemma.

Lemma 44 (0-Sat w Adm, 0/1-Sat w Cmp). Let F = Arg, Att be an AF and µ Distr(F) be conﬂict-free. Then:

(a) If µ is 0-saturated then µ is weakly admissible, i.e., Argµ as Defend(µ).

(b) If µ is 1-saturated then as Defend(µ) Argµ.

(c) If µ is 0/1-saturated then µ is weakly complete, i.e., Argµ = as Defend(µ).

Proof. To prove (a), we suppose that µ is 0-saturated and pick an argument C Argµ. The task is to show that µ almost-surely defends C, i.e., the attack probability for each attacker of C is 1. Let B C. As C Argµ we have µ(C) = 1. As µ is conﬂict-free we obtain µ(B) = 0. By the 0-saturation of µ we obtain:

Hence, B is attacked with probability 1. This shows Argµ as Defend(µ). To prove (b), we suppose that µ is 1-saturated and aim to show as Defend(µ) Argµ. For this, we pick an argument C as Defend(µ) and show µ(C) = 1. Suppose by contradiction that µ(C) < 1. But then 1-saturation yields

Admissibility in Probabilistic Argumentation

So, there is some attacker B of C with µ(B) > 0. On the other hand, as C as Defend(µ), the attack probability of B under µ equals 1. That is, for each assignment β Supp(µ) there exists an argument A with β(A) = T and (A, B) Att. But then β(B) = F as otherwise β would not be conﬂict-free. This shows β(B) = F for all β Supp(µ). This yields µ( B) = 1 and therefore µ(B) = 0. Contradiction. Statement (c) is a direct consequence of (a) and (b).

From Lemma 44 and the fact that weakly complete semantics are also weakly admissible, it is clear that also 0/1-saturated argument sets are weakly admissible. The following examples suﬃce to show that there are no further inclusion relationships between the saturation, admissible, and complete semantics.

Example 45 (1-Sat w Adm). Consider the following almost-surely conﬂict-free distribution for the AF on the right.

µ(A B C D) = 8/10 µ(A B C D) = 1/10 µ(A B C D) = 1/10

A B C D A B C D

Then µ is 1-saturated as µ(A) = 1, while B, C, and D are attacked with positive probability. But µ is not weakly-admissible as µ(A) = 1 but µ (A) = µ(C) = 1/10 = 1.

Example 46 (0-Sat w Cmp). Consider the AF with only a single argument and no attacks F = {A}, {} and the almost-surely conﬂict-free distribution µ with support µ(A) = 9/10 and µ( ) = 1/10. Then µ is 0-saturated trivially. On the other hand, µ (A) = 1 but µ(A) = 1.

Example 47 (0/1-Sat min Adm). Consider the following almost-surely conﬂict-free distribution for the AF on the right.

µ( A B C) = 1/10 µ( A B C) = 1/10 µ( A B C) = 8/10

A B C A B C

Then µ is 0-saturated trivially and 1-saturated as all arguments are attacked with positive probability. But µ is not min-admissible as µ(C) = 8/10 > min X C µ W Y X Y = µ(A) = 1/10.

3.5 Labelings

We established that our probabilistic notions of admissible and complete semantics conservatively extend classical admissibility and complete semantics for argument sets. For most classical argumentation semantics, an alternative formulation in terms of labelings is available (see Baroni et al. (2011) for an overview). In this section, we investigate ways to get from distributions to labelings, so-called labeling schemes, and present a novel approach under which conservative extensions in the argument set view carry over to the labeling-based semantics.

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

A labeling is a function L : Arg {in, out, undec} that assigns to each argument in an AF one of the three statuses in, out, or undec (undecided). A labeling L is conﬂict-free iﬀ no attack between any two arguments that are both labeled with in exists. For admissible labelings, the in and out labels need to be justiﬁed; complete labelings additionally also require a justiﬁcation for the undec labels.

Deﬁnition 48 (Admissible and complete labelings Adm-L and Cmp-L). For an AF F = Arg, Att , a labeling L : Arg {in, out, undec} is admissible if for each A Arg the following two conditions hold:

1. If L(A) = in, then L(B) = out for all attackers B A.

2. If L(A) = out, then L(B) = in for at least one attacker B A.

L is complete if it is admissible and the following additional condition holds:

3. If L(A) = undec, then L(B) = in for all attackers B A and L(B) = out for at least one attacker B A.

Given a conﬂict-free argument set S, a corresponding labeling LS can be constructed by assigning the label in to all arguments in S, out to all arguments attacked by S, and undec to the remaining arguments in Arg \ (S S ):

undec otherwise.

Conversely, given a labeling L, the corresponding argument set Arg L is given by all arguments labeled in by L. The following lemma by (Caminada & Gabbay, 2009) connects the two approaches to classical argumentation for admissibility and complete semantics.

Lemma 49. Let F = Arg, Att be an AF, S Arg a conﬂict-free argument set, and L a labeling on F.

1. If S is admissible, then the labeling LS is admissible.

2. If L is admissible, then the set Arg L is admissible.

3. L is complete iﬀthere is a complete set S Arg with L = LS .

The last statement of Lemma 49 implies that for each AF, a bijection between the complete argument sets and the complete labelings exists. This is not the case for admissibility, as several admissible labelings may correspond to the same admissible argument set.

3.5.1 Labeling Schemes

In the probabilistic setting, we are interested in labelings induced by distributions. To this end, various labeling schemes are imaginable, each specifying how to get from a distribution µ Distr(F) to a labeling Lµ : Arg {in, out, undec}. Arguably the most intuitive approach is to choose the label for each argument A based on its likelihood µ(A). All labeling schemes implementing this approach by a three-way partitioning of the unit interval are instances of the following interval labeling scheme.

Admissibility in Probabilistic Argumentation

Deﬁnition 50 (Interval labeling scheme). Let F = Arg, Att be an AF and µ Distr(F). Given three disjoint intervals i, o, and u that form a partition of the unit interval, i.e., i o u = [0, 1], the interval labeling Li,o,u µ is deﬁned for each A Arg as

Li,o,u µ (A) =

in if µ(A) i

out if µ(A) o

undec if µ(A) u.

An instance of the interval labeling scheme with i = (0.5, 1], o = [0, 0.5), and u = {0.5} can be found in (Hunter & Thimm, 2017), which we will call the Hunter-Thimm-labeling scheme LHT. We will also consider an instance called the cautious labeling scheme Lcts

where only arguments with likelihood 1 or 0 are, respectively, labeled in or out, and all other arguments are labeled undec. That is, Lcts µ = Li,o,u µ with i = {1}, o = {0}, and u = (0, 1). Given the correspondence between argument sets and their induced Dirac distributions, we can check if the labeling for the argument set agrees with the labeling yielded by a labeling scheme for the respective Dirac distribution. If these two labelings coincide for every argument set, we say that the labeling scheme is a conservative extension of argument set induced labelings.

Deﬁnition 51 (Conservative extension of labelings). A labeling scheme Lx conservatively extends the labelings induced by argument sets iﬀfor all conﬂict-free sets S Arg:

LS = Lx Dirac S.

Example 52. Consider the following AF and the admissible argument set S = {A}.

A B C A B C

Then the induced labeling LS is given by LS(A) = in, LS(B) = out, and LS(C) = undec. The distribution Dirac S yields the likelihoods Dirac S(A) = 1 and Dirac S(B) = Dirac S(C) = 0. Now both under the cautious and the Hunter-Thimm-labeling scheme, the labeling induced by Dirac S assigns argument C the label out. Thus, neither Lcts Dirac S nor LHT Dirac S equals LS. In fact, no instance of the interval labeling scheme is a conservative extension: As Dirac S(B) = Dirac S(C), we also have Li,o,u Dirac S(B) = Li,o,u Dirac S(C) regardless of the chosen intervals i, o, and u.

Nevertheless, for each argument set S the labeling LS is contained in the set of all cautious labelings Lcts µ induced by distributions over the assignments for Arg, under the condition that the given AF has no self-attacks.

Lemma 53. Let F = Arg, Att be an AF where the attack relation Att is irreﬂexive. Then for each conﬂict-free argument set S Arg there is a conﬂict-free distribution µ Distr(F) such that LS = Lcts µ .

Proof. Let β = id S be the assignment corresponding to S and let Y denote the set of all arguments C Arg \ S that do not have an attacker in S, i.e.,

Y = C Arg \ S : S C = .

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

As Y S = , we have β(C) = F for all C Y. For each C Y, let βC denote the assignment that agrees with β for all arguments in Arg \{C} but assigns βC(C) = T. Using the assumption that (C, C) / Att, the assignments βC are conﬂict-free. Let now µ be an arbitrary distribution with Supp(µ) = {β} {βC : C Y}. Then each argument in Arg is either in S, Y, or Arg \ (S Y):

For A S, we have β(A) = βC(A) = T for all C Y. Hence, µ(A) = 1 and Lcts µ (A) = in = LS(A).

For C Y, we have µ(C) = µ(βC). By βC Supp(µ), we know µ(βC) > 0, and further µ(βC) < 1 as there are other assignments in Supp(µ). Hence, Lcts µ (C) = undec = LS(C).

For B Arg \ (S Y), we have β(B) = βC(B) = F for all C Y. Hence, µ(B) = 0 and Lcts µ (B) = out = LS(B).

This shows Lcts µ = LS. From Lemma 9 we obtain that µ is also conﬂict-free.

Lemma 53 excludes the case of self-attacks. Indeed, the statement of Lemma 53 does not hold, e.g., for the empty argument set S = in an argumentation framework where all arguments are self-attacking. In this case, the only conﬂict-free distribution is the Dirac distribution µ assigning 1 to the assignment A 7 F for all A Arg. But then Lcts µ labels all arguments out. On the other hand, the labeling induced by S = labels all arguments undec. The same phenomenon would occur for the Hunter-Thimm-labeling scheme.

3.5.2 Conservative Labeling Scheme

We now introduce a labeling scheme that is a conservative extension of labelings induced by argument sets.

Deﬁnition 54 (Conservative labeling scheme). Let F = Arg, Att be an AF and µ Distr(F). The conservative labeling Lcons µ is deﬁned as follows for each argument A Arg:

Lcons µ (A) =

in if µ(A) = 1 out if µ W B A B = 1 undec otherwise.

Lemma 55. For each conﬂict-free argument set S Arg, the labeling LS agrees with the conservative labeling of the induced Dirac distribution. That is, LS = Lcons Dirac S.

Proof. For any argument A Arg, we have

LS(A) = in iﬀ A S iﬀ Dirac S(A) = 1 iﬀ Lcons Dirac S(A) = in.

For the out label, we have

LS(A) = out iﬀ A S = iﬀ Dirac S _

B A B = 1 iﬀ Lcons Dirac S(A) = out.

This yields the claim.

Admissibility in Probabilistic Argumentation

We can observe that the condition for the out label, µ W B A B = 1, implies µ(A) = 0 for each conﬂict-free distribution µ. This yields the following connection between the cautious and the conservative labeling scheme:

Lcts µ (A) = in Lcons µ (A) = in

Lcts µ (A) = out Lcons µ (A) = out

Lcts µ (A) = undec Lcons µ (A) = undec

From this relation it is easy to see that for any distribution µ where µ(A) = 0 implies µ W B A B = 1, both labeling schemes induce the same labeling. This exact condition is enforced by the notion of 0-saturation from Deﬁnition 38. Hence, we obtain:

Lemma 56. If µ is a 0-saturated distribution then Lcts µ = Lcons µ .

We conclude the excursus on labelings with an example from Thimm (2012) that highlights how probabilistic semantics may induce labelings that do not appear in the corresponding classical semantics but are still sensible.

Example 57. Consider the following AF and the two admissible argument sets S1 = {A1} and S2 = {A2}:

Both induce a labeling function LSi where B is labeled out as B s attacker Ai is labeled in with respect to Si. The distribution µ assigning probability 1

2 to the corresponding assignments id S1 and id S2 is element-wise admissible, and the arguments likelihoods are µ(A1) = µ(A2) = 1

2 and µ(B) = 0. Further, we have µ(A1 A2) = 1, so µ is 0-saturated and by Lemma 56 the labeling Lcts µ thus coincides with the labeling Lcons µ : B is labeled out whereas A1 and A2 are labeled undec. This labeling is not admissible as no attacker of B is labeled in, and likewise no argument set exists which could induce it. Nevertheless, we argue that the classiﬁcation of B as out is rather natural given the probabilistic background: B is attacked with probability 1, and µ describes a situation where either A1 or A2 is accepted. Both are equally likely, but regardless of the outcome B is attacked in either case. This is reﬂected in the labeling which is undecided about A1 and A2 but certain in its judgment of B as out.

4. Taxonomy and Related Work

Most closely related to our approach is the work by Hunter and Thimm (2017). Based on earlier works (Thimm, 2012; Hunter, 2013), the authors extend AFs towards a probabilistic setting by attributing a degree of belief to arguments. Inspired by notions from classical argumentation, they introduce several probabilistic semantics featuring constraints on the likelihood of single arguments that can be compared to our semantics. Adapted to our notation, we recall these semantics below for the sake of self-containedness.

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

Deﬁnition 58. Let F = Arg, Att be an AF and µ Distr(F). Then µ is called

(Fou) founded iﬀµ(A) = 1 for all initial A Arg,

(s Fou) semi-founded iﬀµ(A) 1/2 for all initial A Arg,

(Opt) optimistic iﬀµ( A) P B A µ(B) holds for all A Arg,

(s Opt) semi-optimistic iﬀ(Opt) holds for all non-initial A Arg,

(Coh) coherent iﬀµ(A) µ( B) for all (A, B) Att,

(Inv) involutary iﬀµ(A) = µ( B) for all (A, B) Att,

(Jus) justiﬁable iﬀµ is coherent and optimistic,

(Rat) rational iﬀµ(A) > 1/2 implies µ(B) 1/2 for all (A, B) Att,

(Min) minimal iﬀµ(A) = 0 for all A Arg,

(Neu) neutral iﬀµ(A) = 1/2 for all A Arg, and

(Max) maximal iﬀµ(A) = 1 for all A Arg.

Figure 6 gives an overview of all semantics introduced in this paper in perspective to the semantic notions from (Hunter & Thimm, 2017) and the element-wise lifted classical semantics by Thimm et al. (2017) as given in Deﬁnition 6. An arrow from one semantics to another, e.g., w Cmp Jus, indicates that JFKw Cmp JFKJus holds for arbitrary AFs F. In this context, Bot denotes the empty semantics and Top the universal semantics, with JFKBot = and JFKTop = Distr(F). Further, there is at least one AF for each arrow such that the set inclusion is strict, and no other arrows (except for the transitive closure) exist. Proofs for Elm-St Jus and Elm-Cf Coh (and thus as Cf Coh by Lemma 9) are given in (Thimm et al., 2017). All probabilistic semantics introduced in this paper entail or require that the distributions are almost-surely conﬂict-free, so they all imply coherency. However, apart from Elm-St, no other semantics entails Jus. We show this by the following examples. First, Example 59 covers the admissible and complete semantics (which all subsume Elm-Gr and Elm-Prf), followed by Example 60 considering the saturation semantics.

Example 59 (Elm-Gr s Opt, Elm-Prf s Opt). Consider again the odd cycle AF F appearing in Example 37 and the assignment β = {A=F, B=F, C=F}. The distribution Diracβ is element-wise preferred and grounded as the corresponding empty argument set is the only element in both [F]St and [F]Gr. However, Diracβ is not optimistic (and thus not justiﬁable) as, e.g., Diracβ( A) = 1 0 = Diracβ(C).

Example 60 (0/1-Sat s Opt). Recall from Example 40 that the distribution µ assigning probability 1/3 to the assignments id{A}, id{B}, and id{C} for the odd cycle AF in Example 37 is 0/1-saturated. But µ does not satisfy s Opt: for instance, µ( A) = 2/3 1/3 = µ(C).

In turn, all our notions of complete semantics are founded: They all imply weak completeness, and initial arguments have maximal likelihood in weakly complete distributions since they are always almost-surely defended.

Admissibility in Probabilistic Argumentation

Inv Fou s Fou

Inv Fou s Fou

Figure 6: Hierarchy of probabilistic argumentation semantics. Light gray boxes indicate trivial semantics, the boxes on the left-hand side stand for element-wise lifted classical semantics, the boxes on the right refer to the probabilistic semantics introduced by Hunter and Thimm (2017), and the boxes in the middle to the new notions of admissibility (Section 3.2), complete semantics (Deﬁnition 29), and saturation (Deﬁnition 38).

Lemma 61 (w Cmp Fou). If µ is weakly complete, then µ is founded.

Proof. Let A Arg be initial. Due to A = , A is trivially almost-surely defended by µ, i.e., A as Defend(µ). By w Cmp, Argµ = as Defend(µ), so A Argµ holds and thus µ(A) = 1.

Since any 0/1-saturated distribution is weakly complete, Lemma 61 also implies that 0/1saturated distributions are founded. The latter holds already for 1-saturated distributions:

Lemma 62 (1-Sat Fou). If µ is 1-saturated, then µ is founded.

Proof. Assume that µ is 1-saturated but not founded. This means there is some initial A for which µ(A) < 1. But then since µ is 1-saturated, A must be attacked with positive probability, which cannot be the case as A is initial.

On the other hand, 0-Sat does not imply Fou as the next example shows.

Example 63 (0-Sat s Fou). Consider the AF with only one argument A and no attacks and the distribution µ with µ(A) = 2/5 and µ( ) = 3/5. Then µ is 0-saturated trivially but µ is not semi-founded (and, hence, also not founded) as µ(A) < 1/2.

In the setting of Hunter and Thimm (2017), Coh and Jus are generalizations of conﬂictfree argument sets and the complete semantics, respectively. By our deﬁnition (cf. Deﬁnition 5), coherence is a conservative extension of Cf, though this is not the case for Jus and Cmp: The assignment β from Example 59 is complete but Diracβ is not justiﬁable.

Example 64. To illustrate some of the diﬀerences between our semantics and, in particular, justiﬁability semantics, we return to our motivating example from the introduction where we

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

considered an AF for a semi-autonomous car. Consider the following distribution µ given below as the probabilities of all events in its support, where µ(S) abbreviates µ(id S).

µ({st, cl, cl l, cl m, cr, cr m, cr r, ld}) = 0.2

µ({st, ld, cl, cl l, cl m, cr, cr m, cr r}) = 0.1

µ({st, cr, cr r, ld, cl, cl l, cl m}) = 0.3

µ({st, cr, cr m, cr r, ld, ld m, cl, cl l}) = 0.1

µ({st, cl, cl m, cr, cr m, cr r, ld}) = 0.1 µ({st, cl, cl m, cr, cr m, cr r, ld, ld m}) = 0.2

Based on Figure 2, we depict the resulting µ-likelihood of each argument in the ﬁgure below:

Though not visible when looking only at the likelihoods, argument st (bottom center, red) with µ(st) = 1 is only defended by the three (underlined) attackers of ct (center, green) with a total probability of µ(cl m ld m cr m) = 0.4.

That is, st is not almost-surely defended. However, this is required by weak admissibility (and thus by all of our notions of admissibility and complete semantics) for arguments like st that are almost-surely accepted. Justiﬁability, instead, considers solely the likelihoods of the immediate attackers. For the arguments in question, the optimism constraints for argument st and argument ct hold:

µ( st) = 0 0 = µ(ct)

µ( ct) = 1 0.3 + 0.3 + 0.4

= µ(cl m) + µ(ld m) + µ(cr m)

In fact, Opt holds for all arguments, so µ is justiﬁable as coherency is given as well.

Example 65. In the ﬁgure below, we show the argument likelihoods induced by a distribution µ that is joint-attack complete but not justiﬁable.

Admissibility in Probabilistic Argumentation

We see µ is not justiﬁable as, e.g., for argument st, the Opt constraint is violated: µ( st) = 0.6 0 = µ(ct). Note that jnt Cmp cannot be veriﬁed from the likelihoods alone and requires reasoning on the full joint distribution on arguments. We refer to Example 78 for details on how µ was constructed.

The Bigger Picture. Apart from the technical relations between the probabilistic argumentation semantics shown in Figure 6, there is a foundational diﬀerence between the semantical notions by Hunter and Thimm (2017) and the notions we propose. The former only impose constraints on the likelihood of single arguments and therefore tend to be more coarse than our semantics from Section 3. The latter crucially exploit the possibility to impose constraints across the joint probability distributions, and this makes it possible to express dependencies as needed already to spell out admissibility in an adequate manner. Speciﬁcally, when restricting oneself to constraints over the likelihood of single arguments, dependencies between the truth values of arguments cannot be expressed: Whenever a system of constraints for µ(A) can be satisﬁed by at least one distribution, then the solution space contains at least (i) one distribution µ where the arguments are pairwise independent and (ii) one distribution µ such that for all arguments A, B where µ(A) µ(B), it is implied that B A holds for every assignment in the support of µ. If B attacks A and the likelihood of B is positive then both (i) and (ii) are in contrast to standard argumentation semantics. In particular, linear constraints for µ(A) cannot express that arguments are complements of each other and thus mutually exclusive, which is however required to faithfully model our vehicle example. This observation should not be read as a critique at the earlier work by Hunter and Thimm as their focus is on modeling the belief of arguments and the induced three-values labelings, rather than a conservative extension of standard concepts (such as conﬂict-freeness or admissibility) on the level of distributions.

4.1 Further Related Work

There is a large body of work on probabilistic extensions of AFs. In general, one distinguishes between the constellations approach (Dung & Thang, 2010; Li et al., 2011; Hunter, 2012; Fazzinga, Flesca, & Parisi, 2015) where uncertainty pertains the topology of the framework, and the epistemic approach (Hunter & Thimm, 2017; Potyka, 2019) where the

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

framework is ﬁxed and uncertainty revolves around the acceptance of arguments. This paper falls into the latter category. Baroni, Giacomin, and Vicig (2014) approach epistemic probabilities from the angle of de Finetti s theory of subjective probabilities (de Finetti, 1974). They consider rationality conditions based on the notions of defense and reinstatement, which are closely related to admissibility and complete semantics. An investigation of variants of semantics giving uniform distributions over the complete, preferred, and semi-stable labelings of an AF is given by Rienstra, Thimm, Liao, and van der Torre (2018). They show that the schemes investigated produce semantics which are founded, rational, and coherent (see Deﬁnition 58). The authors introduce new principles for probabilistic semantics based on SCC-decomposability and SCC-factorability. Hunter, Polberg, and Thimm (2020) extended the approach by Hunter and Thimm (2017) and proposed epistemic graphs. Besides the notion of support3 of arguments, a notion that complements attacks (Boella, Gabbay, van der Torre, & Villata, 2010), they augment argument graphs by constraints that restrict the degree of beliefs in arguments as well as how these beliefs inﬂuence each other. These constraints can be formulated as Boolean combinations of polynomial inequalities over terms that stand for the probability of acceptance of argument sets (represented with propositional atoms). The semantics considered by Hunter et al. (2020) associates sets of distributions over the powerset of arguments with each epistemic graph. The authors consider three forms of semantics or types of constraints on the distributions, the simplest being the satisfaction semantics, which simply returns the distributions consistent with the constraints of an argument graph. A central impulse for the development of epistemic graphs appears to be work on using argumentation for persuasion (Hadoux, Hunter, & Polberg, 2021), which was already in part also addressed in Hunter et al. (2020). Epistemic graphs are a very general framework. As a matter of fact, all constraints appearing in our work can be cast into the setting of epistemic graphs and its satisfaction semantics.

5. Reasoning Problems and Complexity

Classically, a number of diﬀerent reasoning problems are of interest given an AF and a speciﬁc argumentation semantics. Foremost, one might ask whether there exists an argument set satisfying the semantics constraints. Further, one is surely interested in whether a particular argument set satisﬁes the constraints of a semantics. Finally, checking credulous and skeptical acceptance of single arguments is of interest, that is, deciding whether a given argument is contained in at least one argument set or, respectively, all argument sets that satisfy the semantics constraints. A comprehensive overview is given by Dvoˇr ak and Dunne (2018). Based on these tasks, we deﬁne ﬁve reasoning problems for probabilistic argumentation semantics.

Deﬁnition 66 (Reasoning problems). Let ρ be any probabilistic argumentation semantics. We deﬁne the following reasoning problems:

(NE-ρ) Non-emptiness: Given an AF F, decide whether JFKρ is non-empty.

3. Not to be confused with the support of a distribution as deﬁned in Section 2.3.

Admissibility in Probabilistic Argumentation

(NTNE-ρ) Non-trivial non-emptiness: Given an AF F, decide whether JFKρ\{Dirac } is non-empty.

(CA-ρ) Credulous acceptance: Given an AF F = Arg, Att , an argument A Arg, and a threshold θ Q (0, 1], decide if there is at least one µ JFKρ with µ(A) θ.

(SA-ρ) Skeptical acceptance: Given an AF F = Arg, Att , an argument A Arg, and a threshold θ Q (0, 1], decide if µ(A) θ holds for all µ JFKρ.

(M-ρ) Membership: Given an AF F and a distribution ν Distr(F) as input, decide whether ν JFKρ.

When considering the complexity of these reasoning problems, we assume a simple graph encoding for the input AF and a binary encoding of the rational threshold θ. The input distribution for the membership problem is encoded explicitly as vector of rational values in Q [0, 1], one for each assignment. For the ﬁrst three decision problems, i.e., both variants of non-emptiness and credulous acceptance, a positive answer would usually be accompanied by a witness distribution. For skeptical acceptance, in case of a negative answer one might be interested in a distribution acting as a counterexample. In the following sections we investigate how the reasoning problems provided in Deﬁnition 66 can be algorithmically solved and investigate their complexities when instantiated with the probabilistic semantics introduced in this paper. An overview of all results is given in Table 1.

5.1 Generic Upper Bounds

We show how each of the reasoning problems from Deﬁnition 66 can be computed in a generic way for all semantics introduced in this paper. This establishes decidability for each of the decision problems and yields a general upper bound on their time complexity. With the exception of their weak variants, the introduced admissible and complete semantics share the characteristics that each of them imposes a certain set of linear constraints on the joint probability distributions over assignments. The non-emptiness problem NE-ρ is thus solvable in exponential time since the feasibility of linear constraint systems can be checked in polynomial time and the number of variables grows exponentially in the number of arguments. For weak admissibility, weak complete semantics, and the saturation semantics, the imposed constraints are non-linear as they contain implications that condition the likelihood of arguments. However, an exponential time bound for the existence problem under these semantics can still be obtained by enumerating all subsets of Arg as candidates for the arguments which are accepted with the respective likelihood and checking the feasibility of the resulting then linear constraint system for each of them. NE-ρ is trivially solved if ρ is any semantics implied by Min in Figure 6, as Min always contains the distribution µ0 = Dirac with µ0(A) = 0 for all arguments. This motivated the formulation of the non-trivial non-emptiness problem NTNE-ρ where µ0 is excluded. The switch from NE-ρ to NTNE-ρ can be achieved by adding a single linear constraint, such that the exponential time bound remains the same for all semantics. The same holds for the credulous acceptance problem CA-ρ which can be phrased as existence problem

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

semantics ρ NE-ρ NTNE-ρ CA-ρ SA-ρ M-ρ

Elm-Cf trivial in P in P trivial in P Elm-Gr trivial in P P-c P-c P-c

w Adm trivial in P NP-h trivial in P min Adm trivial NP-h trivial in P jnt Adm trivial NP-h trivial in P pr Adm trivial NP-h trivial in P Elm-Adm trivial NP-c NP-c trivial in P

w Cmp trivial in P NP-h P-c in P min Cmp trivial NP-h P-c in P jnt Cmp trivial NP-h P-c in P pr Cmp trivial NP-h P-c in P Elm-Cmp trivial NP-c NP-c P-c in P

0-Sat NP-h in P 1-Sat in P in P in P in P in P 0/1-Sat NP-h in P Elm-St NP-c NP-c NP-c co NP-c in P

Table 1: Summary of complexity results for the reasoning problems from Deﬁnition 66. EXPTIME is an implicit upper bound for all empty ﬁelds and entries where only a hardness result is given (see Section 5.1), entries for the element-wise lifted semantics are discussed in Section 5.2, results for NE-ρ and NTNE-w Adm and NTNE-w Cmp in Section 5.3.1, and skeptical acceptance SA-ρ in Section 5.3.2. 1-Sat is covered in Section 5.3.3 and the hardness results for CA-ρ are given in Section 5.4. Note that for the membership problem M-ρ, the polynomial time bounds are subject to a trivial full encoding of the input distribution.

with an additional linear constraint encoding µ(A) θ for the given argument A and threshold θ. For the skeptical acceptance problem SA-ρ, we can check for the existence of a counterexample by looking for a distribution which satisﬁes the constraints of ρ but also the linear constraint encoding µ(A) < θ.

For the membership problem M-ρ, the constraints enforced by a semantics ρ for a given AF have to be evaluated under the given distribution. The number of constraints is linear in the number of arguments in the AF, though the size of each constraint can be exponentially large. However, given the trivial encoding of the input distribution as a full list of entries for each possible assignment, the distribution is itself exponentially large compared to the AF. In that case, taking into account the whole input size, evaluating the constraints is possible in polynomial time. The complexity of M-ρ is left open in case the distribution is given by some more eﬃcient encoding, e.g., when the zero entries for the assignments that are not in the support of the distribution are omitted.

Admissibility in Probabilistic Argumentation

In summary, EXPTIME is a general upper bound on the time complexity for all reasoning problems. Upper and lower bounds can however be sharpened for many problem instances, as we show in the following sections.

5.2 Classical Semantics Instances

Decision problems for element-wise lifting semantics inherit their complexity from the corresponding decision problems in the classical setting.

Lemma 67 (Reasoning problems under element-wise lifting). Let F = Arg, Att be an AF and σ a classical argumentation semantics. Then the following equivalences hold for the respective reasoning problem:

(a) Non-emptiness: [F]σ = iﬀJFKElm-σ = .

(b) Non-trivial non-emptiness: [F]σ\{ } = iﬀJFKElm-σ\{Dirac } = .

(c) Credulous acceptance: For any argument A Arg, there is a set S [F]σ with A S iﬀthere is a distribution µ JFKElm-σ and a threshold θ (0, 1] s.t. µ(A) θ.

(d) Skeptical acceptance: For any A Arg, A is contained in each S [F]σ iﬀthere is threshold θ (0, 1] s.t. µ(A) θ holds for all µ JFKElm-σ.

Proof. (a) and (b): The existence of an argument set S [F]σ implies Dirac S JFKElm-σ, and the existence of a distribution µ JFKElm-σ implies there is at least one assignment β Supp(µ) such that Argβ [F]σ. (c): If argument A is contained in at least one argument set S [F]σ, then Dirac S JFKElm-σ and Dirac S(A) = 1 θ for ever θ (0, 1]. Vice versa, if µ(A) θ for any θ > 0 and a distribution µ JFKElm-σ, then there is at least one β Supp(µ) with β(A) = T. Thus, A Argβ and Argβ [F]σ. (d): If A is in each set S [F]σ, then β(A) = T for each assignment β Supp(µ) where µ JFKElm-σ and thus µ(A) = 1. For the reverse direction, note that for every element-wise lifted semantics σ there is a distribution ˆµ JFKElm-σ where Supp(ˆµ) = {id S : S [F]σ}. Now if µ(A) θ holds for all µ JFKElm-σ, we also have ˆµ(A) θ and thus A S for all S [F]σ.

Using complexity results from classical abstract argumentation (see Dvoˇr ak and Dunne (2018) for a summary), the non-trivial non-emptiness problem and the credulous acceptance problem are NP-complete (notated as NP-c) for the element-wise lifted versions of admissible, complete, and stable semantics. Further, for Elm-St also the regular non-emptiness problem is NP-complete and the skeptical acceptance problem is co NP-complete.

5.3 Tractable Instances

Apart from the membership problem and the non-emptiness problem for the various admissibility semantics, several other decision problems can be solved in polynomial time.

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

5.3.1 Non-trivial Non-emptiness

Every argumentation framework has a uniquely deﬁned grounded argument set SGr (see Deﬁnition 2) which is also a complete set and can be computed in polynomial time. As each of our probabilistic variants of complete semantics conservatively extends classical complete semantics, they always contain the distribution Dirac SGr, thus trivializing the non-emptiness problem. However, as the grounded argument set can be the empty set, this does not eﬀect the non-trivial non-emptiness problem NTNE-ρ. For the weakly admissible semantics, the constraint Argµ as Defend(µ) is trivially satisﬁed for all distributions µ where µ(A) < 1 holds for each argument A. At ﬁrst glance this fact might suggest that hence also a non-trivial distribution always exists where µ(A) > 0 for at least one argument. However, special care is needed in case there are self-attacking arguments. As every weakly admissible distribution needs to be almost-surely conﬂict-free, we get µ(A) = 0 for each self-attacking argument A. Thus, if all arguments of an AF are selfattacking (which can be checked in polynomial time) then no non-trivial weakly distribution exists. Otherwise, let Arg Arg denote the set of non-self-attacking arguments and consider the distribution µ with

µ id = 1 |Arg | + 1 and µ id{A} = 1 |Arg | + 1 for each A Arg .

Then µ is almost-surely conﬂict-free, weakly admissible, and diﬀerent to the trivial distribution Dirac . Thus, the problem NTNE-w Adm lies in P. Similarly, a polynomially time-bounded algorithm to compute a non-trivial weakly complete distribution can be obtained. Again, we ﬁrst check whether all arguments are selfattacking. If so, no non-trivial weakly complete distribution exists. Otherwise, we proceed to compute the unique grounded argument set SGr. If it is non-empty, we are ﬁnished and return the distribution Dirac SGr. Otherwise, when SGr = , we know that all arguments in the AF must be attacked (as unattacked arguments necessarily appear in the grounded set). In those cases, the distribution µ is weakly complete: µ (C) < 1 holds for all non-initial arguments C by the construction of µ as µ id > 0 and the assignment id only appears in (C) for initial arguments. Thus, NTNE-w Cmp is in P as well.

5.3.2 Skeptical Acceptance

The skeptical acceptance problem SA-ρ asks whether the likelihood of a given argument A exceeds a given positive threshold θ under all ρ-distributions. Like the non-emptiness problem, this problem is trivially solvable for all semantics that necessarily contain the distribution µ0 = Dirac , as µ0(A) = 0 θ for any θ > 0. Further, for all our notions of complete semantics, the problem is equivalent to deciding if the argument A is part of the grounded set SGr, as shown by the following corollary of Lemma 33. By (Dvoˇr ak, 2012), checking if an argument is in the grounded argument set is P-complete.

Corollary 68. Let ρ be any of the complete semantics from Deﬁnition 29. Given an AF F = Arg, Att , an argument A Arg is skeptically accepted w.r.t. to any threshold θ (0, 1] under ρ if and only if A is in the grounded argument set SGr of F.

Admissibility in Probabilistic Argumentation

Proof. By Lemma 33, we have SGr = T µ JFKρ Argµ. For A SGr, this entails µ(A) = 1 θ for any threshold in (0, 1], so A is skeptically accepted under ρ. Vice-versa, for θ = 1 the set T µ JFKρ Argµ contains exactly the skeptically accepted arguments.

5.3.3 1-saturation Semantics

As shown in Section 3.4.1, a non-trivial 0/1-saturated distribution always exists for AFs that do not contain any self-attacking arguments, though the presence of self-attacks alone is not suﬃcient for no 0/1-saturated distribution to exist. We now focus on 1-saturation and present a polynomial-time bounded algorithm to decide whether a (non-trivial) 1-saturated distribution exists. The algorithm suﬃces to answer almost all reasoning problems for 1-Sat (see Lemma 72). The exception is credulous acceptance checking under a threshold of θ = 1, which is subsequently covered with the help of a second algorithm in Lemma 74. The general idea is as follows. Due to almost-sure conﬂict-freeness, all self-attacking arguments must have a likelihood of zero. If an argument is attacked solely by such arguments (or, alternatively, has no attackers), 1-saturation requires its likelihood to be one. Now again by conﬂict-freeness, arguments attacked by at least a single argument with likelihood one necessarily have a likelihood of zero. Thus, originating from self-attacking arguments, we can iteratively construct two sets of arguments that need to have a likelihood of zero or one under every 1-Sat distribution. The existence of a (non-trivial) 1-saturated distribution then hinges on the coverage and disjointness of these two sets. For example, a self-attacking argument with no other attackers would need to belong to both sets. As this cannot be, no 1-saturated distribution exists for AFs containing arguments that are solely attacked by themselves. Formally, let F = Arg, Att be an AF and let X0 := {A Arg : (A, A) Att} denote the set of self-attacking arguments. We deﬁne two set-valued functions G, H: 2Arg 2Arg

as follows:

G(X) := B Arg : B X

H(X) := X0 G(X)

That is, G(X) denotes the set of all arguments where all attackers belong to X, and an argument is in H(X) iﬀit is self-attacking or has an attacker in G(X). Note that both G and H are monotonic, i.e., for all A, B 2Arg with A B, we have G(A) G(B) and H(A) H(B). By the Knaster-Tarski theorem, the monotonicity of H implies the existence of a least ﬁxed-point which we denote by X . Further, let Y := G(X ). Now consider the two increasing sequences (Xn) and (Yn) given by Xn+1 := H(Xn) and Yn := G(Xn) for n N and X0 as above. Then X and Y are the limits of the sequences (Xn) and (Yn), i.e., there exists k |Arg| such that X = Xk = S n Xn and Y = Yk = S n Yn. This entails that the sets X and Y can be computed in polynomial time by determining X0 and iterating H on X0 until X is found, which also yields Y = G(X ).

Example 69. We demonstrate the algorithm on the AF from Figure 7. Argument A is the only self-attacking argument, so X0 = {A}. Then Y0 = G(X0) = {B, C}, as B = {A} X0 and C = {A} X0 holds. While D and A itself are also attacked by A, note that they are

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

Figure 7: Under 1-saturated distributions the arguments A and E must have likelihood zero, B and C must have likelihood one, and no constraints arise for D and F

not part of Y0 as they each have another attacker not in X0. For the next iteration, we get:

X1 = H(X0) = {A} {B, C} = {A, E}

Y1 = G {A, E} = {B, C}.

That is, X1 contains all self-attacking arguments as well as those attacked by Y0, namely A and E. As E does not have any outgoing attacks, Y1 remains unchanged and equals Y0. Subsequently, we also get X2 = X1, thus X = {A, E} and Y = {B, C}. Now assume we remove the attack from B to A. Then A is also part of Y0 and we get:

Y0 = G(X0) = {A, B, C}

X1 = H(X0) = {A} {A, B, C} = {A, B, C, D, E}

Y1 = G(X1) = {A, B, C, D, E, F}.

In that case, both X and Y would contain all arguments of the AF.

Lemma 70. For each 1-saturated distribution µ, we have

(a) µ(A) = 0 for each A X , and

(b) µ(B) = 1 for each B Y .

Proof. We show µ(A) = 0 for each A Xn and µ(B) = 1 for B Yn by induction on n. Base case. (a): Each A X0 is self-attacking, so µ(A) = 0 follows from the fact that µ is almost-surely conﬂict-free. (b): For B Y0, we know each attacker of B is in X0 and thus µ(W A B A) = 0. By the 1-Sat constraint, this implies µ(B) = 1. Step of induction. (a): Let A Xi+1 = H(Xi) = X0 G(Xi) . If A X0 the same reasoning as in the base case applies. For A G(Xi) = Yi , there is a B Yi which attacks A and, by the induction hypothesis, µ(B) = 1. Then µ(A) must be zero by the conﬂict-freeness of µ. (b): Let B Yi+1 = G(Xi+1). Then each attacker A of B is in Xi+1, so as before we have µ(A) = 0 and thus µ(W A B A) = 0 and µ(B) = 1 as µ is 1-saturated.

An immediate consequence of Lemma 70 is that no 1-saturated distribution can exist for AFs where X and Y are not disjoint, i.e., where X Y = . Let Z := Arg \ (X Y ) denote the set of remaining arguments that are neither in X or Y . We will need the following observations about the arguments in X , Y , and Z .

Admissibility in Probabilistic Argumentation

Lemma 71. For an AF F where X and Y are disjoint, it holds:

(a) For each C Z , the set Y {C} is conﬂict-free.

(b) Each C Z has at least one attacker in Z , i.e., C Z = .

(c) Each A X has at least one attacker in Y or Z , i.e., A (Y Z ) = .

Proof. (a): First note that Y is conﬂict-free as B X for all B Y . As C / X , this entails that C does not attack any argument in Y . Further, as X = H(X ) = X0 G(X ) = X0 Y , we have C / Y , so C has no attackers in Y . (b): As C / Y , we have C X , so C is non-empty. By (a), we also have C Y = , thus C Z = must hold. (c): Suppose by contradiction that A (Y Z ) = for some A X . Then A X . But then A G(X ) = Y , which contradicts the assumption that X and Y are disjoint.

With Lemmas 70 and 71 at hand, we are now ready to show how the reasoning problems NE-1-Sat, NTNE-1-Sat, CA-1-Sat (for θ < 1), and SA-1-Sat can be answered given the sets X and Y . Thus, they are tractable in polynomial time.

Lemma 72 (Reasoning problems for 1-Sat). Let F = Arg, Att be an AF and X , Y , Z Arg as before.

(a) There is a 1-saturated distribution for F iﬀX Y = .

(b) There is a non-trivial 1-saturated distribution for F iﬀX Y = and Z or Y

are non-empty.

(c) For A Arg and a threshold θ (0, 1), there is a 1-saturated distribution for F with µ(A) θ iﬀX Y = and A Y or A Z .

(d) For A Arg and θ (0, 1], then µ(A) θ holds for all 1-saturated distributions for F iﬀeither X Y is non-empty (in which case there is no 1-saturated distribution) or X Y = and A Y .

Proof. For (a), the direction 1-Sat X Y = follows directly from Lemma 70. The other direction follows from (b) in case Z or Y are non-empty, otherwise it is easy to see that the distribution Dirac Y is 1-saturated. (b) immediately follows from (c). From Lemma 70, we also get µ(A) θ for all A Y , θ (0, 1], and 1-saturated distributions µ. It remains to show the case A Z for (c) and (d), i.e., that there is a 1-saturated distribution µ with µ(A) θ for A Z , but this does not hold for all 1-saturated distributions. We show this by constructing a 1-saturated distribution µθ A with µθ A(A) = θ for A Z and any θ (0, 1). For any C Z , let βC denote the assignment id Y {C}. Then we deﬁne the distribution µθ A as follows:

µθ A(βA) = θ and µθ A(βC) = 1 θ |Z | 1 for C Z \ {A}.

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

For all C Z \{A}, we then have a positive likelihood µθ A(C) > 0 as |Z | 2 (from Lemma 71b) and θ < 1. The distribution µθ A is 1-saturated iﬀit is almost-surely conﬂictfree and µθ A(B) < 1 implies µθ A(W C B C) > 0 for all B Arg. The former follows as each assignment βC in the support of µθ A is conﬂict-free by Lemma 71a. For B Y , we have µθ A(B) = 1, so the condition holds trivially. For B Z , we have µθ A(B) < 1, but also µθ A(W C B C) > 0 by Lemma 71b. For B X , we have µθ A(B) = 0, but again µθ A(W C B C) > 0 by Lemma 71c.

Example 73. Continuing Example 69, we have X = {A, E}, Y = {B, C}, and Z = {D, F} for the AF from Figure 7. By Lemma 72, as X and Y are disjunct and Z is non-empty, we know that a non-trivial 1-saturated distributions exists. On the other hand, when dropping the edge from B to A, X and Y both contain all arguments, thus no 1-Sat distribution can exist.

Note that Lemma 72 (c) covers the credulous acceptance problem only for thresholds θ that are strictly less than one. This is because requiring µ(C) = 1 for a 1-saturated distribution comes with a number of implications:

1. µ(A) = 1 implies µ(B) = 0 for B A A by as Cf.

2. µ(A) < 1 implies µ(W B A B) > 0 by 1-Sat.

3. µ(W B A B) = 0 implies µ(A) = 1 by 1-Sat.

Therefore, when argument C belongs to Z , requiring µ(C) = 1 can lead to more arguments that need to be added to X and Y . However, the credulous acceptance problem is still tractable for threshold θ = 1 as shown by Algorithm 1 and Lemma 74. Intuitively, the algorithm tries to add C to X while keeping track of the three implications from above. If a violation occurs, C is not credulously accepted, otherwise a 1-Sat distribution with µ(C) = 1 necessarily exists.

Lemma 74. For an AF F = Arg, Att and an argument C Arg, Algorithm 1 decides in polynomial time whether C is credulously accepted under 1-saturated semantics and threshold θ = 1.

Proof. C is credulously accepted iﬀthere is a distribution µ JFK1-Sat with µ(C) = 1. Lines 2 6 of Algorithm 1 are covered by Lemma 72, for the remainder we can assume C Z . Note that the algorithm observes the following invariants when a 1-saturated distribution µ with µ(C) = 1 exists:

µ(A) = 0 for all A S0,

µ(A) = 1 for all A S1,

µ(W A S A) > 0 for all S D.

We ﬁrst consider the case that the algorithm returns no, i.e., we end up in line 14, 21, or 27. In line 14, the current argument B is contained in S0 (and thus µ(B) = 0), but should be added to S1, which would imply µ(B) = 1. Hence, no such distribution µ can exist. The

Admissibility in Probabilistic Argumentation

Algorithm 1: Decide credulous acceptance for argument C under 1-Sat and θ = 1

Input: C Arg Output: yes or no

1 Function Is Cred Accept(C)

2 Compute X , Y , Z as above

3 if X Y = or C X then

4 return no

5 if C Y then

6 return yes

7 S0 X // S0 collects all arguments that are set to zero

8 S1 Y // S1 collects all arguments that are set to one

9 D { A Z : A S0 where A S1 = }

// D collects sets of arguments that cannot all be set to zero

10 Set To One(C)

11 return yes

12 Function Set To One(B)

13 if B S0 then

14 return no

15 S1 S1 {B}

16 D {S D : B / S} // Remove all sets in D that contain B

17 for B ( B B ) \ S0 do

18 Set To Zero(B ) // All arguments attacked by or attacking B are set to zero

19 Function Set To Zero(B)

20 if B S1 then

21 return no

22 S0 S0 {B}

23 D S \ {B} : S D

// Remove B from all sets in D

24 if B S1 = then

25 D D { B \ S0}

26 if D then

27 return no // all arguments in a set in D were set to zero

28 for B B \ S1 do

29 if B \ S0 = then

30 Set To One(B )

// All its attackers are set to zero, so B is set to one

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

same holds for line 21 with S0 and S1 switched. In line 27, we have D. But then, by the invariant, µ(W A A) = 0 > 0. Now assume the algorithm returns yes. Let S? = Arg \(S0 S1). Then any distribution µ with support Supp( µ) = {id S1} {id{A} S1 : A S?} satisﬁes µ(C) = 1 and 0 < µ(A) < 1 for all A S?. We show that any such distribution µ is 1-saturated. Let A S?. Since µ(A) < 1, we have to show µ(W B A B) > 0. Note that no attacker of A can belong to S1 as each argument in S1 either is in Y (which does not attack Z by Lemma 71a) or is added by Set To One, in which case A would have been added to S0 by line 18. Further, at least one attacker of A belongs to S?: By Lemma 71c there is at least one attacker in Z , and not all attackers can belong to S0 as otherwise A would be added to S1 by line 30. Thus, µ(W B A B) > 0 holds. Finally, note that the algorithm always terminates as the set Z is ﬁnite and Set To One and Set To Zero are called at most once for each argument. All set operations are possible in polynomial time and the size of D is bounded by the number of arguments, so the overall runtime is polynomial.

5.4 Hardness Results

We now show NP-hardness of the credulous acceptance problem for most of our semantics via a polynomial reduction from 3SAT. We make use of the standard translation of a CNF formula as given in (Dvoˇr ak & Dunne, 2018). Let ψ be a 3CNF formula over variables in X = {x1, . . . , xn} with k clauses κ1, . . . , κk. That is, ψ = κ1 κ2 . . . κk where κi = ξ1,i ξ2,i ξ3,i and the ξi,j s are literals in Lit = {x1, . . . , xn, x1, . . . , xn} (for j {1, . . . , k} and i {1, 2, 3}). W.l.o.g. ψ has no tautologic clauses, i.e., there is no j {1, . . . , k} and no x X with {x, x} {ξ1,j, ξ2,j, ξ3,j}. Now we deﬁne an AF Fψ = Argψ, Attψ induced by ψ as follows. The set Argψ contains arguments for all literals, all clauses, and the formula ψ itself. That is:

Argψ := Az : z Lit Clauses {ψ} where Clauses = κ1, . . . , κk .

The attack relation Attψ consists of the following pairs (where we identify each clause with the set of its literals, i.e., κj is identiﬁed with {ξ1,j, ξ2,j, ξ3,j}):

(Ax, A x) and (A x, Ax) for each variable x X,

(Aξ, Aκ) for each κ Clauses and each literal ξ κ,

(Aκ, Aψ) for each κ Clauses.

Thus, Aκj = Aξ1,j, Aξ2,j, Aξ3,j , Aκj = Aψ , and Aψ = Aκ1, . . . , Aκk . An example is given in Figure 8.

Lemma 75. Let ψ be a 3CNF formula and Fψ = Argψ, Attψ the corresponding AF obtained by the standard construction. Then the following statements are equivalent:

(a) ψ is satisﬁable.

(b) Fψ has a stable set containing Aψ.

Admissibility in Probabilistic Argumentation

Ax,y,z Ax, y,z A x,y, z

Ax A x Ay A y Az A z

Ax,y,z Ax, y,z A x,y, z

Ax A x Ay A y Az A z

Figure 8: The AF Fψ corresponding to the formula ψ = (x y z) (x y z) ( x y z).

(c) There is an element-wise stable distribution µ for Fψ with µ(Aψ) = 1.

(d) There is a weakly admissible distribution µ for Fψ with µ(Aψ) = 1.

Proof. The equivalence of (a) and (b) follows from the construction of Fψ and is detailed in (Dvoˇr ak & Dunne, 2018). Intuitively, the formula ψ holds iﬀall its clauses are satisﬁed, and likewise, argument Aψ is in a stable set iﬀall its attackers, the arguments corresponding to the clauses, are not in the set. Each clause κ is satisﬁed iﬀat least one of its literals is true. Likewise, Aκ is not in a stable set if at least one of its attackers, the arguments corresponding to the literals, is part of the set. Finally, a model for ψ is boolean assignment to all variables in X, whereas in a stable set either Ax or A x need to be contained for every variable x X. (b) (c) follows from Lemma 7, and (c) = (d) from the established relationships as summarized in Figure 6. To complete the proof it suﬃces to show (d) = (a). Assume µ Distr(Fψ) is weakly admissible and µ(Aψ) = 1. Then argument Aψ is almost-surely defended, i.e., µ (Aψ) = 1, and there is at least one assignment β Supp(µ) which satisﬁes

j=1 (Aξ1,j Aξ2,j Aξ3,j).

As β |= (Aψ), we have β |= Aξ1,j Aξ2,j Aξ3,j for every j {1, . . . , k}. That is, for each clause κ of ψ there is a literal ξ κ with β(Aξ) = T. Let α Asg(X) be given by α(x) = β(Ax) for each variable x X. We now show that α is a satisfying assignment for ψ. Let X denote the set of variables x X such that β(Ax) = T or β(A x) = T, and Lit = {x, x : x X }. (The variables in X \ X are those where β(Ax) = β(A x) = F. These variables are, however, irrelevant for the proof that α is satisfying for ψ.) As β is conﬂict-free and the literals x and x attack each other:

For each literal ξ Lit : α |= ξ iﬀβ(Aξ) = T .

But then, the above yields that for each clause κ of ψ there is a literal ξ κ Lit with α |= ξ. Thus, α is a satisfying assignment for the 3CNF formula ψ.

Corollary 76. Deciding the credulous acceptance problem CA-ρ is NP-hard for the admissibility and complete semantics from Deﬁnitions 14 19 and 29, as well as the 0-Sat and 0/1-Sat semantics.

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

6. Implementation and Evaluation

We have developed a prototypical implementation to support the understanding and evaluation of abstract argumentation frameworks and the proposed probabilistic semantics. Our tool is capable of solving the reasoning problems speciﬁed in Deﬁnition 66 for all semantics given in the taxonomy overview in Figure 6, including those by Hunter and Thimm (2017). The non-emptiness problem is covered by the basic functionality to synthesize one (or more) distributions that satisfy the given semantics constraints, or to assert that no such distribution exists. The non-trivial non-emptiness problem can easily be checked using the features to enforce multiple semantics simultaneously and to consider complement semantics: A synthesized distribution then satisﬁes all the constraints of each regular semantics, but violates at least one constraint of each speciﬁed complement semantics. Thus, to check if a non-trivial distribution exists under some semantics, one simply requires the complement of the Min semantics to hold as well.

Further features and use cases supported by the tool include the following:

Likelihood optimization. For a given AF F, an argument A, and a semantics ρ, ﬁnd a distribution µ JFKρ such that µ(A) is maximal (or minimal) w.r.t. all other distributions in JFKρ. This task requires the chosen semantics ρ to be linear, i.e., to induce only linear constraints. As mentioned before all semantics except the weakly admissible, weakly complete, and the saturation semantics are linear.

Solution space enumeration. For each linear semantics ρ, the solution space (i.e., the set JFKρ as subspace of Rn when each distribution is viewed as n-dimensional vector) is a convex polytope. This feature allows to export the distributions at the corner of this polytope, yielding a ﬁnite representation of all solutions even in case there are inﬁnitely many. Then each distribution in JFKρ arises as convex combination from these corner distributions.

SMT constraints. In addition to the semantics constraints, context speciﬁc constraints can be added to an AF in SMT-LIB format (Barrett, Fontaine, & Tinelli, 2016). Among others, this allows to specify the following constraints on a probability distribution µ over arguments A and B:

Interval containment constraints µ(A) [u, ℓ] specify that argument A is accepted with some probability u µ(A) ℓ.

Complement constraints µ(A) = 1 µ(B) specify that the interpretation of the arguments A and B are complementary, i.e., their likelihoods sum up to one as counter events do.

Scalar dependency constraints µ(A) = k µ(B) specify that the likelihoods of arguments A and B are proportional w.r.t. some factor k R.

Conditional probability constraints µ(A | B) = p specify that p is the probability of A being accepted given that argument B is accepted. This constraint can be represented by a variant of the scalar dependency: µ(A B) = p µ(B).

Admissibility in Probabilistic Argumentation

Back-end selection. A number of diﬀerent state-of-the-art SMT solvers can be selected as back-end via the py SMT interface (Gario & Micheli, 2015) and number of linear solvers is available via CVXOPT (Andersen, Dahl, & Vandenberghe, 2014).

Labelings. All labeling schemes discussed in Section 3.5 can be used to generate one or all labelings for the chosen semantics.

Let us now provide some examples for the application of our tool on instances of our running example.

Example 77. Example 64 was in fact produced by our tool, synthesizing a distribution that satisﬁes all constraints of the semantics Jus and Elm-Cf, as well as the complement semantics of w Cmp. Additionally, we imposed the following constraints on the likelihoods of some of the arguments: µ(cl) = 0.7, µ(ld) = 0.7, µ(cr r) [0.7, 1], and µ(cr m) [0.4, 1]. Intuitively, e.g., the latter means that the probability of camera right truly detecting an object in the middle in front of the car is between 0.4 and 1.

Example 78. For Example 65, the semantics jnt Cmp and the complement of Jus were enforced, along with the same constraints on argument likelihoods as above. Furthermore, some context-speciﬁc constraints were imposed in an additional ﬁle in SMT-LIB format:

In the example, the arguments for the three sensors come with a complement, e.g., ld and ld. We added constraints such that these arguments are in fact their respective inverse by complement constraints such as µ(ld) = 1 µ(ld).

A maximum 2% risk of a false positive detection was enforced via the conditional probability constraint µ(cr r cr m | cr) 0.98.

In line with the sensor arrangement visualized in Figure 1, we enforced a scalar dependency of arguments cr r and cr m by the constraint µ(cr r) = 2 µ(cr m). Intuitively, this means that one third of the right camera view angle is monitoring the (overlapping) middle.

6.1 Tool Architecture

Each semantics is implemented as a function that takes a representation of an AF as input and returns a set of constraints on the induced joint distribution. This approach enables the combination of semantics as needed, including the option to consider complement semantics, and supports easy addition of new probabilistic semantics to the tool. Tasks like credulous or skeptical acceptance checking are tackled by adding additional constraints as described in Section 5.1. Two kinds of solver back-ends are available to tackle diﬀerent tasks. First, SMT solvers like Z3 (de Moura & Bjørner, 2008) are able to handle arbitrary polynomial constraints in the existential theory of the reals. This covers all semantics considered in this paper as well as their complements. Second, linear-optimization solvers can be used for likelihood optimization and solution space enumeration, provided the selected semantics constraints are linear.

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

instance #nodes distribution synthesis max probability of ct solution polytope

cl-ld-cr 6 0.017 (0.004) 0.006 (0.003) 0.022 (0.003) cl-ld-cr 8 0.055 (0.018) 0.030 (0.018) 1.076 (0.018) cl-ld-cr 12 1.286 (0.651) 2.736 (0.762) > 600 timeout cl-ld-cr 14 7.423 (3.913) 43.093 (15.887) > 600 timeout cl-ld-cr 18 361.033 (119.800) > 600 timeout > 600 timeout

Table 2: Running times in seconds on subgraphs of the vehicle example with increasing size for diﬀerent tasks. cl-ld-cr is the full example, otherwise the arguments in grey stand for omitted sensors that are dropped including related edges. The time to generate the constraints is given in parenthesis.

Example 79 (Constraint encoding). For a simplistic AF F = {A, B}, {(A, B)} with two arguments A and B and a single attack A B, a constraint like µ(A) = 1/2 is encoded as SMT constraint as follows: First of all, for each assignment β Asg({A, B}), a ﬂoatingpoint variable vβ is created, along with the constraints vβ 0 and vβ 1. Exemplary, for β = {A=T, B=F}, we obtain the variable v AB. Additionally, we have to enforce the constraint P β µ(β) = 1, i.e., v AB + v AB + v AB + v AB = 1. Then µ(A) = 1/2 is encoded as v AB + v AB = 0.5. For linear constraints, µ is seen as a vector of length 4. We always get the constraints 1 1 1 1 µ = 1 as well as 1 0 0 0 µ 0, 1 0 0 0 µ 1, etc. Then µ(A) = 1/2 is encoded as 0 0 1 1 µ = 0.5.

The tool is implemented in Python and can either be used via a rich command-line interface or directly by including the provided Python package. Further implementation details are given in (K afer, 2020).

6.2 Running Times

All experiments were conducted on an Intel i9-10900K machine with 64GB of RAM, running Ubuntu 20.10 and Python 3.8.6. Computing solutions according to Example 77 took seventy minutes, while less than ﬁve minutes were required to compute the solution for Example 78. Table 2 provides further statistics for typical tasks applied to the vehicle example and some of its subgraphs under pr Cmp semantics. The majority of the time spend in the tool itself is taken up by the constraint generation (given in parentheses), the remaining time is mostly used by the back-end solvers to solve the imposed constraint system. With distributions ranging over all possible assignments of an AF s arguments, it is clear that increasing the number of arguments in an AF leads to an exponential growth of the associated distributions. This also aﬀects the size of the generated constraints and is reﬂected both in the time spend in the tool as well as the time needed by the solver, as evident by the timings for the distribution synthesis task. The optimization task to ﬁnd a distribution under which µ(ct) is maximal is more involved but still succeeds in time for all but the largest instance. The ﬁnal task of ﬁnding the distributions at the corner points of the solution polytope comes with the additional challenge that especially for larger instances the

Admissibility in Probabilistic Argumentation

number of such corner distributions can become very large itself, so memory consumption may arise as additional limiting factor. The tool, further documentation, and all experimental data are publicly available at https://www.perspicuous-computing.science/cpraa/.

7. Conclusion

In this paper we contributed to the quest for quantitative abstract argumentation frameworks from a probability-theoretic perspective. At the core of our approach, we are viewing each semantics as inducing sets of constraints on the joint distribution over argument sets. We have provided a profound study of admissibility and complete semantics and have discussed a hierarchy of resulting semantics, also in relation to earlier work. We have formulated decision problems for probabilistic semantics and provided a range of complexity results. We experimented with these semantic notions on a probabilistic abstract argumentation framework inspired by an autonomous driving scenario. For this, we implemented a tool based on SMT solvers to harvest present and future advances. In particular, by providing generic support for including additional constraints, our tool is capable of addressing a variety of adapted semantic notions well beyond the notions of admissibility and complete semantics spelled out in this paper, as well as adapting them towards context-speciﬁc needs. Our tool is a research prototype, built for the ease of experimentation with semantic notions across the wider spectrum of probabilistic abstract argumentation frameworks. Indeed, it turned out very helpful for the authors of this paper to sharpen their intuition.

7.1 Future Work

The tool already oﬀers some elementary optimization tasks like maximizing the likelihood of selected arguments. Expanding on this functionality, we plan to investigate quantiﬁcations of how close distributions are to satisfy a certain semantics. This could allow to ﬁnd, e.g., the most min-admissible distribution even if no distribution exists that completely satisﬁes the min Adm constraints, or pave the way for a probabilistic adaption of the semi-stable semantics. Finally, we identiﬁed two further directions that might be worthwhile to explore under the lens of our probabilistic approach. In dynamic abstract argumentation, nodes and edges can be added or removed from an initial AF, giving rise to the question of how these dynamic interventions aﬀect, e.g., the accepted argument sets (see, e.g., Diller, Haret, Linsbichler, R ummele, and Woltran (2018) or Doutre and Mailly (2018) for a survey). In the probabilistic setting, changes to the resulting distributions could be quantiﬁed. Secondly, several logical languages for abstract argumentation have been developed (see, e.g., YALLA (Dupin de Saint-Cyr, Bisquert, Cayrol, & Lagasquie-Schiex, 2016)). Such languages allow to encode and subsequently reason about the basic notions of abstract argumentation, and extensions in the probabilistic domain could prove useful.

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

Acknowledgments

This research was partially funded by the DFG through the Collaborative Research Center TRR 248 (see https://perspicuous-computing.science, project ID 389792660), Cluster of Excellence EXC 2050/1 (Ce TI, project ID 390696704, as part of Germany s Excellence Strategy), the Research Training Groups Quant LA (GRK 1763) and Ro SI (GRK 1907), by the Bundesministerium f ur Bildung und Forschung (BMBF) F orderkennzeichen 01IS20056 NAVAS, by the European Research Council through the Advanced Investigators Grant 695614 (POWVER), and by the Key-Area Research and Development Program Grant 2018B010107004 of Guangdong Province.

Amgoud, L., & Cayrol, C. (2002). A reasoning model based on the production of acceptable arguments. Annals of Mathematics and Artiﬁcial Intelligence, 34(1-3), 197 215.

Amgoud, L., Cayrol, C., Lagasquie-Schiex, M., & Livet, P. (2008). On bipolarity in argumentation frameworks. International Journal of Intelligent Systems, 23(10), 1 32.

Andersen, M., Dahl, J., & Vandenberghe, L. (2014). Cvxopt python software for convex optimization. http://cvxopt.org/.

Baier, C., Diller, M., Dubslaﬀ, C., Gaggl, S. A., Hermanns, H., & K afer, N. (2021). Admissibility in Probabilistic Argumentation. In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, pp. 87 98.

Baroni, P., Caminada, M., & Giacomin, M. (2011). An introduction to argumentation semantics. Knowledge Engineering Review, 26(4), 365 410.

Baroni, P., Giacomin, M., & Vicig, P. (2014). On rationality conditions for epistemic probabilities in abstract argumentation. In Parsons, S., Oren, N., Reed, C., & Cerutti, F. (Eds.), Proceedings of the 5th International Conference on Computational Models of Argument (COMMA 2014), Vol. 266 of Frontiers in Artiﬁcial Intelligence and Applications, pp. 121 132. IOS Press.

Barrett, C., Fontaine, P., & Tinelli, C. (2016). The Satisﬁability Modulo Theories Library (SMT-LIB). www.SMT-LIB.org.

Baumann, R., Brewka, G., & Ulbricht, M. (2020). Revisiting the foundations of abstract argumentation - semantics based on weak admissibility and weak defense. In The Thirty-Fourth AAAI Conference on Artiﬁcial Intelligence, AAAI 2020, The Thirty Second Innovative Applications of Artiﬁcial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artiﬁcial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 2742 2749. AAAI Press.

Bench-Capon, T. J. M. (2003). Persuasion in practical argument using value-based argumentation frameworks. Journal of Logic and Computation, 13(3), 429 448.

Boella, G., Gabbay, D. M., van der Torre, L. W. N., & Villata, S. (2010). Support in abstract argumentation. In Baroni, P., Cerutti, F., Giacomin, M., & Simari, G. R. (Eds.), Proceedings of the 3rd International Conference on Computational Models of Argument

Admissibility in Probabilistic Argumentation

(COMMA 2010), Vol. 216 of Frontiers in Artiﬁcial Intelligence and Applications, pp. 111 122. IOS Press.

Brewka, G., Straß, H., Ellmauthaler, S., Wallner, J. P., & Woltran, S. (2013). Abstract Dialectical Frameworks Revisited. In Rossi, F. (Ed.), Proceedings of the 23rd International Joint Conference on Artiﬁcial Intelligence (IJCAI 2013), pp. 803 809. IJCAI/AAAI.

Brewka, G., & Woltran, S. (2010). Abstract Dialectical Frameworks. In Lin, F., Sattler, U., & Truszczy nski, M. (Eds.), Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning (KR 2010), pp. 102 111. AAAI Press.

Caminada, M., Carnielli, W., & Dunne, P. (2006). Semi-stable semantics.. 22(5), 1207 1254.

Caminada, M., & Gabbay, D. (2009). A Logical Account of Formal Argumentation. Studia Logica, 93(2-3), 109 145.

de Finetti, B. (1974). Theory of Probability. Wiley.

de Moura, L., & Bjørner, N. (2008). Z3: An Eﬃcient SMT Solver. In Tools and Algorithms for the Construction and Analysis of Systems, Vol. 4963 of Lecture Notes in Computer Science, pp. 337 340. Springer Berlin Heidelberg.

Diller, M., Haret, A., Linsbichler, T., R ummele, S., & Woltran, S. (2018). An extensionbased approach to belief revision in abstract argumentation. Int. J. Approx. Reason., 93, 395 423.

Doutre, S., & Mailly, J. (2018). Constraints and changes: A survey of abstract argumentation dynamics. Argument Comput., 9(3), 223 248.

Dung, P. M. (1995). On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artiﬁcial Intelligence, 77(2), 321 358.

Dung, P. M., & Thang, P. M. (2010). Towards (probabilistic) argumentation for jury-based dispute resolution. In Baroni, P., Cerutti, F., Giacomin, M., & Simari, G. R. (Eds.), Proceedings of the 3rd International Conference on Computational Models of Argument (COMMA 2010), Vol. 216 of Frontiers in Artiﬁcial Intelligence and Applications, pp. 171 182. IOS Press.

Dunne, P. E., Hunter, A., Mc Burney, P., Parsons, S., & Wooldridge, M. (2011). Weighted argument systems: Basic deﬁnitions, algorithms, and complexity results. Artiﬁcial Intelligence, 175(2), 457 486.

Dupin de Saint-Cyr, F., Bisquert, P., Cayrol, C., & Lagasquie-Schiex, M.-C. (2016). Argumentation update in yalla (yet another logic language for argumentation). International Journal of Approximate Reasoning, 75, 57 92.

Dvoˇr ak, W., & Dunne, P. E. (2018). Computational problems in formal argumentation and their complexity, pp. 631 687. College Publications.

Dvoˇr ak, W. (2012). Computational Aspects of Abstract Argumentation. Ph.D. thesis, Technischen Universit at Wien.

K afer, Baier, Diller, Dubslaff, Gaggl & Hermanns

Faqeh, R., Fetzer, C., Hermanns, H., Hoﬀmann, J., Klauck, M., K ohl, M. A., Steinmetz, M., & Weidenbach, C. (2020). Towards dynamic dependable systems through evidencebased continuous certiﬁcation. In Margaria, T., & Steﬀen, B. (Eds.), Proceedings of the 9th International Symposium on Leveraging Applications of Formal Methods, ISo LA 2020, Veriﬁcation and Validation: Engineering Principles, Part II, Vol. 12477 of Lecture Notes in Computer Science, pp. 416 439. Springer.

Fazzinga, B., Flesca, S., & Parisi, F. (2015). On the complexity of probabilistic abstract argumentation frameworks. ACM Transactions on Computational Logic, 16(3), 22:1 22:39.

Gaggl, S. A., Rudolph, S., & Straß, H. (2021). On the decomposition of abstract dialectical frameworks and the complexity of naive-based semantics. Journal of Artiﬁcial Intelligence Research, 70, 1 64.

Gario, M., & Micheli, A. (2015). Pysmt: a solver-agnostic library for fast prototyping of smt-based algorithms. In SMT Workshop 2015.

Hadoux, E., Hunter, A., & Polberg, S. (2021). Strategic argumentation dialogues for persuasion: Framework and experiments based on modelling the beliefs and concerns of the persuadee. Co RR, abs/2101.11870.

Hunter, A. (2012). Some foundations for probabilistic abstract argumentation. In Verheij, B., Szeider, S., & Woltran, S. (Eds.), Proceedings of the International Conference on Computational Models of Argument (COMMA 2012), Vol. 245 of Frontiers in Artiﬁcial Intelligence and Applications, pp. 117 128. IOS Press.

Hunter, A. (2013). A probabilistic approach to modelling uncertain logical arguments. International Journal of Approximate Reasoning, 54(1), 47 81.

Hunter, A., Polberg, S., & Thimm, M. (2020). Epistemic graphs for representing and reasoning with positive and negative inﬂuences of arguments. Artiﬁcial Intelligence, 281, 103236.

Hunter, A., & Thimm, M. (2017). Probabilistic reasoning with abstract argumentation frameworks. Journal of Artiﬁcial Intelligence Research, 59, 565 611.

K afer, N. (2020). A general framework for probabilistic abstract argumentation. Master s thesis, Saarland University.

Li, H., Oren, N., & Norman, T. J. (2011). Probabilistic argumentation frameworks. In Modgil, S., Oren, N., & Toni, F. (Eds.), Revised Selected Papers of the 1st International Workshop on Theory and Applications of Formal Argumentation (TAFA 2011), Vol. 7132 of Lecture Notes in Computer Science, pp. 1 16. Springer.

Modgil, S., & Prakken, H. (2018). Abstract Rule-Based Argumentation. In Baroni, P., Gabbay, D., Giacomin, M., & van der Torre, L. (Eds.), Handbook of Formal Argumentation, chap. 6. College Publications.

Nouioua, F., & Risch, V. (2011). Argumentation frameworks with necessities. In Benferhat, S., & Grant, J. (Eds.), Proceedings of the 5th International Conference on Scalable Uncertainty Management (SUM 2011), Vol. 6929 of Lecture Notes in Computer Science, pp. 163 176. Springer.

Admissibility in Probabilistic Argumentation

Polberg, S., & Doder, D. (2014). Probabilistic abstract dialectical frameworks. In Ferm e, E., & Leite, J. (Eds.), Proceedings of the 14th European Conference on Logics in Artiﬁcial Intelligence (JELIA 2014), Vol. 8761 of Lecture Notes in Computer Science, pp. 591 599. Springer.

Potyka, N. (2019). A polynomial-time fragment of epistemic probabilistic argumentation. International Journal of Approximate Reasoning, 115, 265 289.

Rienstra, T., Thimm, M., Liao, B., & van der Torre, L. W. N. (2018). Probabilistic abstract argumentation based on SCC decomposability. In Thielscher, M., Toni, F., & Wolter, F. (Eds.), Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR 2018), pp. 168 177. AAAI Press.

Straß, H., & Wallner, J. P. (2015). Analyzing the Computational Complexity of Abstract Dialectical Frameworks via Approximation Fixpoint Theory. Artiﬁcial Intelligence, 226, 34 74.

Thimm, M. (2012). A probabilistic semantics for abstract argumentation. In Raedt, L. D., Bessiere, C., Dubois, D., Doherty, P., Frasconi, P., Heintz, F., & Lucas, P. J. F. (Eds.), Proceedings of the 20th European Conference on Artiﬁcial Intelligence (ECAI 2012). Including Prestigious Applications of Artiﬁcial Intelligence (PAIS-2012) System Demonstrations Track, Vol. 242 of Frontiers in Artiﬁcial Intelligence and Applications, pp. 750 755. IOS Press.

Thimm, M., Baroni, P., Giacomin, M., & Vicig, P. (2017). Probabilities on extensions in abstract argumentation. In Black, E., Modgil, S., & Oren, N. (Eds.), Proceedings of the 4th International Workshop on Theory and Applications of Formal Argumentation (TAFA 2017), Vol. 10757 of Lecture Notes in Computer Science, pp. 102 119. Springer.