Gabriella Pigozzi
email: gabriella.pigozzi@dauphine.fr

Alexis Tsoukiàs
email: alexis.tsoukias@dauphine.fr

Paolo Viappiani
email: paolo.viappiani@lip6.fr

Preferences in Artificial Intelligence

The paper presents a focused survey about the presence and the use of the concept of "preferences" in Artificial Intelligence. Preferences are a central concept for decision making and have extensively been studied in disciplines such as economy, operational research, decision analysis, psychology and philosophy. However, in the recent years it has also become an important topic both for research and applications in Computer Science and more specifically in Artificial Intelligence, in fields spanning from recommender systems to automatic planning, from non monotonic reasoning to computational social choice and algorithmic decision theory. The survey essentially covers the basics of preference modelling, the use of preference in reasoning and argumentation, the problem of compact representations of preferences, preference learning and the use of non conventional preference models based on extended logical languages. It aims at providing a general reference for all researchers both in Artificial Intelligence and Decision Analysis interested in this exciting interdisciplinary topic.

Introduction and Notation

Preferences are a central concept of decision making and have extensively been studied in disciplines such as economy, operations research, psychology, and philosophy. As preferences are fundamental for the analysis of human choice behaviour, they are becoming of increasing importance for computational fields such as artificial intelligence, databases, and human-computer interaction. Preference models are needed in decision-support systems such as web-based recommender systems, in automated problem solvers such as configurators, in autonomous systems such as Mars rovers. Nearly all areas of artificial intelligence deal with choice situations and can thus benefit from computational methods for handling preferences. Moreover, recommender systems, personal assistants, and other interactive systems need to elicit and satisfy the user's preferences in order to be able to give truly satisfactory recommendations. Social choice methods are also becoming of importance in computational domains such as multi-agent systems.

The field of "preferences" became an emerging area of scientific investigation for several research groups in computer science and in the recent years we assist to a number of workshops, conferences and editorial initiatives aiming at promoting this area at the edge of fields such as decision analysis, artificial intelligence, social choice and economics (see for instance [244]). We mention:

the special issue (vol. 20) of the journal Computational Intelligence in 2004, (see for instance [START_REF] Doyle | Prospects for preferences[END_REF]), the Dagstuhl seminar1 (04271) on "Preferences: Specification, Inference, Applications" in 2004, starting from which a number of seminars and workshops have been organised every year since (notably the MPREF series of Multidisciplinary Workshops on Advances in Preference Handling), the special issue of the AI Magazine on "Preference Handling in AI" published in Winter 2008 (that included a general tutorial [START_REF] Brafman | Preference handling: An introductory tutorial[END_REF], and survey papers covering preferences in interactive systems [223], planning [START_REF] Baier | Planning with preferences[END_REF], conversational recommender systems and electronic commerce applications [237], constraint satisfaction [249], social choice [START_REF] Chevaleyre | Preference handling in combinatorial domains: From AI to social choice[END_REF] and multiobjective optimization [111]), the special issue of the journal Annals of Operations Research (vol. 163) in 2008 (see [245]), the Algorithmic Decision Theory conferences held in 2009, 2011 and 2013 (see [247, 61, 226]), the special issue (vol. 175) of the journal Artificial Intelligence in 2011, (see [START_REF] Domshlak | Preferences in AI: an overview[END_REF]), the Dagstuhl seminar 2 (14101) on "Preference Learning" in 2014, and the establishment of the EURO Working Group on Preference Handling which regroups the international community concerned by this subject. 3This article makes an overview of the recent advances in this area, with a focus on reasoning, argumentation, deontic reasoning, representation, learning, and non-classical models (preference representations based on fuzzy sets and beyond). The reader only needs to be acquainted with basic notions of discrete mathematics and logic.

Traditionally preferences have always been modelled as binary relations applied to a set which we will denote as A. For the purpose of this article we will only consider finite or enumerable infinite sets which can be of three types:

enumeration of objects; subsets of vector spaces (typically A ⊆ R n , A being an enumerable subset); subsets of the product space of n attributes X i (A ⊆ n i X i ).

Hence preferences over composed objects such as trees or graphs are not considered here.

The use of binary relations includes the cases where preferences are expressed either as binary comparisons of objects among them (relative comparison) or as binary comparisons of objects to "norms" or "standards" (absolute comparison), see [START_REF] Colorni | What is a decision problem? preliminary statements[END_REF].

Basic references on this issue can be considered: [115,178,243,117,251,169,269,275,229,119,[START_REF] Aleskerov | Utility maximization, choice and preference[END_REF]219]. In this article we adopt the notation introduced in [251]. The usual definitions of (a)symmetric, (ir)reflexive, transitive, Ferrers4 , etc. relations apply. We use a generic preference relation (being just reflexive) denoted to be read "at least as good as", from which we can get an asymmetric part, denoted (and usually called strict preference) and a symmetric one denoted ∼. The symmetric part can be distinguished in indifference (denoted ≈) and incomparability (denoted ), the later being irreflexive (while indifference is reflexive). In Section 7 we will see that also the asymmetric part can be further decomposed in several relations. Besides using an explicit representation (in terms of sets), preferences are usually represented using graphs, directly representing the binary relation, matrices (a non graphical representation of a graph) and, under precise conditions, numerically (so that the ordering resulting on the set A can be expressed using the natural ordering of numbers).

We adopt the term "preference structure" in order to denote collections of preference relations which establish ordered partitions of A and fulfil a number of properties. Such preference structures are named as "weak orders", "interval orders", "P QI interval orders", etc. (for definitions see [219]). Preference structures can be "characterised": showing the necessary and sufficient conditions for which actual preferences upon a set A happen to be one of these structures. Such representation theorems can be of three types:

direct conditions upon the binary relations and their combinations; forbidden configurations of the associated graph structure; specific conditions admitting numerical presentations.

A typical example is the interval order preference structure. The first type of characterisation states that is an interval order iff ∀x, y, z, w ∈ A (x y ∧ y ∼ z ∧ z w) → x w. The second type of characterisation states that is an interval order iff no subgraph on 4 vertices x, y, z, w can just consist of the arcs (x, y), (z, w) and neither (x, w) nor (z, y). The third type of characterisation states that is an interval order iff ∀x, y ∃l, r : A → R l(x) < r(x) : x y ↔ l(x) > r(y).

We already introduced the difference between "relative" and "absolute" comparisons (or preferences). In the first case ⊆ A × A. In the second case ⊆ A × N ∪ N × A where N is the set of norms or standards to which elements of A have to compare in order to make an assessment (for instance when we say that x ∈ A is "good" we assume that x y, y ∈ N being the norm or standard of "good"). Another difference can be established between "direct" and "extended" preferences. The first ones are as usual represented by ⊆ A×A. The second ones are represented by ⊆ 2 A ×2 A . Generally a certain coherence between and is expected when they concern the same set A. In other terms, extended preferences concern the comparison of whole subsets of A among them and not just among single elements (the reader can see [START_REF] Barberà | Ranking Sets of Objects[END_REF]212,211] for the multiple semantics of this type of preferences). A third distinction can be introduced between "first" and "second" order preferences. First order preferences are the usual orderings upon a set A. Second order preferences instead concern any potential order among the orderings of the set A. Consider the case where we have n orderings j upon a set A representing preferences holding under different scenarios (let us call J the set of scenarios; and j ∈ J). The existence of an ordering relation ⊆ J × J represents a second order preference among the orderings obtained for each single scenario. Typical cases are likelihood comparisons (scenario i is likely to occur not less than scenario j) or importance comparisons (the order according to dimension i is at least as important as the order according to dimension j: i j ). The reader should note that in most cases second order preferences are not independent from first order preferences (cfr. [197,[START_REF] Bouyssou | Evaluation and decision models with multiple criteria: Stepping stones for the analyst[END_REF]) and that despite their intuitive appealing they do not constitute "primitive information" for the construction of decision models (see [START_REF] Colorni | What is a decision problem? preliminary statements[END_REF]).

The types of preferences we discussed until now introduce purely ordinal information. In the case such preferences admit a numerical representation (for instance of the type: x y ↔ f (x) > f (y)) this is not unique: all monotonic increasing transformations of the numerical representation are admissible. In other terms we only consider the ordinal information numbers convey. The values (numbers) we can associate to elements of A in order to respect the order induced by some preference model do not admit any "quantitative" interpretation. Should we be interested in more "quantitative" information we need to be able to model "differences of preferences": the difference of preference between x and y is at least as large as the difference of preference between z and w (xy zw). The reader can see more in [START_REF] Bouyssou | Evaluation and decision models with multiple criteria: Stepping stones for the analyst[END_REF] and [START_REF] Bouyssou | Conjoint measurement models for preference relations[END_REF].

Preferences are conveyed through "preference statements": I like x, y is better than z, I do not like w, x combined to y is worse than z combined to w etc. As such they can also be modeled as logical sentences (using some appropriate language). For this purpose we will make reference to some basic logical notation (for a basic reference see [285]). Moreover we draw the attention of the reader to issues related to the semantics of logical inference (model theory) since preferences can and have been used in order to extend reasoning (for an introduction see [START_REF] Doyle | Prospects for preferences[END_REF]).

The article is organized as follows. Section 2 reviews the literature about the use of preferences in extending reasoning models. Section 3 presents the use of preferences in argumentation theory. Section 4 discusses deontic logic, an approach to model preference statements in specially tailored languages. Section 5 discusses the problem of compact (in computational terms) representations of preferences. Section 6 presents the literature about preference learning. Section 7 reviews non conventional preference models, mainly established using logical approaches.

Preferences in reasoning

I have an appointment for the first time with Björn, a Swedish man. When I arrive, I am introduced to a short man with dark hair and dark eyes. He is Björn. My surprise (and maybe yours as well) is due to the fact that the prototypical Swedish person is tall, blond and blue-eyed. Everyday we reason with incomplete information, we assume the world is as normal as possible and jump to conclusions, that may be later given up upon learning new information. Such kind of reasoning is called nonmonotonic, to distinguish it from the traditional deductive inference in which the set of conclusions grows proportionally to the set of available information. So, following a famous syllogisms, from "All men are mortal" and "Socrates is a man", we can derive that "Socrates is mortal" and this conclusion will remain no matter what other information we may add later. In other words, in classical logic, we cannot retract a previously obtained conclusion. If something was derivable at some point, it will still be derivable if we add more premises. This can be expressed formally by the Monotonicity property for the classical consequence relation:

If Γ α, then Γ ∪ β α (1)
where Γ is a finite set of formulas and α and β are formulas of a propositional language L 5 , built up from a finite set P of propositional symbols and the usual connectives (¬, ∧, ∨, →, ↔). An interpretation is a total function P → {0, 1} that assigns a truth value (0 or 1 or, equivalently, false or true) to any propositional letter. An interpretation w is said to be a model of a formula α (denoted by w |= α) if and only if w makes α true in the usual truth functional way. The notion of model captures the semantics of the logical connectives. The syntactic counterpart Γ α means that α is deducible from Γ (where Γ may be empty).

Our everyday reasoning does not satisfy monotonicity. The most famous bird in computer science is Tweety: if I know that Tweety is a bird, I will assume that Tweety flies. However, upon learning that Tweety is a penguin, I will withdraw the previous conclusion. So, we have that Γ α, but Γ ∪ β α, where β is the information that Tweety is a penguin.

As Robert Koons notes [176], defeasible reasoning has been object of philosophical investigations since Aristotle's Topics and Posterior Analytic, but the subject received particular interest from researchers in artificial intelligence during the last forty years. The need to investigate and formalize nonmonotonicity emerged in the 1970s, when artificial intelligence researchers were facing knowledge representation problems [239,200]. To John McCarthy, nonmonotonicity is what characterizes common sense reasoning. The 1980s saw a great development of formalisms to capture nonmonotonic reasoning: circumscription [200,201,189], default logics [240,112], modal nonmonotonic logics [203,204], an epistemic reformulation of McDermott's logic,i.e. autoepistemic logic [210] which was in its turn modified and investigated by Halpern and Moses in [150], and extended logic programming [133,134], a fragment of Reiter's default logic. One may view all major formalisms for nonmonotonic reasoning as different approaches to the problem of identifying belief sets preferred for reasoning, once the world is assumed to be as normal as possible [START_REF] Brewka | Preferences and nonmonotonic reasoning[END_REF].

Yoav Shoham [261,260,262] observed that, in spite of the differences between the various formalisms for nonmonotonic reasoning, it is possible to provide a unifying semantical framework for nonmonotonic logics by generalizing the notion of minimal models introduced in circumscription. 6 Shoham considers any standard logic L, that is, any logic with the usual model-theoretic semantics, such as propositional logic, first-order predicate logic, and modal logic. A preference logic is obtained by associating L with a strict partial preference order on interpretations. If in classical logic the meaning of a formula is the set of models that satisfy it, Shoham shows that nonmonotonic logics are obtained by adding a preference ordering, which allows the logic to focus only on a subset of these interpretations. This captures the idea behind all nonmonotonic logics, that is to assume the world is as normal as possible and use this assumption to identify those models that are 'preferable' in a certain respect. So, when waiting for Björn, I'm justified to expect a blond, tall and blue-eyed man as the prototypical Swedish person is blond, tall and with blue eyes. An inference in the preferential framework can be seen as a selection of those conclusions that hold in all maximally preferred interpretations. Thus, from having that ∆ |= α if α is true in all models of ∆ (as in classical logic), we now have that ∆ |= α if α is true in all preferred models of ∆. Also, from the previous it does not automatically follow that ∆ ∪ β |= α. This is so because the set of preferred models of ∆ ∪ β may not be a subset of the set of preferred models of ∆. Shoham needs to modify the usual notions of satisfaction and entailment to take the ordering on interpretations into account. In [260] he defines a preferred model and preferential entailment as follows:

Definition 1 (Preferred model) An interpretation m preferentially satisfies α (written m |= α) iff m satisfies α and there is no other interpretation m (with m m) such that m satisfies α. Then, m is said to be a preferred model of α.

Definition 2 (Preferential entailment) α preferentially entails β (written α |= β) iff the models of β are a superset of the preferred models of α.

Shoham claims that some nonmonotonic logics are special cases of his general framework while the connections to others is not clear. The system that is closest to Shoham's framework is the family of logics based on circumscription. In general terms, circumscribing a predicate is reducing the individuals that satisfy that predicate in the theory to only those that are necessary in view of the theory. Predicate circumscription assumes that the objects that can be shown to have a certain property by reasoning from certain facts are all the objects that satisfy such given predicate, as in the famous missionaries and cannibals puzzle. 7 . Thus, circumscription means preferring those models of the theory that have minimal extensions of the predicates in question. Circumscription can then be captured by Shoham's preferential model semantics. That is not surprising since, as Shoham himself acknowledges, "the notion of preferred models was implicit in McCarthy's work from the start" [260, p. 237].

Unlike circumscription and the minimal knowledge logic of Halpern and Moses, the relation of Reiter's default logic with Shoham's framework is less clear. Default logics are consistency-based logics as they privilege the syntactic approach in the definition of nonmonotonic inference. A default theory is a

[Circumscription] will allow us to conjecture that no relevant objects exist in certain categories except those whose existence follows from the statement of the problem and common sense knowledge. When we circumscribe the first order logic statement of the problem together with the common sense facts about boats etc., we will be able to conclude that there is no bridge or helicopter. [200, p.30] first-order classical logic theory to which nonmonotonic inference rules are added. These are default rules and have the form:

α : β 1 , ..., β n /γ (2)
where α, β 1 , ..., β n and γ are closed predicate logic formulae. The meaning of Equation 2is the following: if α is known, and if it is consistent to assume β 1 , ..., β n , then infer γ. The crucial notion of default logics is that of extensions (conclusion sets), which are obtained by applying as many default rules as possible without running into an inconsistency. A default theory can have one, several or no extensions. Shoham translates default theories into a modal one and adds a preference relation on the Kripke structures. He then considers examples where the default theory and its translation into a modal theory have a different number of extensions. Introducing a preference criterion does not lead to capture Reiter's definition of extensions. Shoham, then, concludes that more work needs to be done to cast light on that relationship. This was finally achieved by David Makinson [195], who showed that Reiter's default logic cannot be captured by the preferential entailment framework. The reason is that, unlike preferential logics, default logics are not cumulative. 8The variety of nonmonotonic formalisms raised the question of whether it was possible to provide a systematic approach that could classify, distinguish and clarify the relations between each formalism. Dov Gabbay was the first to suggest to study the different consequence relations defined by the different nonmonotonic systems [127]. The step undertaken was not an obvious one, as not all nonmonotonic formalisms assumed a consequence relation [155,156]. In his seminal paper, Gabbay worked on Gentzen-style consequence relations to single out the minimal conditions a nonmonotonic consequence relation ∼ | should satisfy in order to represent a nonmonotonic logic. In addition to Monotonicity (1), a classical consequence relation satisfies other two properties, Reflexivity:

Γ ∪ α α (3)
and Cut:

If Γ α and Γ ∪ α β, then Γ β (4)
Assuming that α and β are formulas, α ∼ | β should be read as "β is a plausible consequence of α". If we substitute ∼ | to the classical consequence relation, we obtain the defeasible versions of Reflexivity (α ∼ | α) and Cut, to which Gabbay added a weak version of Monotonicity (which obviously cannot hold in a nonmonotonic system), called Cautious Monotony:

If Γ ∼ | α and Γ ∼ | β, then Γ ∪ α ∼ | β (5)
Cautious Monotony is the converse of Cut, and it is also called Cumulative Monotony because it says that it is safe to draw consequences and then use them as additional premises.

If Gabbay did not provide a semantics for his properties, five years later, Kraus,Lehmann and Magidor [179] developed Gabbay's and Shoham's works and characterized nonmonotonic consequence relations both proof-theoretically and semantically:

[N]one of the nonmonotonic systems defined so far in the literature [...] may represent all nonmonotonic inference systems that may be defined by preferential models. The framework of preferential models, therefore, has an expressive power that cannot be captured by negation as failure, circumscription, default logic or autoepistemic logic. [...] The main point of this work, therefore, is to characterize the consequence relations that can be defined by models similar to Shoham's in terms of proof-theoretic properties. To this end, Gabbay's conditions have to be augmented. [179, p. 168-169] The weakest logical system introduced by Kraus, Lehmann and Magidor, system C (for cumulative), adds to the properties of Reflexivity, Cut and Cautious Monotonicity proposed by Gabbay, the inference rules of Left Logical Equivalence:

If |= α ↔ β and α ∼ | γ, then β ∼ | γ (6)
and Right Weakening:

If |= α → β and γ ∼ | α, then γ ∼ | β (7)
Among the rules that can be derived in C, we should mention the And rule:

If α ∼ | β and α ∼ | γ, then α ∼ | β ∧ γ (8)
This rule guarantees that plausible consequences can be accumulated via conjunction, and so can be seen as a principle of cumulativity that all basic nonmonotonic logics satisfy. Kraus, Lehmann and Magidor develop a semantic account for C, and provide a representation theorem.

Even though system C satisfies the minimal requirement for a nonmonotonic logic, Kraus, Lehmann and Magidor consider it to be too weak. A stronger and best fitted for nonmonotonic inference systems is system P (for preferential ), which generalizes Shoham's preferential semantics and so it is of particular interest here. This system is equivalent to the one proposed by Ernest Adams in the context of conditional logic [START_REF] Adams | The Logic of Conditionals[END_REF] and to the 'conservative core' of Judea Pearl and Hector Geffner' probabilistic system for default reasoning [222]. The system P consists of all the rules of C with the addition of the Or rule:

If α ∼ | γ and β ∼ | γ, then α ∨ β ∼ | γ (9)
An important derived rule of P is D, originally suggested by Makinson in a personal communication to the authors:

If α ∧ ¬β ∼ | γ and α ∧ β ∼ | γ, then α ∼ | γ (10)
The relevance of D resides in the fact that it allows the principle of reasoning by cases, which is a problem in nonmonotonic reasoning, as Pearl's famous example [220] shows. Suppose that we know that male birds fly and, as a separate default rule, that female birds fly. The default theory in which, in addition to the previous two default rules, we know that Tweety is a bird (without having information about its gender) has as only extension the original information that Tweety is a bird. This is so because the prerequisites of the two rules cannot be verified. This means that the conclusion that Tweety flies is not obtained, even though it is an intuitively desirable conclusion.

The semantics of P is based on the notion of preferential model. Preferential models are cumulative ordered models in which the agent has a preference over worlds (instead of set of worlds, as in Shoham's version). The preference relation is a strict partial order (it was a well-order 9 in Shoham's framework), satisfying the smoothness condition, a technical condition ensuring the existence of a minimal element when we deal with infinite sets of formulas.

Cumulative reasoning systems provide expected results for the inheritance of defaults in taxonomies but cannot support transitive reasoning. Kraus, Lehmann and Magidor show that in the presence of the rules of C, transitivity and monotonicity are equivalent [179, Lemma 3.4]. Hence, frameworks like system P are too general as they do not allow chaining of defaults. In order to overcome such limitation, other approaches introduce preference statements between defaults in order to constrain the possible preference relations. Examples for such approaches are prioritized circumscription [189,201], pointwise circumscription [190,135], and prioritized default logic [START_REF] Boutilier | What is a default priority[END_REF][START_REF] Brewka | Adding priorities and specificity to default logic[END_REF][START_REF] Baader | Priorities on defaults with prerequisites, and their application in treating specificity in terminological default logic[END_REF][START_REF] Delgrande | Compiling reasoning with and about preferences into default logic[END_REF].

Approaches using preferences among default rules avoid also to be too weak in presence of too many conflicting defaults, as it is the case of systems based on preferential models. Preference information can be explicit (the information 9 A well-order relation on a set Q is a total order on Q with the property that every non-empty subset of Q has a minimal element. A total ordering of a finite set is trivially a well-ordering, while this is not the case for infinite sets. Intuitively, such ordering on possible worlds represents the plausibility order that an agent assigns to a world. An agent's current beliefs are the minimal worlds at the bottom of the ranking. The higher a world is, the less plausible it is for the agent.

has to be specified by the knowledge engineer, as in [189,[START_REF] Brewka | Preferred subtheories: An extended logical framework for default reasoning[END_REF]) or implicit. Approaches based on an implicit preference information often give higher priority to more specific rules [274,179,273,131]. But, as observed in [START_REF] Brewka | Reasoning about priorities in default logic[END_REF][START_REF] Brewka | Preferences and nonmonotonic reasoning[END_REF], there may be other reasons than specificity to prefer one rule over another. In legal reasoning, for example, the criteria of recency or authority (for instance, federal law overrides state law) may also be used in case of conflict between laws.

Systems like Brewka's [START_REF] Brewka | Reasoning about priorities in default logic[END_REF] include a flexible treatment of preferences over defaults (unlike in the explicit preference ordering approaches, where the preference is fixed) and, at the same time, by representing the priority information within the logical language, handle other criteria than specificity. Starting from [START_REF] Brewka | Adding priorities and specificity to default logic[END_REF] which added a partial order on defaults to Reiter's default logic [240], the idea is to extend the language to make reasoning about default priorities possible (via the naming of default rules), to generate default extensions and, finally, to keep only those extensions compatible with the priority information.

Example 1 [START_REF] Brewka | Reasoning about priorities in default logic[END_REF] Suppose that we have the following default rules and facts:

d 1 : bird → f lies d 2 : penguin → ¬f lies penguin bird
Reither's default theory would give two extensions, namely E 1 = T h{(penguin, bird, flies)} and E 2 = T h({penguin, bird, ¬f lies}). 10 Suppose now that we also have the information that d 2 has priority over d 1 (denoted as d 2 ≺ d 1 ). Clearly, only the second extension is compatible with this information. The system proposed in [START_REF] Brewka | Reasoning about priorities in default logic[END_REF] has a mechanism that ensures that E 1 is eliminated.

Delgrande and Schaub [START_REF] Delgrande | Compiling reasoning with and about preferences into default logic[END_REF][START_REF] Delgrande | Expressing preferences in default logic[END_REF] also consider a default theory where preference information is part of the theory and preferences among default rules can be part of a default rule. The novelty is that they show that such a generalised default theory can be translated into a standard default theory without preferences, but in which defaults are applied in the appropriate order. This means that all default logic theorem provers can be used for the prioritised version.

Frameworks for preferential reasoning have not been limited to the propositional context [179,187]. Among the proposals to capture defeasible reasoning in logics other than propositional one, we recall Lehmann and Magidor' extension to preferential predicate logics [186], defeasible deontic logics [214] (cf. Section 4), preferential extensions of description logics [START_REF] Britz | Semantic preferential subsumption[END_REF]138,[START_REF] Casini | Rational closure for defeasible description logics[END_REF], and semantics for preferential reasoning in modal logics [START_REF] Britz | Preferential Reasoning for Modal Logics[END_REF].

After this short excursus, we may ask ourselves whether a universal logic of nonmonotonic reasoning is possible. Doyle and Wellman [START_REF] Doyle | Impediments to universal preference-based default theories[END_REF] answered negatively to this question. Each formalism for nonmonotonic reasoning can be seen as a special theory of preferential or rational inference (i.e. how to select the maximally preferred states). If one could combine the different rational choices made by the several nonmonotonic formalisms into a single choice, then one could claim that a universal logic of nonmonotonic reasoning exists. Yet, by adapting the framework for the aggregation of individual preferences of social choice theory, they show that a negative result similar to Arrow's impossibility theorem [START_REF] Arrow | Social choice and individual values[END_REF] can be obtained for preferential nonmonotonic logics.

Preferences in argumentation theory

An argumentation system contains alternative arguments for or against some conclusions. Argument-based systems were mostly developed within artificial intelligence to study defeasible reasoning [230,231,192,213,233,[START_REF] Bondarenko | An assumption-based framework for nonmonotonic reasoning[END_REF]. 11 The nonmonotonicity lies in the fact that an argument may be defeated by another argument, which in turns may support the opposite claim. Formal argumentation can thus be seen as a generalized way of nonmonotonic reasoning [START_REF] Bondarenko | An abstract, argumentationtheoretic approach to default reasoning[END_REF], and indeed several nonmonotonic formalisms including Nute's Defeasible Logic [144], Simari's DeLP [129], logic programming Default Logic [107] have been shown to conform to the standard semantics of argumentation theory.

Abstract argumentation theory studies the positions that a rational agent can take in presence of a given set of arguments, where some arguments are in conflict with others. Arguments and the conflict relations are considered as generally as possible. Arguments are abstract entities, i.e. their internal structure is disregarded. Likewise, the conflict relation is left unspecified. If two arguments are in conflict, this roughly means that they cannot both hold. Abstracting away from the internal structure of the arguments and from the precise meaning of the conflict relation allows us to study how to reason in presence of a conflicting set of arguments in the most general way. Some approaches assume a particular logic [235] while others do not specify the underlying logic [START_REF] Bondarenko | An assumption-based framework for nonmonotonic reasoning[END_REF]107].

Argumentation theory is central within artificial intelligence [START_REF] Bench-Capon | Argumentation in artificial intelligence[END_REF] as it provides a logic-based formalism for the treatment of defeasible reasoning and conflict resolution [263,[START_REF] Amgoud | A formal framework for handling conflicting desires[END_REF]171,208,[START_REF] Besnard | Elements of Argumentation[END_REF], negotiation [267,180,[START_REF] Amgoud | A unified and general framework for argumentation-based negotiation[END_REF], and argumentationbased dialogues [START_REF] Amgoud | Modeling dialogues using argumentation[END_REF]234,175].

An argumentation framework is simply a set of arguments and a binary relation among them. Dung (who can be considered to be the father of abstract argumentation) identified the binary relation with an attack relation [107]. Given an argumentation framework, the aim of argumentation theory is to identify and characterize the sets of arguments (extensions) that can reasonably survive the conflicts expressed in the framework. In general, given an argumentation framework, there are several possible extensions [107].

In order to simplify the discussion, we only consider finite argumentation frameworks. Different semantics have been proposed to define the acceptability of arguments in an argumentation framework. In Dung's original extension approach [107], an extension is a subset of Ar that represents the set of arguments that can be accepted. Dung's semantics are based on the notion of conflict-freeness, namely a set should not be self-contradictory nor include arguments that attack each other [107]. This ensures that no extension will support contradictory conclusions.

Definition 4 (Conflict-free / defence) Let (Ar , R) be an argumentation framework. The set S ⊆ Ar is conflict-free if and only if there are no A, B ∈ S such that (A, B) ∈ R.

We also say that S defends A (or, the argument A is acceptable with respect to S) if, ∀B ∈ Ar such that (B, A) ∈ R, ∃C ∈ S such that (C, B) ∈ R.

As we have seen, conflict-freeness is the minimal requirement for an extension. The most common acceptability semantics used in the literature are the following:

Definition 5 (Acceptability semantics) Let AF := (Ar , R) be an argumentation framework and set S ⊆ Ar .

-S is an admissible extension if and only if it is conflict-free and defends all its elements. -S is a complete extension if and only if it is conflict-free and contains precisely all the elements it defends, i.e., S = {A | S defends A}. -S is a grounded extension if and only if S is the smallest (w.r.t. set inclusion) complete extension of AF . -S is a preferred extension if and only if S is maximal (w.r.t. set inclusion) among admissible extensions of AF .

-S is a stable extension if and only if S is conflict-free and ∀B / ∈ S, ∃A ∈ S such that (A, B) ∈ R.

It is known that for every argumentation framework, there exists at least one admissible set (the empty set), exactly one grounded extension, one or more complete extensions, one or more preferred extensions, and zero or more stable extensions.

The admissible extensions of the argumentation framework in Figure 1 are ∅, {A}, {B}{A, D} and {B, D}. The preferred and stable extensions are {A, D} and {B, D}, the complete extensions are ∅, {A, D} and {B, D} and, finally, the grounded extension is ∅.

Though the generality of the framework we have briefly reviewed is part of its attractiveness, it has been argued that arguments do not have the same strengths [263,[START_REF] Benferhat | Argumentative inference in uncertain and inconsistent knowledge bases[END_REF][START_REF] Cayrol | Management of preferences in assumption-based reasoning[END_REF]. Preferences can be added and taken into account in order to evaluate arguments [START_REF] Amgoud | Comparing arguments using preference orderings for argument-based reasoning[END_REF]235,[START_REF] Amgoud | Integrating preference orderings into argument-based reasoning[END_REF][START_REF] Amgoud | Making decisions through preference-based argumentation[END_REF]209]. Consider the following example due to Amgoud and Cayrol.

Example 2 [START_REF] Amgoud | A reasoning model based on the production of acceptable arguments[END_REF] Let (Ar , R) be an argumentation framework with Ar = {A, B, C} and R = {(A, B), (B, C)}. The set of acceptable arguments is {A, C}. However, suppose that argument B is preferred to A and to C. How can the preference over arguments and the attack relation be combined when deciding which arguments to accept? One natural way is to say that, since B is preferred to A, it can defend itself from the attack of A. This would lead to accept B and reject C.

Adding preference relations allows for more expressivity. Not only we can express that some arguments are in conflict, but also that some arguments are preferable to others, for example, because they express more probable beliefs or promote more important values [START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF]. Dung's framework has then been extended by introducing preference relations into argumentation systems [START_REF] Amgoud | Comparing arguments using preference orderings for argument-based reasoning[END_REF]235,[START_REF] Amgoud | Integrating preference orderings into argument-based reasoning[END_REF][START_REF] Amgoud | On the acceptability of arguments in preference-based argumentation framework[END_REF]209]. Simari and Loui [263] introduced preferences over arguments, and [START_REF] Benferhat | Argumentative inference in uncertain and inconsistent knowledge bases[END_REF] considered arguments from prioritised beliefs in inconsistent knowledge bases. A natural domain of application of argument-based systems has been the modelling of legal disagreement [232,257,143]. Indeed, one of the first extensions of Dung's argumentation framework was inspired by legal reasoning [235]. In order to increase the potential for implementation and following [106], arguments were expressed in a logic-programming language and their conflicts decided with the help of (defeasible) priorities over rules.

A more direct extension of Dung's framework is the one proposed in [START_REF] Amgoud | A reasoning model based on the production of acceptable arguments[END_REF], where a preference ordering enriches Dung's framework. In the literature on preference-based argumentation, the attack relation in a preference-based argumentation framework is called defeat, and is denoted by Def .

Definition 6 (Preference-based argumentation framework (PAF ))

A preference-based argumentation framework (PAF ) is a triplet (Ar , Def , ), where Ar is a set of arguments, Def is the defeat binary relation on Ar , and is a (partial or total) preorder defined on Ar × Ar .

Thus, A B means that argument A is at least as preferred as B and the relation is the strict counterpart of . As illustrated in Example 2, one idea to combine preference and attack relations is that if an argument B is preferred to its attacker A, then A's attack against B is not successful and B is accepted. Informally, the idea in [START_REF] Amgoud | A reasoning model based on the production of acceptable arguments[END_REF] is to remove those attacks that conflict with preferences and calculate Dung's classical semantics on the resulting argumentation framework. So, what is the relation between the two frameworks? Kaci and van der Torre [166] show that a preference-based argumentation framework can represent an argumentation framework: Definition 7 (PAF representing an AF ) A preference-based argumentation framework (Ar , Def , ) represents an argumentation framework (Ar , R) iff ∀A, B ∈ Ar , it is the case that (A, B) ∈ R iff (A, B) ∈ Def and it is not the case that B A.

It should be easy to see that each preference-based argumentation framework represents one argumentation framework, whereas each argumentation framework can be represented by various preference-based argumentation frameworks [166].

Inspired by Perelman's work on persuasion [225,224], Bench-Capon [START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF] extends standard argumentation framework to take into account values promoted by arguments and defines value-based argumentation frameworks (VAF ). The idea is that in practical reasoning, two individuals may agree on the fact that an argument attacks another argument, but may disagree on whether that attack is successful because the two arguments promote different values and the two individuals disagree on the preference over those values. So, preferences over arguments are determined by the values those arguments support, like human life, world security and good world relations can be values promoted by some arguments in a political debate over whether invading Iraq or not [START_REF] Atkinson | Persuasive political argument[END_REF]. Dung's framework is thus enriched by adding a non-empty set of values V, a function val that assigns a value to each argument, and a partial order > over values. The idea is that an argument A defeats (successfully attacks) an argument B iff (A, B) ∈ R and the value promoted by B is not more important than the value promoted by A (i.e. not val(B) > val(A)).

Kaci and van der Torre [166] extend Bench-Capon's value-based argumentation frameworks in two directions. They take into account the possibility that arguments support multiple values, and consider various types of preferences over values. In [START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF], if values v 1 is preferred to value v 2 , then each argument supporting v 1 is preferred to each argument supporting v 2 . Kaci and van der Torre claim that real-world situations are more complex and consider two additional preferences: that v 1 is preferred to value v 2 according to a first preference relation if and only if at least one argument supporting v 1 is preferred to each argument supporting v 2 , and that v 1 is preferred to value v 2 according to a second preference relation if and only if each argument supporting v 1 is preferred to at least one argument supporting v 2 . Similarly as for the relation between PAF and AF , Kaci and van der Torre show that a VAF represents a PAF if and only if, for any two arguments A, B, it is the case that A B if and only if val(A) > val(B) or val(A) = val(B).

Instead of having a pre-specified preference relation among arguments or values, one may consider the case in which arguments can express preferences between other arguments. This is the route explored by Modgil with the introduction of extended argumentation framework (EAF) [209]. Suppose, for example, that the BBC and the CNN disagree on today's weather forecast in London and that argument C says that BBC are more trustworthy than CNN. Argument C is expressing a preference for the argument that today it will be dry in London since BBC said so (argument A) over argument B which claims the opposite as CNN forecasted a rainy day. Dung's argumentation framework is then extended by adding a second attack relation D to Ar and the standard binary attack relation R. D ranges from an argument to an element of R: if A attacks (B, C) (denoted by (A, (B, C))), then A claims that C is preferred to B. In an extended argumentation framework, the success of an attack is relative to the set of arguments S one is currently considering. Thus, the notion of defeat is parametrised w.r.t. S:

let S ⊆ Ar , A is said to defeat S B 12 iff (A, B) ∈ R and C ∈ S such that (C, (A, B)) ∈ D.
In [209] and [START_REF] Amgoud | Generalizing stable semantics by preferences[END_REF] it was observed that ignoring those attacks where the attacked argument is stronger than the attacker does not always give intuitive results. It can happen that the resulting extension violates the basic condition imposed on acceptability semantics, namely the conflict-freeness of extensions. This is problematic as, in turns, it may lead to violate the rationality postulates put forward in [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF].

Example 3 Suppose that an argumentation framework contains only two arguments A and B, and that A attacks B. Assume also that B A. Preferencebased argumentation frameworks run into troubles because, since B is preferred to A, the attack against B fails, i.e. no defeat relation holds between the two arguments. The problem is that, by removing an attack, we remove an important piece of information from the graph, namely that there is a conflict between two arguments. By doing so, the two arguments may end up in the same acceptable extension, violating the basic requirement of conflict-freeness that grounds the idea of Dung's extensions as representing coherent positions.

Amgoud and Vesic [START_REF] Amgoud | Generalizing stable semantics by preferences[END_REF][START_REF] Amgoud | A new approach for preference-based argumentation frameworks[END_REF] propose a new preference-based argumentation framework that guarantees conflict-free extensions to deal with the above problem. However, according to [167,164,165], the source of the problem concerning removing attacks resides in a misunderstanding of Dung's framework. The abstract nature of Dung's framework imposes a careful instantiation of it and, in particular, a suitable choice of the appropriate defeat relation. A preferencebased argumentation framework with a symmetric conflict relation guarantees to prevent the undesirable result [164]. The preference relation is then used to decide the direction of the defeat relation between two arguments.

Deontic logics

The Swedish man we encountered in Section 2 is in fact a serial killer and my life is now in danger. I know that nobody should kill. However, in order to save my own life, I have to consider the possibility of killing Björn. If I have the choice between a bloody murder and a bloodless one, I should go for the second option. Philosophers, logicians and computer scientists have reasoned about such a situation, which is one of the many paradoxes (or puzzles) arising in deontic logic, a logic to reason about concepts like obligations and permissions. The gentle murderer paradox says that one should not kill but, if one does, he has the obligation to kill gently [124]. The paradox arises from the fact that in one of the most familiar systems of deontic logic, the so-called Standard Deontic Logic (SDL), from those premises one can derive that it is obligatory to kill tout court, a hardly defendable conclusion.

Deontic logic studies concepts that have a clear practical relevance for law, ethics, human and artificial institutions, security systems etc. But, as it happened for modal logic (which strongly influenced deontic logic [205] 13 ), contributions have also been made on a more theoretical level. Even though the first natural applications were to formalise legal reasoning [265], deontic logic has been increasingly used in computer applications. As observed by Thorne McCarty [202], one of the primary applications of deontic logic is to detect a violation of an obligation and to trigger the appropriate sanction to such violation.

The use of deontic logic is especially useful as a knowledge representation language in all those situations in which a system designer wants to take into account the violation of some obligations and the appropriate action [161,162]. The study of logical systems of deontic logic, the formal analysis of normative systems, the formal representation of legal knowledge, the specification of aspects of norm-governed multi-agent systems and autonomous agents, as well as normative aspects of protocols for communication, negotiation and multi-agent decision making are all among the topics of DEON, a biennal international conference on deontic logic in computer science. Recently, an extension of multi-agent systems with concepts traditionally studied in deontic logic gave rise to a new area called Normative Multi-agent Systems [START_REF] Boella | Introduction to normative multiagent systems[END_REF] with the satellite NorMAS workshops 14 .

The beginning of deontic logic can be traced back to the Thirties, when the Danish philosopher Jørgensen discussed the logical character of imperatives [163]: 13 An exception was the work by Ernst Mally [196], an early pioneer of deontic logic and the first one to have used the term Deontik. His work was not influenced by modal logic but his impact on the discipline was undermined by technical problems [122]. 14 According to the definition of the first workshop on normative multiagent systems in 2005, "Normative Multi-Agent Systems are multi-agent systems with normative systems in which agents can decide whether to follow the explicitly represented norms, and the normative systems specify how and in which extent the agents can modify the norms" [START_REF] Boella | Introduction to normative multiagent systems[END_REF].

[A]ccording to a generally accepted definition of logical inference only sentences which are capable of being true or false can function as premises or conclusions in an inference; nevertheless it seems evident that a conclusion in the imperative mood may be drawn from two premises one of which or both of which are in the imperative mood. [163, p. 290] The point is that imperatives, legal statutes, moral standards etc. are usually not viewed as being true or false. Expressions like "Mark, leave the room!" command a specific behaviour and are not descriptive. Being nondescriptive, they cannot be termed true or false. Thus, they cannot be premise or conclusion of a logical inference. The Jørgensen's dilemma expresses the fact that, though there certainly exists a logical study of normative concepts, it seems difficult to have a logic of normative concepts. The logic of imperatives is tightly connected to deontic logic [151], and some authors claim they are essentially the same discipline.

The discussion of whether norms have truth values continued, but the first formal system of deontic logic was given only in 1951 by the Finnish philosopher Georg Henrik von Wright [293,292]. It is consensus to fix in von Wright's work the beginning of deontic logic. Subsequent deontic logic systems built on his work, though essentially any aspect of von Wright's logic has been criticised and von Wright himself proposed several systems to overcome difficulties he encountered.

Many deontic logic systems have been proposed in the literature, like Standard Deontic Logic (SDL), von Wright's Old System (OS) [292], Chellas' Minimal Deontic Logic (MDL) [START_REF] Chellas | Conditional obligation[END_REF], Hansson's Preference-based Deontic Logic (PDL) [152] and variants of these logics. By taking obligation to be the primary concept and represent it by the operator O (so Oα reads as "It is obligatory that α") 15 , van der Torre classified those logics on the basis of the following three properties [271]:

(Weakening) O(α ∧ β) → Oα (And) (Oα ∧ Oβ) → O(α ∧ β) (Violations) wff: α ∧ O¬α
The first two properties should be clear. The third property gives the wellformed formulas (wff) to express violations in the language, by saying that it may happen that ¬α was obligatory and nevertheless we have that α is the case. So, if a certain logic (like OS) does not have Violations, it means that it lacks the possibility to express violations in its language. SDL satisfies all three properties. MDL satisfies Weakening and Violations, and PDL is the only system in which Weakening does not hold 16 , but it satisfies And and Violations.

We give here the syntax and the semantic of the most cited of such systems, that is Standard Deontic Logic (SDL), a monadic deontic logic that builds upon propositional logic.

Definition 8 (SDL) Let L be the language built upon a denumerable set P of propositional variables, the usual connectives ¬ and → and the operator O. Axioms of SDL are the following:

(T aut) All tautologies of L. (K) O(α → β) → (Oα → Oβ) (D) ¬O⊥
SDL is closed under the following rules of inference:

(Modus Ponens) If α and α → β, then β (Necessitation) If α then Oα
To the reader familiar with modal logic, it will be clear that SDL is just the normal modal logic KD with a reinterpretation of the symbol as O for obligation. Since its birth deontic logic was seen as a branch of modal logic, thanks to the similarities between modal notions of necessity and possibility and deontic notions of obligations and permissions. Dissimilarities between the two fields were, however, noticed by von Wright [295].

The semantics of SDL is a possible worlds (Kripke) semantics. A particular class of obligations that was highly relevant for the development of formal deontic logic systems are contrary-to-duty ones. A contraryto-duty obligation expresses what one should do when obligations have been violated, like Gabriella's violation of the obligation to abstain from killing or, to take a less prosaic example, what Saint Paul said in the first letter to the Corinthians:

It is good for a man not to touch a woman. But if they cannot contain, let them marry: for it is better to marry than to burn. (Cited in [287].) Many of the deontic logic paradoxes are related to contrary-to-duty paradoxes. Probably the most famous one is the gentle murderer paradox [124], which we informally encountered at the beginning of this section. 2) and ( 3) we obtain O(k ∧ g), thus Ok by Weakening. Our theory is thus inconsistent as it contains both Ok and O¬k.

As we have seen in Section 2, default logic formalises the reasoning based on default assumptions. The world is assumed as normal as possible (Swedish men are assumed to be tall, blond and with blue eyes, birds are assumed to be able to fly etc.) unless evidence to the contrary. If this is the case, previously obtained conclusions may be not any longer derivable. The idea behind Shoham's proposal was to add preferences to nonmonotonic logics, where preferences represent different degrees of normality. In the most normal case, Swedish men are tall and blond.

Deontic logic can also be a preference-based logic. As preferences served to represent and treat exceptions in a preference-based nonmonotonic logic, so they can be used to represent and treat violations in a preference-based deontic logic. In other words, similar to degrees of normality in preferencebased default logics, preferences can be seen as degrees of ideality in a logic for normative reasoning. Indeed, many preference-based deontic logics are default logics (see also Nute's collection on defeasible deontic logic [214]).

This was the way taken by Bengt Hansson to treat paradoxes in deontic logic. He realised that paradoxes arose because the semantics used in deontic logic was too rigid [151]. As seen in Definition 9, the truth condition for deontic statements is defined by considering only the actual world and the worlds that are accessible from the actual one (in which everything that is obligatory in the actual world holds):

In SDL, norms are assumed to refer exclusively to what obtains in the best possible alternatives. [. . . ] In SDL, only what is compatible with the best is not wrong. [152, p. 83] So, for example, the gentle murderer leads to a paradox because we obtain two conflicting obligations, Ok and O¬k. No world can possibly satisfy both. The solution prospected by Hansson was to move from the "best possible alternatives" to a hierarchy of alternatives by defining a preference ordering over alternative worlds. Depending on the properties of , different logics can be obtained. Hansson, for example, at the beginning assumed only reflexivity though in general, the preference ordering over the worlds is any partial preorder. The gentle murderer paradox can be solved by distinguishing accessible worlds in which ¬k is true (and k is false) and worlds in which k is true (and ¬k is false) and say that the first kind of worlds are better than the second one.

A dyadic deontic logic (or logic of conditional obligation) is a logic in which an obligation is relative to some circumstances. An obligation O(α|β) means that "α is obligatory, if β is the case". Clearly, monadic obligations of type Oα are a special kind of dyadic obligations where the antecedent is a tautology O(α| ).

Hansson gave a semantics of dyadic obligations in which an "ideality ordering" over possible worlds is added [151]. When a preference relation over worlds is added, the intuition is that O(α|β) means that worlds in which α ∧ β is true are preferred to those in which ¬α ∧ β is true. Dyadic deontic logics with a preference ordering were also proposed by Danielsson [START_REF] Danielsson | Preference and obligation[END_REF], though it is Hansson's work that is the most cited since it is the most easily accessible [START_REF] Åqvist | Deontic logic[END_REF].

Properties like Weakening and And can be reformulated for dyadic logics:

(Weakening) O(α 1 ∧ α 2 |β) → O(α 1 |β) (And) O(α 1 |β) ∧ O(α 2 |β) → O(α 1 ∧ α 2 |β)
Deontic logics in a dyadic form were previously introduced by von Wright [292] and Rescher [241]. Among the several dyadic logics that have been proposed in the literature we recall those by Chellas [START_REF] Chellas | Conditional obligation[END_REF], Alchourrón [START_REF] Alchourrón | Philosophical foundations of deontic logic and the logic of defeasible conditionals[END_REF], Lewis [188] (an extension of Hansson's [151]), Føllesdal and Hilpinen [122], and van Fraassen [286]. One difference is that, unlike [188,151,122,286], the logics of [START_REF] Chellas | Conditional obligation[END_REF][START_REF] Alchourrón | Philosophical foundations of deontic logic and the logic of defeasible conditionals[END_REF] satisfy the property called strengthening of the antecedent:

(Strengthening of the Antecedent) O(α|β 1 ) → O(α|β 1 ∧ β 2 )
van der Torre [271] shows that logics that satisfy strengthening of the antecedent cannot formalise contrary-to-duty reasoning because strengthening of the antecedent is one of the key properties that lead to contrary-toduty paradoxes. On the other hand, logics that do not have strengthening of the antecedent can formalise the contrary-to-duty paradoxes. However, Alchourrón [START_REF] Alchourrón | Philosophical foundations of deontic logic and the logic of defeasible conditionals[END_REF], Castañeda [START_REF] Castañeda | The paradoxes of deontic logic: The simplest solution to all of them in one fell swoop[END_REF], and Tan and van der Torre [268] criticise the lack of strengthening of the antecedent as -in the words of Castañeda -it is a "negative solution that looks like overkill" (though such criticism is not undisputed -see, for example, van Benthem et al [34]). A solution to this problem proposed by van der Torre is a two-phase deontic logic [271]. The idea is to have a logic that allows the combination of two desirable properties for a dyadic deontic logic, that is strengthening of the antecedent and weakening of the consequent, by forbidding the application of strengthening of the antecedent after weakening of the consequent, a sequence that leads to paradoxical results.

Compact representations of preferences

As already mentioned in the introduction, preferences are traditionally viewed as binary relations applied to a set A, such that ⊆ A × A. If the size of A is reasonable then an explicit representation of is feasible both from a cognitive (human agent) and a computational (artificial agent) point of view.

Consider now the case of choosing a digital camera out of an e-commerce site. Digital cameras are described by tens of features (each with different possible values: size of the memory, type of the lens, batteries, brand, price, etc.). If we denote by X i the values of each possible attribute, the whole space of possible digital cameras is a large subset of i X i . Considering only binary attributes it is easy to see that the size of A rapidly approaches 2 n , n being the number of attributes. There is no way to handle such a set for several different reasons:

a human agent cannot compare the 2 n potential options in order to compile his preferences; there is no space in the memory of many artificial agents allowing to store such a set; supposing that we manage to get the whole set of comparisons and that we managed to store it somewhere, there is no way to compute something operational out of it, such as verifying if it is at least partially ordered and (if this is the case) identifying the maximal elements of A (Max(A)={x : y ∈ A : y x}).

Problems of the same type arise when the set A on which preferences are expected to apply results from other combinatorial manipulations such as being constructed as the power set of some set Ω of elementary actions (A ⊆ 2 Ω ). It is the case when a "portfolio" of actions (or candidates) needs to be chosen out of a list of alternatives.

An "obvious" solution to this problem could be to use some numerical representation for the different attributes and/or elementary actions and then aggregate them appropriately. In a typical case, each attribute is associated to a value function (u i ) and then these are summed to an overall value (U ). However, there are several problems:

1. Suppose we have i ⊆ X i × X i . The conditions under which ∃u i : X i → R such that x i y ⇔ u i (x) ≥ u i (y) are restrictive ( i needs to be a weak order) and do not hold a priori (see also [START_REF] Bouyssou | Evaluation and decision models: a critical perspective[END_REF]). 2. Suppose that the conditions for having such value functions are satisfied.

The conditions under which ∃U : A → R such that U = i u i represents the preference over A are even more restrictive:

the u i need to be more than ordinal measures (to be more precise: they need to be interval measures such that differences of preferences can be explicitly considered); the u i need to be commensurable among them (to be more precise: the differences of preferences along one attribute need to be comparable to the differences of preferences along any other attribute, such comparison establishing the trade-offs among the attributes); the i (and thus u i ) need to be preferentially independent among them (to be more precise: x i y needs to hold independently from how x and y compare along all other attributes and this condition should hold among any subset of attributes). Once again such conditions are not naturally met (see [START_REF] Bouyssou | Evaluation and decision models: a critical perspective[END_REF]).

Generally speaking we are looking how to compare vectors of the i X i space among them (and then possibly find an appropriate way to "measure" such vectors in some appropriate value scale). Under a conjoint measurement theory perspective, given two vectors (from the vector space i X i )

x 1 = x 1 1 • • • x n 1 and x 2 = x 1 2 • • • x n 2
, the most general model representing a global preference should be

x 1 1 • • • x n 1 x 1 2 • • • x n 2 iff ∃F : X 2n i → R such that F (x 1 1 • • • x n 1 , x 1 2 • • • x n 2 ) ≥ 0
The function F is characterisable in many different ways: decomposable, transitive, skew symmetric, additive etc. (for more details see [178,243,[START_REF] Bouyssou | Preferences for multiattributed alternatives: Traces, dominance, and numerical representations[END_REF][START_REF] Bouyssou | Following the traces: -an introduction to conjoint measurement without transitivity and additivity[END_REF][START_REF] Bouyssou | Conjoint measurement tools for MCDM[END_REF][START_REF] Bouyssou | Evaluation and decision models with multiple criteria: Stepping stones for the analyst[END_REF]).

However, this is of little practical interest since it does not tell us how to handle the cases where the simple additive model does not hold (as in the case of preferential dependencies). The basic idea, proposed in the recent years has been to develop appropriate languages for compact representations (see [184]). Before presenting some of such languages we should mention that these are classified in the literature according to a number of criteria:

expressiveness; concision; cognitive relevance; computational complexity.

For a discussion about these issues the reader can see [START_REF] Chevaleyre | Expressive power of weighted propositional formulas for cardinal preference modeling[END_REF]199,301].

Compact representations of preference models have been considered mainly in order to take into account preferential dependencies and conditioning which impede the use of simple additive conjoint measurement functions. The two main languages developed for this purpose are CP-nets (accounting for conditional preference statements) and GAI-networks (accounting for generalised additivity). We mention (without discussing it) the use of lexicographic preferences, a specific case of totally ordered attributes space studied in [116] and recently used for both aggregation and learning algorithms facing conditional preferences (see [302], [185]). We will also briefly discuss the approach consisting in directly modelling preference statements as logical sentences. We will not discuss the problem of choosing a "portfolio" of actions out of a set of alternatives, since there is no specific language developed for this purpose (although the reader can have a look at [183]) . The literature rather focusses on how to "extend" preferences expressed upon a set Ω to the power set 2 Ω and how to handle efficiently the optimisation problems deriving from such an operation. The reader can see more details in [START_REF] Barberà | Ranking Sets of Objects[END_REF]212,255,283].

CP-nets CP-nets have been conceived in order to allow the representation (and efficient computation) of situations where somebody wants to claim that xw yw , but yz xz (the preference between x and y depends on what comes together to x and to y). A typical example concerns choosing between red and white wine: I prefer red wine to white wine if we eat meat, but I prefer white wine to red wine if we eat fish. We can distinguish between:

unconditional "Ceteris Paribus" (CP) preferences along some of the attributes of X. For instance, if we say that x 3 1 (the first value of attribute 3) is preferred to x 3 2 (the second possible value for the same attribute) all other things being the same (ceteris paribus), expressed as x 3 1 CP x 3 2 , we can deduce (assuming that there are three attributes in our domain) that, for example

x 1 1 x 2 1 x 3 1 x 1 1 x 2 1 x 3 2
, and in general that

x 1 i x 2 j x 3 1 x 1 i x 2 j x 3 2
with i, j being the indices associated to X i and X j . conditional preferences, where preferences along a certain attribute (let us say attribute k) are conditioned by preferences expressed on another attribute (let us say attribute l).

Technically speaking, a CP-net is represented through a directed graph among the variables (attributes), where the maximal elements of the graph are the ones where preferences are unconditioned. It is easy to see that when the graph is acyclic, computing within a CP-net is very efficient (while it is not the case otherwise). The reader can see more about CP-nets in [START_REF] Boutilier | Reasoning with conditional ceteris paribus preference statements[END_REF][START_REF] Brafman | Graphically structured value-function compilation[END_REF][START_REF] Domshlak | CP-nets -reasoning and consistency testing[END_REF]299]. CP-nets have been extended to TCP-nets [START_REF] Brafman | Introducing variable importance tradeoffs into CP-Nets[END_REF][START_REF] Brafman | Extended semantics and optimization algorithms for CP-networks[END_REF] in order to take into account the "relative importance" that some attributes may have with respect to other ones and from that to more general CP-theories (see [300]), and to UCP-nets (see [START_REF] Boutilier | UCP-networks: A directed graphical representation of conditional utilities[END_REF]) in order to consider conditional utilities. The case of multiple agents has been discussed in [248]. CP-nets have been applied in several configuration problems as well as in planning.

GAI-networks

The intuition behind additive utility (such that U (x) = j u j (x j )) is that the contribution of each attribute to the overall utility is independent from all other attributes (and subsets of attributes). However, decomposable and additive conjoint measurement functions hold only under very strong conditions. Under less restrictive conditions [START_REF] Bacchus | Graphical models for preference and utility[END_REF]115]) we can instead have utility functions based on a "generalised additive independence" such that:

U (x) = k i=1 u i (x Ci )
where:

-C i are subsets of the set of attributes X (and there are k of these factors);

-D Ci = j∈Ci X j ; -∃u i : D Ci → R.
The general idea within such functions is to measure both the utility contribution of each single attribute and the utility contribution of each subset of attributes (as if they were single ones). The reason for this is due to the positive or negative "synergies" two or more attributes may present: for instance having white wine (first attribute) with fish (second attribute) has a positive synergy (which implies giving a positive reward in the function), while having red wine (first attribute) with fish (second attribute) has a negative synergy (which implies giving a penalisation in the function). Such generalised additivity includes many of the existing utility aggregation procedures (additive, k-additive etc.). However, what is important with such functions is the possibility to represent them in suitable graphical models, named GAI networks allowing for nice compact representations and efficient computation even for rather complex dependencies. The reader can see more details in [105,141,142].

Logical representations

The basic idea here is to work directly on a set of sentences (which express preferences, values, desires and their opposite) instead of the binary relations. We can distinguish two approaches.

The first one consists in associating to each sentence ϕ ∈ L (where L is a set of preferential sentences) a numerical value representing the contribution of ϕ (when logically satisfied) to the overall utility of the agent owing L. Such values can also represent priorities in satisfying sentences or "distances" from some "target state of the agent" (see for instance [START_REF] Benferhat | Argumentative inference in uncertain and inconsistent knowledge bases[END_REF][START_REF] Brewka | A rank-based description language for qualitative preferences[END_REF]182,221]). It is easy to show that in most cases such an approach boils down to use possibility theory (and possibility logic) as representation language (see for instance [START_REF] Benferhat | Towards a possibilistic logic handling of preferences[END_REF]108]). A slightly different approach has been developed starting from a Constraint Satisfaction Programming perspective: the idea here is to see preference statements as compact constraints and use the power of constraint programming in order to solve preference aggregation and recommendation problems. The reader can see more in [246,249,250,132]. For other approaches the reader can also see [START_REF] Brewka | Answer set optimization[END_REF][START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF].

The second approach consists in establishing a "logic of preferences", an idea going back to the 60s [294,296]. We have discussed several aspects of this approach in Section 4. We just recall here that the principle consists in elaborating a language allowing to express sentences of the type ϕ∧¬ψ£¬ϕ∧ψ: it is preferred a situation where ϕ holds and ψ does not hold to one where ϕ does not hold and ψ holds. For more details the reader can see [START_REF] Bienvenu | From preference logics to preference languages, and back[END_REF]168,284].

Analytics of preferences: learning and eliciting

We now take the point of view of Björn, who has invited Gabriella for dinner. He needs to decide the menu (consisting of a first course, a second course, a beverage and a dessert) for the evening's dinner based on his very limited information about her preferences. In addition, he might be able to use stereotype information (e.g. it is known that many researchers in logic-based artificial intelligence have a preference for spicy foods), or he may try to extrapolate preferences by observations of past behaviors (she has been noticed at the conference dinner choosing chicken and not beef). Finally, he might call her on the phone in order to ask her very specific questions about her preferences, as for instance comparison queries (would you prefer pasta or risotto as a first course?). Queries of specific semantics need to be asked for attributes that are not preferentially independent; for example if the preference over beverages depends on the instantiation of the second course, one cannot simply ask to compare between red and white wine, but Björn may ask: given that the second course is fish, do you prefer red or white wine ? It will however be impossible for him to ask Gabriella to reveal her complete preference relation over the (combinatorial) combinations, so he will do better asking questions that are informative (for instance, if he knows for sure that she is allergic to nuts, he will not ask preference questions involving this item; and neither will ask about caviar, if this item is too expensive given the available budget).

The topic of preference learning or eliciting has recently raised substantial interest in the communities of operations research and artificial intelligence. Note that in the former, the term preference elicitation is more frequent, while in the latter (especially in the subfield of machine learning) the term preference learning is common (due to different emphasis on the process for the former and on the data for the latter). Indeed there is a convergence between these communities in addressing these problems; a stream on preference learning has been organized at the European conference on Operations Research (EURO) for a number of years; we also mention the recent initiative of establishing the workshop From Multi-criteria Decision Aid to Preference Learning (DA2PL). In order to emphasize this convergence we propose to adopt the term of preference analytics as more general term.

Learning or eliciting preferences means to acquire preference information in either direct or indirect way, from preference statements, critiques to examples, observations of user's clicking behaviour, etc. The study of the assessment of the preferences of a decision maker goes back to several decades; particular emphasis has been given to the elicitation of utility functions for multi-attribute and multi-criteria settings [173]. Classic approaches for utility elicitation focus on high risk decision and aim at assessing the decision maker's utility very precisely. The decision maker is asked a number of questions in order to assess precisely the parameters of the utility function, with the exact questions to be asked depending on the adopted protocol.

Decision makers are asked questions that can be local, focusing on attributes in isolation, or global, aimed at comparing complete outcomes. In particular, standard gamble queries (SGQ) ask the following: "Choose between option x 0 for sure or a lottery < x , l, x ⊥ , 1-l >" (where the best option x is obtained with probability l, the worst option x ⊥ is obtained with probability 1 -l). An answer to a SGQ gives a constraint on the utility of x 0 . Assume, without loss of generality that u(x ) = 1 and u(x ⊥ ) = 0; the expected utility of the lottery < x , l, x ⊥ , 1-l > is l. Consider, for instance, the standard elicitation procedure for additive models; the decision analyst would typically ask to consider an attribute (for example, dessert), ask for the best (say, the Italian dessert tiramisù) and worst value (apple pie). He will then ask local standard gamble queries for each remaining color to assess its local utility value (value function). The subsequent problem is that of refining the intervals on local utility values, which can be done with the so-called bound queries. The next step is then of assessing the "scaling" factors that relate the weighting attributes to each other. In order to do this, a "reference" outcome is fixed and typical questions are based on the notion of indifference swaps (asking the decision maker to assess the required changes to make two alternatives equally preferred) in order to assess the relative importance of different features or criteria.

The classic approach to elicitation suffers from a number of drawbacks. Gamble queries (and similar questions) are difficult to respond. The precision attained with classical elicitation methods is often unnecessary and the cognitive cost might just not be worth the effort. While classic elicitation protocols are well-founded, and can lead to being able to rank alternatives from the best to the worst, their applicability has been questioned. Starting from a couple of decades ago, in the operations research community, several researchers [158,[START_REF] Bana E Costa | MACBETH -an interactive path towards the construction of cardinal value functions[END_REF] started to deal with the problem of eliciting a utility function when only incomplete information is available. Instead of fully eliciting a utility function, indirect elicitation methods assess a utility function from assignment examples (for instance, examples are assigned to classes). More recently, researchers in artificial intelligence [START_REF] Boutilier | A POMDP formulation of preference elicitation problems[END_REF][START_REF] Chajewska | Making rational decisions using adaptive utility elicitation[END_REF]298,[START_REF] Boutilier | Constraint-based Optimization and Utility Elicitation using the Minimax Decision Criterion[END_REF]288,289] have developed elicitation techniques for utility elicitation, with the goal of mitigating the cognitive cost for the user. Indeed in AI, the aim is that of developing agents that act regionally on behalf of the user; eliciting the preferences of the user in an effective way is therefore crucial.

Preference disaggregation methods The UTA method [158] is an assessment procedure for a set of utility functions based on linear programming. Local utilities are piecewise linear; the interval is divided in subintervals and linear interpolation is used to approximate the utility contribution of a given feature. Pairwise preferences are expressed with linear inequalities; slack variables are added to allow inconsistencies in the preference information. Since several utility functions may in general be feasible, a typical approach is the minimization of the sum of such slack variables, yielding a utility function that fits as good as possible the available preference information. An alternative method is MACBETH 18 [84], also based on a system of linear inequalities, that asks the user to give some reference levels for each feature/criterion and information about the difference of satisfaction between the values of a given feature. Utility elicitation methods goes beyond additive models; several researchers have considered models based on the Choquet integral; for instance the TOMASO decision support system [198] and the MYRIAD software tools [181]. A review of methods for preference disaggregation (the general term for this kind of assessment; this is in contrast to preference aggregation that combines preference information given a specified model) can be found in [159].

The idea that, when presented with limited information about the user preferences, there is not just one but many consistent utility functions, gives rise to robustness concerns. Let us assume that at a given point in the interaction P represents the set of preference statements available and U P the set of possible overall utility functions consistent with those. In robust ordinal regression [147], a choice x is necessarily preferred to y, written N , if, for all feasible utility functions u, it holds that u(y) ≥ u(x) (with strict necessary preference x N y if u(y) > u(x) for all feasible utility functions u); x is possibly preferred to y, written P , if there exists at least one utility function u such that u(x) ≥ u(y) with u ∈ U P . The properties of the necessary preference N and of possible preference relation N are analyzed: it is easy to see that N ⊆ P (if something is necessary, it is also possible); moreover it holds that if something is necessarily preferred to something else, the latter cannot be possibly preferred to the former19 : if x N y then it cannot hold y P x. The method U T A GM S provides linear programming formulations in order to compute necessary and possible rankings; notice that when additional preference statements are added, P might only decreases and N increases. The method U T ADIS GM S (UTilités Additives DIScriminantes) is the analogous for sorting problems [148] (alternatives need to be assigned to classes, that are ordered from the most to the worst preferred), given a set of examples of assignments and assuming an underlying additive model, the method associates to each alternative the set of necessary and possible assignments.

Analytic Hierarchy Process (AHP) A number of methods base the evaluation of alternatives under conflicting criteria on subjective judgments of the decision maker about pairwise comparisons of alternatives [191]. The most famous approach of this family is the Analytic Hierarchy Process (AHP) [253], a method widely used for decision aid. The decision maker provides pairwise information about the intensity of the different criteria that are mapped in a numerical scale, constructing an evaluation matrix. The principal eigenvector of the matrix is used as a weighting vector. The items are also evaluated in a pairwise fashion with respect to each of the criteria; then, item evaluations are multiplied by the weighting vector in order to assess the ranking. Despite its popularity, AHP has been criticized by several authors. In particular, [START_REF] Bana E Costa | A critical analysis of the eigenvalue method used to derive priorities in AHP[END_REF] criticizes the method with respect to the semantics of the priority vector derived from the principal eigenvalue method, as the method derived violates a condition of order preservation between importance weights. More problematic is that AHP, in its classic formulation, may display the (usually undesired) phenomenon of rank reversal: adding, as additional choice, an alternative that is a copy of a dominated item, can impact the final ranks (obtained with AHP) of other alternatives, and even change the item that is ranked first (in other words aggregation with AHP violates the independence of irrelevant alternatives). Belton and Gear [START_REF] Belton | On a short-coming of saaty's method of analytic hierarchies[END_REF] give a numeric example for which AHP gives B A C but, after adding D (a clone of B) AHP gives A B ∼ D C. Dyer [110] shows how rank reversal of this kind might happen even when D is dominated by B (and not just a clone). These observations sparked a vigor-ous debate in the community, with several replies to Dyer's papers [153,254] and followups [109], with the opinions differing on the interpretation of rank reversal and its acceptability, and the applicability of variants of AHP that circumvents the problem.

Leaving aside technical problems, we note that the procedure underlying AHP is quite cognitive demanding: the construction of the comparison matrices involves asking the decision maker a number of questions that is quadratic in the number of constraints and features; therefore this method can only be applied to decision problems involving a small number of items and features. Indeed, consider the problem of choosing a camera out of n possible choices and m criteria (quality of lens, memory, software,...), the user will be requested to answer m 2 + mn 2 questions (for example, if there are 20 different models of cameras and 10 criteria, the user will be asked to answer 520 questions, something considered unacceptable in typical electronic commerce applications).

Reasoning about similar decision problems Departing from traditional axiomatic approaches in economics, [136] analyzes (from a formal point of view) the situation of a decision maker who makes use of previous choices in memory in order to estimate the utility of a choice in a new problem. This is similar to what happens in case-based reasoning (a subfield of artificial intelligence) where solutions to previous similar problems are adapted in order to solve the problem at hand. This idea has been also considered in preference-based systems, in particular in approaches to recommendation based on case-based reasoning [206,266].

Adaptive Utility Elicitation Ideally, a system for automated elicitation and recommendation will only consider cognitive plausible forms of interactions, focusing on the available alternatives of the current decision problem. A number of researchers [START_REF] Boutilier | A POMDP formulation of preference elicitation problems[END_REF][START_REF] Chajewska | Making rational decisions using adaptive utility elicitation[END_REF]298,[START_REF] Boutilier | Constraint-based Optimization and Utility Elicitation using the Minimax Decision Criterion[END_REF]288] have proposed the idea of an interactive utility-based recommender system. It is assumed that the user has a latent utility function that dictates his preferences; the system maintains a "belief" (whose nature will be clearer in a moment) about such utility function u. The general schema is as follows (bearing some similarity to active learning):

1. Some initial user preferences P 0 are given; initialize belief 2. Repeat until the belief meets some termination condition (a) Ask user a query q (b) Observe the user response r (c) Update the belief given r 3. Recommend the item optimal according to the current belief A number of alternative proposals have been made with respect to 1) how preference uncertainty is represented in a belief, 2) which criterion is used to make a recommendation, and 3) how to select the question that is asked next. In the following A possibility for representing the current belief about the utility is to encode user responses with constraints (as in UTA) and reason about all possible consistent utility functions (as in robust ordinal regression) making use of a robust decision criterion to select the item to recommend. While maximin is a possibility [290], Boutilier et al. [50] suggest to adopt minimax regret, that is a less conservative robust criterion for decision making under uncertainty [258,177]. The intuition behind the approach of minimax regret is that of an adversarial game; the recommender selects the item reducing the "regret" with respect to the "best" item when the uninown parameters are chosen by the adversary. As before, P represents the set of preference statements available and U P the set of possible overall utility functions consistent with those. The max regret of an option x is the maximum difference between the utility of the best item and the utility of x when an adversary is choosing the utility function u ∈ U P :

MR(x; U P ) = max y∈X max u∈U P u(y)-u(x) (11)
with X being the set of possible choices. The minimax regret MMR(W ) of U P and the minimax optimal item x * P are then found by finding the item associated with the smallest maximum regret: MMR(U P ) = min threefold: 1) it is easy to update our knowledge about the user: whenever a query is answered, we treat the answer r as a new preference and derive a new set U P∪r 20 2) simple "priors" can be encoded with constraints on U P and 3) there are efficient heuristics that directly use the computation of minimax regret to choose the queries to ask next to the user: the current solution strategy [298,[START_REF] Boutilier | Constraint-based Optimization and Utility Elicitation using the Minimax Decision Criterion[END_REF] asks the user to compare x * P and its adversarial choice y * P associated with maximum regret. The approach comes with limitations too, as it cannot deal with noisy responses and the formulation of the optimization depends on the assumption about the utility.

A principled idea is that of asking queries with high (a posteriori) improvement in decision quality. Assuming a query q that can have R responses, for each response r ∈ R we can consider the updated utility space U P∪r assuming 20 For instance U P is a polytope in the case of a linear utility model defined by a vector of weights w; U P∪r will be then a subset of U P , consisting of all instantiations of w that satisfies r in addition to P.

that the answer to q is r; the associated minimax regret is MMR(U P∪r ) (that can only be lower or equal to MMR(U P )). A good query will significantly reduce minimax regret in each of the scenarios. A (non probabilistic) notion of myopic value of information [288] can be defined considering the worst-case regret reduction of query q when the utility function must lie in U P : RR(q; U P ) = min r∈R [MMR(U P )-MMR(U P∪r )] = MMR(U P )-max r∈R MMR(U P∪r ). ( 12) For example, consider the question q ="Do you prefer pizza or pasta?". The possible responses are R = {pizza pasta, pasta pizza, pasta ∼ pizza}. In order to compute the regret reduction RR(q; U P ) (with respect to a set of already stated preferences P) we need to consider U P∪{pizza pasta} (the set of utility functions satisfying pizza pasta in addition to P), U P∪{pizza≺pasta} and U P∪{pizza∼pasta} . In each of these utility spaces we compute minimax regret, consider the response associated with the highest value (in order to be robust with respect to the less favorable response), and subtract the current minimax regret value.

We can now use RR to numerically compare queries, as for example establishing that asking to compare pizza with pasta is less informative than asking to compare the shepherd's pie with risotto. In particular asking to compare pasta alla carbonara with pasta in bianco (pasta with butter) when the former is known to be necessarily preferred to the latter (according to the N introduced before) gives no regret reduction at all; nor there is value in repeating questions in this model. The "best" query according to this measure is then the query with maximal regret reduction; q * = arg max q RR(q; U P ). Notice that a query can have significantly different RR values depending on the U P (the currently known preferences may have a strong impact on the value of the query). The straightforward approach for query selection would be to consider all candidate queries, evaluate RR and pick the one with highest value; however this is impractical for large outcomes spaces. Practical methods for framing query selection as an optimization problems for comparison queries (and choice queries, that extend comparison queries to a set of elements) are thoroughly discussed in [288].

Alternatively, one could assume a Bayesian standpoint: this has the advantage of handling noisy information, can exploit prior information (if available) and can be used with different assumption about the choice model of the user. We assume distributional information about the parameters involved in the user's utility function; the belief θ(w) is a probability distribution over the parameters of the utility function that encodes the knowledge of the system about the user's preferences; expected utility of a given item x is given by EU θ (x) = u(x; w) θ(w) dw. The recommendation x * θ is the one associated with maximal expected utility under the current probabilistic belief:

EU * θ = max x∈A EU (x); and x * θ = arg max x∈A EU θ (x).
When a new preference is acquired (for instance, the user states that he prefers apples over orange), the distribution is updated according to Bayes, using Monte Carlo methods, or in-ference scheme based on expectation-propagation [207], in particular Trueskill [154] can be adapted to preference elicitation [149].

The problem of deciding which questions to ask could be formulated as a Partially Observable Markov Decision Process (POMDP) [START_REF] Boutilier | A POMDP formulation of preference elicitation problems[END_REF], however it is impractical to solve for non trivial cases. A more tractable approach is to consider (myopic) Expected Value Of Information (EVOI), the difference between the expected posterior utility (of the best recommendation in the updated belief) EPU * θ (q) associated to a query q and the current EU * θ :

EVOI θ (q) = EPU * θ (q) -EU * θ = r∈R P θ (r) EU * θ|r -EU * θ ( 13
)
where R is the set of possible responses (answers), θ is the current belief distribution, θ|r the posterior and P θ (r) the probability of a given response according to θ, whose value depends on the assumptions made about the choice model. Returning to our example about the dinner, a possible query could be to choose the preferred dish among pasta, risotto and shepherd's pie (these three dishes constitute R in this example); the posterior distributions would be θ|risotto, θ|pasta and θ|shepherd respectively (the distribution of the parameters conditioned to the selected dish being the preferred one among those mentioned); P θ (risotto) would weigh numerically (let's say, for instance, 75% of probability) the scenario of preferring risotto to both pasta and to the shepherd's pie; and similarly we can assess P θ (pasta) and P θ (shepherd). In order to ask the most informative question, we then ask the query q * = arg max EV OI θ (q) with highest EVOI or, equivalently, the query with highest EPU (since the current EU * value can be considered as a constant when choosing the query maximizing EVOI). For choice queries ("Among the following options, which one do you prefer?"), Viappiani and Boutilier [289] showed that the problem of finding the optimal query is tightly connected to the problem of finding an optimal recommendation set (the generation of shortlisted alternatives from which the user makes a selection [236], as in the display of search engine results) and near-optimal queries can be computed efficiently with worst-case guarantees.

Learning preferences from data A number of methods in the machine learning community have been developed in order to assess a set of parameters consistent with what is known about the user; these include methods based on support vector machines, such as SVM-rank [160]. The common ground of these approaches is that they fit an assumed model using the available data, and use the learned model to make predictions. For the problem of learning a utility function, this can mean that each user's preference is viewed as a constraint (an hyperplane in case of linear models) on the parameter space, and max-margin learners aim at identifying the set of parameters that maximize the minimum distance from the nearest hyperplane. These methods are "pointwise" in the sense that a single best guess of the user's utility function is provided as output. While these methods work well for tasks such as prediction (as this is the setting they were designed to), they are not readily apt for interactive systems, when one needs to assess which question the system should ask next (the focus of machine learning is most often of learning from available data). Some approaches do not make the assumption that a latent numeric utility function exists. These include models from ranking, such as Mallows models [START_REF] Critchlow | Probability models on rankings[END_REF]; for an approach for learning Mallows models see for instance Lu and Boutilier [193]. At the extreme model-free approaches do not make any specific model assumption at all, but rely on local estimation techniques. Common approaches are based on clustering and on using the information about the nearest neighbors in order to make estimations about the preferences of the user (implicitly there is an assumption of regularity, meaning that preferences of neighbors are similar). These approaches are popular for label ranking (a type of preference problem where the input data is based on preference rankings that are assigned to a specific label), in particular for the problem of predicting preferences based on demographic information, where the notion of similarity between user is defined naturally. A case-based nearest neighbors approach is proposed by Brinker and Hüllermeier [START_REF] Brinker | Case-based label ranking[END_REF], while Yu,Wan and Le [303] propose a method based on decision trees.

If one knows specific information about the underlying preference model, it is advantageous to exploit this information. A number of works focused on algorithms for learning preferences under specific model assumptions. In particular efforts have been made to learn lexicographic models [302] (the lexicographic assumption greatly simplifies the learning task, as only very few rankings are consistent with a lexicographic model) and preferences over sets [297]. As mentioned before in Section 5, CP-nets are a compact language representation for preferences in multi-attribute domains. If we know that a user has preferences that are consistent with a CP net, what is the best way to learn them? Chevaleyre et al. [START_REF] Chevaleyre | Learning ordinal preferences on multiattribute domains: The case of cp-nets[END_REF] address this problem from a theoretical point of view, providing learnability results. If we want to reason about possible CP networks consistent with current information, we may use Probabilistic CP networks (PCP-nets) [START_REF] Bigot | Probabilistic conditional preference networks[END_REF], a compact representation of a probabilistic distribution over CP networks; PCP-nets can be used for learning by conditioning on available information. Finally, [START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF] describes how to learn conditionally lexicographic preference relations.

Non classical preference models

Until now we have always considered preferences as model of "certain information". Indeed they have been considered as binary relations and the language used in order to formalise any theory about them has been (obviously) classic logic; the reader can check this in all basic texts about preference modelling: [115,119,251].

However, it is reasonable that if asked about a preference between any two x and y one could reply "I do not know" or more generally hesitate replying partially and/or ambiguously. The problem of representing values and uncertainty is not really new: Ramsey [238] and De Finetti [START_REF] De Finetti | La prvision: Ses lois logiques, ses sources subjectives[END_REF] have addressed the issue already in the 30s and it has been formalised in decision analysis both in prescriptive terms [291] and normative ones [258]. The problem with these approaches is that they are limited by the way uncertainty and hesitation are modelled: practically only probability (although subjective) is considered along with economically rational preferences ([115]). Such limitations gave rise to alternative approaches either within the decision theory community [118,136,174,256] or within the artificial intelligence community (see for instance [START_REF] Dubois | Qualitative decision theory: from Savage's axioms to non-monotonic reasoning[END_REF]). In the following we are going to survey the results of the latter approach.

Fuzzy sets

The basic idea here is the one to create and/or use languages specifically tailored to uncertainty modelling purposes, and more specifically the language of fuzzy sets. The first attempts to use fuzzy sets for preference modelling purposes date back to the late 70s (see [215] If, on the one hand, fuzzy (or valued as they are often are called) preference relations allowed to introduce a more nuanced and realistic preference modelling language, on the other hand they opened a certain number of problems.

-Preference structures and representation theorems require the introduction of complex logical sentences. For instance the definition of transitivity (∀x, y, z ∈ A x y ∧ y z → x z) requires to translate the universal quantifier as well as the connectives "and" and "imply" under form of appropriate functions. This problem has been addressed through the use of T-norms and conorms [101,259] possibly satisfying the De Morgan principle (such that T (x, y) = N (S(N (x), N (y))), where T , S and N are the functions representing T-norms, T-conorms and negations respectively). It has been soon proved that the system of functional equations which results when usual preference structures need to be characterised does not admit a unique solution (see [START_REF] Alsina | On a family of connectives for fuzzy sets[END_REF]121]). This is not surprising knowing the truth functionality problems of fuzzy reasoning and introduces a degree of freedom which needs to be managed during the modelling process.

-Most of the times valued preference relations are practically sentences where preferences are associated to some "measure of uncertainty" (it is typically the case of expected utility). Under such a perspective when several different valued preferences need to be aggregated what practically we get is a problem of aggregating the associated measures (as in most ordered statistics problems), which in this case are supposed to be fuzzy values. The problem has been addressed extending well known aggregation procedures through the introduction of the Choquet and Sugeno integrals which are the more general ordered statistics we can conceive (see [146]).

The reader should note that this approach allows to include probability measures above preference statements within the same theoretical framework. Actually the concept of fuzzy measure is nothing more than the one of "capacity": a function f over the power set of a set Ω (f : 2 Ω → [0, 1] such that f (∅) = 0 and A ⊆ B ⊆ Ω → f (A) ≤ f (B)). Probabilities are just additive capacities. All that said, such tools implicitly introduce a commensurability hypothesis among these different measures, which is far from being true in practice. -A specific way to address the problem of measuring the uncertainty associated to preference statements has been the use of possibility distributions (see [102]): these replace the additive property characterising probabilities (seen as capacities) with a pure ordinal sum (π(A∪B) = max(π(A), π(B)), π being a possibility distribution). If we now consider purely ordinal preference statements and purely ordinal likelihoods (such as described by possibilities) we get a possibilistic version of "Qualitative Decision Theory" an attempt to establish an ordinal version of classic Decision Theory (see [103], [START_REF] Dubois | Qualitative decision theory with preference relations and comparative uncertainty: An axiomatic approach[END_REF]). The problem here is that the resulting decision rules are either overconfident or not decisive and thus operationally of little interest (see [START_REF] Dubois | Qualitative decision theory: from Savage's axioms to non-monotonic reasoning[END_REF], [114]).

Beyond fuzzy sets

As already mentioned it might be the case that it is not possible to establish precisely whether a certain relation holds or not. However, hesitation can be due either to incomplete information (missing values, unknown replies, unwillingness to reply etc.) or to contradictory information (conflicting evaluation dimensions, conflicting reasons for and against the relation, inconsistent replies etc.). More generally speaking while we try to assess the belief of a sentence or the value of something we may face the, rather common, situation where both positive information (reasons, values) and negative information (reasons, values) are available. Typical cases include positive and negative witnesses, majorities for and vetoes against (a preference or a statement), arguments for and against, gains and losses etc. Such situations have been considered in argumentation theory ([272]), value theory ([242]), cognitive studies about decision under risk and uncertainty ([170], as well as in philosophy and formal logic (see [START_REF] Dubarle | Essai sur la généralisation naturelle de la logique usuelle[END_REF]), [START_REF] Belnap | How a computer should think[END_REF] and [START_REF] Belnap | A useful four-valued logic[END_REF]). The common idea behind these approaches is that the negative information (reasons, values) is not just the complement of the positive one, but needs to be considered explicitly and formalised appropriately. In formal logic this idea has been further developing multi-valued logics and more precisely four-valued logics (see in [START_REF] Arieli | The value of the four values[END_REF][START_REF] Arieli | Ideal paraconsistent logics[END_REF][START_REF] Bergstra | A propositional logic with four values: true, false, divergent and meaningless[END_REF]113,123,120,137,172,270,277]).

In the case of preference modelling, the use of such logics was first suggested in [276] and [START_REF] Doherty | Partial logics and partial preferences[END_REF]. Such logics extend the semantics of classical logic through two hypotheses:

the complement of a first order formula does not necessarily coincide with its negation; truth values are only partially ordered (in a bilattice), thus allowing the definition of a boolean algebra on the set of truth values.

The result is that using such logics, it is possible to formally characterise different states of hesitation when preferences are modelled (see [279], [280]). Furthermore, using such a formalism, it becomes possible to generalise the concordance/discordance principle (used in several decision aiding methods) as shown in [278] and several characterisation problems can be solved (see for instance [281]). More recently (see [228,125,[START_REF] Arieli | Preference modeling by rectangular bilattices[END_REF][START_REF] Deschrijver | A bilattice-based framework for handling graded truth and imprecision[END_REF]217,218,282]) it has been suggested to use the extension of such logics for continuous valuations.

Among others, this research allowed to show that such continuous valuations correspond to the logical counterpart of the concept of bi-capacity introduced as measure of "bipolar" preference measurement. The issue of bipolarity returned of interest in the recent years (see [104]) through different contributions where the presence of clearly distinct positive and negative reasons are considered in representing preferences and supporting decisions (see [START_REF] Amgoud | Using arguments for making and explaining decisions[END_REF][START_REF] Bistarelli | From soft constraints to bipolar preferences: modelling framework and solving issues[END_REF][START_REF] Bistarelli | Uncertainty in bipolar preference problems[END_REF]).

Conclusions

Preferences are a key element of decision making and a basic concept for several research fields such as economics, decision theory, game theory, artificial intelligence, classification, databases, etc. This article presented the state of the art of preferences in artificial intelligence; it introduced techniques for reasoning about, argumenting, representing and learning preferences. Note that, due to the width of the topic, we did not cover some important domains where handling preferences have also been considered as planning [START_REF] Baier | Planning with preferences[END_REF], personalized user interfaces [128], and the recently very active field of preference-based reinforcement learning [126].

Preferences play a role in almost all sub-areas of artificial intelligence, as witnessed by the diversity of the formalisms employed in the different sections of this article. We prospect that in the future preferences will play an even increasing role (some prominent research directions are mentioned in the different sections of this article). Indeed, artificial intelligence aims at producing computational artifacts that can help humans in a number of problems acting on their behalf; reasoning, explaining, learning and in general handling preferences are central issues to be tackled in any non trivial artificial intelligence system. There are several applications [223] of this research area, some already deployed in practice, including personalized and location-aware recommendation systems [START_REF] Braunhofer | Location-aware music recommendation[END_REF] and interactive personalized configuration systems [264].

We envision that the research issues covered by this survey will be more and more interconnected: for instance, we can foresee the development of preference elicitation strategies for non classical preference models (following the recent works of [START_REF] Benabbou | Incremental elicitation of choquet capacities for multicriteria decision making[END_REF], where adaptive elicitation techniques are proposed for assessing preferences dictated by a Choquet integral), or the development of richer languages for representation of complex preferences, that can then be used for argumentation. A critical point is that of providing explanations (generated automatically) to the user on how his preferences are treated (aggregated, assessed,...) and the reasons behind a particular action taken by the system. This issue is crucial in the research field of recommender systems [130]; a recommender system should be able to explain why a particular product is suggested.

Finally, preferences constitute the central element of negotiations and social choice problems, that arise from the fact that different agents (or organizations) have conflicting objectives, expressed in terms of preferences. Voting systems are ways to aggregate the preferences of different users (or agents) in order to make a collective choice (as in elections); however for novel application domains, such as internet-based decision support tools for groups of users, new frameworks need to be developed (for instance, voting systems with incomplete preference profiles and incremental elicitation of votes, following [194]; alternatively autonomous agents might engage in online argumentations in order to choose the best candidate for a job). Computational social choice is the field that studies algorithmic methods to reason about collective choices, as such preferences are a central element.

We expect that our general survey about preferences in artificial intelligence can be of interest to the researchers of various sub-disciplines of artificial intelligence, contributing in the widespread adoption of preference handling methods and fostering the development of new research directions at the intersection of different fields.

Definition 3 (Fig. 1

 31 Fig. 1 An argumentation framework.

Definition 9 (

 9 Kripke semantics) A possible world (Kripke) model for a deontic theory in SDL is a tuple M =< W, R O , V > that consists of a nonempty set of worlds W , a binary serial deontic accessibility relation R O between worlds17 , and a valuation function V that assigns a truth value to atomic propositions in each world w ∈ W . Intuitively, R O (w, w ) means that w is an ideal deontic alternative to the actual world w and that in w it holds everything obligatory in world w. A formula Oα is true in w in M (denoted M, w |= Oα) iff M, w |= α for all w with R O (w, w ).

Example 4 (

 4 The gentle murderer paradox) Suppose that the following are wff's in a SDL theory: 1. Gabriella should not kill Björn: O¬k 2. If Gabriella kills Björn, then she should do it gently: k → O(k ∧ g) 3. Gabriella kills Björn: k k → O(k ∧ g) is a contrary-to-duty obligation of O¬k, as it says what one should do if one violates an obligation. The problem with the gentle murderer is that in a SDL theory with these sentences, one can derive Ok. By applying Modus Ponens to (

  U P ). The advantages of regret-based approach are

  Table, we outline some possibilities.

		minimax-regret	maximin-utility	Bayesian
		approach	approach	approach
	knoweldge	constraints	constraints	prob. distribtion
	representation
	which option	minimax	maximin	expected
	to recommend? regret	utility	utility
	which query	worst-case	worst-case maximin expected value
	to ask next?	regret reduction improvement	of information

  ,[216],[252]). The major challenge was to translate the theoretical structures already used in order to characterise and work with preferences into the new language: what is a fuzzy partition? How to define a fuzzy transitive binary relation? What should be a fuzzy preference structure? There is a wide literature in this area (partially surveyed in[211]) for which we cite some classic references: [100], [121], [145], [169], [227].

http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=04271

http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=14101

The reader is invited to check the website http://preferencehandling.free.fr for an account of all the activities related to this domain.

4 A relation R ⊆ A × A is Ferrers if ∀x, y, z, w ∈ A, (xRy ∧ zRw) → (xRw ∨ zRy).

For simplicity here we consider classical propositional logic.

A similar but less general proposal was made byBossu and Siegel [45].

The puzzle asks how three missionaries and three cannibals can cross a river. The information given is that there is a rowboat for two people and that, if the cannibals outnumber the missionaries, the missionaries will be eaten. As McCarthy observed, if someone would suggest to use the bridge or the helicopter, we would be irritated. This is because the assumption is that only the elements explicitly provided in the puzzle are assumed to exist. If we want to be able to avoid the excessive qualification (for example, saying that the capacity of the boat does not change in the course of the action, that no bridge or helicopter exist, etc.), circumscription is a candidate to achieve this:

For the same reason, Reiter's default logic does not satisfy Cautious Monotonicity[START_REF] Alsina | On a family of connectives for fuzzy sets[END_REF].

T h denotes that an extension is a theory (i.e., it is a deductively closed set).

However, John L. Pollock's work, who developed Roderick Chisholm's ideas[START_REF] Chisholm | Perceiving[END_REF][START_REF] Chisholm | Theory of Knowledge[END_REF] into a theory of prima facie reasons and their defeaters, was rather motivated by epistemological questions in philosophy of science.

Taking O as the primary concept means that other notions, like permissible, can be defined from O. So, for example, if we denote 'permissible' by P , we have that P α ↔ ¬O¬α.

For explanations of why Weakening cannot hold in preference-based deontic logics, see[157, 139, 140, 152].

An accessibility relation is serial if, for every world w, there is at least one world accessible to w.

Measuring Attractiveness by a Categorical Based Evaluation TecHnique.

There is an obvious similarity to approaches using modal logic, however no formal logical treatment is made in robust ordinal regression.

Acknowledgments

We thank the three anonymous referees for their valuable comments and suggestions that helped us improving the content and readability of the paper.

Gabriella Pigozzi benefited from the support of the AMANDE project of the French National Research Agency (ANR-13-BS02-0004); Paolo Viappiani is supported by the ELICIT project funded by the French National Research Agency through the Idex Sorbonne Universités under grant ANR-11-IDEX-0004-02.