Abstract argumentation with conditional preferences

1.Introduction

Preferences are of great importance in computer science and artificial intelligence [16,25,39], where research areas such as recommender systems [18], computational social choice [31], and non-monotonic reasoning [15,40] are concerned with the representation and processing of preferences. Moreover, many situations require the use of conditional preferences, where a choice between two options (e.g. whether to drink tea or coffee) is dependent on other factors (e.g. the time of day). This has lead to the introduction of formalisms such as CP-nets [19], which are explicitly defined to deal with conditional preferences.

In formal argumentation theory, preferences have been studied from various points of view, be it in terms of argument strength [3,4,6,32,33], preferences between values [8,12], or weighted arguments/attacks [17]. Despite this, conditional preferences have received only limited attention in the field of argumentation. Dung et al. investigated conditional preferences in the setting of structured argumentation [27]. There, argumentation frameworks (AFs) are built from defeasible knowledge bases containing preference rules of the form a1,…,an→d0≻d1, where d0 and d1 are defeasible rules. Similarly, there is only one recent paper we are aware of that deals with conditional preferences on the abstract level [2]. This is in contrast to unconditional preferences, which are extensively studied both in structured [36–38] and abstract [1,8,13,17,32] argumentation in the literature.

Outside of argumentation, conditional preferences appear in many situations and formalisms. One example for this are CP-nets [19], which use graphs for preference representation. Another instance is logic programming, where conditional preferences may occur in the head of rules [21,23,24] or as dedicated preference statements [20]. To demonstrate the importance of conditional preferences in common reasoning tasks, we now adapt an example given by Dung et al. [27]:

In this paper, we aim to capture conditional preferences in argumentation on the abstract level rather than the structured level. Doing so will generalize existing formalisms for unconditional preferences in abstract argumentation and provide a more direct target formalism for structured approaches. To this end, we introduce Conditional Preference-based AFs (CPAFs), where each subset of arguments S can be associated with its own preference relation ≻S. Preferences are then resolved via so-called preference-reductions [32], which modify the attack relation based on the given preferences. As a consequence, S must be justified in view of its own preferences, i.e., S must be an extension in view of ≻S. We investigate the following topics relevant to CPAFs:

The remainder of this paper is structured as follows: Section 2 covers the necessary preliminaries on abstract argumentation. In Section 3 we introduce CPAFs and investigate them with respect to some basic properties. Section 4 contains our principle-based analysis, and in Section 5 we analyze the computational complexity of CPAFs. We discuss related formalisms in Section 6 and conclude in Section 7.

This paper is an extended version of [14]. In Section 4 we now generalize and investigate all ten principles of Kaci et al. [32] instead of just the initial six [33]. The complexity analysis featured in Section 5 is entirely new. In Section 6.1 we now provide a second translation from VAFs to CPAFs. The comparison of our formalism with lifting-based CPAFs in Section 6.3 is new as well. Moreover, this version contains additional figures and explanations to improve readability.

2.Preliminaries

We first define (abstract) argumentation frameworks [26].

Semantics for AFs are defined as functions σ which assign to each AF F=(A,R) a set σ(F)⊆2A of extensions [9]. We consider for σ the functions cf (conflict-free), naive, adm (admissible), com (complete), grd (grounded), prf (preferred), and stb (stable).

The computational complexity of AFs has been extensively studied in the literature [29], with the three central problems being those of credulous acceptance, skeptical acceptance, and verification.

Table 1 shows the complexity of these problems [29]. We assume familiarity with the complexity classes of P, NP, and coNP. Furthermore, the class Σ2P contains exactly those problems that can be solved in NP-time with access to an NP-oracle and Π2P contains the complementary problems of Σ2P [7].

Preference-based AFs enrich standard AFs with preferences between arguments [3,4,6,32,33].

If a and b are arguments and a≻b holds then we say that a is stronger than b. An established method of resolving preferences in PAFs are so-called preference reductions, of which there exist four in the literature [32]. If in a PAF (A,R,≻) there is an attack (a,b)∈R and a preference b≻a then (a,b) is called a critical attack. In other words, critical attacks are from weak to strong arguments. The preference-reductions deal with these critical attacks, e.g., by removing or reverting them.

Intuitively, Reduction 1 removes critical attacks while Reduction 2 reverts them. Reduction 3 removes critical attacks, but only if the stronger argument also attacks the weaker one. Reduction 4 can be seen as a combination of Reduction 2 and 3: if the weaker argument attacks the stronger argument, but not vice versa, then we retain the critical attack (as in Reduction 3) but also add a reverse attack (as in Reduction 2). Note that on symmetric attacks, all four reductions function in the same way. The following example demonstrates the reductions and PAF-semantics.

Fig. 1.

PAF F and its preference reducts from Example 2.

PAFs have the same complexity as AFs with respect to the decision problems of Definition 3: hardness results follows from the fact that PAFs generalize AFs, and membership results from the fact that the four preference reductions can be carried out in polynomial time.

A principle-based analysis of the four preference reductions was conducted for complete, grounded, preferred, and stable semantics [32,33]. To this end, ten PAF-properties were laid out and investigated. We now recall them in Definitions 6, 7, 9, 11 according to [32].

Intuitively, P1 states that if there is an attack between two arguments, then there is no extension containing both of them. P2 expresses that adding more preferences to a PAF can exclude extensions, but not introduce them. P3 states that this is also true if we add preferences to a framework without any preferences, i.e., P3 is a special case of P2.

P4 states that adding preferences means extensions will be supersets of extensions in the original PAF. P5 says that adding preferences will preserve skeptically accepted arguments, and might cause new arguments to be skeptically accepted. P6 expresses that the number of extensions will not grow if new preferences are added.

For the next two principles, we need to define the notion of an argument’s status.

Note that in stable semantics an argument is not always credulously accepted if it is skeptically accepted, since there are AFs without stable extensions. Thus, some argument x might be skeptically accepted with respect to stable semantics, yet we still might have status(a,F)=rej.

If a semantics satisfies P7 then the status of an argument x can not be lowered by adding a preference x≻y where x is the preferred (stronger) argument. P8 states that if an argument x is not self-attacking and also stronger than all other arguments, then x can not be rejected.

For principles P9 and P10 we need the concept of paths between two arguments, by which we mean a path in the underlying undirected graph of a PAF.

If P9 is satisfied then adding a preference between two arguments x and y that do not occur in the same weakly connected component does not change the extensions of a PAF. P10 is similar to P9, but only requires that there is no direct connection between x and y.

Table 2 shows which semantics satisfy which principle, as investigated in [32,33].

3.Conditional preference-based argumentation frameworks

As argued in the introduction, our aim is to provide a framework for reasoning with conditional preferences in abstract argumentation. This means that arguments themselves must be capable of expressing preferences, and that those argument-bound preferences are relevant only if the corresponding arguments are themselves accepted. How this is implemented must be considered carefully, as Example 1 demonstrates. There, the fact that Person 1 has a motive (let us refer to this as m1) and the fact that Person 1 has an alibi (a1) result in opposing preferences. When accepting both m1 and a1 it seems natural to combine these opposing preferences, i.e., to cancel them. But this does not allow us to express that alibis are more important than motives, as required in Example 1. Therefore, we need to define our formalism in a general way such that the joint acceptance of arguments must not necessarily result in the combination of their associated preferences. We solve this by mapping each subset S of arguments to a separate preference relation ≻S.

We set no restriction on how exactly conditional preferences are represented. This is deliberate, as we wish to stay as general as possible. In practice, succinct representations could be achieved, e.g., by expressing the cond-function via rules of the form φ⇒x≻y where φ is a propositional formula over the arguments. Indeed, this representation will be used by us in Section 5 where we analyze the complexity of CPAFs.

Just as in PAFs, preferences in CPAFs are resolved with the help of the four preference-reductions (cf. Definition 5). A set of arguments S is an extension of some CPAF if it is an extension relative to its associated preference relation cond(S).

Using CPAFs we can easily formalize our Sherlock Holmes example.

Fig. 2.

The CPAF F from Example 3.

Fig. 3.

The preference-reducts of the CPAF F from Fig. 2/Example 3.

Note that, according to Definition 13, preferred semantics do not maximize over all admissible sets of a CPAF, but rather over all admissible sets in the given S-reduct. This means that if there is a set S that is admissible in the S-reduct of F, but there is also some T⊃S that is admissible in the S-reduct of F, then S is not preferred in the S-reduct of F (and therefore S∉prfcpi(F)). But this T does not have to be admissible in F, since it might not be admissible in the T-reduct of F. The situation is analogous for naive semantics. The following alternative semantics may be considered more natural:

Intuitively, naive-glbcpi and prf-glbcpi maximize globally over all admissible sets of a CPAF, while naivecpi and prfcpi maximize locally over the admissible sets of the given S-reduct.

The difference between local and global maximization is not only philosophical, but impacts fundamental properties for maximization-based semantics such as I-maximality [11]. A semantics σcpi is I-maximal if and only if S⊆T implies S=T for all CPAFs F and all S,T∈σcpi(F).

Fig. 4.

Counterexamples for I-maximality (cf. Propositions 1,2,3).

One may be tempted to deduce from the above proposition that prf-glbcpi is more suitable as a default preferred semantics than prfcpi. However, we will see in Section 6.1 that prfcpi allows us to capture the problems of subjective/objective acceptance in VAFs in a natural way. In our subsequent analysis of CPAFs we consider both local and global subset maximization. Like preferred semantics, naive and stable semantics satisfy I-maximality on AFs. Interestingly, on CPAFs, this depends on the preference-reduction.

A further well-known property of AFs is that if an argument set S is stable in a framework F, then S is also preferred in F [26]. The same is true for CPAFs, with the exception of preferred semantics utilizing global maximization and Reduction 1.

Another interesting point is that grounded extensions are not necessarily unique in CPAFs: consider F=({a,b},{(a,b)},cond) with cond such that b≻{b}a. Then {a}∈grdcp2(F) and {b}∈grdcp2(F). We stress that each grounded extension S is still unique in the S-reduct of the given CPAF and thus unique with respect to its own preferences.

Lastly, by the following proposition we express that every CPAF-semantics considered here generalizes their corresponding PAF-semantics, i.e., that CPAFs generalize PAFs.

4.Principle-based analysis

Principles play an important role in argumentation theory, as they allow us to examine the vast amount of semantics defined for AFs in a general way [11,30,41]. In this section, we generalize the principles of Kaci et al. [32] for PAFs (cf. Definitions 6, 7, 9, 11) to account for conditional preferences. We then investigate by which semantics these principles are satisfied, and show that there are differences to PAFs.

In the case of PAFs, adding more preferences to a framework (A,R,≻) means that we now deal with the PAF (A,R,≻∪≻′). In the case of CPAFs, if we want (A,R,cond′) to have at least the same preferences as (A,R,cond), we must require that cond(S)⊆cond′(S) for all S⊆A. However, if we only want to add a single preference x≻y to a CPAF, then we add x≻Sy to only a single subset S and leave the preferences associated with other subsets unchanged. Given the above considerations, generalizing the PAF-principles to CPAF-principles is quite straightforward. The notions of an argument’s status and paths between two arguments in a CPAF are defined analogously to PAFs (cf. Definitions 8, 10), e.g., status(x,F)=cr iff x is contained in some but not all extensions of the CPAF F.

The following lemma establishes some relationships between the CPAF-principles and is a generalization of known relationships between PAF-principles [32].

Observe that, since CPAFs are a generalization of PAFs (cf. Proposition 5), a CPAF-semantics σcpi can not satisfy Pj∗ if the corresponding PAF-semantics σpi does not satisfy Pj. Moreover, it is obvious that P1∗ is still satisfied under Reductions 2, 3, and 4, as conflicts are not removed by these reductions even if we consider conditional preferences. We can also show that satisfaction of P2 carries over from PAFs to CPAFs.

Lemma 7 implies that complete and stable semantics satisfy P2∗ on CPAFs under Reduction 3. By Lemma 6 these semantics also satisfy P3∗, P4∗, and P6∗. However, we can not use Lemma 6 to show that complete semantics satisfy P5∗, since conditional preferences allow for frameworks without complete extensions. Indeed, we can find a counter-example in this case. Counterexamples for the satisfaction of various principles can also be found for grounded semantics, both variants of the preferred semantics, and even stable semantics in the case of P8∗.

We have now fully investigated the first six principles. It remains to examine principles 7-10, of which we so far only know that P8∗ is not satisfied by most semantics. It turns out that P8∗ is retained when using preferred semantics with global maximization.

Now we turn our attention to P7∗, where, analogously to P2∗ (cf. Lemma 7), it turns out that satisfaction carries over from PAFs to CPAFs.

However, unlike in the case of P2∗, the above lemma does not constitute an exhaustive investigation of P7∗. The reason for this is that P7, in contrast to P2, is satisfied by preferred semantics on PAFs (cf. Table 2). Lemma 10 only allows us to conclude that prfcpi satisfies P7∗, but it says nothing about the satisfaction of prf-glbcpi. We find that P7∗ is satisfied also when maximizing admissible sets globally.