A Ceteris Paribus Deontic Logic

Abstract

We present a formal semantics for deontic logic based on the concept of ceteris paribus preferences. We introduce notions of unconditional obligation and permission as well as conditional obligation and permission that are interpreted relative to this semantics. We show that these notions satisfy some intuitive properties and, at the same time, do not encounter some problems and paradoxes that have been extensively discussed in the deontic logic literature. Moreover, we show how obligations and permissions can be represented compactly using existing preference frameworks from the arti cial intelligence area of computational social choice.

Keywords

• Deontic Logic Ceteris paribus preferences CP-net

Introduction

Arti cial agents are used to automate tasks in many di erent scenarios. Nowadays, they are so pervasive and so fast that it is almost impossible for humans to monitor them in order to predict illegal behaviour. A possible solution is to embed a mapping of the governance into these entities. This will allow to partially translate legal and ethical requirements into computable representations of legal knowledge and reasoning. An example comes from obligations and permissions that are pervasive in law. Obligations are used to impose a requirement while permissions describe allowances. Both of them are concepts captured in deontic logic which has been viewed as a promising component of computational models of legal knowledge and reasoning, on di erent grounds. On the other side, AI's researchers look for modelling legal knowledge and reasoning about it. They can nd in deontic logic a set of formal tools, usually based on modal logic [ 2, 9 ], which could be compositionally integrated with other logical formalism, such as predicate logic, logic programming, or defeasible logics. By complementing (computational) logics with deontic logic, it was hoped that a logical formalism would able to capture the speci cities of legal language [ 3, 19 ]. We leverage on preferences, which are central in making decision processes and thus implemented in many frameworks to drive and assist individuals (e.g., recommender system [ 32 ], sentiment analysis [ 11 ]). In this regard, a new line of AI's research is focused on comparing agents' preferences in order to understand how similar they are [ 20, 22 ]. The approach is useful in di erent multi-agent scenarios to compare agents behaviour with exogenous priorities. Examples of such priorities can be a moral principle, a legal requirement, a guideline or a business process. The aim is to understand whether an agent deviates from a desired behaviour [ 21, 23 ]. In this paper, we provide the semantics for a deontic logic based on the intuitive idea that obligations and permissions consist in preferences over worlds: strict ones for obligations and weak ones for permissions. Such preferences are ceteris paribus in the sense that they only concern worlds that are equal in all remaining circumstances, namely, in all aspects except for those contributing to the states of a airs that are a rmed to be obligatory or permitted. Thus, deontic propositions are to be evaluated against model-theoretical frames consisting of sets of worlds over which ceteris paribus preferences are de ned. While there have been various attempts at basing a deontic logic on the idea of preferences (see for instance [ 15, 2, 16 ]), nobody has yet, to the best of our knowledge, explored the perspective of a ceteris paribus deontic logic. Our formalisation does not allow for the derivation of deontic paradoxes, but supports some deontic inferences. In the following pages, we rst provide a formal account of the idea of ceteris paribus preferences, and of the corresponding semantic structures. We then formalise conditional and unconditional obligations and permissions as ceteris paribus preferences, and study their basic logical properties. We illustrate and discuss both ceteris paribus preferences and deontic operators with the help of extensive examples. We also show how existing AI formalisms (such as CP-nets [ 4 ]) can be used to represent our idea of ceteris paribus deontic logic. 2

Related work

The idea of ceteris paribus preference was originally introduced by Georg Henrik Von Wright [ 29, 31 ]. He observes that our preferences over states of a airs (as opposed to preferences over objects) are usually \holistic", in the sense that they address the compared situations | denoted by Boolean combination of atoms | in the circumstances accompanying such states. Ceteris paribus preferences have recently been the object of renewed interest by logicians, who have developed ceteris paribus semantics for action and preference [ 12, 27 ].

An intuitive semantics and a simple axiomatisation are provided by the socalled standard deontic logic or SDL [ 7 ], built on the basis of the so-called old system of deontic logic by [ 28 ], (for a discussion of SDL, see [ 17, 18 ]). In SDL, to be obligatory means to be true in all ideal (perfectly good) worlds, and to be permissible means to be true in at least one ideal world. This idea is captured by a serial accessibility relation R over possible worlds, to be understood an ideality relation: for every world u there exists at least one world v, such that uRv (v is ideal, relatively to u). In such a semantics frame, ' is obligatory in a world u if and only if ' is true in every world v such that uRv, and ' is permitted in a world u if and only if there exists a world v such that ' is true in at v and uRv.

As it has been often remarked, SDL gives rise to several apparently counterintuitive implications, the so-called deontic paradoxes (for a recent discussion, see [ 2 ], for an analysis from the perspective of legal theory, see also [ 33, 13 ]). First of all, as legal theorist Alf Ross critically observed [ 26 ], the obligation of a certain proposition should not entail the obligation of the disjunction of that proposition and any other arbitrary proposition. Other paradoxes have to do with the so-called contrary to duty obligations, namely, with obligations that emerge when other obligations are violated, and whose content may contradict obligations holding when no violation takes place. The classical examples are represented by Forrester's gentle murderer paradox, Roderick Chisholm [ 6 ] and by Marek Sergot and Henry Prakken [ 24 ]. Various solutions have been proposed to address contrary to duty obligation, often involving technical complexities and sometimes giving rise to additional problems [ 5 ].

A further problematic aspect of SDL concerns conditional or rather contextual obligations, namely, assertions to the e ect that a certain proposition ' is obligatory under a certain condition . Neither a conditional of classical propositional logic. i.e., ' ! O , nor the embedment of a such a conditional within a deontic operator. i.e., O(' ! ), appear to provide fully convincing solutions. This issue has spawn the development of dyadic deontic logic, which capture deontic conditionality through a special conditional operator. Dyadic deontic logic was initiated by Georg Von Wright [ 30 ], while a semantics for it was rst proposed by Bengt Hansson [ 14 ].

Technical solutions have been proposed to deal with deontic conditionals and contrary to duty obligations (see [ 24, 5 ]). These solutions, however, generally require a more complex logical framework and a less intuitive semantics, in comparison with SDL. Recently, [ 3 ] noticed how preference logics and AI preference representation languages are both concerned with reasoning about preferences on combinatorial domains and how in both areas the key notion of ceteris paribus principle appeared for interpreting preference statements[ 27 ]. 3

Background

In this section, we provide a formal de nition of the relevant concepts, and then we discuss them and exemplify their application. 3.1

Ceteris paribus Preferences

To capture the idea of a holistic preference, von Wright considers a set of atoms Atm = fp1; : : : ; png, each describing an elementary and independent state of a complete situation, or world. Von Wright [ 31 ] observes that the set Atm does not need to account for all states that can exist in the real world. It is rather limited to the \preference horizon of a given subject at a given time", namely, to the \states which the subject takes into consideration as constituting accompanying circumstances when he contemplates his preference or not-preferences between states". We rst present the basic elements of the formal semantics, namely, the concepts of preference model and ceteris paribus preference.

Let Atm be a countable set of atomic propositions and let Lit = Atm [ f:p : p 2 Atmg be the corresponding set of literals.

De nition 1 (Preference model). A preference model is a tuple M = (W; ) such that: W = 2Atm is the set of worlds, and is a complete preorder4 on W . Elements of W are denoted by w; v; : : :. We also de ne and as the strict order and indi erence relations induced from . The class of preference models is denoted by P. A weak preference model di ers from a preference model as it does not necessarily include all valuations of propositional variables. Speci cally, W is a subset of all the possible set of worlds. In particular:

De nition 2 (Weak preference model). A weak preference model is a tuple

M = (W; ) such that W 2Atm is the set of worlds, and is a complete preorder on W .

Let us introduce the following concepts of circumstantial indistinguishability and circumstantial preference.

De nition 3 (Circumstantial Indistinguishability). Let M = (W; ) be a preference model, let w; v 2 W and let X be a nite set of atomic propositions. We say that w X v i 8p 2 X : p 2 w i p 2 v. w X v means that w and v are indistinguishable, with regard to the circumstances (the atoms) in X.

De nition 4 (Circumstantial Preference). Let M = (W; ) be a preference model, let w; v 2 W and let X be a nite set of atomic propositions. We introduce the following abbreviations: w X v; i w X v and w v; respectively w X v; i w X v and w v: w X v means that v is at least as good as w, the two worlds being indistinguishable relative to X. w X v means that v is better than w, the two worlds being indistinguishable relative to X. On the basis of the notions of circumstantial equivalence and preference, we can characterise the notions of ceteris paribus (all-the-rest-being equal) preference relatively to an atom set X.

AtmnX w or v

AtmnX w.

De nition 5 (Ceteris Paribus Preference). A world w is ceteris paribus

at least as good as or ceteris paribus better than a world v relative to X, if respectively v The former de nition concerns indistinguishability and preference relatively to all atoms not in X, i.e., relatively to Atm n X. 4 That is a binary relation on W which is re exive, transitive and complete.

CP-net CP-nets [ 4 ] are a compact representation of conditional preferences over ceteris paribus semantics.

De nition 6. A CP-net over a set of binary variables V is a tuple N = (G; CP T ), where G = (V; E) is a directed graph and CP T = fCP T (Vi)jVi 2 V g is a set of conditional preference tables (CP-tables). An edge (Vi; Vj ) 2 E represents that preferences over Dom(Vi) depend on the value of Vj .

For each variable Vi 2 V;, given the assignment to its parents, a CP-table CP T (Vi) represents the preference order over the values of the domain of Vi. For instance, CP T (A) = fa ag represents the strict preference over the values of a variable A, i.e., a is more preferred than a. Each preference order in a CPtable is also called a CP-statement. A CP-net induces a preference graph over all the possible outcomes: each node corresponds to an outcome, that is, a complete assignment of values to variables. Moreover, a directed edge between a pair of outcomes (oj ; oi), which di er only in the value of one variable, means that oj oi. A worsening ip is a change in the value of a variable to a less preferred value according to the CP-statement for that variable. A more recent extension, namely CP-net with indi erence [ 1 ], takes into account indi erence and models lack of information using incomparability. The qualitative compact representation of ceteris paribus scenario and the algorithms developed for inference, make CP-net an interesting and useful tool to represent our model. 4

Ceteris paribus Obligations and Permissions

On the basis of the notions introduced in the previous section, we shall now address obligations and permission. Basically, deontic propositions (assertions of obligations and permissions) can be interpreted over semantic structures of ceteris paribus preferences. The basic idea of this paper is that the semantics of obligations and permissions can be captured by viewing obligations as strict ceteris paribus preferences and permissions as weak ceteris paribus preferences. We rst introduce a formalisation and then illustrate it with examples. 4.1

Unconditional obligations and permissions: formalisation

We call ceteris paribus Deontic Logic - CPDL the resulting deontic logic of obligation and permission interpreted with respect to the ceteris paribus semantics presented in the previous section. The logic also has the so-called universal modal operator that, as we will show in Section 5, allows us to capture factual detachment of obligations.

De nition 7. LCPDL(Atm) is a modal language which includes atomic propositions p; q; : : : 2 Atm, standard Boolean operators and the modal operators O; P; U. The language is such that: { if p 2 Atm, then p 2 LCPDL { if '; 2 LCPDL, then :'; ' ^ 2 LCPDL { if '; 2 LCPDL, then O'; P'; U' 2 LCPDL:

Formulas O' and P' have to be read, respectively, \' is obligatory" and \' is permitted". Formula U' has to be read \' is universally true". The truth conditions for the formulas in the language LCPDL(Atm) are de ned as follows: De nition 8 (Truth Conditions). Let M = (W; ) be a preference model and let w 2 W . Then:

M; w j= p () p 2 w

M; w j= :' () M; w 6j= ' M; w j= ' ^

() M; w j= ' and M; w j= M; w j= O' () 8v; u 2 W : if M; v j= ' and v M; w j= P' () 8v; u 2 W : if M; v j= ' and v where Atm(') denotes the set of atoms from Atm occurring in '.

In other words, O' means that, for every two possible worlds that are Atm n Atm(')-indistinguishable and that disagree about the truth value of ', the world in which ' is true is better than the world in which ' is false. P' means that, for every two possible worlds that are Atm n Atm(')-indistinguishable and that disagree about the truth value of ', the world in which ' is true is at least as good as the world in which ' is false. We say that the formula ' 2 LCPDL(Atm) is valid relative to the class of preference models P, denoted by j=P ', i , for every preference model M and for every world w in M , we have M; w j= '. We say that the formula ' 2 LCPDL(Atm) is satis able relative to the class of preference models i , there exists a preference model M and a world w in M , such that M; w j= '. In this section we extend the logic CPDL by operators of conditional obligation and conditional permission. We call CPDL+ the resulting logic. De nition 9. LCPDL+ (Atm) is a modal language which includes atomic propositions p; q; : : : 2 Atm, standard Boolean operators and the modal operators O; P; U. The language is such that: { if p 2 Atm, then p 2 LCPDL+ { if '; 2 LCPDL+ , then :'; ' ^ 2 LCPDL+ { if '; 2 LCPDL+ , then O'; P'; O( j'); P( j'); U' 2 LCPDL+ :

Formulas O( j') and P( j') have to be read, respectively, \under condition , ' is obligatory " and \under condition , ' is permitted". The truth conditions for the formulas in the language LCPDL+ (Atm) are the ones given in De nition 8 plus the following two extra truth conditions for the conditional obligation operator and the conditional permission operator: De nition 10 (Truth conditions (cont.)). Let M = (W; ) be a preference model and let w 2 W . Then:

M; w j= O( j') () 8v; u 2 jj jjM : if M; v j= ' and v The de nitions of validity and satis ability for the formulas in LCPDL+ (Atm) relative to preference models are analogous to the de nitions of validity and satis ability for the formulas in LCPDL(Atm) relative to preference models. 5

Properties

In this section, we study the logical properties of the operators of unconditional and conditional obligation and permission introduced above as well as the relationship with CP-nets. Our model does not produce several well-known paradoxes in deontic logic. If we restrict our model to obligations and permissions that are stated only on atoms, then we can show that the induced preference model can be represented compactly by a CP-net with indi erence [ 1 ]. Proposition 1. Let C be a set of obligations and permissions. Let M = (W; ) be the minimal preference model induced by C and N = (G; P ) be the CP-net induced by C. Then, M and N are isomorphic.

Proof. Due to lack of space, we introduce and explain the inducing notion in what follows. The minimal preference model induced by C is the one which satis es C and has the less restrictive constraints. First, for each permission in C, introduce a weak order among worlds that di er only for the consequent of the permission, ceteris paribus the antecedent of the permission. For each obligation, introduce a strict order over the worlds that di er only for the consequent of the obligation ceteris paribus the antecedent of the obligation. For all the worlds that are not explicitly compared we introduced a weak order among them. The induced CPnet is built as follows: to each atom vi 2 Atm there is a corresponding variable Vi 2 V such that Dom(Vi) = fvi; vig.

Each conditional obligation O(vijvj ) 2 N introduces a directed edge (Vi; Vj ) in the dependency graph G, such that Vi becomes a parent of Vj . It induces a strict order over Dom(Vj ) given the assignment of Vi such that CP T (Vj ) = fvi : vj vj ; vi : vj vj g. Similarly, each conditional concession P (vijvj ) 2 N induces a weak order over Dom(Vj ) such that CP T (Vj ) = fvi : vj vj ; vi : vj vj g. Notice that in our model, as well as in SDL, everything that is not explicitly forbidden is permitted, i.e., in general :O(vi) ! P (vi). Thus, a variable with indi erence over its domain is introduced for each atom that is not explicitly a consequent of any obligation/permission. To show the isomorphism, consider the bijection between the set of worlds W and the set of all the outcomes in the partial orders. We can show that there is a bijection between edges of the partial order and the ordering relations among worlds in preference model. From the subset of worlds that satisfy all the obligations we can move to less preferred worlds by changing one literal at a time until we visit all the possible worlds. This corresponds to visit all the outcomes in the partial order starting from the subset of optimal outcomes using the de nition of worsening ip of CP-net. Proposition 2. For all ' 2 LCPDL+ (Atm): j=P O' $ O(>j') j=P P' $ P(>j') This highlights that unconditional obligation and permission do not need to be added as primitives in the language of the logic CPDL+, as they are de nable from conditional obligation and permission.

Example 1 (Running example). Let us introduce a running example concerning the presence of cats, dogs, and fences in beach houses (developing the example from [ 24 ]). The set of atoms is Atm = fc; d; f g, where: c represents whether there is a cat; d represents whether there is a dog and f represents whether there is a fence. Mary is the mayor of the town. For safety reasons, she has ordered that there should be fences when there are dogs, and that, on the contrary, there should be no fences when there are no dogs. Cats are allowed with no restrictions. It is easy to check that the following preferences verify P(c), O(djf ) and O(:dj:f ): wfc;d;fg wfd;fg; wfc;dg wfdg; wfc;fg wffg; wfg wfcg; wfc;dg wfc;d;fg; wfdg wfd;fg; wfc;fg wfcg; wffg wfg

Following Proposition 1, Mary's obligations and concessions can be represented using the CP-net with indi erence depicted in Figure 1a which compactly represents the partial order depicted in Figure 1b. Following Proposition 1, to each atom there is a corresponding variable, thus we have V = fC; D; F g representing respectively whether there is cat, a dog and a fence, Dom(C) = fc; cg, Dom(D) = fd; dg and Dom(F ) = ff; f g. Due to obligations and permission, variables C; D are independent while variable F depends on D. Moreover, obligations de ne the strict orders over Dom(D); Dom(F ). From Proposition 2, the unconditional permission P (c) is de ned as P(>jc) and introduces indi erence over Dom(C):

The following proposition highlights that if ' is obligatory, then it is also permitted: Proposition 3. For all ' 2 LCPDL+ (Atm):

j=P O' ! P'

Before dealing with deontic paradoxes, let us consider how factual detachment is represented in the context of the logic CPDL+: This means that if the condition of a conditional obligation/permission is necessarily true, then the obligation/permission is detached and becomes unconditional.

Let us consider the well-known Ross's paradox [ 26 ]. In standard deontic logic (SDL), an obligation to mail a letter (i.e., Om) implies the obligation to mail a letter or to burn it (i.e., O(m _ b)), something that goes against intuition. As the following preference model highlights, our logic CPDL does not encounter this problem.

Example 2. Let Atm = fm; bg with w1 = fm; bg, w2 = fmg, w3 = fbg and w4 = ;. Let us suppose the following preference order over the worlds in W : w3 w1; w4 w2; w3 M; w1 j= Om ^ :O(m _ b).

w2; w1 More generally, it is worth noting that the ceteris paribus obligation operator is not normal as it does not satisfy Axiom K. In particular, there exists '; 2 LCPDL+ (Atm) such that the formula (O' ^ O(' ! )) ! O is not valid in CPDL. To show this, it is su cient to consider the preference model in Example 2. We have M; w1 j= (Om ^ O(m ! (m _ b)) ^ :O(m _ b). An interesting property of the ceteris paribus operators for obligation and permission concerns aggregation over conjunction. First of all, it is worth noting that, in the general case, ceteris paribus obligation and permission do not aggregate over conjunction. More precisely, there exists '; 2 LCPDL+ (Atm) such that: 6j=P (O' ^ O ) ! O(' ^ ); 6j=P (P' ^ P ) ! P(' ^ )

To show this it is su cient to consider the following example. (The latter is proved in an analogous way.) Example 3. Let Atm = fp; qg and w1 = fp; qg; w2 = fqg; w3 = fpg; w4 = ;. Moreover, let us consider the following preference order : w3 w1 w4 w2.

It is routine exercise to check that M; w1 j= O(p ! q), M; w1 j= Oq, but M; w1 6j= O((p ! q) ^ q). To verify the latter it is su cient to observe that w1 w4 and w4 6 w1.

Nonetheless, if ' and are conjunctive clauses (i.e., nite conjunctions of literals from Lit ) whose sets of atoms have empty intersection (i.e., ' and are independent formulas), then the obligation/permission that ' and the obligation/permission that aggregate over conjunction.

Proposition 5. If ';

are conjunctive clauses and Atm(') \ Atm( ) = ; then: j=P (O' ^ O ) ! O(' ^ j=P (P' ^ P ) ! P(' ^ ) ) Proof. We only prove the former as the latter is proved in an analogous way. We prove it by reductio ad absurdum. Let us suppose that (i) M; w j= O' ^ O and (ii) M; w 6j= O(' ^ ). Item (i) means that 8v; u 2 W : if M; v j= ' and v AtmnAtm(') u and v u then M; u j= ', and 8v; u 2 W : if M; v j= and v AtmnAtm(') u and v u then M; u j= . Item (ii) means that 9v; u 2 W : M; v j= ' ^ and v AtmnAtm('^ ) u and v u and M; u j= :' _ : . We consider the three possible cases for the latter.

Case 1: M; u j= :' ^ . Since ' and are conjunctive clauses we have v AtmnAtm(') u. But this is in contradiction with item (i) above.

Case 2: M; u j= ' ^ : . Since ' and are conjunctive clauses we have v AtmnAtm( ) u. But this is in contradiction with item (i) above.

Case 3: M; u j= :' ^ : . There exists w 2 W such that M; w j= :' ^ and v AtmnAtm(') w and w AtmnAtm( ) u. It is su cient to consider the world w such that 8p 2 Atm(') : p 2 w i p 2 u, 8p 2 Atm( ) : p 2 w i p 2 v, and 8p 2 Atm n (Atm(') [ Atm( )) : p 2 w i p 2 v. Such a world w exists since Atm(') \ Atm( ) = ;. By item (i) above and the fact that is complete, we have that w v. Hence, by the transitivity of , we have w in contradiction with item (i) above. u. The latter is

As shown in Example 3, the formula (O(p ! q) ^ Oq) ! O((p ! q) ^ q) is not valid in our logic. Notice that ((p ! q) ^ q) is logically equivalent to q. This highlights a more general property of the logic CPDL, namely, the fact that the obligation operator is not closed under logical equivalence. The same property holds for permissions, as they are also not closed under logical equivalence. On the one hand, this might be seen as a limitation of Von Wright's approach to ceteris paribus preferences extended here to ceteris paribus permissions and obligations. Indeed, closure under logical equivalence is the minimal property that any classical modal logic has to satisfy. From this perspective, our logic of obligations is not a classical modal logic. On the other hand, it might be seen as a virtue of the formalism from the point of view of the imperative theory of norms defended, among the others, by Von Wright. Clearly an obligation, seen as a imperative or a command that a certain fact ought to be the case, does not necessarily imply that all its logically equivalent facts are obligatory as well.

We conclude this section by considering the well-known Forrester's gentle murderer paradox [ 8 ]. Let us assume the following facts: (1) it is obligatory that you do not kill; (2) if you kill you ought to kill gently, and (3) it is necessarily the case that if you kill gently then you kill. Let us assume that the action of killing is captured by the atom k, while the action of killing gently is captured by the conjunction of atom k and atom g (i.e., doing something gently). Fact 1 is expressed by the formula O:k, fact 2 is expressed by the formula k ! O(k ^ g), while fact 3 is expressed by the formula U((k ^ g) ! k). The latter trivially holds since (k ^ g) ! k is a tautology of propositional logic. As emphasized in the introduction, under the assumption that you kill, fact 1 and fact 2 are together inconsistent in SDL, i.e., k ^ O:k ^ (k ! O(k ^ g)) is an inconsistent SDL formula. The problem is that in SDL from k and k ! O(k ^ g) we can infer O(k ^ g) which, in turn, implies Ok. The latter is inconsistent with O:k, since in SDL con icting obligations are not admitted. We have a similar problem in our logic, as the formula k ^ O:k ^ (k ! O(k ^ g)) 2 LCPDL(Atm) is not satis able in the class of preference models. Indeed, from k and k ! O(k ^ g) we trivially infer O(k ^ g). As the following proposition highlights the latter and O:k are together inconsistent: Proposition 6. For all p; q 2 Atm :

j=P O(p ^ q) ! :O:p Proof. Let us suppose that M; w j= O(p ^ q). The latter means that 8v; u 2 W : if M; v j= p ^ q and v AtmnAtm(p^q) u and v u then M; u j= p ^ q. The latter implies that 9v; u 2 W : M; v j= p and v AtmnAtm(p) u and u v and M; u j= :p. The latter just means that M; w j= :O:p.

A solution to the Forrester's gentle murderer paradox, widely explored in the literature (see, e.g., [ 24 ]) consists in reformulating condition (2) above as the conditional obligation of killing gently under the condition of killing, and of applying a principle of factual detachment as the one of Proposition 4. Speci cally, we again represent fact 1 by the formula O:k, while we now represent fact 2 by the formula O(kjk ^ g). Moreover, in order to apply factual detachment for the conditional obligation, we need to assume that k is necessarily true, which is represented by the formula Uk. The problem is that the latter formula is not satis able, as a preference model includes all possible valuations of propositional atoms and, consequently, at least one world in which atom k is false. It follows that the formula O:k ^ O(kjk ^ g) ^ Uk is not satis able either. In order to provide a solution to the Forrester's gentle murderer paradox, which is in line with existing solutions proposed in the literature, we need to weaken the concept of preference model.

Interpretations of formulas with respect to weak preference models is the same as interpretations of formulas with respect to preference models. We denote validity of formulas relative to weak preference models by the symbol j=WP . The following proposition highlights, the validity of Propositions 2, 3 and 4 generalize to weak preference models.

Proposition 7. For all ';

2 LCPDL+ (Atm): j=WP O' $ O(>j') j=WP P' $ P(>j') j=WP O' ! P' j=WP (O( j') ^ U ) ! O' j=WP (P( j') ^ U ) ! P' The following proposition is the counterpart of Proposition 5 with respect to weak preference models.

Proposition 8. If ';

are conjunctive clauses and Atm (') \ Atm( ) = ; then: j=WP (AllV(' ^ j=WP (AllV(' ^ ) ^ O' ^ O ) ! O(' ^ ) ^ P' ^ P ) ! P(' ^ ) ) where:

AllV(' ^ ) =def

^ X Atm('^ )

E( ^ p ^ p2X

^ p2(Atm('^ ))nX :p) and where E' =def :U:'.

The abbreviation AllV('; ) just expresses the fact that the obligation that ' and the obligation that aggregate under conjunction when interpreting them relative to weak preference models if, for every valuation of the atoms in Atm(')[ Atm( ), there exists a world corresponding to this valuation. It is easy to check that the formula O:k^O(kjk^g)^Uk is satis able in the class of weak preference models. Indeed, although O(kjk ^ g) ^ Uk implies O(k ^ g), O(k ^ g) ^ O:k is satis able in the class of weak preference models. As shown in Proposition 6, the latter is not the case in the class of preference models. This highlights that Forrester's gentle murderer paradox is solved in the variant of our logic interpreted over weak preference models by adopting either the solution in which Condition (2) is interpreted via the material implication k ! O(k ^ g) or the solution in which it is interpreted via the conditional obligation O(kjk ^ g). 6

From Syntax Dependence to Independence

The general idea behind our ceteris paribus notion of obligation is that ' is obligatory if and only if the utility of a world increases in the direction by the formula ' ceteris paribus, \all else being equal". Following Von Wright (see also [ 27 ]), in CPDL we capture this ceteris paribus aspect, by keeping xed the truth values of the atoms not occurring in ' (i.e., Atm n Atm(')). The fact that the sets of atoms not occurring in two logical equivalent formulas do not necessarily coincide explains why the obligation and permission operators of CPDL are not closed under logical equivalence. A natural way to obtain obligation and permission operators which are closed under logical equivalence consists in de ning the ceteris paribus condition by keeping xed the truth values of the atoms with respect to which ' is independent (i.e., the atoms which do not a ect the truth value of '). This is consistent with Rescher's idea that the concept of ceteris paribus should be de ned in terms of a concept of independence between formulas [ 25 ] (see also [ 10 ]). In formal terms, let ' be a propositional formula. Then:

i M; w j= O ' () 8v; u 2 W : if M; v j= ' and v M; w j= Pi' () 8v; u 2 W : if M; v j= ' and v Indep(') u then M; u j= ' Indep(') u then M; u j= ' where Indep(') = fp 2 Atm : 8w 2 W; w [ fpg j= ' i w n fpg j= 'g denotes the set of atoms with respect to which ' is independent and w j= ' means that the valuation w satis es the propositional formula '. We use the notation Oi for independence-based \ceteris paribus" obligation and Pi for independence-based \ceteris paribus" permission. Notice that Atm n Atm(') Indep('). Thus, a ceteris paribus obligation/permission de ned in terms of Atm n Atm(') implies a ceteris paribus obligation/permission de ned in terms of Indep('), as if two worlds are equivalent with regard to Indep(') then they are also equivalent with regard to Atm n Atm('). The reason why the previous notions of obligation and permission are closed under logical equivalence is that two logical equivalent formulas are independent with respect to the same set of atomic propositions. Moreover, they have the same truth values at all worlds of a preference model. This feature is captured by the following two validities: j=P U(' $ j=P U(' $ ) ! (Oi' ! Oi ) ) ! (Pi' ! Pi ) This means that if ' and are universally equivalent, then having the obligation (resp. permission) that ' is the same as having the obligation (resp. permission) that . Since logical equivalence (i.e., equivalence relative to all preference models) is stronger than universal equivalence (i.e., equivalence relative to a speci c preference model), we also have the following properties: j=P ' $ j=P ' $ then j=P (Oi' ! Oi ) then j=P (Pi' ! Pi ) 7

Conclusion and perspectives

In this paper, we have presented a new approach to deontic logic, based on ceteris paribus preferences, which provides a fresh foundation to the logical analysis of deontic concepts. We have introduced the idea of ceteris paribus preferences and on this basis we have built the semantics of a deontic logic, named CPDL (ceteris paribus deontic logic). We have shown that CPDL not only avoids some deontic paradoxes, but also provides an adequate conceptualisation of obligations and permission, conditioned and unconditioned. In particular, CPDL supports formal models of obligations and permission that match common-sense intuitions and legal language. We have also examined some properties of the resulting logical system showing in particular how it supports for limited aggregation of conjunctions and factual detachment. We provided a connection with knowledge representation in order to compactly represent and reason over the set of obligations and permissions using the CP-net formalism. We are currently working to develop the framework of CPDL in various directions, concerning both theory and applications.

References

1. Allen , T.E.: CP-nets with indi erence . In: 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton) . pp. 1488 { 1495 . IEEE ( 2013 )

2. Aqvist , L. : Deontic logic . In: Handbook of philosophical logic , pp. 605 { 714 . Springer ( 1984 )

3. Bienvenu , M. , Lang , J. , Wilson, N.: From preference logics to preference languages, and back . In: Twelfth International Conference on the Principles of Knowledge Representation and Reasoning ( 2010 )

4. Boutilier , C. , Brafman , R.I. , Hoos , H.H. , Poole , D. : Reasoning with conditional ceteris paribus preference statements . In: Proc. of the 15th UAI . pp. 71 { 80 ( 1999 )

5. Carmo , J. , Jones , A.J.: Deontic logic and contrary-to-duties . In: Handbook of philosophical logic , pp. 265 { 343 . Springer ( 2002 )

6. Chisholm , R.M. : Contrary-to-duty imperatives and deontic logic . Analysis 24 ( 2 ), 33 { 36 ( 1963 )

7. F llesdal, D. , Hilpinen , R.: Deontic logic: An introduction . In: Deontic logic: Introductory and systematic readings , pp. 1 { 35 . Springer ( 1970 )

8. Forrester , J.W. : Gentle murder, or the adverbial samaritan . The Journal of Philosophy 81 ( 4 ), 193 { 197 ( 1984 )

9. Gabbay , D. , Horty , J. , Parent , X., van der Meyden , R., van der Torre, L.: Handbook of deontic logic and normative systems ( 2013 )

10. Girard , P. : Von wright's preference logic reconsidered ( 2006 )

11. Grandi , U. , Loreggia , A. , Rossi , F. , Saraswat , V. : From sentiment analysis to preference aggregation . In: ISAIM ( 2014 )

12. Grossi , D. , Lorini , E. , Schwarzentruber , F. : The ceteris paribus structure of logics of game forms . Journal of Arti cial Intelligence Research 53 , 91 { 126 ( 2015 )

13. Hansen , J.: Is there a logic of imperatives. Deontic Logic in Computer Science, Twentieth European summer school in Logic, Language and Information, Germany ( 2008 )

14. Hansson , B. : An analysis of some deontic logics . In: Deontic Logic: Introductory and Systematic Readings , pp. 121 { 147 . Springer ( 1970 )

15. Hansson , S.O. : Preference-based deontic logic (pdl) . Journal of Philosophical Logic 19 ( 1 ), 75 { 93 ( 1990 )

16. Hansson , S.O.: The structure of values and norms . Cambridge University Press ( 2001 )

17. Hilpinen , R.: Deontic logic: Introductory and systematic readings , vol. 33 . Springer Science & Business Media ( 2012 )

18. Hilpinen , R. , McNamara , P. : Deontic logic: A historical survey and introduction . Handbook of deontic logic and normative systems 1 , 3{ 136 ( 2013 )

19. Jones , A.J.: Deontic logic and legal knowledge representation . Ratio Juris 3 ( 2 ), 237 { 244 ( 1990 )

20. Li , M. , Kazimipour , B. : An e cient algorithm to compute distance between lexicographic preference trees . In: Proc. of the 27th IJCAI 2018 . pp. 1898 { 1904 ( 2018 )

21. Loreggia , A. , Mattei , N. , Rossi , F. , Venable , K.B. : Preferences and ethical principles in decision making . In: Proc. 1st AIES ( 2018 )

22. Loreggia , A. , Mattei , N. , Rossi , F. , Venable , K.B.: On the distance between CPnets . In: Proc. of the 17th AAMAS . pp. 955 { 963 ( 2018 )

23. Loreggia , A. , Mattei , N. , Rossi , F. , Venable , K.B.: CPMetric: Deep siamese networks for metric learning on structured preferences . In: Arti cial Intelligence . IJCAI 2019 International Workshops . pp. 217 { 234 . Springer ( 2020 )

24. Prakken , H. , Sergot , M. : Dyadic deontic logic and contrary-to-duty obligations . In: Defeasible deontic logic , pp. 223 { 262 . Springer ( 1997 )

25. Rescher , N.: Semantic foundations for the logic of preference. The logic of decision and action pp. 37 { 62 ( 1967 )

26. Ross , A. : Imperatives and logic . Philosophy of Science 11 ( 1 ), 30 { 46 ( 1944 )

27. Van Benthem , J. , Girard , P. , Roy , O. : Everything else being equal: A modal logic for ceteris paribus preferences . Journal of philosophical logic 38(1) , 83 { 125 ( 2009 )

28. Von Wright , G.H. : Deontic logic . Mind 60 ( 237 ), 1 { 15 ( 1951 )

29. Von Wright , G.H.: The logic of preference ( 1963 )

30. Von Wright , G.H.: A new system of deontic logic . In: Deontic Logic: Introductory and Systematic Readings , pp. 105 { 120 . Springer ( 1970 )

31. Von Wright , G.H.: The logic of preference reconsidered ( 1972 )

32. Wang , H. , Shao , S. , Zhou , X. , Wan , C. , Bouguettaya , A. : Preference recommendation for personalized search . Knowledge-Based Systems 100 , 124 { 136 ( 2016 )

33. Weinberger , C. , Weinberger , O. : Logik, semantik, hermeneutik ( 1980 )