Several methods have been introduced in the literature to extend preferences over items from a population to preferences over the groups they may form - a problem known as the Order Lifting problem. The converse matter of deducing preferences over items from expressed preferences over the coalitions that may be formed within a population - a problem known as the Social Ranking Problem - has also been studied more recently. In this paper, we investigate the links between these two problems: after an examination of the general case, we consider the impact of missing information, by studying which social ranking methods allow for the most accurate recovery of initial preferences over items, depending on the amount of missing information about coalitions. Finally, we consider the specific case in which preferences are only expressed over coalitions of same size, and examine the accuracy of social ranking methods when faced with impartial information about preferences over k-sized coalitions.

International audience

Nowadays, the environmental footprint of a process has become an important aspect to be considered in each human activity from industrial production to logistics. Despite this increased awareness, environmental friendliness is a quite new aspect in the IT sector and even less considered in the field of recommendation systems. Bundle recommendation aims to generate bundles of associated products that users tend to consume as a whole under certain circumstances, and poses additional challenges in terms of environmental friendliness. Nevertheless, current bundle recommendation systems fail to consider the environmental impact of the product bundle when generating recommendations. We introduce a new preference-based approach for bundle recommendation exploiting the Choquet integral. This allows us to formalize preferences for coalitions of environmental-related attributes, thus recommending product bundles accounting for synergies among product attributes. An experimental evaluation on a dataset of local food products in Northern Italy shows how the Choquet integral allows to naturally formalize a sensible notion of environmental friendliness, and that standard approaches based on weighted sums of attributes end up recommending bundles with lower environmental friendliness even if weights are explicitly learned to maximize it.

This paper deals with decision making under risk with the Weighted Expected Utility (WEU) model, which is a model generalizing expected utility and providing stronger descriptive possibilities. We address the problem of identifying, within a given set of lotteries, a (near-)optimal solution for a given decision maker consistent with the WEU theory. The WEU model is parameterized by two real-valued functions. We propose here a new incremental elicitation procedure to progressively reduce the imprecision about these functions until a robust decision can be made. We also give experimental results showing the practical efficiency of our method.

The Choquet integral is one of the most sophisticated and expressive preference models used in decision theory for multicriteria decision making. It performs a weighted aggregation of criterion values using a capacity function assigning a weight to any coalition of criteria, thus enabling positive and/or negative interactions among criteria and covering an important range of possible decision behaviors. However, the specification of the capacity involves many parameters which raises challenging questions, both in terms of elicitation burden and guarantee on the quality of the final recommendation. In this paper, we investigate the incremental elicitation of the capacity through a sequence of preference queries selected one-by-one using a minimax regret strategy so as to progressively reduce the set of possible capacities until a decision can be made. We propose a new approach designed to efficiently compute minimax regret for the Choquet model. Numerical experiments are provided to demonstrate the practical efficiency of our approach.

This tutorial, addressed to researchers and practitioners in the area of recommendation systems, reviews the foundations of decision and utility theory, focusing on methods for representing, learning and reasoning with preferences. Recent advances on handling preferences will also be discussed, with a focus on preference learning, preference aggregation and preferences in argumentation. Finally, we will show how these techniques can be used in a practice in recommender systems.

Utility elicitation is an important component of many applications, such as decision support systems and recommender systems. Such systems query users about their preferences and offer recommendations based on the system's belief about the user's utility function. We analyze the connection between the problem of generating optimal recommendation sets and the problem of generating optimal choice queries, considering both Bayesian and regret-based elicitation. Our results show that, somewhat surprisingly, under very general circumstances, the optimal recommendation set coincides with the optimal query.

Most frameworks for utility elicitation assume a predefined set of features over which user preferences are expressed. We consider utility elicitation in the presence of subjective or user-defined features, whose definitions are not known in advance. We treat the problem of learning a user's feature definition as one of concept learning, but whose goal is to learn only enough about the concept definition to enable a good decision to be made. This is complicated by the fact that user utility is unknown. We describe computational procedures for identifying optimal alternatives w.r.t minimax regret in the presence of both utility and concept uncertainty; and develop several heuristic query strategies that focus simultaneously on reduction of relevant concept and utility uncertainty.

Bayesian approaches to utility elicitation typically adopt (myopic) expected value of information (EVOI) as a natural criterion for selecting queries. However, EVOI-optimization is usually computationally prohibitive. In this paper, we examine EVOI optimization using \emph{choice queries}, queries in which a user is ask to select her most preferred product from a set. We show that, under very general assumptions, the optimal choice query w.r.t.\ EVOI coincides with \emph{optimal recommendation set}, that is, a set maximizing expected utility of the user selection. Since recommendation set optimization is a simpler, submodular problem, this can greatly reduce the complexity of both exact and approximate (greedy) computation of optimal choice queries. We also examine the case where user responses to choice queries are error-prone (using both constant and follow mixed multinomial logit noise models) and provide worst-case guarantees. Finally we present a local search technique that works well with large outcome spaces.

Most models of utility elicitation in decision support and interactive optimization assume a predefined set of "catalog" features over which user preferences are expressed. However, users may differ in the features over which they are most comfortable expressing their preferences. In this work we consider the problem of feature elicitation: a user's utility function is expressed using features whose definitions (in terms of "catalog" features) are unknown. We cast this as a problem of concept learning, but whose goal is to identify only enough about the concept to enable a good decision to be recommended. We describe computational procedures for identifying optimal alternatives w.r.t. minimax regret in the presence of concept uncertainty; and describe several heuristic query strategies that focus on reduction of relevant concept uncertainty.

Utility or preference elicitation is a critical component in many recommender and decision support systems. However, most frameworks for elicitation assume a predefined set of features (e.g., as derived from catalog descriptions) over which user preferences are expressed. Just as user preferences vary considerably, so too can the features over which they are most comfortable expressing these preferences. In this work, we consider preference elicitation in the presence of subjective or user-defined features. We treat the problem of learning a user's feature definition as one of concept learning, but whose goal is to learn only enough about the concept definition to enable a good decision to be made. This is complicated by the fact that user preferences are unknown. We describe computational procedures for identifying optimal alternatives w.r.t minimax regret in the presence of both utility and concept uncertainty; and develop several heuristic query strategies that focus on reduction of relevant concept and utility uncertainty. Computational experiments verify the efficacy of these strategies.

Current conversational recommender systems are unable to offer guarantees on the quality of their recommendations due to a lack of principled user utility models. We develop an approach to recommender systems that incorporates an explicit utility model into the recommendation process in a decision-theoretically sound fashion. The system maintains explicit constraints on user utility based on preferences revealed by the user's actions. We investigate a new decision criterion, setwise minimax regret (SMR), for constructing optimal recommendation sets: we develop algorithms for computing SMR, and prove that SMR determines choice sets for queries that are myopically optimal. This provides a natural basis for generating compound critiques in conversational recommender systems. Our simulation results suggest that this utility-theoretically sound approach to user modeling allows much more effective navigation of a product space than traditional approaches based on, for example, heuristic utility models and product similarity measures.

We consider a conversational recommender system based on example-critiquing where some recommendations are suggestions aimed at stimulating preference expression to acquire an accurate preference model. User studies show that suggestions are particularly effective when they present additional opportunities to the user according to the look-ahead principle [32].

The internet presents people with an increasingly bewildering variety of choices. Online consumers have to rely on computerized search tools to find the most preferred option in a reasonable amount of time. Recommender systems address this problem by searching for options based on a model of the user's preferences. We consider example critiquing as a methodology for mixed-initiative recommender systems. In this technique, users volunteer their preferences as critiques on examples. It is thus important to stimulate their preference expression by selecting the proper examples, called suggestions. We describe the look-ahead principle for suggestions and describe several suggestion strategies based on it. We compare them in simulations and, for the first time, report a set of user studies which prove their effectiveness in increasing users' decision accuracy by up to 75%.

Preference-based search is the problem of finding an item thatmatches best with a user's preferences. User studies show that example-based tools for preference-based search can achievesignificantly higher accuracy when they are complemented withsuggestions chosen to inform users about the available choices. We discuss how suggestions can be efficiently implemented even for large product databases.

We consider interactive tools that help users search for their most preferred item in a large collection of options. In particular, we examine example-critiquing, a technique for enabling users to incrementally construct preference models by critiquing example options that are presented to them. We present novel techniques for improving the example-critiquing technology by adding suggestions to its displayed options. Such suggestions are calculated based on an analysis of users' current preference model and their potential hidden preferences. We evaluate the performance of our model-based suggestion techniques with both synthetic and real users. Results show that such suggestions are highly attractive to users and can stimulate them to express more preferences to improve the chance of identifying their most preferred item by up to 78%.

In many practical scenarios, users are faced with the problem of choosing the most preferred outcome from a large set of possibilities. As people are unable to sift through them manually, decisions support systems are often used to automatically find the optimal solution. A crucial requirement for such a system is to have an accurate model of the user's preferences. Studies have shown that people are usually unable to accurately state their preferences up front, but are greatly helped by seeing examples of actual solutions. Thus, several researchers have proposed preference elicitation strategies based on example critiquing. The essential design question in example critiquing is what examples to show users in order to best help them locate their most preferred solution. In this paper, we analyze this question based on two requirements. The first is that it must stimulate the user to express further preferences by showing the range of alternatives available. The second is that the examples that are shown must contain the solution that the user would consider optimal if the currently expressed preference model was complete so that he select it as a final solution. Copyright 2004 ACM.