Andrea Loreggia

Roberta Calegari

Emiliano Lorini

Francesca Rossi

Giovanni Sartor

How to model contrary-to-duty with GCP-nets

Keywords: Deontic logic, GCP-nets, ceteris-paribus semantics, contrary-to-duty, strong and weak permission

Preferences are ubiquitous in our everyday life. They are essential in the decision making process of individuals. Recently, they have also been employed to represent ethical principles, normative systems or guidelines. In this work we focus on a ceteris paribus semantics for deontic logic: a state of affairs where a larger set of respected prescriptions is preferable to a state of affairs where some are violated. Conditional preference networks (CP-nets) are a compact formalism to express and analyse ceteris paribus preferences, with some desirable computational properties. In this paper, we show how deontic concepts (such as contrary-to-duty obligations) can be modeled with generalized CP-nets (GCP-nets) and how to capture the distinction between strong and weak permission in this formalism. To do that, we leverage on an existing restricted deontic logic that will be mapped into conditional preference nets.

Introduction

Deontic logic allows us to model legal and ethical prescriptions such as obligations and permissions. Its computational implementation may provide a framework to govern the functioning of AI systems, assessing their behaviour in different situations and scenarios, detecting violations and ensuring compliance with ethical and legal requirements [START_REF] Bench-Capon | Norms and value based reasoning: justifying compliance and violation[END_REF].

Modelling deontic notions through preferences [START_REF] Carmo | Deontic Logic and Contrary-to-Duties[END_REF][START_REF] Hansson | The Structure of Values and Norms. Cambridge Studies in Probability, Induction and Decision Theory[END_REF][START_REF] Van Der Torre | Contrary-to-duty reasoning with preference-based dyadic obligations[END_REF] has the advantage of linking deontic notions to the rich research on preferences, in multiple disciplines, such as philosophy, mathematics, economics and politics. Preferences are also central in artificial intelligence. In this area, researchers study the computational aspects of classical social choice problems, * Corresponding author: Andrea Loreggia, University of Brescia -Brescia, Italy. E-mail: andrea.loreggia@unibs.it.

preference aggregation and preference reasoning [START_REF] Domshlak | Preferences in AI: An overview[END_REF][START_REF] Pigozzi | Preferences in artificial intelligence[END_REF][START_REF] Rossi | A short introduction to preferences: between artificial intelligence and social choice[END_REF]. Applications of preferences can be found in many different contexts: from multi-agent and recommender systems [START_REF] Ricci | Introduction to recommender systems handbook[END_REF][START_REF] Shoham | Multiagent systems: Algorithmic, game-theoretic, and logical foundations[END_REF]-where preferences are employed to drive the making decision process of agents or to describe the profile of users-to sentiment analysis techniques [START_REF] Grandi | From sentiment analysis to preference aggregation[END_REF][START_REF] Grandi | A borda count for collective sentiment analysis[END_REF] and machine learning ensemble approaches [START_REF] Cornelio | Voting with random classifiers (VORACE)[END_REF][START_REF] Cornelio | Voting with random classifiers (VORACE): theoretical and experimental analysis[END_REF][START_REF] Werbin-Ofir | Beyond majority: Label ranking ensembles based on voting rules[END_REF]-where they are adopted to improve the quality of predictions.

In his seminal paper, Makinson [START_REF] Makinson | On a fundamental problem of deontic logic[END_REF] discussed the traditional preference based deontic logics and observed that "The definition of a "betterness" relation between possible worlds suggested above, in terms of the set of explicit promulgations of the code that are violated in each world, is perfectly precise; and such a relation permits a semantic account of conditional obligation."

As already done in literature [START_REF] Carmo | Deontic Logic and Contrary-to-Duties[END_REF][START_REF] Loreggia | A ceteris paribus deontic logic[END_REF][START_REF] Loreggia | Modelling ceteris paribus preferences with deontic logic[END_REF][START_REF] Prakken | Dyadic deontic logic and contraryto-duty obligations[END_REF], we model deontic notions through ceteris-paribus pref-ISSN 1724-8035/$35.00 © 2022 -IOS Press. All rights reserved.

C O R R E C T E D P R O O
F erences, namely, conditional preferences for a state of affairs over other states of affairs, all the rest being equal. Conditional or rather contextual obligations have been captured in the development of dyadic deontic logic, which captures deontic conditionality through a special conditional operator. The idea of ceteris-paribus preferences was originally introduced by the philosopher and logician Georg Henrik Von Wright [START_REF] Von | The logic of preference[END_REF][START_REF] Von | A new system of deontic logic[END_REF], and after that, a semantics ables to represent it was first proposed by Bengt Hansson [START_REF] Hansson | An analysis of some deontic logics[END_REF].

In particular, we focus on the ceteris-paribus preference for a proposition over its complement. This idea provides the intuition at the basis of CP-nets [START_REF] Boutilier | Reasoning with conditional ceteris paribus preference statements[END_REF], a formalism which enables representing preferences in a compact way and reasoning about them. Their application can be effective for the multiagent pervasive systems of artificial intelligence (AI). Indeed, AI agents are pervasive and they need to be flexible, adaptive, and creative, but at the same time, they have to comply with many ethical and legal requirements [START_REF] Boella | Introduction to normative multiagent systems[END_REF][START_REF] Calegari | Logicbased technologies for multi-agent systems: A systematic literature review[END_REF][START_REF] Omicini | Injecting (micro)intelligence in the IoT: Logic-based approaches for (M)MAS[END_REF]. Whether an AI agent is autonomous or collaborating with humans, it should be aware and follow appropriate ethical principles and should thus exhibit properties such as fairness or other virtues [START_REF] Booch | Thinking fast and slow in AI[END_REF][START_REF] Rossi | Preferences and ethical priorities: Thinking fast and slow in AI[END_REF][START_REF] Rossi | Building ethically bounded AI[END_REF]. Based on these needs, during the last decade, researchers proposes languages to model and reason with norms in multi-agent systems, enabling methodologies and organization models for checking conflicts between the norms at design time [START_REF] Da Silva | A modeling language to model norms[END_REF][START_REF] Freire | Normas-ml: Supporting the modeling of normative multi-agent systems[END_REF].

By modelling a normative system of a multiagent system through a CP-net we obtain a compact representation that shall allow us to check important properties of the modelled normative system, like for instance consistency. Moreover, preferences of agents can also be modelled through CP-nets [START_REF] Mohajeriparizi | Preferencebased goal refinement in bdi agents[END_REF]. This would enable to check agents' preferences against the exogenous preferences expressed by various normative systems, such as laws, ethical principles, feasibility constraints, or safety regulations [START_REF] Loreggia | Modeling and reasoning with preferences and ethical priorities in ai systems[END_REF][START_REF] Loreggia | Preferences and ethical principles in decision making[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 CP-Nets[END_REF], providing feasible ways for preferences' comparison. Whilst modeling deontic concepts with ceteris paribus preferences has become a standard approach (see for instance, [START_REF] Hansson | Preference-based deontic logic (pdl)[END_REF][START_REF] Van Benthem | On the two faces of deontics: Semantic betterness and syntactic priority[END_REF][START_REF] Van Der Torre | Contrary-to-duty reasoning with preference-based dyadic obligations[END_REF]), we found just one first attempt to model deontic notions with CP-nets in [START_REF] Garion | Apports de la logique mathématique en ingénierie des exigences[END_REF]. Unfortunately, this work did not recognise CP-nets limitations (in their original formalization). Indeed, they do not allow for the representation of incomplete preference orders over the values of one or more variables. This limitation can be removed by adopting a recent model generalization called GCPnet (aka generalized CP-net) [START_REF] Goldsmith | The computational complexity of dominance and consistency in CP-nets[END_REF]. To the best of our knowledge, no one else investigated the relationship between deontic concepts and GCP-nets. We think cooperation among researchers from deontic logic and GCP-nets can be very beneficial, and possibly lead to a new workable approach to modelling norms and reasoning about them.

We assume that norms establishing obligations can be viewed as expressing social preferences for situations in which the obligation has complied with other situations in which it is violated. Similarly, we assume that norms establishing liberties (bilateral permissions, to do and not to do) express indifference over complementary situations. In this regard, we discuss and address two topics in deontic logic, namely contrary-to-duty obligations [START_REF] Carmo | Deontic Logic and Contrary-to-Duties[END_REF] and the distinction between strong and weak permissions.

We show that a consistent GCP-net can be built that captures both an obligation and the prescriptions specifying what should be done in case the obligation is violated. The latter prescriptions may be incompatible with prescriptions on what should be done in case of compliance [START_REF] Chisholm | Perceiving: A Philosophical Study[END_REF]. We illustrate contrary-to-duty obligations with a well-known example discussed in the literature. However, realistic examples of contrary-to-duty obligations can be found in various domains, such as in commercial contracts, where repair obligations can be established for delay or non-fulfilment: to inform, compensate the damage, replace defective goods, pay penalties, etc. (for a logical model see [START_REF] Governatori | Justice delayed is justice denied: Logics for a temporal account of reparations and legal compliance[END_REF]). It can also be found in civil liability, where harmful behaviour is met with obligations to repair, mitigate, and pay punitive damages in case of persistence.

We also show that a GCP-net model can capture concepts of strong and weak permission, a distinction that has been long discussed in deontic logic [START_REF] Van Der Torre | Contrary-to-duty reasoning with preference-based dyadic obligations[END_REF][START_REF] Von | Norm and Action: A Logical Inquiry[END_REF] and even earlier in legal theory, in connection with issues concerning the completeness of legal systems [START_REF] Zitelmann | Lücken im Recht[END_REF]. We indeed distinguish the case in which an action is positively permitted, through a permissive norm, and the case in which the action is rather unregulated, as no norm, and in particular, no prohibition addresses it [START_REF] Van Der Torre | Reasoning about Obligations: Defeasibility in Preference-Based Deontic Logic[END_REF].

Contribution.

We propose to leverage GCP-net, an existing preference framework, to model contraryto-duty in a compact way. We define different levels of incomparability to differentiate between two situations: one where two outcomes are incomparable because nothing is said about all the values of a

C O R R E C T E D P R O O
F feature, and another, where two or more variables are independent and thus preferences are described over the domains of these variables no matter the assignment of the others. We show that a normative system represented through a restricted deontic logic for contrary-to-duty is isomorphic to preferences represented compactly with GCP-nets.

A running example

In this section, we 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 contraryto-duty obligations[END_REF]). The example is used throughout the paper to explicate new notions when they are introduced.

Example 1. (Running example). Mary is the mayor of Cattown, the city of cats lovers. She knows that her community, with few exceptions, dislikes dogs and likes cats. Cattown people also dislike the sight of fences around houses and generally prefer to be able to move around and visit each other without the obstacle of fences. However, there was a problem with dogs entering other people's property and causing fear and sometimes harm. Moreover, people are fussy about the way in which their town looks, they like that all houses and street furniture are white, as indeed they are. Mary believes that her role consists in defining policies that fit the preferences of her constituency. Thus, she has enacted the following, making them mandatory in Cattown:

1. dogs are forbidden; 2. people may have a cat or not; 3. if there is a dog, then there must be a fence; 4. if there is a fence, then there must be white; 5. if there is no dog, then there must be no fence.

Though most people in her constituency like these policies, some do not. In particular, there are few dog lovers in the city, who do not share the approach to dogs prevailing in Cattown. However, Mary believes that -given the preferences of the majority and the history and peculiar spirit of Cattown -her regulation articulates a social perspective, namely, a view of the community on what it prefers and a view that can justifiably be imposed on all its citizens. If a dog lover has decided to move into Cattown, he should have known what he would find there.

An issue has recently emerged concerning bobcats. It is being debated whether, in the absence of a provision prohibiting or allowing bobcats, John is allowed to keep a bobcat in his garden. Mary thinks that he is not, he should have asked for it, while John believes that he is. Can their conflict of opinion be explained away as merely concerning a conceptual misunderstanding (on the notion of permission)?

Background

To formally express rules such as those enacted by Mary, a restricted deontic language is sufficient. In what follows, we adopt the language proposed and defined in a recent paper [START_REF] Loreggia | Modelling ceteris paribus preferences with deontic logic[END_REF]. Let Atm be a countable set of atomic propositions and let Lit Atm = Atm ∪ {¬p : p ∈ Atm}, be the corresponding set of literals. Under this assumption, we can identify propositional valuations (or worlds) with maximal consistent conjunctions of literals. In the following, we will use interchangeably ¬ and ¯to specify the negation.

Definition 1. (Ceteris Paribus Deontic Language [START_REF] Loreggia | Modelling ceteris paribus preferences with deontic logic[END_REF]). CPDL + (Atm) is a modal language which consists of atomic propositions p, q, . . . ∈ Atm, standard Boolean operators and the modal operators O and P. More precisely, it is the smallest set such that:

-if p ∈ Atm, then p ∈ CPDL + -if ϕ, ψ ∈ CPDL + , then ¬ϕ, ϕ ∧ ψ ∈ CPDL + -if ϕ, ψ ∈ CPDL + , then O(ψ|ϕ) and P(ψ|ϕ) ∈ CPDL + .
In particular, O(ψ|ϕ) models an obligation and P(ψ|ϕ) models a permission, and they have to be read respectively "under condition ψ, ϕ is obligatory" and "under condition ψ, ϕ is permitted."

Notice that unconditional obligation and permission do not need to be added as primitives in the language of the logic as they are definable from conditional obligation and permission. We also do not need a primitive for the bilateral permission, or liberty, which consists in the permission both of a proposition and of its complement. For the sake of readability let us introduce the following definition: Definition 2. For all ϕ ∈ CPDL + (Atm):

O(ϕ) = def O( |ϕ) P(ϕ) = def P( |ϕ) L(ψ|ϕ) = def P(ψ|ϕ) ∧ P(ψ|¬ϕ) L(ϕ) = def L( |ϕ) C O R R E C T E D P R O O F
Using this language and taking into account previous definitions, we can model obligations and permissions depicted in Example 1. We use the following abbreviations: d for "there is a dog", c for "there is a cat", f for "there is a fence", w for "the fence is white", b for "there is a bobcat". We can express the norms enacted by Mary as follows (enumeration corresponds to the Example 1): ( 1)

O(¬d) (2) L(c) (3) O(d|f ) (4) O(f |w) (5) O(¬d| ¬f ).

Contrary-to-duty obligations

The norms in our running example include a "contrary-to-duty" obligation, namely, obligations that are triggered by the violation of another obligation. According to the norm O(d|f ), having a dog, and thus violating norm O(¬d) (the prohibition to have dogs), triggers the obligation to have a fence. Contrary-to-duty obligations cannot be captured by standard deontic logic: according to those semantics, a proposition is obligatory if and only if it is true in every perfect (ideal) world, a world in which everything is as it should be. But the world in which a contrary-to-duty obligation is triggered is a sub-ideal one, since in it another obligation is violated, and it remains sub-ideal even if the contrary-to-duty obligation is complied with. In all perfect Cattowns there are no dogs, and in such cities, there are also no fences. So, according to the semantics for standard deontic logic, there cannot be an obligation to have fences in Cattown. Different approaches captured the idea of contrary-to-duty (see for instance [START_REF] Carmo | Deontic Logic and Contrary-to-Duties[END_REF][START_REF] Governatori | Logic of violations: A gentzen system for reasoning with contrary-to-duty obligations[END_REF][START_REF] Van Der Torre | Contrary-to-duty reasoning with preference-based dyadic obligations[END_REF]). A semantics that just distinguishes between ideal and non-ideal worlds cannot capture contrary-to-duty obligations: compliance with a contrary-to-duty obligation takes us to a world that is better -ceteris paribus -than a world in which the contrary-to-duty is not complied with, but which is still imperfect. A world with dogs and fences is ceteris paribus better than a world which has dogs and does not have fences, but the former is still worse than a world in which, ceteris paribus, there are no dogs. To capture contrary-to-duty obligations we need a semantics that distinguishes different levels of preferability so that we can distinguish the imperfect situation in which the main duty is violated, but the contrary-to-duty obligation is complied, from the even more imperfect situation in which both the main duty and the contrary-to-duty obligation are violated.

Strong and weak permissions

Our running example also shows the difference between strong (explicit) and weak (tacit) permissions, an issue much debated within deontic logic. On the one hand, cats are regulated: there is a norm that deals with cats (L(c)), stating that both having and not having cats is allowed. On the other hand, nothing is said about bobcats. In other terms, while the normative system expresses an equal preference for having and not having cats (both are OK), it expresses no attitude towards bobcats. This distinction too cannot be captured by the semantics for standard deontic logic, where P(φ) means that there is at least one perfect world in which φ is true, in which case ¬O(¬φ) is true. In legal logic, the most popular perspective to distinguish strong and weak permissions is an inferential one. To say that φ is strongly permitted relative to a normative system means that the normative entails P(φ). To say that φ is weakly permitted means that the normative system under consideration does not entail a corresponding prohibition O(¬φ). Here we shall provide a different way to capture the difference between strong and weak permission, based on the distinction between indifference (equal ceterisparibus preference) and incomparability (absence of any preference).

Ceteris-Paribus Preferences

We assume a set of variables (also called features or attributes) V = {X 1 , . . . , X n } each one with a binary domain, i.e. the domain of each X i ∈ V is such that Dom(X i ) = {x i , x i }. An instantiation Ass(X), where X ⊆ V , is an assignment of values to X. When X = V then we call it a complete assignment or outcome or world, otherwise we call it a partial assignment.

A preorder is a reflexive and transitive binary relation over the set of all outcomes U = 2 V , which are usually denoted by o, w, . . . , v. In what follows, w v means that v is at least as good/ideal as w, w ≈ v means that w is equivalent to v which is an abbreviation for w v and v w. Moreover, w ≺ v means that v is better/more ideal than v to be an abbreviation of w v and v / w. Given two possible outcomes w, v ∈ O, if neither w v nor v w are valid, then we say that w and v are incomparable, denoted with wZ v. The notation o[V i ] returns the value of the variable V i in the outcome o, while o[-V i ] returns the value of all the variables but V i in the outcome o.

C O R R E C T E D P R O O F
We borrow some notations from [START_REF] Boutilier | Reasoning with conditional ceteris paribus preference statements[END_REF] in order to define ceteris paribus semantics. In our analysis of the semantics of preferences, we assume that the set of variables V is partitioned into three sets: A set X which includes the variables over whose values the preference is expressed, a set Y which includes the variables whose values are irrelevant to the preference, a set Z which includes the variables that are assumed to remain constant, i.e., that provide the context for the preference. Definition 3. (Ceteris-Paribus Preference). Let V be a set of variables and X, Y, Z partitions of V with X be nonempty set. Let z ∈ Ass(Z) and x 1 , x 2 ∈ Ass(X), we say that x 2 is ceteris-paribus at least as good as (resp. better than) x 1 given z if and only if for all y ∈ Ass(Y ), x 1 yz x 2 yz (resp. x 1 yz ≺ x 2 yz).

We use z :

x 1 Y x 2 (≺ Y resp.
) as an abbreviation for it (we will omit the subscript when it is clear from the context).

As the preference for x 1 over x 2 , in the context of z, is independent from the values of Y , we may say that X is preferentially independent of Y if Z = ∅, otherwise we say that X is conditionally preferentially independent of Y given the assignment of Z.

Moreover, from Definition 3 we derive the following notation regarding ceteris-paribus relation between two outcomes u, v. Definition 4. Given two outcomes u, v ∈ U, we say that u is ceteris-paribus at least as good as (resp. better than) v relative to X i , if and only if they differ only in the value of the variable X i and we abbreviate it with v (-

X i ) u (resp. v ≺ (-X i ) u).
The previous definition introduces a notation that is useful in those situations where u and v are two complete assignments that differ only in the value for the variable

X i , that is u = x i yz and v = x i yz, with y ∈ Ass(Y ), z ∈ Ass(Z), Y ∪ Z = V \ {X i } and x i , x i ∈ Dom(X i ).
Then adopting Definition 3 this is similar to say that z :

x i Y x i (resp. z : x i ≺ Y x i ).
Let us refer to Example 1. Mary's community preferences are over a set of five features, specifically V = {C, D, F, W, B}, with the following domains:

Dom(C) = {c, c}, Dom(D) = {d, d}, Dom(F ) = {f, f }, Dom(W) = {w, w} and Dom(B) = {b, b}.
The meaning of variables is the same introduced in Section 3 for atoms: for instance, variable C concerns cats, its value is c or c depending on whether there is a cat or not.

Since V has 5 elements, the set of all outcomes U = 2 V contains 32 possible outcomes. For the sake of readability, in this section, we do not consider variables W and C. Examining a reduced number of outcomes will allow for making the partial orders limited in size. Thus, considering the subset {B, D, F }, the set of outcomes is denoted by the complete assignments to the contemplated variables:

U = {bdf, bdf, b df, bd f , bd f , b d f , b df, b d f }
The different attitudes of the community can be represented with a set of ceteris paribus preferences. In particular, with respect to ¬dogs-assignments (i.e., D = d) and dog-assignments (i.e. D = d), the negative attitude to dogs is represented by the preference for ¬dogs-assignments over ceteris-paribus dog-assignments (i.e.

d ≺ V \D d): bdf ≺ b df, bdf ≺ b df, bd f , b d f , bd f ≺ b d f
Preference is ceteris-paribus (about d) in the sense that it only concerns the comparison between dogassignments and ¬dog-assignments that are equal in all the rest (bobcats and fences). These are all pairs of outcomes u and v such that the evaluations of u and v coincide in all values except for D.

Preference for having fences when there are dogs in the house is captured by preferences for fence-assignments over the ceteris-paribus ¬fenceassignments, taking only dog-assignments into consideration (i.e. d : f ≺ B f ):

bd f ≺ bdf, bd f ≺ bdf
Instead, unawareness of bobcats can be modelled through incomparability between bobcat-assignments and ¬bobcat-assignments, which expresses unfamiliarity to the presence of bobcats, i.e. for all x 1 , x 2 ∈ Ass(D) and for all y 1 , y 2 ∈ Ass(F ) : bx 1 y 1 Z bx 2 y 2 .

At last, let us include again the variable C in our analysis, so we can have cats and not have them. This can be represented through the indifference for catassignments over ceteris paribus ¬cat-assignments (i.e. c ≈ V \C c). These are all the pairs of outcomes u and v such that v is ceteris-paribus at least as good as u and vice-versa (i.e.,(u (-C) v) ∧ (v (-C) u)), that is for instance:

cb df ≈ cb df, cbd f ≈ cbd f C O R R E C T E D P R O O F 3.

GCP-nets

In order to be able to represent the described scenario, we propose to leverage existing preference frameworks from AI, namely GCP-nets (generalized CP-nets) [START_REF] Goldsmith | The computational complexity of dominance and consistency in CP-nets[END_REF]. GCP-net is an extension of CP-net [START_REF] Boutilier | Reasoning with conditional ceteris paribus preference statements[END_REF] that allows incomplete preference orders over some values of the features. GCP-nets and related extensions of the formalism [START_REF] Cornelio | Updates and uncertainty in CP-nets[END_REF][START_REF] Cornelio | Reasoning with PCP-Nets in a multiagent context[END_REF][START_REF] Goldsmith | The computational complexity of dominance and consistency in CP-nets[END_REF] are often on multi-valued variables, this means that variables are not strictly boolean. Nevertheless, in this work, we assume that all the variables have binary domains. We start by introducing and defining some useful notions.

We borrow the following definition from [START_REF] Goldsmith | The computational complexity of dominance and consistency in CP-nets[END_REF]:

Definition 5.
(Generalized CP-net). A generalized CP-net C (for short, a GCP-net) over V is a set of conditional preference rules. For x ∈ V , we define p + (x) and p -(x), as follows: p + (x) is equal to the disjunction of all p such that there exists a rule p : ¬x ≺ x in C; p -(x) is the disjunction of all p such that there exists a rule p : x ≺ ¬x in C. We define the associated directed graph G C (the dependency graph) over V to consist of all pairs (y, x) of variables such that y appears in either p + (x) or p -(x).

For each variable V i ∈ V, a CPT (V i ) is a set of cp-statements, each one represents an ordering over the specific domain Dom(V i ) given the assignment to the parents of V i , which are denoted with Pa(V i ). For instance, CPT (F ) = {d : f ≺ f, d : f ≺ f }. In its original formulation, each CPT (V i ) reports strict linear order over the values of the domain of V i given the partial assignment to Pa(V i ). In a GCP-net, CPtables may be incomplete (i.e., for some values of its parents, the preferred value of a variable X may not be specified) and/or locally inconsistent (i.e., for some values of its parents, the table may both contain the information that x ∈ Dom(X) is preferred and the information that x ∈ Dom(X) is preferred).

The semantics is connected with the induced preference graph over all the outcomes. A directed edge between a pair of outcomes (o i , o j ), 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.

The semantics of a GCP-net is a preorder over all the outcomes, i.e. a reflexive and transitive binary relation over the set of complete assignment of values to the variables of the GCP-net. Thus, for any two outcomes o, u which differs only on the value of one variable X i ∈ V we have:

-o u if o[X i ] u[X i ] given o[Pa(X i )] -oZ u if there is not a cp-statements for o[X i ], u[X i ] given o[Pa(X i )]
The partial order induced by the GCP-net is denoted as Ord .

The GCP-net formalism provides a qualitative compact representation that is useful to represent scenarios similar to the one depicted by the reduced deontic logic introduced in Section 3.

Deontic Language and GCP-nets: bridging the gap

A set of obligations and liberties (bilateral permissions) expressed in the restricted language defined in Section 3 can be represented using a GCP-net, we will call it a prescriptive CP-net. Note that we do not provide for the representation of unilateral permission. In fact, we assume that unilateral permissions must be implied either by an obligation (in case the complement is forbidden) or by liberty (in case the complement is also permitted). Indeed, the restriction on obligations and liberties where antecedents are conjunctions of literals and consequent is a single literal is compatible with the syntax of generalized CP-nets.

Incomparability

In the previous section, we introduced the notion of incomparability. In the ceteris paribus semantics, the notion of incomparability does not allow to differentiate between two different states of affairs: one where two outcomes are incomparable because nothing is said about some values of a feature, and another, where two or more variables are independent and thus preferences are described over the domains of these variables no matter the assignment of the others. Both cases induce a preference graph where some outcomes are incomparable because there does not exist a path between them. But, while the former case describes a lack of information, possibly because the individual does not know or does not have any information about some features (for instance, in our example the lack of information about bobcats), the latter describes a situation where preferences are reported on all the features but not on all combinations of them (for instance, in the running example norms do not tell whether the situation in which there is not a dog and no fence-whatever the color-is bet-

C O R R E C T E D P R O O F
ter or worse than the situation where there is not a dog and there is a white fence). In this last situation, the issue is connected with the color of the fence and the lack of dependencies between the fence's presence and the color. This seems to be simpler to fix: the individual already has preferences over values of the single features, thus the incomparability can be overcome by adding a contextual dependency over some values. For instance, forcing the choice of white color only when a fence is present and the liberty of choosing the color whenever the fence is not present.

Definition 6. (Strong incomparability)

. Given a preorder P, two outcomes w, v ∈ P are said to be strongly incomparable if they belong to two different components of P.

Strong incomparability describes the relation among outcomes of different components. They are incomparable because some information is missing: specifically, preferences are not reported for all the values in the domain of some features. This lack of information can be hard to fix since it entails a lack of knowledge about the scenario.

The next definition refers to weakly connected components: a directed graph is said to be weakly connected if the undirected graph resulting from removing the orientation of the edges is connected, i.e. if any pair of vertexes w, v in the undirected graph has a path from w to v. Definition 7. (Weak incomparability). Given a preorder P, two outcomes w, v ∈ P are said to be weakly incomparable if they belong to the same weakly connected component of P but there does not exist a path from w to v or vice-versa.

Weak incomparability describes a less problematic situation. In this case, preferences are reported for values in the domain, but the incomparability is due to some missing dependencies among features. We can reduce the number of incomparable outcomes by adding dependencies among features.

Modeling Deontic Language with GCP-nets

In this section, we define the GCP-net that is induced by a given set of prescriptions. We call this extension a Prescriptive CP-net. a set of variables V ) defined as follows:

-for each atomic proposition v i ∈ Atm corresponds a variable V i ∈ V with Dom(V i ) = {v i , vi } -for each conditional obligation O(ψ|φ) ∈ C and each conditional liberty L(ψ|φ) ∈ C, dependencies are introduced in G. Specifically, for each literal x j ∈ ψ, a directed edge is introduced between X j and in G, thus X j becomes a parent of -each obligation O(ψ|φ) ∈ C induces a strict order over Dom( ) given the assignment ψ such that CPT ( ) = {ψ : φ ≺ φ} and each liberty L(ψ|φ) ∈ C induces a weak order over Dom( ) given the assignment ψ such that CPT ( ) = {ψ : φ ≈ φ}.

Notice that variables with empty CP-tables or partially empty CP-tables may exist. These variables will induce incomparability in the preorder.

Based on preferences described in Example 1, Fig. 1 reports the dependency graph and CP-tables of the prescriptive CP-net which represents Mary's community preferences. The prescriptive CP-net is over the set of variables V = {B, C, D, F, W}. Notice that: (a) Variable B does not have a CP-table because the community did not express any preferences about bobcats. (b) The indifference on the values of variable C describes the liberty to have or not cats.

The strong attitude about dogs induces strict order over the domain of the variable D, similarly, orders over the variable W depend on the strong preference for the white color. Orders over the variable F depend on whether or not there is a dog.

The partial order induced by the GCP-net is reported in Fig. 2. The binary relation among outcomes is based on dependencies and preferences reported in the CP-tables of the GCP-net. For instance, outcome cdf wb is indifferent to outcome cdf wb, this is due to the indifference on values of the variable C all the rest being equal. In order to

C O R R E C T E D P R O O F Fig. 2.
The partial order induced by the GCP-net in Fig. 1: for the sake of readability, we group into the same nodes some outcomes of the preference model. Outcomes in the same node are indifferent, this is due to the indifference over the values of variable C.

maintain a low level of complexity in the representation of the partial order, we group into the same node outcomes that differ only in the value of the variable C.

Another example is cdf wb ≺ cdf wb, this is because ¬dog-assignments are ceteris-paribus better than dog-assignments. Instead, following Definition 7, cdf wb and cdf wb are weakly incomparable: albeit they belong to the same weakly connected component, there does not exist a path from one outcome to the other nor vice-versa.

Notice that the preference graph has two components. Outcomes in the two components differ on the assignment of the variable B for which no preferences are expressed. Thus each component represents a scenario: one in which we consider the presence of bobcats, and the other in which there are no bobcats. Following Definition 6, cdf wb and cdf wb are strongly incomparable.

Mapping Preference Models to GCP-nets

In this section we shall provide a ceteris paribus semantics for the deontic language provided above. In the next session, we shall show that this semantics identifies models that correspond to GCP-nets. The semantics of the deontic language is defined in terms of preference relations on worlds.

Definition 9. (Preference models of CPDL +

). A preference model of CPDL + , M = (U, ) is a preorder on the set U of outcomes.

A set of ceteris-paribus conditional obligations and liberties C is consistent if it has at least one model, and inconsistent otherwise. A set of ceterisparibus conditional obligations and liberties C entails another preference formula C , written C |= C , if every model of C is also a model of C . In the following definition, an outcome refers to conjunctions of propositional literals referring to each variable in V exactly once, and which are consistent. Thus, for instance, φ refers to the valuation of variable . Satisfaction for formulas in the language CPDL + (Atm) is defined as follows, where u |= ϕ means that the propositional formula ϕ is true at the valuation corresponding to the outcome u:

Definition 10. (Satisfaction in

CPDL + [START_REF] Loreggia | Modelling ceteris paribus preferences with deontic logic[END_REF]). 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 |= ϕ C O R R E C T E D P R O O F
where ||ψ|| M = {w ∈ W : M, w |= ψ} is the truth set of ψ relative to the preference model M.

The class of models satisfying a set of norms C is denoted with C . Among all the possible M ∈ C , rel( C ) ⊆ C is the subset of models that refers only to consistent conjunctions of propositional literals in C. Then M C = (U, C ) is the preference model such that for each M = (U, ) ∈ rel( C ), C ⊆ . Proposition 1. As a liberty is a bilateral permission (L(ψ|φ) = def P(ψ|φ) ∧ P(ψ|¬φ)), we have that

M |= L(ψ|φ) ⇐⇒ ∀v, u ∈ U : v |= ψ, u |= ψ, if v |= φ and v ≺ (-) u then u |= φ, and if v |= ¬φ and v ≺ (-) u then u |= ¬φ
Given the previous definitions we now show that a set of ceteris-paribus norms in CPDL + (Atm) is expressible with a prescriptive CP-net, this means that the preorder induced by the GCP-net is a model which satisfies C. Proof. This is equivalent to proving that for each norm

N ∈ C M C |= N iff Ord C |= N (1)
We show how to prove [START_REF] Awad | When is it morally acceptable to break the rules? a preference-based approach[END_REF] showing how this can be done for obligations. Let start by assuming that M C |= O(ψ|φ), by definition this is equivalent to ∀u, v ∈ U : u ≺ ψ,φ v, thus for consistency of Proof. The CP-net is reported in Fig. 3a, and the induced partial order is depicted in Fig. 3b.

Possible applications

Our analysis shows that a set of norms expressed in deontic logic can be translated into a corresponding GCP-net without loss of semantics, thus providing a conditional preference network giving a compact representation.

On the contrary, GCP-nets allow different scenarios to be modelled and interesting properties and information about the set of norms to be inferred. Adopting the GCP-net framework we are able to reason about: Dominance testing: the problem consists in deciding whether one outcome v dominates another outcome u, i.e. u ≺ v. Consistency testing: the problem consists in finding out whether there is a dominance cycle in the preorder defined by a GCP-net, i.e. whether there is an outcome that dominates (is preferred to) itself.

Both of the aforementioned problems are usually far from easy. In general both dominance and consistency for CP-nets can be NP-complete [START_REF] Boutilier | Reasoning with conditional ceteris paribus preference statements[END_REF][START_REF] Goldsmith | The computational complexity of dominance and consistency in CP-nets[END_REF]. But when the CP-net is over a set of binary variables, and the dependency graph is a tree, the dominance testing becomes linear in the number of variables, if it is a poly-tree then dominance testing becomes polynomial in the number of variables [START_REF] Boutilier | Reasoning with conditional ceteris paribus preference statements[END_REF]. Moreover, in many scenarios, the presence of cycles in the dependency graph means that the network is inconsistent [START_REF] Domshlak | CP-Nets: Reasoning and consistency testing[END_REF]. Thus, consistency testing would allow inconsistencies (contradiction) to be determined in a set of norms while the dominance test allows for testing whether one world is better than another. There are other possible applications that can be enabled with the adoption of a GCP-net, we briefly describe them in the next paragraphs. ences. We can think of the decision-making process as an evaluation of the resulting state-of-affairs. We choose one among all the available options because we prefer the resulting state-of-affair over the others. Thus, we can think of moral and normative judgements as a form of preferences, driven by moral or normative reasoning [START_REF] Sen | Choice, ordering and morality[END_REF]. Finding a feasible way to model, reason, and compare these preferences are central in the field of Artificial Intelligence in order to ensure a convergence of AI agents' behavior with humans' values. One possible solution is to compute the distance among preferences by exploiting the compact representation of such domains. In recent studies, preferences represented with compact representation are used in metric spaces in order to define how similar they are [START_REF] Li | An efficient algorithm to compute distance between lexicographic preference trees[END_REF][START_REF] Loreggia | On the distance between CP-Nets[END_REF]. When both the normative system and individual preferences are represented compactly, preferences comparisons might be useful to understand whether an agent is deviating from the desired behaviour-which is depicted by the legal framework. When this is the case, the system might intervene to find a trade-off which better aligns with the set of values [START_REF] Loreggia | Value alignment via tractable preference distance[END_REF].

Let us expand Example 1 in order to depict a situation in which preferences of individuals deviate from the normative system.

Example 2. (Running Example continued

). The inhabitants of Cattown are not homogeneous in their preferences, but they have different opinions on the norms that Mary enforced. Bob, for instance, moved to Cattown because of his job. He is a dog lover and he has a beautiful Golden Retriever with him. At the same time, he is respectful of the law and shares the same worries about fences when a dog is on a property. Bob's preferences are reported in the CP-net of Fig. 4a.

On the other side, a group of activists in Cattown is fighting the normative system and attacking the set of obligations and permissions which should regulate the presence of dogs, cats and fences. They think that anyone-humans and animals-should move freely in the city and thus they prefer to live without fences. Moreover, many of the people in the group are dog lovers and are indifferent to cats. The preferences of this group are represented in Fig. 4b.

The previous example describes the different points of view that might exist in society: different perspectives that people might have over the same set of features, a situation which is very common in practice. Sometimes norms are closed to the preferences of people, some others are not.

We can use a metric space to measure the similarity of preferences in Mary's community [START_REF] Loreggia | On the distance between CP-Nets[END_REF][START_REF] Loreggia | CPMetric: Deep siamese networks for metric learning on structured preferences[END_REF]. This may help to understand which individual is adhering to the normative system or how to adjust the set of obligations and permissions in order to mitigate differences in society. A definition of distance over GCP-nets does not exist yet, but existing metrics work on the induced partial orders making the comparison feasible.

These kinds of assessments may be used to study possible ways of changing a normative system in order to get closer to the preferences of individuals in the community. This should be done to reduce divergences between a group of people and the normative system. On the contrary, they can also be used to identify which part of the normative system is more infringed.

Modelling factual and deontic detachment.. The proposed language allows two important principles of detachments related to the conditional nature of the modeled norms to be modelled:

-Factual detachment: It represents a situation where a conditional norm O(φ|ψ) exists. If φ is true in the scenario, then we can conclude that in that specific scenario it ought to be that ψ. -Deontic detachment: It represents a situation where two norms O(φ) and O(φ|ψ) exist, the first prescribing the state which is the antecedent of the second. We can then conclude that in the scenario it ought to be ψ.

The CP-net framework allows us to model factual detachment: from fact φ and conditional norm O(φ|ψ) we infer ψ. In the CP-net, factual detachment can be computed by considering the partial assignments of variables in P corresponding to φ: for each literal p or ¬p in φ the corresponding atom p in P is assigned respectively true or false. Then for each CP-table of the descendants of P, we consider only preference orders where atoms in P have the given partial assignments. The process is repeated recursively for each atom in P. Called m the number of atoms in P, if the dependency graph is acyclic, then this can be done in O(m).

On the contrary, deontic detachment cannot be captured by our preference model. Indeed, inferring O(ψ) from O(φ|ψ) when O(φ) is the case, corresponds to removing the edges in the dependency graph between variables corresponding to φ and to ψ. This move is not allowed since within the CP-net framework it is not possible to remove a dependency between two variables unless it is a fake dependency. A fake dependency is introduced in the dependency graph when it concerns complementary literals p and ¬p. This would apply for instance to a pair of obligations O(p|q) and O(¬p|q) (i.e., an obligation that has the same consequent and complementary antecedents).

Modelling disjunctive obligations.. The proposed language does not allow for deontic operators O and P to be applied to disjunctions. This means that the consequent of norms cannot contain disjunctions. This limitation, however, does not really affect the expressiveness of the language, since an obligation to realise at least one of two states of affairs φ and ψ can be modelled through the combination of two obligations O(¬φ|ψ) and O(¬ψ|φ), possibly with permissions to realise both, P(φ) and P(ψ), if this is meant to be the case.

Let us exemplify this situation by expanding our running example.

Example 3. (Running example continued). The municipality of Cattown is tolerant towards the ownership of dogs, as long as they are kept in private properties. As already mentioned, for some security reasons, if there is a dog on a property then there should also be a fence. This would allow the dog to be left free on the property. Otherwise, the municipality tolerates the absence of a fence, but in these cases, dogs must be kept on a leash. The previous example describes a situation where mutually exclusive norms can be enforced. Using our language, the normative system can be represented with the following obligations:

O(d ∧ ¬f |l) ∧ O(d ∧ ¬l|f )
Focusing only on the norms in Example 3, we can build the prescriptive CP-net represented in Fig. 5. Notice that in this case the dependency graph of the related prescriptive CP-net is not acyclic.

Conclusions

GCP-nets, and their variants, are an interesting and emerging preference frameworks that enable the representation of conditional preferences in a compact way. These frameworks are adopted in many different scenarios. For instance, in recommender systems, it is used to improve the accuracy of personalized search [START_REF] Wang | Preference recommendation for personalized search[END_REF], and recently it was also employed to capture and represent how the deliberation process of a group of individuals switches to different moral frameworks in order to make a moral decision [START_REF] Awad | When is it morally acceptable to break the rules? a preference-based approach[END_REF].

In this work, we have shown how to model contrary-to-duty obligations and permissions using GCP-nets. Using this formalism, we have also shown how to capture the distinction between strong and weak permissions. In order to do that, we adopted a restricted deontic logic representing a set of obligations and permissions. The resulting normative system induces a preference order over the possible worlds.

The adoption of these preference representations shall allow the combination of machine learning methods and standard reasoning frameworks to compare preferences from different users [START_REF] Loreggia | CPMetric: Deep siamese networks for metric learning on structured preferences[END_REF].

C O R R E C T E D P R O O F C O R R E C T E D P R O O F C O R R E C T E D P R O O F

Definition 8 .

 8 Let C ⊆ + (Atm) be a set of statements. A prescriptive CP-net C = (G, CPT ) is a generalized CP-net (with G a directed graph over

Fig. 1 .

 1 Fig. 1. The GCP-net which represents Mary's community preferences of Example 1.

Theorem 1 .

 1 Given a set of norms C ⊆ CPDL + (Atm) and the prescriptive CP-net C , then Ord C = M C .

C

  with C:Ord C |= ψ : ¬φ ≺ φ Ord C |= ∀y 1 , y 2 ∈ (V --{ }) : ¬φψy 1 ≺ φψy 2by definition, this is equivalent toOrd C |= ∀u, v ∈ U : u, v |= ψ, u |= ¬φ, v |= φOrd C |= O(ψ|φ) This proves =⇒ direction. We show the other way round (⇐=) by contradiction. Let us assume that Ord C / O(ψ|φ), thus O(ψ|φ) / ∈ but this also O(ψ|φ) ∈ But this is a contradic-On the basis of the GCP-net models described above the following proposition holds. Proposition 2. A contrary-to-duty framework having the following prescriptions O(φ), O(¬φ|ψ),O(φ|¬ψ) is modelled by a consistent prescriptive CP-net.

FFig. 3 .

 3 Fig. 3. (3a) The prescriptive CP-net induced by the duty framework of Proposition 2. (3b) The partial order induced by the prescriptive CP-net which satisfies the duty framework of Proposition 2.

FFig. 4 .

 4 Fig. 4. (4a) The GCP-net which represents Bob preferences of Example 2. (4b) The GCP-net represents preferences of the group of activists as described in Example 2.

FFig. 5 .

 5 Fig. 5. The prescriptive CP-net which represents the normative system described in the Example 3.

Acknowledgments

Roberta Calegari, Andrea Loreggia, and Giovanni Sartor have been supported by the H2020 ERC Project "CompuLaw" (G.A. 833647).

Authors have no Conflict of Interest (CoI) to share.


Ali I Ozkes
email: ali.ozkes@skema.edu

M Remzi Sanver
email: remzi.sanver@lamsade.dauphine.fr

Felix Brandt

Olivier Cailloux

Shurojit Chatterji

Patrick Lederer

Ali Nesin

Dominik Peters

Uniform Random Dictatorship: A characterization without strategy-proofness *

Although they exclude any possibility of a compromise ex-post, uniform random dictatorship methods provide a solution to conflicts of interest that guarantees an ex-ante fairness. Axiomatic characterizations of random dictatorships in the classical literature of social choice theory use strategy-proofness. In a probabilistic framework that embeds tops-onlyness and anonymity, for three or more alternatives, we provide a characterization that uses an independence condition instead: uniform random dictatorship is the only social choice rule that is efficient and independent. This characterization also establishes that under efficiency and anonymity, independence and strategy-proofness are equivalent. In the particular case of two alternatives, independence becomes vacuous and we propose a characterization without independence.

Introduction

Tops-only social choice rules are those whose choices depend only on the alternatives individuals find the best. As such, they overlook how individuals rank alternatives other than the one they think to be the best. Tops-onlyness is a condition of interest for at least two reasons. First, it economizes the information required to make a collective decision. Next, there is a tight connection between strategy-proofness and tops-onlyness for resolute social choice rules that choose a single alternative: over the full domain of preferences, unanimity and strategy-proofness result in dictatorships, hence implying tops-onlyness [START_REF] Gibbard | Manipulation of voting schemes: a general result[END_REF][START_REF] Satterthwaite | Strategy-proofness and Arrow's conditions: Existence correspondence theorems for voting procedures and social welfare functions[END_REF]. The implication of tops-onlyness by strategy-proofness prevails for several restricted domains [START_REF] Weymark | Strategy-Proofness and the Tops-Only Property[END_REF][START_REF] Chatterji | Tops-only domains[END_REF].

While dictatorships strongly violate anonymity, the plurality rule that picks the alternatives considered as best by the highest number of individuals exemplifies an irresolute social choice rule that is anonymous and tops-only.

In fact, on a fixed population, it is the only social choice rule that is tops-only, anonymous, neutral and satisfies a certain monotonicity property [START_REF] Kelly | Characterizing plurality rule on a fixed population[END_REF]. Tops-onlyness is also a key condition to characterize the plurality rule in social choice models with a variable society [START_REF] Yeh | An efficiency characterization of plurality rule in collective choice problems[END_REF][START_REF] Sekiguchi | A characterization of the plurality rule[END_REF].

All these concepts have their counterparts in social choice models where outcomes are randomized1 . A well-known class of social choice rules in this framework are random dictatorships, which assign to individuals a probability distribution for being a dictator. Not only random dictatorships are tops-only but they are the only probabilistic social choice rules that are strategy-proof and (ex-post) efficient (Gibbard, 1977, Corollary 1). As in the resolute case, the implication of tops-onlyness by unanimity and strategyproofness prevails for several restricted domains [START_REF] Chatterji | Tops-only domains[END_REF][START_REF] Chatterji | On random social choice functions with the tops-only property[END_REF].

We focus on a particular element of the class of random dictatorships, namely the uniform random dictatorship where individuals have the same probability of being the dictator. Thus, uniform random dictatorship chooses the top alternative of an individual who is picked uniformly at random. Therefore, the probability that a given alternative is chosen is the topsupport of that alternative, defined as the percentage of voters for whom this alternative is top-ranked.

Letting m ≥ 2 be the number of alternatives, a probabilistic and topsonly social choice rule is a mapping whose inputs are elements of the m -1 dimensional simplex, where each entry corresponds to the top-support of a specific alternative, defined as the percentage of voters for whom this alternative is top-ranked. The outcome is also an element of the m -1 dimensional simplex whose value at each entry gives the probability that the corresponding alternative gets chosen. Thus, we consider probabilistic topsonly social choice rules (PTS) that map a multidimensional simplex into itself. As inputs are m-tuples of percentages rather than being preferences assigned to individuals, anonymity is embedded in the definition of a PTS.

By the same token, the model is able to handle variable-size societies.

Remark that a profile of top alternatives does not reflect any information about how individuals rank rest of the alternatives. As such, nothing can be said about the social welfare induced by an alternative that is top-ranked by no individual. Thus, it makes sense for a PTS to overlook such alternatives and only consider those that are top-ranked by at least one individual. As a condition in this spirit, we qualify a PTS as efficient, if it requires that an alternative whose top-support is zero gets zero probability of being chosen.

We also consider an independence condition under which the probability that an alternative is chosen depends only on its top-support. Thus, when an independent PTS is used, the probability that an alternative is chosen becomes independent of the top-support of other alternatives. As a result, an independent PTS can be expressed by a family of basic mappings, one for each alternative, that map the unit interval [0, 1] to itself, transforming the top-support of an alternative into its probability of being picked.

The conjunction of independence with efficiency singles out uniform random dictatorship when m ≥ 3. Uniform random dictatorship is neutral (i.e., ensures an equal treatment of alternatives) and monotonic (i.e., increasing the top-support of an alternative without increasing the top-support of any other should increase this alternative's probability of getting elected). Thus, the conjunction of independence with efficiency implies neutrality and monotonicity.

Although independence is rather demanding when m ≥ 3, it becomes vacuous for m = 2, being trivially satisfied by every PTS. Moreover, the conjunction of efficiency, neutrality and monotonicity does not imply uniform random dictatorship in this case. On the other hand, when we additionally require basic mappings to be twice differentiable with uniform sign of the second derivative, we again single-out uniform random dictatorship.

Section 2 presents the basic notions and notation. Sections 3 and 4 present the results for m ≥ 3 and m = 2, respectively. Section 5 makes concluding remarks.

Basic notions and notation

Let A with #A = m ≥ 2 be a set of alternatives and N with #N ≥ 2 be a finite set of individuals. The preference of each i ∈ N on A is expressed by her top alternative

t i ∈ A. Let [0, 1] Q = [0, 1] ∩ Q be the set of rational numbers in the [0, 1] interval. A profile of top alternatives (henceforth a profile) is a mapping π : A -→ [0, 1] Q with x∈A π(x) = 1 where π(x) is the ratio of the number of individuals for whom x is the top alternative to #N . A lottery over A is a mapping λ : A -→ [0, 1] with x∈A λ(x) = 1.
We write Π and Λ for the set of profiles and lotteries, respectively. A probabilistic tops-only social choice rule (PTS) is a mapping τ : Π -→ Λ. Given π ∈ Π, we write τ π instead of τ (π) ∈ Λ. Note that anonymity of a PTS, in the sense of equal treatment of individuals, is embedded in the definition of a profile.

3 Uniform random dictatorship: a characterization for more than two alternatives

We qualify a PTS τ as being efficient iff π

(x) = 0 =⇒ τ π (x) = 0 ∀x ∈ A, ∀π ∈ Π. Proposition 1 Let m ≥ 2. If τ : Π -→ Λ is efficient then π(x) = 1 =⇒ τ π (x) = 1 ∀x ∈ A, ∀π ∈ Π.
Proof : Take any π ∈ Π with π(x) = 1 for some x ∈ A. Hence, π(y) = 0 for all y ∈ A\{x}. As τ is efficient, we have τ π (y) = 0 for all y ∈ A\{x}. Thus,

x∈A τ (x) = 1 implies τ π (x) = 1. ■ A PTS τ is independent iff given any x ∈ A and any π, π ′ ∈ Π with π(x) = π ′ (x), we have τ π (x) = τ π ′ (x)
. Note that independence is trivially satisfied when m = 2. Every independent PTS τ can be expressed through a vector (

β x : [0, 1] Q -→ [0, 1]) x∈A of mappings such that τ π (x) = β x (π(x))
∀x ∈ A, ∀π ∈ Π. We refer to each β x as a basic mapping. For the rest, we write A = {x 1 , ..., x m } and index basic mappings over the set M = {1, ..., m} such that for each i ∈ M , β i is used for x i ∈ A. We now characterize basic mappings that express efficient and independent PTSs.

Proposition 2 Let m ≥ 2. A vector (β i ) i∈M of basic mappings expresses an efficient and independent PTS τ iff 1. β i (0) = 0 and β i (1) = 1 for every i ∈ M.

2.

i∈K β i (r i ) + β j (1 - i∈K r i ) = 1 for any k ∈ M \{m}, any K ⊂ M with #K = k, any (r i ) i∈K ∈ [0, 1] k Q with i∈K r i ∈ [0, 1] and any j ∈ M \K.
Proof : To see the "only if" part let (β i ) i∈M express an efficient and independent PTS τ . It is straightforward to see that when

β i (0) = 0 or β i (1) = 1 fails for some i ∈ M , τ is not efficient. Now suppose i∈K β i (r i ) + β j (1 - i∈K r i ) = 1 fails for some k ∈ M \{m}, some K ⊂ M with #K = k, some (r i ) i∈K ∈ [0, 1] k Q with i∈K r i ∈ [0, 1] and some j ∈ M \K. Take π ∈ Π with π(x i ) = r i for all i ∈ K, π(x j ) = 1 - i∈K r i and π(x i ) = 0 for all i ∈ M \(K ∪ {j}). As β expresses τ , we have τ π (x i ) = β(r i ) for all i ∈ K, τ π (x j ) = β(1 - i∈K r i ) and τ π (x i ) = 0 for all i ∈ M \(K ∪ {j}). By construc- tion, m i=1 τ π (x i ) = i∈K β i (r i ) + β j (1 - i∈K r i ) ̸ = 1, contradicting that τ is a PTS.
To see the "if" part, let (β i ) i∈M satisfy the conditions of the proposition.

Take any π ∈ Π. Define

τ π (x i ) = β i (π(x i )) ∀x i ∈ A. Let K = {i ∈ M : π(x i ) > 0}. If #K = 1, say K = {k}, then π(x k ) = 1 and π(x i ) = 0 ∀i ∈ M \{k}. As β i (0) = 0 and β i (1) = 1 for every i ∈ M , we have τ π (x k ) = 1 and τ π (x i ) = 0 ∀i ∈ M \{k}, establishing i∈M τ π (x i ) = 1. Now let #K > 1.
Pick some j ∈ K. By definition of τ , we have

τ π (x i ) = β i (π(x i )) ∀i ∈ K\{j}. By construction, τ π (x j ) = β j (1 - i∈K\{j} π(x i )) and τ π (x i ) = 0 ∀i ∈ M \K.
By construction,

m i=1 τ π (x i ) = i∈K\{j} β i (π(x i )) + β j (1 - i∈K\{j} π(x i ))
which equals 1. Thus, τ is well-defined. By construction it is independent. Finally, it is efficient, as β i (0) = 0 and β i (1) = 1 for every i ∈ M. ■

A PTS τ is neutral iff given any π ∈ Π and any permutation σ :

A ←→ A, we have τ π•σ (x) = τ π (σ(x)) ∀x ∈ A. Remark that an independent PTS τ = (β i ) i∈M is neutral iff β i = β j ∀i, j ∈ M .
Thus, an independent and neutral PTS τ can be expressed by a single basic mapping β:

[0, 1] Q -→ [0, 1] that satisfies τ π (x) = β(π(x)) ∀x ∈ A, ∀π ∈ Π.
Proposition 3 Let m ≥ 3. Every efficient and independent PTS is neutral.

Proof : Let τ = (β i ) i∈M be an efficient and independent PTS. Proposition 2 implies the following two equalities:

β i (r) + β j (1 -r) = 1 ∀i, j ∈ M , ∀r ∈ [0, 1]. β i (r) + β j (q) + β k (1 -r -q) = 1 ∀i, j, k ∈ M , ∀r, q ∈ [0, 1].
Note that the second inequality exploits m ≥ 3.

From the first equality, we can derive β k (1 -r -q) = 1 -β i (r + q) as well as β k (1-r -q) = 1-β j (r +q). Substituting these into the second inequality, we get

β i (r) + β j (q) = β i (r + q) = β j (r + q) ∀i, j ∈ M , ∀(r + q) ∈ [0, 1],
establishing the neutrality of τ . ■ Uniform random dictatorship is the PTS that assigns to each alternative a probability that equals the percentage of individuals for whom that alternative is top. So the uniform random dictatorship τ is expressed by the basic mapping β(r) = r ∀r ∈ [0, 1], ensuring τ π (x) = π(x) ∀x ∈ A, ∀π ∈ Π.

As we show below, not only uniform random dictatorship is efficient and independent, but it is the unique PTS that satisfies both conditions.

Theorem 1 Let m ≥ 3. A PTS τ : Π -→ Λ is efficient and independent iff τ is the uniform random dictatorship.

Proof : It is straightforward to check that the uniform random dictatorship is efficient and independent. To show the "only if" part, let τ be an efficient and independent PTS. Thus, τ is neutral by Proposition 3. Let β be the basic mapping that expresses τ . As τ is efficient, we have β(0) = 0 and β(1) = 1. Proposition 2 implies the following two equalities:

β(r) + β(1 -r) = 1 ∀r ∈ [0, 1]. β(r) + β(q) + β(1 -r -q) = 1 ∀r, q ∈ [0, 1] with r + q ⩽ 1.
satisfied by every PTS. Remark that for for m = 2, Proposition 2 can be restated as follows:

Proposition 4 Let m = 2. A vector (β 1 , β 2 ) of basic mappings expresses an efficient and independent PTS τ iff 1. β i (0) = 0 and β i (1) = 1 for every i ∈ {1, 2} .

2. β 1 (r) + β 2 (1 -r) = 1 ∀r ∈ [0, 1].
Thus, when m = 2, efficient PTSs are precisely those that can be expressed by a basic mapping β 1 with β 1 (0) = 0 and β 1 (1) = 1, which deter-

mines β 2 (r) = 1 -β 1 (1 -r) ∀r ∈ [0, 1].
As Theorem 1 and Proposition 3 both use the strength of independence, they vanish when m = 2, as can be seen through the example that follows.

Example 1 Let β 1 (r) = r2 and β 2 (r) = -r 2 + 2r . By Proposition 4, β 1 and β 2 express a PTS that is efficient, (trivially) independent but not neutral and not the uniform random dictatorship.

For a similar observation, note that the uniform random dictatorship satisfies the following monotonicity condition: A PTS τ is monotonic iff given any x ∈ A and any π, π ′ ∈ Π with π(x) > π ′ (x) and π(y) ⩽ π ′ (y)

∀y ∈ A\{x}, we have τ π (x) > τ π ′ (x). Hence, by Theorem 1, efficiency and independence imply monotonicity when m ≥ 3. On the other hand, when m = 2, an efficient (and trivially independent) PTS may not be monotonic.

We observe this at the example below.

2 Example 2 Let β = β i (r) =            r, if r ⩽ 1 4 or r > 3 4 1 2 -r, if 1 4 < r ⩽ 1 3 2r -1 2 , if 1 3 < r ⩽ 2 3 3 2 -r, othwerwise for all i ∈ {1, 2}
and r ∈ [0, 1] . By Proposition 4, β expresses an efficient PTS τ that is trivially independent. However, β is not monotonically increasing, hence τ is not monotonic.

At this stage, one may ask whether adopting monotonicity and neutrality explicitly while conjoining them with efficiency would characterize the uniform random dictatorship, a result reminiscent to Theorem 1. The answer is negative, as the example below shows.

Example 3 Consider the basic mapping β defined as β(r) = r 2 for r ∈ [0, 1 2 ), β( 1 2 ) = 1 2 and β(r) = -r 2 + 2r for r ∈ ( 1 2 , 1] . By Proposition 4, β expresses an efficient PTS τ which is monotonic and neutral by construction while doesn't express the uniform random dictatorship.

Remark that Example 3 uses a basic mapping that is not continuous, which we now rule out by adopting continuity as an independent condition.

We say that a PTS τ = (β i ) i∈{1,2} is continuous iff β 1 and β 2 are both continuous. Before characterizing the class of continuous, efficient, monotonic and neutral PTSs, observe the logical independence of the four conditions:

Example 1 exemplifies a PTS that is continuous, efficient, monotonic but not neutral. Example 2 is a PTS that is continuous, efficient, neutral but not monotonic. The basic mapping β(r) = 1 2 r + 1 4 ∀r ∈ [0, 1] expresses a PTS that is continuous, monotonic, neutral but not efficient. Example 3 is a PTS that is efficient, monotonic, neutral but not continuous.

The class of continuous, efficient, monotonic and neutral PTSs is not limited to uniform random dictatorship either, as the example below shows.

Example 4 Consider the basic mapping defined as β(r) = 3r 2 -2r 3 for r ∈ [0, 1] . By Proposition 4, β expresses an efficient PTS τ . Moreover, τ is continuous, monotonic, and neutral while it is not the uniform random dictatorship.

Note that the basic mapping β in Example 4 is not only continuous but also twice differentiable. Note also that sgnβ ′′ (r) = -sgnβ ′′ (r) for r ∈ [0, 1 2 ) and r ∈ ( 1 2 , 1]. In fact, the following result singles out the uniform random dictatorship within the class of twice differentiable, efficient, monotonic and neutral PTSs.

Concluding remarks

In a probabilistic social choice setting that embeds tops-onlyness and anonymity, we characterize uniform random dictatorship in terms of independence and efficiency (Theorem 1). The result needs at least three alternatives. In fact, when there are only two alternatives, independence is vacuously satisfied and we provide an alternative characterization of uniform random dictatorship by using efficiency, monotonicity, neutrality, together with certain differentiability conditions over basic mappings (Theorem 2).3

There is an abundance of frameworks where imposing independence over the collective choice rule is so demanding that an impossibility is reached.

This literature of impossibilities dates back to the seminal result of [START_REF] Arrow | Social choice and individual values[END_REF] in an ordinal preference aggregation framework, which has its reflections to other frameworks such as group identification by [START_REF] Kasher | On the question" who is aj?" a social choice approach[END_REF], judgement aggregation by [START_REF] List | Aggregating sets of judgments: An impossibility result[END_REF]Pettit (2002, 2004), and classification aggregation by [START_REF] Maniquet | A theorem on aggregating classifications[END_REF], among others. Our framework falls out of this universe: for probabilistic tops-only social choice rules, not only independence can be satisfied, but it almost singles out uniform random dictatorship. Therefore, Theorem 1 can be seen as a positive result.

Muto and Sato (2017) introduce a "same-sidedness" axiom that leads to an impossibility result in a deterministic setting. A probabilistic version of this axiom is considered by [START_REF] Bandhu | Stochastic Samesidedness in the Random Voting Model[END_REF] who characterize the general class of random dictatorships with efficiency and "stochastic samesidedness" when n = 2 or m = 3. Their characterization does not use topsonlyness and cannot be extended to the general case. However, they show that when tops-onlyness is added, random dictatorship can be characterized with efficiency and stochastic same-sidedness for m ≥ 4. Thus, our choice to embed tops-onlyness into the model seems to be a natural choice in order to obtain a general and simple characterization of uniform random dictatorship.

Comparing our Theorem 1 to Theorem 2 (b) of [START_REF] Bandhu | Stochastic Samesidedness in the Random Voting Model[END_REF] allows to observe that when m ≥ 4, stochastic same-sidedness and independence turn out to be equivalent under tops-onlyness, efficiency and anonymity.

This observation is of interest given the technical nature of stochastic samesidedness and the fact that it is implied by independence in a general setting.

These comparisons we make do not apply to the case when m = 2, which is not considered by [START_REF] Bandhu | Stochastic Samesidedness in the Random Voting Model[END_REF].

We close by connecting our findings to the classical characterization of random dictatorships by Gibbard (1977) where strategy-proofness is used as a core axiom without referring to an independence condition. In fact, (Gibbard, 1977, Corollary 1) characterizes random dictatorships in terms of strategy-proofness and efficiency. It follows from Gibbard (1977) that uniform random dictatorship is characterized by strategy-proofness, efficiency and anonymity. As anonymity is embedded to our model, our Theorem 1 can be read as a characterization of uniform random dictatorship in terms of independence, efficiency and anonymity. These two observations establish that under efficiency and anonymity, strategy-proofness and independence are equivalent, which calls for further exploring the relation between the two concepts in the general context of probabilistic tops-only social choice.

Theorem 2

 2 Within the class of twice differentiable, efficient, monotonic and neutral PTSs, uniform random dictatorship is the only PTS τ = (β, β) with sgnβ ′′ (r) = sgnβ ′′ (r) ∀r, r ∈ [0, 1]. Proof : It is straightforward to see that the uniform random dictatorship is efficient, monotonic, neutral, twice differentiable and satisfies sgnβ ′′ (r) = 0 ∀r ∈ [0, 1]. Now, take any PTS τ = (β, β) within the class of twice differentiable, efficient, monotonic, neutral PTSs. Condition 2 of Proposition 4 implies β ′′ (r) = -β ′′ (1 -r) ∀r ∈ [0, 1]. Thus, β ′′ (r) > 0 for some r ∈ [0, 1] implies β ′′ (1 -r) < 0. As a result, sgnβ ′′ (r) = sgnβ ′′ (r) ∀r, r ∈ [0, 1] implies β ′′ (r) = 0 ∀r ∈ [0, 1]. Thus, β(r) = ar +c for some a, c ∈ R. As τ is efficient, a = 1 and c = 0, showing that τ is the uniform random dictatorship. ■

See Brandt (2017) for an eloquent survey of the recent probabilistic social choice literature.

Note that the basic mappings of an independent and monotonic PTS must be monotonically increasing.

The rather technical condition that sgnβ ′′ (r) = sgnβ ′′ (r) ∀r, r ∈ [0, 1] is used towards identification of what exactly uniform random dictatorship entails, rather than as a desired property with interpretability.

Note that the second inequality exploits m ≥ 3.

From the first equality, we can derive β(1 -r -q) = 1 -β(r + q). Substituting this into the second inequality, we get β(r) + β(q) = β(r + q) ∀r, q ∈ [0, 1] with r + q ⩽ 1. We first claim and show β(n

The equality holds for n = 1. Take any n ∈ N and assume

showing the claim by induction. As for every n ∈ N and every r ∈ [0, 1], we can write

In the statement of Theorem 1, the domain of a PTS is restricted to rational numbers. This restriction is exploited to establish Cauchy's functional equation used in the proof. When a PTS admits a more general domain with real numbers, Cauchy's functional equation can be established by assuming the continuity of β [START_REF] Cauchy | Cours d'analyse de l'Ecole royale polytechnique[END_REF]. However, continuity of β is not necessary, as certain weaker continuity conditions such as imposing continuity on at least one point in the domain of β would also establish the Cauchy equation [START_REF] Darboux | Sur la composition des forces en statique[END_REF]. Discarding this continuity assumption and allowing β to be nowhere continuous opens room to a PTS that behaves as the uniform random dictatorship at rational values of profiles but not at irrational values.

We close the section by noting that efficiency and independence do not imply each other. The PTS expressed by the basic mapping β x (r) = 1 m ∀r ∈ [0, 1], ∀x ∈ A is independent but not efficient. For a PTS that is efficient but not independent, at each π ∈ Π, write X(π) = {x ∈ A : π(x) > 0} and let τ π (x) = 1 #X(π) ∀x ∈ X(π) and τ π (x) = 0 ∀x ∈ A\X(π).

The case of two alternatives

We start by emphasizing the difference in the strength of independence depending on whether there are at least three alternatives or not. For m ≥ 3, this is a demanding condition failed by many PTSs. In fact, as Theorem 1

shows, conjoined with efficiency, it singles out the uniform random dictatorship. On the other hand, for m = 2, independence becomes vacuous, being


Sarazin Arthur
email: arthur@datactivi.st

Morey Mathis

Debru Romain

Designing a data standard for mountain climbing : the Mountain High open reference dataset

Keywords: rock climbing, open data, reference data, design fiction Conceptualization, Methodology, Writing -Original draft

The Mountain High dataset is an open dataset designed to be a reference for the study of rock climbing expeditions and all of their aspects, including equipment and human behavior, medical experiments, climbing techniques, and weather conditions. This open dataset is built on top of the Himalayan database published by the American Alpine Club in 2004. The data is currently stored on recherche.data.gouv.fr, along with a design scenario that provides an example of how the Mountain High dataset can be used by physicians interested in the classification of altitude-related hallucinations.

demonstrate how design fiction can assist in designing useful open datasets and related data products. The Mountain High Dataset was created to support the eponymous design fiction (available here) in which a fictional physician, F.G Thomson develops a classification of high-altitude-related hallucinations that occur during rock climbing expeditions.

The designed dataset meets the need for an open reference dataset on mountain climbing that can assist climbers in their decision-making process [START_REF] Ivanova | Content-based recommendations for crags and climbing routes[END_REF], provide researchers with an interesting context to study teamwork and leadership [START_REF] Walsh | What climbing expeditions tell us about teamwork[END_REF], and offer physicians firsthand data to measure the impact of physiological variables on summit success rates and mortality [START_REF] Huey | Mountaineers on mount everest: effects of age, sex, experience, and crowding on rates of success and death[END_REF]. Furthermore, such a reference dataset will play a key role in structuring the digital ecosystem surrounding mountaineering (e.g., camptocamp.org) and provide valuable support for developers seeking to create new products and services for climbers. This open reference dataset also serves as a way to carry on Elizabeth Hawley's life work. She was the encyclopedic mind behind the Himalayan Database, who spent 40 years interviewing climbers,

Method

To produce the Mountain High open reference dataset, we first utilized the Frictionless Data containerization method to convert the metadata and documentation from the Himalayan Database into a Data Package (OpenKnowledgeFoundation & Datopian, 2022). This Data Package makes the metadata and documentation from the Himalayan Database interoperable, reusable, and testable.

Steps

• Data containerization : it involves merging small specifications, each one for a subpart of a dataset: metadata, table structure, and data file (e.g., .csv, .json, etc.). When combined, they form a "Data Resource" that can be merged with other data resources and data-level metadata to create a "Data Package" (see Figure 1) : • Data standardisation : Data standardisation is a socio-technical process that aims to create a reference for the Data package created. For this purpose, we adopted Datapublica's standardisation process [START_REF] Goëta | La standardisation des données ouvertes: favoriser l'interopérabilité, accroître l'impact de l'open data[END_REF], as displayed in Figure 2. We referenced our table schema on schema.data.gouv.fr, a platform built by the French Interministerial Digital Service (DINUM), where mountaineering data producers discussed and iterated over the table schema we proposed. In addition to these online discussions, we conducted 10 interviews with data producers to gather feedback on pain points and difficulties in producing data compliant with the standard. We also led one working group with mountain climbers, physicians, and researchers from Grenoble to get feedback on the reusability of the data produced and the external validity of our design scenario.

The results, including the table schema, the example datafiles and their metadata is shown in File A while the design scenario is shown in File B. Sampling strategy We used a sampling strategy to create a statistically meaningful example dataset in our data package. We extracted data distributions from [START_REF] Salisbury | The himalaya by the numbers[END_REF] to create a sample from which we can infer all types of mountain climbers.

For quality control, we used the data management service Frictionless Repository, which provides continuous data validation to tabular data, checking and reporting for cell and label errors (OpenKnowledgeFoundation, 2023).

Dataset Description

Object name Mountain high open reference dataset.

Format names and versions CSV (data),

Reuse Potential

The designed dataset addresses the need for an open reference dataset on mountain climbing. It can assist climbers in their decision-making process, provide researchers with an interesting setting to study teamwork and leadership, and offer physicians firsthand data to quantify the effects of physiological variables on rates of summit success and death. Furthermore, such a reference dataset will play a key role in structuring the digital ecosystem surrounding mountaineering (e.g., camptocamp.org) and provide useful support for developers willing to create new products and services for climbers.

Moreover, a reference dataset on mountain climbing could serve as a valuable training tool for aspiring climbers, allowing them to simulate and prepare for the challenges of a mountain ascent. It could also inform public policy and safety regulations related to mountain climbing, based on evidence of accident rates and safety practices. Finally, adventure tourism companies could use such a dataset to design safer and more enjoyable mountain expeditions for their clients.

Figure 1 :

 1 Figure 1: Composition of a data package.

Figure 2 :

 2 Figure 2: Workflow of the Datapublica's standardisation process from (Goëta & Ho-Pun-Cheung, 2022)

Table Schema

 Schema

	(metadata), Data Package (data
	metadata)
	Creation dates 2023-01-15 to 2023-04-13
	Dataset creators Elizabeth Hawley (archivist, main data producers), Richard Salisbury (pro-
	grammer, main data producers), Mathis Mourey (programmer, data editor), Arthur Sarazin (de-
	signer, data designer)
	Language Javascript (JSON).
	License Open License.
	Repository name Schema.data.gouv.fr
	Publication date 2023-04-13.

Acknowledgements

The authors would like to express their deepest gratitude to Elizabeth Hawley, the most significant non-climber in the mountain climbing community, who tirelessly collected data for 40 years on Nepal's mountaineering expeditions. Without her tireless work, so much knowledge would not have been made available.

Funding Statement

This research resulted from the research project Dataflow funded by Datactivist and the UNESCO Chair in AI and Data science for Society

Competing interests

The author(s) has/have no competing interests to declare.

Supplementary Files

• File A : Mountain high data package Repository of the data package • File B : Mountain high data usage scenario Repository of the data usage scenario