Andrea Loreggia

Emiliano Lorini

Giovanni Sartor

Modeling Ceteris Paribus Preferences with Deontic Logic

Keywords: Deontic Logic, Ceteris paribus preferences, CP-net

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. We show that the fragment of our logic in which the content of a deontic operator is a literal has an equivalent representation based on CP-nets.

Introduction

Artificial agents are used to automate tasks in many scenarios. They are so pervasive and fast that it is almost impossible for humans to monitor them in order to prevent illegal or unethical behaviour. A possible solution is to embed (aspects of) normative governance into such agents. This requires translating legal and ethical requirements into computable representations of legal knowledge and reasoning. The basic component of normative knowledge consists in obligations and permissions. Obligations impose requirements while permissions confer allowances.

Our approach to model obligations and permission connects deontic logic and preference models.

Deontic logic has been viewed as a key component of logical models of normative knowledge and reasoning. It provides a set of formal tools, usually based on modal logic [START_REF] Åqvist | Deontic logic[END_REF][START_REF] Gabbay | Handbook of deontic logic and normative systems[END_REF] to capture normative notions, which can be compositionally integrated with other logical formalism, such as predicate logic, logic programming, defeasible logics, logics of action [START_REF] Bienvenu | From preference logics to preference languages, and back[END_REF][START_REF] Jones | Deontic logic and legal knowledge representation[END_REF].

Preferences are central to decision processes and thus are implemented in many frameworks to drive, assist, or influence individuals (e.g., recommender system [START_REF] Wang | Preference recommendation for personalized search[END_REF], sentiment analysis [START_REF] Grandi | From sentiment analysis to preference aggregation[END_REF][START_REF] Grandi | A borda count for collective sentiment analysis[END_REF], and in deep learning ensemble methods [START_REF] Cornelio | Voting with random classifiers (VORACE): theoretical and experimental analysis[END_REF]). By comparing agents' preferences, it is possible to assess the similarity of their evaluative attitudes, [START_REF] Li | An efficient algorithm to compute distance between lexicographic preference trees[END_REF][START_REF] Loreggia | On the distance between CPnets[END_REF]. Similarly, agents' behaviour can be compared with exogenous priorities, based on moral principles, legal requirements, guidelines or expected business processes. In this way it is possible to assess the extent to which the agent deviates from what is desired [START_REF] Sen | Choice, ordering and morality[END_REF][START_REF] Loreggia | Preferences and ethical principles in decision making[END_REF][START_REF] Loreggia | Value alignment via tractable preference distance[END_REF][START_REF] Loreggia | Modeling and reasoning with preferences and ethical priorities in AI systems[END_REF].

A usual criticism of standard deontic logic is that it focuses on ideal worlds, namely on a set of worlds in which all obligations are satisfied, and each permission can be implemented. Unfortunately real life situations do not meet this description: even if some obligations are not complied with, still the involved agents have to determine what they should do, relatively to the other obligations at stake. A ceteris-paribus based deontic logic provides for this situation, since it focuses on partial improvements, rather than on perfect worlds, namely in those changes in the given worlds which could make it better, all remaining aspects being unchanged (e.g., possibly imperfect as before).

To connect deontic logic and preferences, we provide semantics for a deontic logic based on the idea that obligations and permissions consist in ceteris paribus 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 affairs that are affirmed 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 defined.

In this work, we are also interested in making a connection between the area of deontic logic and artificial intelligence. We think cooperation among researchers from the two areas can be very beneficial, and possibly lead to a new workable approach to model norms and reason about them. There have been various attempts at basing a deontic logic on the idea of preferences (see for instance [START_REF] Hansson | Preference-based deontic logic (pdl)[END_REF][START_REF] Åqvist | Deontic logic[END_REF][START_REF] Hansson | The structure of values and norms[END_REF]). The notion of ceteris paribus preferences is employed in literature for modeling deontic concepts such as contrary-to-duties (e.g., [START_REF] Van Benthem | On the two faces of deontics: Semantic betterness and syntactic priority[END_REF][START_REF] Cholvy | An attempt to adapt a logic of conditional preferences for reasoning with contrary-to-duties[END_REF][START_REF] Garion | Design by contract deontic design language for multiagent systems[END_REF][START_REF] Loreggia | A ceteris paribus deontic logic[END_REF]) and they also provide the intuition at the basis of a preference framework named conditional preference networks or CP-nets [START_REF] Boutilier | Reasoning with conditional ceteris paribus preference statements[END_REF]. CP-nets, and their variants, are emerging preference frameworks that allow representing conditional preferences in a compact way. The framework is adopted in many different scenarios. For instance, in recommender systems, they are employed to improve the accuracy of personalized search [START_REF] Wang | Preference recommendation for personalized search[END_REF]. A first attempt to model deontic notions with CP-nets has been done in [START_REF] Garion | Apports de la logique mathématique en ingénierie des exigences[END_REF].

By modeling the normative system of a multi-agent system with a CP-net we obtain a compact representation that would allow us to check important properties of the modeled normative system, like for instance its consistency [START_REF] Loreggia | Modelling ethical theories compactly[END_REF]. When preferences of agents are also modeled through CP-nets, it is possible to check their compliance against exogenous preferences (e.g., normative systems, laws, ethical principles) [START_REF] Loreggia | CPMetric: Deep siamese networks for metric learning on structured preferences[END_REF][START_REF] Loreggia | Modeling and reasoning with preferences and ethical priorities in AI systems[END_REF][START_REF] Rossi | Preferences and ethical priorities: Thinking fast and slow in AI[END_REF]. In this regard, recently, new approaches define metric spaces over structured preferences [START_REF] Li | An efficient algorithm to compute distance between lexicographic preference trees[END_REF][START_REF] Loreggia | On the distance between CPnets[END_REF][START_REF] Loreggia | Metric learning for value alignment[END_REF], providing feasible ways for preferences comparison.

Our formalisation does not allow for the derivation of deontic paradoxes, but supports some deontic inferences. In future work, we plan to complement our work with a dynamical analysis of the way in which prescriptive acts generate ceteris paribus preferences, so determining the truth-values of primary and inferred deontic propositions. This paper expands results published in [START_REF] Loreggia | A ceteris paribus deontic logic[END_REF][START_REF] Loreggia | A novel approach for a ceteris paribus deontic logic[END_REF], and discusses some limitations of our current definitions, which we hope we will be able to address in our future research.

The paper is organized as follows: we first 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 show that the satisfiability problem for the proposed languages is P-complete. This is done by providing a polynomial procedure that allows to transform our language into the one proposed in [START_REF] Grossi | The ceteris paribus structure of logics of game forms[END_REF]. We also put the basis for a syntax independence of the ceteris paribus deontic logic. Finally, we show how existing AI formalisms (such as CP-nets [START_REF] Boutilier | Reasoning with conditional ceteris paribus preference statements[END_REF]) can be used to represent our idea of ceteris paribus deontic logic.

Related work

In this section we shall provide some background for our proposal, by referring first to deontic logic and then to preferences.

Deontic logic

An intuitive semantics and a simple axiomatisation for deontic notions are provided by the so-called standard deontic logic or SDL [START_REF] Føllesdal | Deontic logic: An introduction[END_REF], built on the basis of the so-called old system of deontic logic by [START_REF] Wright | Deontic logic[END_REF], (for a discussion of SDL, see [START_REF] Hilpinen | Deontic logic: Introductory and systematic readings[END_REF][START_REF] Hilpinen | Deontic logic: A historical survey and introduction[END_REF]). 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 as 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. A corresponding axiomatisation can be obtained by adding to propositional logic the deontic K principle O(ϕ → ψ) → (Oϕ → Oψ), the principle of deontic consistency Oϕ → Pϕ, and the rule of necessitation ϕ Oϕ according to which if ϕ is a logical necessity then it is obligatory.

As it has been often remarked, SDL gives rise to several apparently counterintuitive implications, the so-called deontic paradoxes (for a discussion, see [START_REF] Åqvist | Deontic logic[END_REF],

for an analysis from the perspective of legal theory, see also [START_REF] Weinberger | Logik, semantik[END_REF][START_REF] Hansen | Is there a logic of imperatives[END_REF]). First of all, as legal theorist Alf Ross critically observed [START_REF] Ross | Imperatives and logic[END_REF], the obligation of a certain proposition should not entail the obligation concerning the disjunction of that proposition and any other arbitrary proposition. For instance, the obligation that a letter is posted (Op), should not entail the obligation that the letter is posted or burned, O(p ∨ b). In SDL, however, Oϕ entails O(ϕ ∨ ψ). It is easy to see that this entailment is sound according to the semantics of SDL: if in all ideal worlds it is the case that ϕ in all such worlds it must also be the case that ϕ ∨ ψ. 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 the paradoxes by Forrester (the gentle murderer), Roderick Chishol [START_REF] Chisholm | Contrary-to-duty imperatives and deontic logic[END_REF] and by Marek Sergot and Henry Prakken [START_REF] Prakken | Dyadic deontic logic and contrary-to-duty obligations[END_REF]. Various solutions have been proposed to address contrary to duty obligations, often involving technical complexities and sometimes giving rise to additional problems [START_REF] Carmo | Deontic logic and contrary-to-duties[END_REF].

A further problematic aspect of SDL concerns conditional or rather contextual obligations, namely, assertions to the effect 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 spawned the development of dyadic deontic logic, which captures deontic conditionality through a special conditional operator. Dyadic deontic logic was initiated by Georg Henrik Von Wright [START_REF] Wright | A new system of deontic logic[END_REF], while a semantics for it was first proposed by Bengt Hansson [START_REF] Hansson | An analysis of some deontic logics[END_REF].

Technical solutions have been proposed to deal with deontic conditionals and contrary to duty obligations (see [START_REF] Prakken | Dyadic deontic logic and contrary-to-duty obligations[END_REF][START_REF] Carmo | Deontic logic and contrary-to-duties[END_REF]). These solutions, however, generally require a more complex logical framework and a less intuitive semantics, in comparison with SDL (see [START_REF] Hilpinen | Deontic logic[END_REF]).

Preferences

The idea of ceteris paribus preference was originally introduced by Von Wright [START_REF] Wright | The logic of preference[END_REF][START_REF] Wright | The logic of preference reconsidered[END_REF].

Von Wright observes that our preferences over states of affairs (as opposed to preferences over objects) are usually "holistic", in the sense that they address the compared states of affairs-denoted by Boolean combination of atoms-in the context of the circumstances accompanying such states of affairs: "What makes a person at one time prefer a state of affairs p to a state of affairs q, and at another time perhaps prefer q to p, can be the fact that the circumstances, i.e., the other states beside p and q themselves, which obtain or are taken into account at the first time, are different from the circumstances obtaining or being taken into account at the other time" [START_REF] Wright | The logic of preference reconsidered[END_REF].

However, there is a sense in which we may claim that a certain state of affairs is preferred to another state of affairs without making this preference conditional on particular circumstances. This is the case in which a state of affairs is preferred to another in every possible context. In such a case we say that the first state of affairs is preferred ceteris paribus (all the rest being equal).

To capture the idea of a holistic preference, von Wright considers a set of atoms Atm = {p 1 , . . . , p n }, each describing an elementary and independent state of a complete situation, or world. Since each atom can be true or false in any possible world, Atm originates a powerset W = 2 Atm of distinct possible worlds. Von Wright [START_REF] Wright | The logic of preference reconsidered[END_REF] observes that the set W = 2 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".

Ceteris paribus preferences have recently been the object of renewed interest by logicians, who have developed ceteris paribus semantics for action and preference [START_REF] Grossi | The ceteris paribus structure of logics of game forms[END_REF][START_REF] Van Benthem | Everything else being equal: A modal logic for ceteris paribus preferences[END_REF]. It has also been remarked [START_REF] Bienvenu | From preference logics to preference languages, and back[END_REF] that preference logics and preference representation languages are both concerned with reasoning about preferences over combinatorial domains and that in both areas the ceteris paribus principle plays a key role in the interpretation of preference statements [START_REF] Van Benthem | Everything else being equal: A modal logic for ceteris paribus preferences[END_REF].

Our notion of an obligation can be connected to the notion of goal introduced in [START_REF] Wellman | Preferential semantics for goals[END_REF], in which a goal represents a partition of possible states, those which satisfy the goal being ceteris paribus preferable to those that do not satisfy the goal.

The ceteris paribus Deontic Logic-CPDL

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 call ceteris paribus Deontic Logic (CPDL) the resulting deontic logic of obligation and permission.

In this section, we provide a formal definition of the relevant concepts. In the next section we shall discuss them and exemplify their application.

Ceteris paribus Preferences

We first present the basic elements of the formal semantics, namely, the concepts of preference model and ceteris paribus preference.

Let Atm be a non-empty finite set of atomic propositions and let Lit = Atm ∪ {¬p : p ∈ Atm} be the corresponding set of literals.

Definition 1 (Preference model).

A preference model is a tuple M = (W, ) such that: W = 2 Atm is the set of worlds, and is a complete preorder on W . 4Elements of W are denoted by w, v, . . .. Note that we assume that the set W is complete, i.e., that it includes all possible words (relative to atoms Atm). We write w v meaning that v is at least as good/ideal as w. As usual, we define w ≺ v, meaning that world v is better/more ideal than world w, to be an abbreviation of w v and v w. Moreover, we define w ≈ v, meaning that v is equivalent to w, to be an abbreviation of w v and v w. The class of preference models is denoted by P.

A weak preference model differs from a preference model as it does not necessarily include all valuations of propositional variables. Specifically, W is a subset of the set of all the possible worlds. In particular: Definition 2 (Weak preference model). A weak preference model is a tuple M = (W, ) such that W ⊆ 2 Atm is the set of worlds, and is a complete preorder on W .

In the following, unless differently specified, we shall only make use of preference model tout court. We shall consider weak preference models only in section 4.2, to deal with contrary-to-duty obligations.

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

Definition 3 (Circumstantial Indistinguishability). Let M = (W, ) be a preference model, let w, v ∈ W and let X be a finite set of atomic propositions. We say that w

≡ X v iff ∀p ∈ X : p ∈ w iff p ∈ v.
According to definition 3, w ≡ X v means that w and v are indistinguishable, with regard to the circumstances (the atoms) in X.

Definition 4 (Circumstantial Preference

). Let M = (W, ) be a preference model, let w, v ∈ W and let X be a finite set of atomic propositions. We introduce the following abbreviations: w X v, iff w ≡ X v and w v, w ≺ X v, iff w ≡ X v and w ≺ v respectively.

According to definition 4, w X v means that v is at least as good as w, the two worlds being indistinguishable relative to X. Correspondingly, 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 relative to an atom set X.

Definition 5 (Ceteris Paribus Preference).

A world w is ceteris paribus at least as good as or ceteris paribus better than a world v apart from Y , if v Atm\Y w or v ≺ Atm\Y w respectively.

The former definition concerns indistinguishability and preference relative to all atoms not in Y , i.e., relatively to Atm \ Y .

Unconditional obligations and permissions: formalisation

On the basis of the notions introduced in the previous section, we shall now address obligations and permission. Definition 6. L CPDL (Atm) is the modal language which consists of atomic propositions p, q, . . . ∈ Atm, standard Boolean operators and the modal operators O, P, U. More precisely, it is the smallest set such that:

-if p ∈ Atm, then p ∈ L CPDL -if ϕ, ψ ∈ L CPDL , then ¬ϕ, ϕ ∧ ψ ∈ L CPDL -if ϕ, ψ ∈ L CPDL , then Oϕ, Pϕ, Uϕ ∈ L CPDL .
We note by L CPDL-Prop (Atm) the fragment of the language L CPDL (Atm) in which formulas in the scope of deontic operators O and P can only be propositional.

Boolean constructions , ⊥, ∨, → and ↔ are defined from p, ¬ and ∧ in the standard way.

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 L CPDL (Atm) are defined as follows:

Definition 7 (Truth Conditions). Let M = (W, ) be a preference model and let w ∈ W . Then:

M, w |= p ⇐⇒ p ∈ w M, w |= ¬ϕ ⇐⇒ M, w |= ϕ M, w |= ϕ ∧ ψ ⇐⇒ M, w |= ϕ and M, w |= ψ M, w |= Oϕ ⇐⇒ ∃v ∈ W such that M, v |= ϕ, and ∀v, u ∈ W : if M, v |= ϕ and v Atm\Atm(ϕ) u then M, u |= ϕ M, w |= Pϕ ⇐⇒ ∃v ∈ W such that M, v |= ϕ, and ∀v, u ∈ W : if M, v |= ϕ and v ≺ Atm\Atm(ϕ) u then M, u |= ϕ M, w |= Uϕ ⇐⇒ ∀v ∈ W : M, v |= ϕ
where Atm(ϕ) denotes the set of atoms from Atm occurring in ϕ.

It is worth noting that the interpretation of the obligation and permission operator could be equivalently stated as follows:

M, w |= Oϕ ⇐⇒ ∃v ∈ W such that M, v |= ϕ, and ∀v, u ∈ W : if M, u |= ϕ, M, v |= ¬ϕ and v ≡ Atm\Atm(ϕ) u then v ≺ u M, w |= Pϕ ⇐⇒ ∃v ∈ W such that M, v |= ϕ, and ∀v, u ∈ W : if M, u |= ϕ, M, v |= ¬ϕ and v ≡ Atm\Atm(ϕ) u then v u
In other words, Oϕ means that ϕ is possible and, for every two possible worlds that are Atm \ 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 ϕ is possible and, for every two possible worlds that are Atm \ 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.

Note that the valuation of the obligation operator does not depend on the actual world. Either Oϕ is true at all worlds of the model or at none of them. This is justified by the fact that we are not providing a dynamic model of obligations and permissions whereby norms may differ from world to world. Our model is meant to capture a normative system at a single point in time and no space.

We say that the formula ϕ ∈ L CPDL (Atm) is valid relative to the class of preference models P, denoted by |= P ϕ, iff, for every preference model M and for every world w in M , we have M, w |= ϕ. We say that the formula ϕ ∈ L CPDL (Atm) is satisfiable relative to the class of preference models iff, there exists a preference model M and a world w in M , such that M, w |= ϕ.

Conditional obligations and permissions: formalisation

In this section we extend the logic CPDL by operators of conditional obligation and conditional permission. We call CPDL + the resulting logic. Definition 8. L CPDL + (Atm) is a modal language which consists of atomic propositions p, q, . . . ∈ Atm, standard Boolean operators and the modal operators O, P, U. More precisely, it is the smallest set such that:

-if p ∈ Atm, then p ∈ L CPDL + -if ϕ, ψ ∈ L CPDL + , then ¬ϕ, ϕ ∧ ψ ∈ L CPDL + -if ϕ, ψ ∈ L CPDL + , then Oϕ, Pϕ, O(ψ|ϕ), P(ψ|ϕ), Uϕ ∈ L CPDL + .
We note by L CPDL + -Prop (Atm) the fragment of the language L CPDL + (Atm) in which formulas in the scope of deontic operators O and P can only be propositional.

Formulas O(ψ|ϕ) and P(ψ|ϕ) have to be read, respectively, "under condition ψ, ϕ is obligatory " and "under condition ψ, ϕ is permitted". The truth conditions for the formulas in the language L CPDL + (Atm) are the ones given in Definition 7 plus the following two extra truth conditions for the conditional obligation operator and the conditional permission operator: Definition 9 (Truth conditions (cont.)). Let M = (W, ) be a preference model and let w ∈ W . Then:

M, w |= O(ψ|ϕ) ⇐⇒ ∃v ∈ W such that M, v |= ϕ ∧ ψ, and ∀v, u ∈ ||ψ|| M : if M, v |= ϕ and v Atm\Atm(ϕ) u then M, u |= ϕ M, w |= P(ψ|ϕ) ⇐⇒ ∃v ∈ W such that M, v |= ϕ ∧ ψ, and ∀v, u ∈ ||ψ|| M : if M, v |= ϕ and v ≺ Atm\Atm(ϕ) u then M, u |= ϕ where ||ψ|| M = {w ∈ W : M, w |= ψ} is the truth set of ψ relative to the preference model M .
The definitions of validity and satisfiability for the formulas in L CPDL + (Atm) relative to preference models are analogous to the definitions of validity and satisfiability for the formulas in L CPDL (Atm) relative to preference models.

Discussion and examples

In this section, we describe several properties of our logic as well as showing that our model does not produce several well-known paradoxes in deontic logic. We give more insights by using detailed examples. We shall first discuss the general properties of our logic.

Properties of CPDL

In this section we shall illustrates some basic validities of our logic, which enable corresponding deontic inferences.

Proposition 1. For all ϕ ∈ L CPDL + (Atm):

|= P Oϕ ↔ O( |ϕ) |= P Pϕ ↔ P( |ϕ)
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 definable from conditional obligation and permission.

The following proposition highlights that if ϕ is obligatory, then it is also permitted: Proposition 2. For all ϕ ∈ L CPDL + (Atm):

|= P Oϕ → Pϕ
Before dealing with deontic paradoxes, let us consider how factual detachment is represented in the context of the logic CPDL + : Proposition 3. For all ϕ ∈ L CPDL + (Atm):

|= P (O(ψ|ϕ) ∧ Uψ) → Oϕ |= P (P(ψ|ϕ) ∧ Uψ) → Pϕ
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 [START_REF] Ross | Imperatives and logic[END_REF]. 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 1. Let Atm = {m, b} with w 1 = {m, b}, w 2 = {m}, w 3 = {b} and w 4 = ∅. Let us suppose the following preference ordering over the worlds in W :

w 3 ≺ w 1 ≺ w 4 ≺ w 2 . We clearly have M, w 1 |= Om ∧ ¬O(m ∨ b).
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 ϕ, ψ ∈ L CPDL + (Atm) such that the formula (Oϕ ∧ O(ϕ → ψ)) → Oψ is not valid in CPDL. To show this, it is sufficient to consider the preference model in Example 1. We have M,

w 1 |= (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 ϕ, ψ ∈ L CPDL + (Atm) such that:

|= P (Oϕ ∧ Oψ) → O(ϕ ∧ ψ), |= P (Pϕ ∧ Pψ) → P(ϕ ∧ ψ)
To show this it is sufficient to consider the following example. (The latter is proved in an analogous way.) Example 2. Let Atm = {p, q} and w 1 = {p, q}, w 2 = {q}, w 3 = {p}, w 4 = ∅. Moreover, let us consider the following preference order : w3 ≺ w1 ≺ w4 ≺ w2.

It is routine exercise to check that M, w

1 |= O(p → q), M, w 1 |= Oq, but M, w 1 |= O((p → q) ∧ q).
To verify the latter it is sufficient to observe that w 1 w 4 .

Nonetheless, if ϕ and ψ are conjunctive clauses (i.e., finite 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.

|= P (Oϕ ∧ Oψ) → O(ϕ ∧ ψ) |= 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 |= Oϕ ∧ Oψ and (ii) M, w |= O(ϕ ∧ ψ). Item (i) means that: Let us suppose that (C) holds. We consider three possible cases. Case 1: M, u |= ¬ϕ ∧ ψ. Since ϕ and ψ are conjunctive clauses we have v ≡ Atm\Atm(ϕ) u. But this is in contradiction with item (i) above.

(A) ∀v, u ∈ W : if M, v |= ϕ and v ≡ Atm\Atm
Case 2: M, u |= ϕ ∧ ¬ψ. Since ϕ and ψ are conjunctive clauses we have v ≡ Atm\Atm(ψ) u. But this is in contradiction with item (i) above.

Case 3: M, u |= ¬ϕ ∧ ¬ψ. There exists w ∈ W such that M, w |= ¬ϕ ∧ ψ and v ≡ Atm\Atm(ϕ) w and w ≡ Atm\Atm(ψ) u. It is sufficient to consider the world w such that ∀p ∈ Atm(ϕ) : p ∈ w iff p ∈ u, ∀p ∈ Atm(ψ) : p ∈ w iff p ∈ v, and ∀p ∈ Atm \ (Atm(ϕ) ∪ Atm(ψ)) : p ∈ w iff p ∈ 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 u. The latter is in contradiction with item (A) above. Now, let us suppose that (D) holds. Since ϕ and ψ are assumed to be conjunctive clauses such that Atm(ϕ) ∩ Atm(ψ) = ∅ and M is a preference model such that W = 2 Atm , item (B) above implies that ∃z ∈ W such that M, z |= ϕ ∧ ψ. The latter is in contradiction with item (D).

As shown in Example 2, 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. 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. Thus, our logic of obligations is not a classical modal logic. On the other hand, not meeting closure under logical equivalence might be acceptable from the point of view of the imperative theory of norms defended, among the others, by Von Wright. It has been argued that an obligation, seen as an imperative or a command that a certain fact ought to be the case, does not necessarily imply that all logically equivalent facts are obligatory as well ( [START_REF] Kanger | New foundations for ethical theory[END_REF], [START_REF] Hansen | Is there a logic of imperatives[END_REF]).

In our logic the principle of the substitution of a formula ϕ with a logically equivalent formula ψ in a deontic expression O(χ|ϕ) or P(χ|ϕ) only holds if exactly the same atoms occur in ϕ and ψ.

However, we agree that in many contexts closure under logical equivalence may be a desirable feature of a deontic logic. In Section 6 we introduce a variant of our logic that provides such feature.

It also worth noting that the obligation operator does not satisfy weakening. Indeed, the formula O(p ∧ q) → Op is not valid in the class of preference models for p = q. Nonetheless, as the following proposition highlights, we have a weaker property.

Proposition 5. For all p, q ∈ Atm such that p = q:

|= P O(p ∧ q) → ¬O¬p
Proof. Let us suppose that M, w |= O(p ∧ q). The latter implies that:

(A) ∀v, u ∈ W : if M, v |= p ∧ q and v ≡ Atm\Atm(p∧q) u and v u then M, u |= p ∧ q.
Since M is a preference model such that W = 2 Atm , we have:

(B) ∃z, z ∈ W such that M, z |= p ∧ q, M, z |= ¬p ∧ q and z ≡ Atm\Atm(p) z .

Items (A) and (B) together imply that:

(C) ∃z, z ∈ W such that M, z |= p and M, z |= ¬p and z ≡ Atm\Atm(p) z and z z.

The latter means that M, w |= ¬O¬p.

Before concluding, we would like to discuss a validity concerning nesting of obligations. In our logic, if ϕ is obligatory then it is obligatory that ϕ is obligatory, that is:

|= P Oϕ → OOϕ
This is due to the fact that (i) if ϕ is obligatory then it is necessarily the case that ϕ is obligatory (i.e., Oϕ → UOϕ) and (ii) if ϕ is necessary then ϕ is obligatory (i.e., Uϕ → Oϕ). To prevent such an entailment, a further condition should be added to the definition of obligation, namely, the fact that for ϕ to be obligatory, ¬ϕ has to be possible (i.e., ∃v ∈ W such that M, v |= ¬ϕ). By adding this negative condition to the definition of the obligation operator, obligations about tautologies become impossible (i.e., ¬O becomes valid), which is often considered a requirement for deontic logic [START_REF] Wright | Norm and Action: A Logical Inquiry[END_REF]. Also, thanks to the previous negative condition, Oϕ → ¬OOϕ becomes valid. Indeed, Oϕ still implies UOϕ and, thanks to the negative condition, OOϕ implies ¬UOϕ.

The Forrester's paradox and weak models

We conclude this section by considering the well-known Forrester's gentle murderer paradox [START_REF] Forrester | Gentle murder, or the adverbial samaritan[END_REF]. 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 atom kg.

A first formalisation may be obtained in the following way: fact 1 is expressed by the formula O¬k; fact 2 and is expressed by the formula k → Okg; while fact 3 is expressed by the formula U(kg → k).

As emphasized in the introduction, under the assumption that you kill, fact 1, fact 2 and fact 3 are together inconsistent in SDL (expanded with a necessity operator U), i.e., k ∧ O¬k ∧ (k → Okg)) is an inconsistent SDL formula. The problem is that in SDL from k and k → Okg we can infer Okg which, in combination with U(kg → k), implies Ok. Since the SDL obligation operator O satisfies Axiom D, it is not possible to have Ok and O¬k. This formalisation is not meaningful in our preference model, since in these models all logically possible words have to be taken into account. Therefore, the formula U(kg → k) (which would exclude from a model all worlds satisfying kg ∧ ¬k) is unsatisfiable in the class of preference models.

To capture the Forrester paradox, we need to use weak preference models. The formula k ∧ O¬k ∧ (k → Okg) ∧ U(kg → k) is satisfiable for the class of weak preference models. Indeed, there exists a weak preference model which concomitantly satisfies the three formulas O¬k, Okg and U(kg → k). The following is an example of such a weak preference model: W = {w 1 , w 2 , w 3 }, w 1 = {kg, k}, w 2 = {k} and w 3 = ∅ with w 2 ≺ w 1 , w 2 ≺ w 3 and w 1 ≈ w 3 .

An alternative solution to the Forrester's gentle murderer paradox, widely explored in the literature (see, e.g., [START_REF] Prakken | Dyadic deontic logic and contrary-to-duty obligations[END_REF]) consists in reformulating condition (2) above as the conditional obligation of killing gently under the condition of killing. Specifically, we again represent fact 1 by the formula O¬k and fact 3 as U(kg → k), while we now represent fact 2 by the formula O(k|kg). Let us also assume that k is true. It is easy to verify that the formula O¬k ∧O(k|kg)∧k ∧U(kg → k) is satisfiable in the class of weak preference models.

Computational Complexity

In this section, we prove that the satisfiability problems for the fragments of L CPDL (Atm) and L CPDL + (Atm) in which obligations and permissions are only about propositional facts are P-complete. In order to do that, we provide a translation from these languages to the language proposed in [START_REF] Grossi | The ceteris paribus structure of logics of game forms[END_REF], namely the language of the ceteris paribus logic CP. This was designed and developed with the purpose of embedding other formal logics, such as for instance the atemporal version of the logic of "seeing to it that" STIT [START_REF] Balbiani | Alternative axiomatics and complexity of deliberative STIT theories[END_REF] and dynamic logic of propositional assignments DL -PA [START_REF] Herzig | A dynamic logic of normative systems[END_REF], and highlighting common relationships and structures employed in different formalisms.

In order to provide a formal translation, we borrow some useful notations from [START_REF] Grossi | The ceteris paribus structure of logics of game forms[END_REF] to define the CP logic and the corresponding language L CP .

Given the finite set of atomic propositions Atm, the language L CP is such that:

L CP (Atm) :

ϕ ::= p | ¬ϕ | (ϕ ∧ ψ) | X ϕ
where p ∈ P and X ⊆ Atm. Formula X ϕ has to be read "ϕ is possible in some state which is X-equivalent to the current one (or also all things expressed in X being equal )". The dual of the operator X is defined in the usal way as follows:

[X]ϕ = def ¬ X ¬ϕ.
The language L CP is interpreted relative to a simple model W ⊆ 2 Atm and a point v ∈ W as follows. (We omit interpretation of atomic propositions and boolean operators since they are defined in the usual way.)

W, v |= X ϕ ⇐⇒ ∃u ∈ W such that v ≡ X u and W, u |= ϕ,
where ≡ X is the notion of circumstantial indistinguishability defined in Definition 3.

Translating Unconditional Obligations and Permissions

In this section, we provide a polynomial satisfiability preserving translation from the fragment of CPDL in which deontic operators can only be about propositional formulas to the CP logic. The idea of the translation is to exploit special atomic formulas for utility of type u k which allow us to simulate the preference ordering of the original preference model. In particular, the meaning of u k is that the actual world has a utility value equal to k where k ranges over Util = {0, . . . , n}. Since the set of atomic propositions Atm is finite, a weak preference model includes at most |2 Atm | elements while a preference model includes exactly |2 Atm | elements. Therefore, it suffices to suppose that n = |2 Atm |. Our translation tr : L CPDL (Atm) → L CP Atm ∪ {u k : k ∈ Util } is defined as follows:

tr(p) = p for p ∈ Atm, tr(¬ϕ) = ¬tr(ϕ), tr(ϕ ∧ ψ) = tr(ϕ) ∧ tr(ψ), tr(Oϕ) = ∅ tr(ϕ) ∧ [∅] k∈Util u k ∧ tr(¬ϕ) → [Atm \ Atm(ϕ)] tr(ϕ) → u >k , tr(Pϕ) = ∅ tr(ϕ) ∧ [∅]
u ≥k = def k ∈Util:k ≥k u k .
Note that when the formula in the scope of a deontic operator for obligation or permission is propositional, the previous translation is polynomial in the size of the input formula.

As the following theorem indicates, the previous translation provides an embedding of satisfiability checking for the language L CPDL into satisfiability checking for the language L CP .

Theorem 1. Let ϕ ∈ L CPDL (Atm). Then, ϕ is satisfiable relative to weak preference models if and only if [∅](χ 0 ∧ χ 1 ) ∧ tr(ϕ) is satisfiable relative to simple models, and ϕ is satisfiable relative to preference models if and only if [∅](χ 0 ∧ χ 1 ∧ χ 2 ) ∧ tr(ϕ) is satisfiable relative to simple models, where

χ 0 = def X⊆Atm,k∈Util ∅ u k ∧ con(X) → [∅] con(X) → u k , χ 1 = def k∈Util u k ∧ k,k ∈Util:k =k (u k → ¬u k ) , χ 2 = def X⊆Atm ∅ con(X), with con(X) = def p∈X p ∧ p∈Atm\X ¬p.
Proof. We only prove the first item, as the proof of the second item is analogous.

(⇒) Let W be a simple model and v ∈ W such that W, v |= [∅](χ 0 ∧ χ 1 ). We build the weak preference model M = (W , ) where W is defined as follows:

W = w \ {u k : k ∈ Util } : w ∈ W .
The fact W, v |= [∅](χ 0 ∧ χ 1 ) guarantees that we can build a bijection f from W to W such that, for every w ∈ W , w ∩ Atm = f (w) ∩ Atm . For notational convenience, for each w ∈ W , we denote f (w) by s w . We moreover define in M as follows:

∀s w , s w ∈ W : s w s w iff ∃k, k ∈ Util such that k ≤ k , u k ∈ w and u k ∈ w .
By induction on the structure of ϕ, we can prove that W, v |= tr(ϕ) iff M, s v |= ϕ. The atomic case and the boolean cases are straightforward. We just prove the case ϕ = ¬ψ as an example. M, s v |= ¬ψ is equivalent to M, s v |= ψ. By induction hypothesis, the latter is equivalent to W, v |= tr(ψ). The latter is equivalent to W, v |= ¬tr(ψ) which, by the definition of the translation tr, is the same as W, v |= tr(¬ψ).

w ≡ Atm\Atm(ψ) u then ∃k, k ∈ Util such that k < k , u k ∈ u and u k ∈ w (by definition of ), ⇐⇒ ∃z ∈ W s.t. W, z |= tr(ψ) and ∀w, u ∈ W, ∀k ∈ Util : if W, u |= tr(¬ψ), u k ∈ u, W, w |= tr(ψ) and w ≡ Atm\Atm(ψ) u then ∃k ∈ Util such that k < k and u k ∈ w (by the fact that W, v |= [∅]χ 1 ), ⇐⇒ W, v |= ∅ tr(ψ) and W, v |= [∅] k∈Util (u k ∧ tr(¬ψ)) → [Atm \ Atm(ϕ)](tr(ψ) → u >k ) , ⇐⇒ W, v |= tr Oψ .
The case ϕ = Pψ is analogous, while the case ϕ = Uψ is straightforward. Therefore, we do not need to prove them explicitly.

(⇐) Let M = (W, ) be a weak preference model and v ∈ W . We build the following utility ranking inductively:

U 0 = {w ∈ W : ∀u ∈ W, w u}, U k+1 = w ∈ W \ h≤k U h : ∀u ∈ W \ h≤k U h , w u .
U 0 is the set of worlds of 0-utility, while U k+1 is the set of worlds with k + 1utility. We build the simple model W as follows:

W = w ∪ {u k : w ∈ U k } : w ∈ W . It is easy to check that W , s v |= [∅] k∈Util u k ∧ k,k ∈Util:k =k (u k → ¬u k ) .
Moreover, by induction on the structure of ϕ, we can prove that W ,

s v |= tr(ϕ) iff M, v |= ϕ.
The following is a direct corollary of (i) the previous Theorem 1, (ii) the fact that the translation tr applied to the fragment L CPDL-Prop (Atm) is polynomial, (iii) the fact that satisfiability checking for the language L CP with finitely many atomic propositions is in PTIME. Item (iii) is a consequence of the fact that, as shown in [START_REF] Grossi | The ceteris paribus structure of logics of game forms[END_REF]Section 2.3], there exists a polynomial satisfiability preserving translation of the finite-variable CP logic into the finite-variable modal logic S5. It is known that satisfiability checking for the latter can be done in polynomial time [START_REF] Halpern | The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic[END_REF].

Corollary 1. Let ϕ ∈ L CPDL-Prop (Atm). Then, checking satisfiability of ϕ relative to the class of preference models (resp. weak preference models) can be done in polynomial time.

Translating Conditional Obligations and Permissions

All the observations done in the previous section are valid also for the case of conditional obligations and permissions. Notice that a condition simply enforces a preference relation on a smaller set of state-of-affairs. This means that the class of equivalence is smaller in the sense that the states that belong to it are all of those that have the partial assignment specified in the condition. In order to capture this idea, we enrich the translation with the following rules:

tr O(ψ|ϕ) = ∅ tr(ϕ ∧ ψ) ∧ [∅] tr(ψ) → k∈Util u k ∧ tr(¬ϕ) → [Atm \ Atm(ϕ)] (tr(ψ) ∧ tr(ϕ)) → u >k , tr P(ψ|ϕ) = ∅ tr(ϕ ∧ ψ) ∧ [∅] tr(ψ) → k∈Util u k ∧ tr(¬ϕ) → [Atm \ Atm(ϕ)] (tr(ψ) ∧ tr(ϕ)) → u ≥k .
The following theorem is a straightforward generalization of Theorem 1.

Theorem 2. Let ϕ ∈ L CPDL + (Atm). Then, ϕ is satisfiable relative to weak preference models if and only if [∅]χ 1 ∧ tr(ϕ) is satisfiable relative to simple models, and ϕ is satisfiable relative to preference models if and only if

[∅](χ 1 ∧ χ 2 ) ∧ tr(ϕ)
is satisfiable relative to simple models, where

χ 1 = def k∈Util u k ∧ k,k ∈Util:k =k (u k → ¬u k ) , χ 2 = def X⊆Atm ∅ p∈X p ∧ p∈Atm\X ¬p .
The following is a direct corollary of Theorem 2 and is proved in the same way as Corollary 1.

Corollary 2. Let ϕ ∈ L CPDL + -Prop (Atm). Then, checking satisfiability of ϕ relative to the class of preference models (resp. weak preference models) can be done in polynomial time.

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, i.e., "all else being equal". Following Von Wright (see also [START_REF] Van Benthem | Everything else being equal: A modal logic for ceteris paribus preferences[END_REF]), in CPDL we capture this ceteris paribus aspect, by keeping fixed the truth values of the atoms not occurring in ϕ (i.e., Atm \ 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 defining the ceteris paribus condition by keeping fixed the truth values of the atoms with respect to which ϕ is independent (i.e., the atoms which do not affect the truth value of ϕ). This connects to Rescher's idea that the concept of ceteris paribus should be defined in terms of a concept of independence between formulas [START_REF] Rescher | Semantic foundations for the logic of preference[END_REF] (see also [START_REF] Girard | Von wright's preference logic reconsidered[END_REF]). In formal terms, let ϕ be a propositional formula. Then: where Indep(ϕ) = {p ∈ Atm : ∀w ∈ W, w ∪ {p} |= ϕ iff w \ {p} |= ϕ} denotes the set of atoms with respect to which ϕ is independent and w |= ϕ means that the valuation w satisfies the propositional formula ϕ. We use the notation O i for independence-based "ceteris paribus" obligation and P i for independence-based "ceteris paribus" permission. Notice that Atm \ Atm(ϕ) ⊆ Indep(ϕ). Thus, a ceteris paribus obligation/permission defined in terms of Atm \ Atm(ϕ) implies a ceteris paribus obligation/permission defined in terms of Indep(ϕ), as if two worlds are equivalent with regard to Indep(ϕ) then they are also equivalent with regard to Atm \ Atm(ϕ).

M, w |= O i ϕ ⇐⇒ ∃v ∈ W such that M, v |= ϕ,
The translation given in Section 5.1 can be easily adapted to this new semantics based on the concept of semantic independence. It is sufficient to replace all occurrences of Atm \ Atm(ϕ) by Indep(ϕ) in the translation rules for the deontic operators. Therefore, for every formula of the deontic language with the independence-based obligation operator O i and permission operator P i , we can find a logically equivalent formula of the ceteris paribus language L CP .

Note that when ϕ is propositional computing Indep(ϕ) can be done in polynomial time. Indeed, all atoms in Atm \ Atm(ϕ) belong to Indep(ϕ). We simply need to enumerate the atoms in Atm(ϕ) and, for each of them, to verify whether ϕ is independent with respect to it. The latter problem is reducible to finite-variable SAT which is in PTIME. Therefore, satisfiability checking relative to preference models for the deontic language in which formulas in the scope of deontic operators O i and P i are propositional remains polynomial.

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:

|= P U(ϕ ↔ ψ) → (O i ϕ → O i ψ) |= P U(ϕ ↔ ψ) → (P i ϕ → P i ψ)
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 specific preference model), we also have the following properties:

|= P ϕ ↔ ψ then |= P (O i ϕ → O i ψ) |= P ϕ ↔ ψ then |= P (P i ϕ → P i ψ)

From Deontic Logic to CP-nets

In this section we shall show how the fragment of the logic for complete preference models introduced in Section 3 has an equivalent representation based on CPnets. Specifically, this is the fragment in which the content of a deontic operator is a literal. In the case of conditional deontic operators the antecedent can be a conjunction of literals.

CP-nets

CP-nets [START_REF] Boutilier | Reasoning with conditional ceteris paribus preference statements[END_REF] are a compact representation of conditional preferences over ceteris paribus semantics. Definition 10. 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 = {CP T (V i )|V i ∈ V } is a set of conditional preference tables (CP-tables). An edge (V i , V j ) ∈ E represents that preferences over Dom(V i ) depend on the value of V j .

For each variable V i ∈ V , given the assignment to its parents, a CP-table CP T (V i ) represents the preference order over the values of the domain of V i . For instance, CP T (A) = {a ≺ ā} represents the strict preference over the values of a variable A, i.e., ā 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 (o j , o i ), which differ only in the value of one variable, means that o j o i . A worsening flip 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 indifference [START_REF] Allen | CP-nets with indifference[END_REF], takes into account indifference 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.

CP-net Representation

Let us restrict our analysis to conditional obligations and permissions whose antecedent is a consistent conjunction of literals l 1 ∧. . .∧l n and whose consequent is a literal l such that Atm(l 1 ∧ . . . ∧ l n ) ∩ Atm(l) = ∅. We note L Frag CPDL + such a fragment of the language L CPDL + . We can show that the induced preference model can be represented compactly by a CP-net with indifference [START_REF] Allen | CP-nets with indifference[END_REF]. Proposition 6. Let C be a set of obligations and permissions from the language L Frag CPDL + . 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. The minimal preference model induced by C is the one which satisfies C and has the less restrictive constraints. First, for each permission in C, introduce a weak order among worlds that differ 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 differ 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 v i ∈ Atm there is a corresponding variable

V i ∈ V such that Dom(V i ) = {v i , vi }.
Each conditional obligation O(v i |v j ) ∈ N introduces a directed edge (V i , V j ) in the dependency graph G, such that V i becomes a parent of V j . It induces a strict order over Dom(V j ) given the assignment of V i such that CP T (V j ) = {v i : vj ≺ v j , vi : v j ≺ vj }. Similarly, each conditional concession P (v i |v j ) ∈ N induces a weak order over Dom(V j ) such that CP T (V j ) = {v i : vj v j , vi : v j vj }. Notice that in our model, as well as in SDL, everything that is not explicitly forbidden is permitted, i.e., in general ¬O(v i ) → P ( vi ). Thus, a variable with indifference 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 definition of worsening flip of CP-net. Example 3 (Running example). Let us introduce a running example concerning the presence of cats, dogs, and fences in beach houses (developing the example from [START_REF] Prakken | Dyadic deontic logic and contrary-to-duty obligations[END_REF]). The set of atoms is Atm = {c, d, f }, 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(d|f ) and O(¬d|¬f ): w {c,d,f } ≈ w {d,f } , w {c,d} ≈ w {d} , w {c,f } ≈ w {f } , w {} ≈ w {c} , w {c,d} ≺ w {c,d,f } , w {d} ≺ w {d,f } , w {c,f } ≺ w {c} , w {f } ≺ w {} Moreover, these preferences are compatible with O¬d, since this obligation only concerns the ceteris paribus preference for worlds that do not have dogs over worlds that have them. Following Proposition 6, Mary's obligations and concessions can be represented using the CP-net with indifference depicted in Figure 1a, which compactly represents the partial order depicted in Figure 1b. For the sake of readability, we group into the same nodes some worlds of the preference model. Worlds in the same node are indifferent, this is due to the indifference over the values of variable C.

Following Proposition 6, to each atom there is a corresponding variable, thus we have V = {C, D, F } representing respectively whether there is cat, a dog and a fence, Dom(C) = {c, c}, Dom(D) = {d, d} and Dom(F ) = {f, f }. Due to obligations and permission, variables C, D are independent while variable F depends on D. Moreover, obligations define the strict orders over Dom(D), Dom(F ). From Proposition 1, the unconditional permission P (c) is defined as P( |c) and introduces indifference over Dom(C).

Conclusion and perspectives

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 have provided variants of our logic that enable for detachment and for closure under logical equivalence. Finally, we have established a connection with the CP-nets, which provide for a compact representation and efficient reasoning over sets of ceteris paribus obligations and permissions. We are currently working to develop the framework of CPDL in various directions, such as the integration of our logic with logics of time and actions, and further exploring its translation into different kinds of CP-nets.

We believe that the complexity results presented in Sections 5 and 6 set the basis for an implementation of our deontic logic. Specifically, given the NPcompleteness for the satisfiability checking of our logic, we expect to find a reduction of the latter to SAT. This opens up the possibility of using existing SAT solvers for verifying deontic properties and automating deontic reasoning in our setting.

Proposition 4 .

 4 If ϕ, ψ are conjunctive clauses and Atm(ϕ)∩Atm(ψ) = ∅ then:

  (ϕ) u and v u then M, u |= ϕ, and ∀v, u ∈ W : if M, v |= ψ and v ≡ Atm\Atm(ψ) u and v u then M, u |= ψ, AND (B) ∃z, z ∈ W such that M, z |= ϕ and M, z |= ψ. Item (ii) means that: (C) ∃v, u ∈ W : M, v |= ϕ ∧ ψ and v ≡ Atm\Atm(ϕ∧ψ) u and v u and M, u |= ¬ϕ ∨ ¬ψ, OR (D) ∀z ∈ W , M, z |= ¬ϕ ∨ ¬ψ.

  k∈Util u k ∧ tr(¬ϕ) → [Atm \ Atm(ϕ)] tr(ϕ) → u ≥k , tr(Uϕ) = [∅]tr(ϕ), with u >k = def k ∈Util:k >k u k , and

  Let us prove the modal case ϕ = Oψ. M, s v |= Oψ ⇐⇒ ∃s z ∈ W s.t. M, s z |= ψ and ∀s w , s u ∈ W : if M, s w |= ψ and s w Atm\Atm(ψ) s u then M, s u |= ψ, ⇐⇒ ∃z ∈ W s.t. W, z |= tr(ψ) and ∀s w , s u ∈ W : if M, s u |= ¬ψ, M, s w |= ψ and s w ≡ Atm\Atm(ψ) s u then s u ≺ s w , ⇐⇒ ∃z ∈ W s.t. W, z |= tr(ψ) and ∀w, u ∈ W : if W, u |= tr(¬ψ), W, w |= tr(ψ) and w ≡ Atm\Atm(ψ) u then s u ≺ s w (by induction hypothesis), ⇐⇒ ∃z ∈ W s.t. W, z |= tr(ψ) and ∀w, u ∈ W : if W, u |= tr(¬ψ), W, w |= tr(ψ) and

  and ∀v, u ∈ W : if M, v |= ϕ and v Indep(ϕ) u then M, u |= ϕ M, w |= P i ϕ ⇐⇒ ∃v ∈ W such that M, v |= ϕ, and ∀v, u ∈ W : if M, v |= ϕ and v ≺ Indep(ϕ) u then M, u |= ϕ

Fig. 1 :

 1 Fig. 1: (a) The CP-net with indifference which represents obligations and permissions in Example 3. (b) The partial order induced by the CP-net in Figure 1a.

That is a binary relation on W which is reflexive, transitive and complete.

A. Loreggia and G. Sartor have been supported by the H2020 ERC Project "Com-puLaw" (G.A. 833647). E. Lorini would like to gratefully acknowledge the support from the ANR-3IA Artificial and Natural Intelligence Toulouse Institute.