A Novel Approach For a Ceteris Paribus Deontic Logic Andrea Loreggia2[0000−0002−9846−0157] , Emiliano Lorini3[0000−0002−7014−6756] , and Giovanni Sartor1,2[0000−0003−2210−0398] ? ?? 1 CIRSFID - Alma AI, University of Bologna, Italy 2 European University Institute, Florence, Italy 3 IRIT Abstract. We present a formal semantics for deontic logic based on the concept of ceteris paribus preferences. It allows to introduce notions of conditional/unconditional obligation and permission that are interpreted relative to this semantics. We show how obligations and permissions can be represented compactly using existing preference frameworks from the artificial intelligence area. Keywords: Deontic Logic · Ceteris paribus preferences · CP-net. 1 Introduction Artificial agents are used to automate task in many different scenarios. Nowa- days, 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 [10]. This will allow to partially translate legal and ethical requirements into computable representa- tions of legal knowledge and reasoning. An example comes from obligations and permissions that are pervasive in law. 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 different grounds [7, 15]. Deontic logic is a set of formal tools, usually based on modal logic [2, 5] which could be compositionally integrated with other logical formalism [3, 8]. In this work, we provide the semantics for a deontic logic based on the intuitive idea that obligations and permissions consist in preferences over worlds. 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 contribut- ing to the states of affairs that are affirmed to be obligatory or permitted. This approach allows to adopt well-known preference frameworks and algorithms to reason about them. For instance, given a set of obligations and permissions one ? A. Loreggia and G. Sartor have been supported by the H2020 ERC Project “Com- puLaw” (G.A. 833647). ?? Copyright c 2020 for this paper by its authors. Use permitted under Creative Com- mons License Attribution 4.0 International (CC BY 4.0). 2 Loreggia A., Lorini E., Sartor G. can compare them with an agent’s preferences to understand how similar they are [9, 11, 12] and whether the agent is deviating from a desired behaviour. Our work is based on the idea of ceteris paribus preference originally introduced by Georg Henrik Von Wright [16, 17]. To capture the idea of a holistic preference, von Wright considers a set of atoms Atm = {p1 , . . . , pn }, each describing an ele- mentary and independent state of a complete situation, or world. Let Atm be a countable set of atomic propositions and let Lit = Atm ∪ {¬p : p ∈ Atm} be the corresponding set of literals. We call preference model a tuple M = (W, ) such that: W = 2Atm is the set of worlds, and  is a complete preorder4 on W . Ele- ments of W are denoted by w, v, . . .. We also define ≺ and ≈ as the strict order and indifference relations induced from . Given 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. w ≡X v means that w and v are indistin- guishable, with regard to the circumstances (the atoms) in X. Let M = (W, ) be a preference model, let w, v ∈ W and let X be a finite set of atomic proposi- tions. We introduce the following abbreviations: w X v, iff w ≡X v and w  v, respectively w ≺X v, iff 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. 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 Atm\X w or v ≺Atm\X w. The former definition concerns indistinguishability and preference relatively to all atoms not in X, i.e., relatively to Atm \ X. In this work we introduce how some deontic operators can be mapped to preference models and we focus on CP-nets [4]. They are a compact representation of conditional preferences over ceteris paribus semantics. Due to the lack of space, we refer to the literature [4, 1, 11] for more information. 2 Ceteris Paribus Deontinc Logic The ceteris paribus deontic logic - CPDL+ has the so-called universal modal operator which allows us to capture factual detachment of obligations. Definition 1. LCPDL+ (Atm) is a modal language which includes atomic propo- sitions p, q, . . . ∈ Atm, standard boolean operators and the modal operators O, P, U. The language is such that: if p ∈ Atm then p ∈ LCPDL+ , if ϕ, ψ ∈ LCPDL+ then ¬ϕ, ϕ∧ψ ∈ LCPDL+ , if ϕ, ψ ∈ LCPDL+ then Oϕ, Pϕ, O(ψ|ϕ), P(ψ|ϕ), Uϕ ∈ LCPDL+ . Formulas Oϕ and Pϕ have to be read, respectively, “ϕ is obligatory” and “ϕ is permitted”. Formula Uϕ has to be read “ϕ is universally true”. 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 LCPDL+ (Atm) are defined as follows: 4 That is a binary relation on W which is reflexive, transitive and complete. A Novel Approach For a Ceteris Paribus Deontic Logic 3 Definition 2 (Truth Conditions). Let M = (W, ) be a preference model, let w ∈ W and let Atm −ϕ = Atm \ Atm(ϕ) where Atm(ϕ) is the set of atoms from Atm occurring in ϕ. Then: – M, w |= p ⇐⇒ p ∈ w – M, w |= ¬ϕ ⇐⇒ M, w 6|= ϕ – M, w |= ϕ ∧ ψ ⇐⇒ M, w |= ϕ and M, w |= ψ – M, w |= Oϕ ⇐⇒ ∀v, u ∈ W : if M, v |= ϕ and v Atm −ϕ u then M, u |= ϕ – M, w |= Pϕ ⇐⇒ ∀v, u ∈ W : if M, v |= ϕ and v ≺Atm −ϕ u then M, u |= ϕ – M, w |= Uϕ ⇐⇒ ∀v ∈ W : M, v |= ϕ – M, w |= O(ψ|ϕ) ⇐⇒ ∀v, u ∈ ||ψ||M : if M, v |= ϕ and v Atm −ϕ u then M, u |= ϕ – M, w |= P(ψ|ϕ) ⇐⇒ ∀v, u ∈ ||ψ||M : if M, v |= ϕ and v ≺Atm −ϕ u then M, u |= ϕ In other words, Oϕ means that, for every two possible worlds that are 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 −ϕ -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 ϕ ∈ LCPDL+ (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 ϕ ∈ LCPDL+ (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 |= ϕ. The proposed model has several interesting properties that we list here: – restricting our model to obligations and permissions that are stated only on atoms, then the induced preference model can be represented compactly by a CP-net; – unconditional obligation and permission do not need to be added as primi- tives in the language of the logic CPDL+ , as they are definable from condi- tional obligation and permission; – if ϕ, ψ are conjunctive clauses and Atm(ϕ) ∩ Atm(ψ) = ∅ then: |=P (Oϕ ∧ Oψ) → O(ϕ ∧ ψ) and |=P (Pϕ ∧ Pψ) → P(ϕ ∧ ψ); – if ϕ is obligatory then it is also permitted; – if the condition of a conditional obligation/permission is necessarily true then the obligation/permission is detached and becomes unconditional; – CPDL+ does not encounter Ross’s paradox [14]. 3 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 [15]), in CPDL+ we capture this ceteris paribus aspect, by keeping fixed the truth values of the atoms not occurring in ϕ (i.e., Atm−ϕ ). The fact that the sets of atoms not occurring in two logical equivalent formulas do not necessar- ily coincide explains why the obligation and permission operators of CPDL+ 4 Loreggia A., Lorini E., Sartor G. 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 is consistent with Rescher’s idea that the concept of ceteris paribus should be defined in terms of a concept of independence between formulas [13] (see also [6]). 4 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, named CPDL+ . We provided a connection with knowledge represen- tation in order to compactly represent and reason over the set of obligations and permissions using the CP-net formalism. We are currently working to de- velop the framework of CPDL+ in various directions, concerning both theory and applications. References 1. Allen, T.E.: CP-nets with indifference. In: 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton). pp. 1488–1495. IEEE (2013) 2. Åqvist, L.: Deontic logic. In: Handbook of philosophical logic, pp. 605–714. Springer (1984) 3. Bienvenu, M., Lang, J., Wilson, N., et al.: From preference logics to preference languages, and back. In: KR. pp. 9–13 (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. Gabbay, D., Horty, J., Parent, X., van der Meyden, R., van der Torre, L.: Handbook of deontic logic and normative systems (2013) 6. Girard, P.: Von wright’s preference logic reconsidered (2006) 7. Grossi, D., Lorini, E., Schwarzentruber, F.: The ceteris paribus structure of logics of game forms. Journal of Artificial Intelligence Research 53, 91–126 (2015) 8. Jones, A.J.: Deontic logic and legal knowledge representation. Ratio Juris 3(2), 237–244 (1990) 9. Li, M., Kazimipour, B.: An efficient algorithm to compute distance between lexi- cographic preference trees. In: Proc. of the 27th IJCAI 2018. pp. 1898–1904 (2018) 10. Loreggia, A., Mattei, N., Rossi, F., Venable, K.B.: Preferences and ethical princi- ples in decision making. In: Proc. 1st AIES (2018) 11. Loreggia, A., Mattei, N., Rossi, F., Venable, K.B.: On the distance between CP- nets. In: Proc. of the 17th AAMAS. pp. 955–963 (2018) 12. Loreggia, A., Mattei, N., Rossi, F., Venable, K.B.: CPMetric: Deep siamese net- works for metric learning on structured preferences. In: Artificial Intelligence. IJ- CAI 2019 International Workshops. pp. 217–234. Springer (2020) 13. Rescher, N.: Semantic foundations for the logic of preference. The logic of decision and action pp. 37–62 (1967) 14. Ross, A.: Imperatives and logic. Philosophy of Science 11(1), 30–46 (1944) A Novel Approach For a Ceteris Paribus Deontic Logic EKAW 2020 Andrea Loreggia (andrea.loreggia@gmail.com) , Emiliano Lorini (lorini@irit.fr), Giovanni Sartor (giovanni.sartor@gmail.com) 22nd International Conference on Knowledge Engineering and European University Institute, Institut De Recherche En Informatique De Toulouse, CIRSIFD Knowledge Management Introduction Results Background We present a formal semantics for deontic The proposed model has several A CP-net compactly represents a set of logic based on the concept of ceteris conditional preferences over a set of variables. paribus preferences. It allows to introduce interesting properties: notions of conditional/unconditional • If obligations and permissions obligation and permission that are MAIN ENT are stated only on atoms, then interpreted relative to this semantics. Meat >Fish we can model compactly using a TV > Music Language Definition CP-net; 𝐿!"#$! (𝐴𝑡𝑚) is a modal language which • If 𝜑, 𝜓 are conjunctive clauses This is an and 𝐴𝑡𝑚(𝜑) ∩ 𝐴𝑡𝑚(𝜓) = ∅ then: DRINK example of includes atomic propositions 𝑝, 𝑞, … ∈ ⊨" (𝑂𝜑 ∧ 𝑂𝜓) → 𝑂(𝜑 ∧ 𝜓) and CP-net 𝐴𝑡𝑚, standard boolean operators and which ⊨" 𝑃𝜑 ∧ 𝑃𝜓 → 𝑃 𝜑 ∧ 𝜓 Meat: RedWine > WhitWwine the modal operators 𝑂, 𝑃, 𝑈. The Fish: WhiteWine>RedWine represent • If 𝜑 is obligatory then it is also conditional language is such that: permitted preferences • if 𝑝 ∈ 𝐴𝑡𝑚 then 𝑝 ∈ 𝐿!"#$! , Conclusion over a meal. • if the condition of a conditional • if 𝜑, 𝜓 ∈ 𝐿!"#$! then ¬𝜑, 𝜑 ∧ 𝜓 ∈ We have presented a new 16. Von Wright, G.H.: The logic of preference (1963) obligation/permission is 𝐿!"#$! , necessarily true then the approach to deontic logic: • If 𝜑, 𝜓 ∈ 𝐿!"#$! then obligation/permission is • based on ceteris paribus 𝑂𝜑, 𝑃𝜑, 𝑂(𝜓|𝜑), 𝑃(𝜓|𝜑), 𝑈𝜑 ∈ 𝐿!"#$! . detached and becomes preferences Fig. 1: EKAW - Poster image. unconditional; • provides a fresh foundation to the 𝑂𝜑 and 𝑃𝜑 have to be read, respectively, • 𝐶𝑃𝐷𝐿 + does not encounter logical analysis of deontic concepts ”𝜑 is obligatory” and ”𝜑 is permitted”. Ross’s paradox • provided a connection with Formula 𝑈𝜑 has to be read ”𝜑 is knowledge representation 17. Von Wright, G.H.: The logic of preference reconsidered (1972) universally true”. Formulas 𝑂(𝜓|𝜑) and • compactly represent and reason 𝑃(𝜓|𝜑) have to be read, respectively, over the set of obligations and “under condition 𝜓, 𝜑 is obligatory ”and permissions using the CP-net “under condition 𝜓, 𝜑 is permitted”. formalism A Novel Approach For a Ceteris Paribus Deontic Logic for ceteris paribus preferences. Journal of philosophical logic 38(1), 83–125 (2009) 15. Van Benthem, J., Girard, P., Roy, O.: Everything else being equal: A modal logic 5