Given the assumption that a user’s preference relation, on a finite set of alternatives, is in a particular family of preference relations, we consider the problem of how many queries are required to determine sufficient information about the preference relation that an alternative can be returned that is optimal for the user. We focus especially on queries based on comparisons between two alternatives and related forms of query. We consider both a fixed version of this problem, where the user is given a questionnaire (or batch of queries), and is asked to answer them all; and a dynamic, i.e., interactive, version, where the choice of query can depend on previous answers. We derive upper and lower bounds for the numbers of queries required, and give preference families that achieve these bounds; and we determine the solution of the batch problem for linear preference families.

International audience

Max regret is frequently used, in situations when there is uncertainty about a user preference model in a multi-objective optimisation problem, as a measure of how close an alternative is to being necessarily optimal. It is used in a termination condition for a dialogue with a user, and for recommending a compromise solution, and in different ways of generating informative queries. In this paper we consider linear user preference models based on simple weighted sums of the objectives. Unfortunately, max regret lacks a desirable scale-invariance property: changing the units (or the linear scaling) of the objectives can significantly alter the relative values of max regret between alternatives, even though the choice of units is often somewhat arbitrary. In this paper we define variations of max regret in which the regret, of an alternative given a particular user model, is divided by a function expressing a range of utility values. This leads to scale-invariance, and maintains important properties of max regret such as translation-invariance (in contrast with max relative regret). We show how linear programming and extreme points algorithms can be used for computation.

A constraint-based model represents knowledge about a domain by a set of constraints, which must be satisfied by solutions in that domain. These models may be used for reasoning, decision making and optimisation. Unfortunately, modelling itself is a hard and error-prone task that requires expertise. The automation of this process is often referred to as constraint acquisition and has been pursued for over 20 years. Methods typically learn constraints by testing candidates against a dataset of solutions and non-solutions, and often use some form of machine learning to decide which should be learned. However, few methods are robust under errors in the data, some cannot handle large sets of candidates, and most are computationally expensive even for small problems. We describe a statistical approach based on sequential analysis that is robust, fast and scalable to large biases. Its correctness depends on an assumption that does not always hold but which is, we show using Bayesian analysis , reasonable in practice.

In a multi-objective optimisation problem, when there is uncertainty regarding the correct user preference model, max regret is a natural measure for how far an alternative is from being necessarily optimal (i.e., optimal with respect to every candidate preference model). It can be used for recommending a relatively safe choice to the user, or used in the generation of an informative query, and in the decision to terminate the user interaction, because an alternative is sufficiently close to being necessarily optimal. We consider a common and simple form of user preference model: a weighted average over the objectives (with unknown weights). However, changing the scale of an objective by a linear factor leads to an essentially different set of preference models, and this changes the max regret values (and potentially their relative ordering), sometimes very considerably. Since the scaling of the objectives is often partly subjective and somewhat arbitrary, it is important to be aware of how sensitive the max regret values are to the choices of scaling of the objectives. We give mathematical results that characterise and enable computation of this variability, along with an asymptotic analysis.

One important and natural representation of preferences is a choice function, which returns the preferred options amongst any given subset of the alternatives. There are some very intuitive coherence conditions that might be assumed for an agent’s choice function, in particular path independence, and a consistency condition stating that there is always at least one preferred alternative among any non-empty set. However, an elicited choice function may not satisfy path independence, because of the elicitation being incomplete, or because of there being some incoherence in the agent’s reported choice function (despite the agent assenting to the general coherence conditions). Furthermore, if we wish to combine the choice functions of more than one agent, simple natural combination operations can lose path independence. This paper develops methods for enforcing path independence and restoring consistency, thus, making the user preferences coherent; this method also leads to approaches for combining two choice functions, in order to suggest the most promising alternatives for a pair of agents.

Abstract In a decision-making problem, there is often some uncertainty regarding the user preferences. We assume a parameterised utility model, where in each scenario we have a utility function over alternatives, and where each scenario represents a possible user preference model consistent with the input preference information. With a set $$A$$ A of alternatives available to the decision-maker, we can consider the associated utility function, expressing, for each scenario, the maximum utility among the alternatives. We consider two main problems: firstly, finding a minimal subset of $$A$$ A that is equivalent to it, i.e., that has the same utility function. We show that for important classes of preference models, the set of possibly strictly optimal alternatives is the unique minimal equivalent subset. Secondly, we consider how to compare $$A$$ A to another set of alternatives $$B$$ B , where $$A$$ A and $$B$$ B correspond to different initial decision choices. This is closely related to the problem of computing setwise max regret. We derive mathematical results that allow different computational techniques for these problems, using linear programming, and especially, with a novel approach using the extreme points of the epigraph of the utility function.

One natural way to express preferences over items is to represent them in the form of pairwise comparisons, from which a model is learned in order to predict further preferences. In this setting, if an item a is preferred to the item b, then it is natural to consider that the preference still holds after multiplying both vectors by a positive scalar (e.g., 2a≻2b). Such invariance to scaling is satisfied in maximum margin learning approaches for pairs of test vectors, but not for the preference input pairs, i.e., scaling the inputs in a different way could result in a different preference relation being learned. In addition to the scaling of preference inputs, maximum margin methods are also sensitive to the way used for normalizing (scaling) the features, which is an essential pre-processing phase for these methods. In this paper, we define and analyse more cautious preference relations that are invariant to the scaling of features, or preference inputs, or both simultaneously; this leads to computational methods for testing dominance with respect to the induced relations, and for generating optimal solutions (i.e., best items) among a set of alternatives. In our experiments, we compare the relations and their associated optimality sets based on their decisiveness, computation time and cardinality of the optimal set.

In a decision-making problem, there is often some uncertainty regarding the user preferences.We assume a parameterised utility model, where in each scenario we have a utility function over alternatives, and where each scenario represents a possible user preference model consistent with the input preference information.With a set A of alternatives available to the decision maker, we can consider the associated utility function, expressing, for each scenario, the maximum utility among the alternatives.We consider two main problems: firstly, finding a minimal subset of A that is equivalent to it, i.e., that has the same utility function.We show that for important classes of preference models, the set of so-called possibly strictly optimal alternatives is the unique minimal equivalent subset.Secondly, we consider how to compare A to another set of alternatives B, where A and B correspond to different initial decision choices.We derive mathematical results that allow different computational techniques for these two problems, using linear programming, and especially, with a novel approach using the extreme points of the epigraph of the utility function.

We consider a way of generating voting rules based on a random relation, the winners being alternatives that have the highest probability of being supported. We define different notions of support, such as whether an alternative dominates the other alternatives, or whether an alternative is undominated, and we consider structural assumptions on the form of the random relation, such as being acyclic, asymmetric, connex or transitive. We give sufficient conditions on the supporting function for the associated voting rule to satisfy various properties such as Pareto and monotonicity. The random generation scheme involves a parameter p between zero and one. Further voting rules are obtained by tending p to zero, and by tending p to one, and these limiting rules satisfy a homogeneity property, and, in certain cases, Condorcet consistency. We define a language of supporting functions based on eight natural properties, and categorise the different rules that can be generated for the limiting p cases.

In this paper we describe a complex optimization application arising in maintenance scheduling, developed in close collaboration with an industrial partner. We have to plan and schedule preventive and corrective maintenance activities at customer sites by a group of traveling repair technicians. A specific property of the problem considered here is a mix of customers in both urban centers and rural areas. This means that travel times between customers must be considered when balancing overall workload for each agent. We discuss a problem decomposition compatible with current management practice, describe different solvers for the individual problem steps, and show results on real-world data from the industrial partner.

The formalism of multi-objective influence diagrams has recently been developed for modeling and solving sequential decision problems under uncertainty and multiple objectives. Since utility values representing the decision maker's preferences are only partially ordered (e.g., by the Pareto order) we no longer have a unique maximal value of expected utility, but a set of them. Computing the set of maximal values of expected utility and the corresponding policies can be computationally very challenging. In this paper, we consider alternative notions of optimality, one of the most important one being the notion of possibly optimal, namely optimal in at least one scenario compatible with the inter-objective tradeoffs. We develop a variable elimination algorithm for computing the set of possibly optimal expected utility values, prove formally its correctness, and compare variants of the algorithm experimentally.

In the task of preference learning, there can be natural invariance properties that one might often expect a method to satisfy. These include (i) invariance to scaling of a pair of alternatives, e.g., replacing a pair (a,b) by (2a,2b); and (ii) invariance to rescaling of features across all alternatives. Maximum margin learning approaches satisfy such invariance properties for pairs of test vectors, but not for the preference input pairs, i.e., scaling the inputs in a different way could result in a different preference relation. In this paper we define and analyse more cautious preference relations that are invariant to the scaling of features, or inputs, or both simultaneously; this leads to computational methods for testing dominance with respect to the induced relations, and for generating optimal solutions among a set of alternatives. In our experiments, we compare the relations and their associated optimality sets based on their decisiveness, computation time and cardinality of the optimal set. We also discuss connections with imprecise probability.

Support Vector Machines (SVM) are among the most well-known machine learning methods, with broad use in different scientific areas. However, one necessary pre-processing phase for SVM is normalization (scaling) of features, since SVM is not invariant to the scales of the features’ spaces, i.e., different ways of scaling may lead to different results. We define a more robust decision-making approach for binary classification, in which one sample strongly belongs to a class if it belongs to that class for all possible rescalings of features. We derive a way of characterising the approach for binary SVM that allows determining when an instance strongly belongs to a class and when the classification is invariant to rescaling. The characterisation leads to a computation method to determine whether one sample is strongly positive, strongly negative or neither. Our experimental results back up the intuition that being strongly positive suggests stronger confidence that an instance really is positive.

We analyse preference inference, through consistency, for general preference languages based on lexicographic models. We identify a property, which we call strong compositionality, that applies for many natural kinds of preference statement, and that allows a greedy algorithm for determining consistency of a set of preference statements. We also consider different natural definitions of optimality, and their relations to each other, for general preference languages based on lexicographic models. Based on our framework, we show that testing consistency, and thus inference, is polynomial for a specific preference language which allows strict and non-strict statements, comparisons between outcomes and between partial tuples, both ceteris paribus and strong statements, and their combination. Computing different kinds of optimal sets is also shown to be polynomial; this is backed up by our experimental results.

Sharing car journeys can be very beneficial, since it can save travel costs, as well as reducing traffic congestion and pollution. The process of matching riders and drivers automatically at short notice, is referred to as dynamic ridesharing, which has attracted a lot of attention in recent years. In this paper, amongst the wide range of challenges in dynamic ridesharing, we consider the problem of ride-matching. While existing studies mainly consider fixed assignments of participants in the matching process, our main contribution is focused on the learning of the user preferences regarding the desirability of a choice of matching; this could then form an important component of a system that can generate robust matchings that maintain high user satisfaction, thus encouraging repeat usage of the system. An SVM inspired method is exploited which is able to learn a scoring function from a set of preferences; this function measures the predicted satisfaction degree of the user regarding specific matches. To the best of our knowledge, we are the first to present a model that is able to implicitly learn individual preferences of participants. Our experimental results, which are conducted on a real ridesharing data set, show the effectiveness of our approach.

In this paper, we consider the effect of different order relations on the solutions of Multi-Objective Constraint Optimization Problems (MOCOP) with tradeoffs, where the tradeoffs are given in the form of elicited or observed preferences over alternatives. In MOCOP, alternatives are evaluated on a number of objectives (utility scales) and thus correspond to utility vectors, the set of optimal solutions corresponds to the set of undominated alternatives with respect to some order relation on the utility vectors. Thus, the choice of an order relation on the utility vectors is crucial, a strong order relation results in a smaller set of solutions which can be helpful for the decision maker. Our focus lies on the comparison between Pareto, weighted average and lexicographic orderings. We show that every inference that can be made from a set of given preferences considering weighted average orders can be made for lexicographic orders as well. Further results on the relation between the sets of optimal solutions corresponding to lexicographic and weighted average orders are established under the distinction between strict and non-strict preferences. For solving MOCOP, we apply variants of Preference Inference for the different order relations as dominance checks. Our experimental results show that lexicographic orders give much stronger inferences than Pareto and weighted average orders. However, the lexicographic order based algorithm also results in a longer running time than the other two.

Maintaining comfortable thermal conditions in an office environment is very important, as it can affect the quality of life of the occupants, their work productivity, and improve energy efficiency. One significant aspect of this task is how to balance the preferences of a number of occupants sharing the same space. We suggest three families of approaches to this problem, both for the case of optimising for a single time period, and for the problem of optimising over multiple different time periods. We analyse in detail the different approaches based on a number of natural properties, proving which of the properties the different families satisfy.

With personalisation becoming more prevalent, it can often be useful to be able to infer additional preferences from input user preferences. Preference inference techniques assume a set of possible user preference models, and derive inferences that hold in all models satisfying the inputs; the more restrictive one makes the set of possible user preference models, the more inferences one gets. Sometimes it can be useful to have an adventurous form of preference inference when the input information is relatively weak, for example, in a conversational recommender system context, to give some justification for showing some options before others. This paper considers an adventurous inference based on assuming that the user preferences are lexicographic, and also an inference based on an even more restrictive preference model. We show how preference inference can be efficiently computed for these cases, based on a relatively general language of preference inputs.

The problem of real-time occupancy forecasting for single person offices is critical for energy efficient buildings which use predictive control techniques. Due to the highly uncertain nature of occupancy dynamics, the modeling and prediction of occupancy is a challenging problem. This paper proposes an algorithm for learning and predicting single occupant presence in office buildings, by considering the occupant behaviour as an ensemble of multiple Markov models at different time lags. This model has been tested using real occupancy data collected from PIR sensors installed in three different buildings and compared with state of the art methods, reducing the error rate by on average 5% over the best comparator method.

The Pareto dominance relation compares decisions with each other over multiple aspects, and any decision that is not dominated by another is called Pareto optimal, which is a desirable property in decision making. However, the Pareto dominance relation is not very discerning, and often leads to a large number of non-dominated or Pareto optimal decisions. By strengthening the relation, we can narrow down this nondominated set of decisions to a smaller set, e.g., for presenting a smaller number of more interesting decisions to a decision maker. In this paper, we look at a particular strengthening of the Pareto dominance called Sorted-Pareto dominance, giving some properties that characterise the relation, and giving a semantics in the context of decision making under uncertainty. We then examine the use of the relation in a Soft Constraints setting, and explore some algorithms for generating Sorted-Pareto optimal solutions to Soft Constraints problems.

A soft global constraint SOFTPREC has been proposed recently for solving optimisation problems involving precedence relations. In this paper we present new pruning rules for this global constraint. We introduce a pruning rule that improves propagation from the objective variable to the decision variables, which is believed to be harder to achieve. We further introduce a pruning rule based on linear programming, and thereby make SOFTPREC a hybrid of constraint programming and linear programming. We present results demonstrating the efficiency of the pruning rules.

A conversational recommender system iteratively shows a small set of options for its user to choose between. In order to select these options, the system may analyze the queries tried by the user to derive whether one option is dominated by others with respect to the user's preferences. This paper describes a framework for preference dominance. Two instances of the framework are developed for query suggestion in a conversational recommender system. The first instance of the framework is based on a basic quantitative preferences formalism, where products are compared using sums of weights of features. The second is a qualitative preference formalism, using a language that generalizes CP-nets, where models are a kind of generalized lexicographic order. A key feature of both methods is that deductions of preference dominance can be made efficiently, since this procedure needs to be applied for many pairs of products. We show that, by allowing the recommender to focus on undominated options, which are ones that the user is likely to be contemplating, both approaches can dramatically reduce the amount of advice the recommender needs to give to a user compared to what would be given by systems without this kind of reasoning.

Call control features (e.g., call-divert, voice-mail) are primitive options to which users can subscribe off-line to personalise their service. The configuration of a feature subscription involves choosing and sequencing features from a catalogue and is subject to constraints that prevent undesirable feature interactions at run-time. When the subscription requested by a user is inconsistent, one problem is to find an optimal relaxation, which is a generalisation of the feedback vertex set problem on directed graphs, and thus it is an NP-hard task. We present several constraint programming formulations of the problem. We also present formulations using partial weighted maximum Boolean satisfiability and mixed integer linear programming. We study all these formulations by experimentally comparing them on a variety of randomly generated instances of the feature subscription problem.

Modern feature-rich telecommunications services offer significant opportunities to human users. To make these services more usable, facilitating personalisation is very important since it enhances the users' experience considerably. However, regardless how service providers organise their catalogues of features, they cannot achieve complete configurability due to the existence of feature interactions. Distributed Feature Composition (DFC) provides a comprehensive methodology, underpinned by a formal architecture model to address this issue. In this paper we present an approach based on using Binary Decision Diagrams (BDD) to find optimal reconfigurations of features when a user's preferences violate the technical constraints defined by a set of DFC rules. In particular, we propose hybridizing constraint programming and standard BDD compilation techniques in order to scale the construction of a BDD for larger size catalogues. Our approach outperforms the standard BDD techniques by reducing the memory requirements by as much as five orders-of-magnitude and compiles the catalogues for which the standard techniques ran out of memory.

Telecommunication services are playing an increasing and potentially disruptive role in our lives. As a result, service providers seek to develop personalisation solutions that put customers in charge of controlling and enriching their services. In this context, the personalisation approach consists of exposing a catalogue of call control features (e.g., call-divert, voice-mail) to end-users and letting them subscribe to a subset of features subject to a set of precedence and exclusion constraints. When a subscription is inconsistent, the problem is to find an optimal relaxation. We present a constraint programming formulation to find an optimal reconfiguration of features. We investigate the performance of maintaining arc consistency within branch and bound search. We also study the impact of maintaining mixed consistency, that is maintaining different levels of consistency on different sets of variables. We further present a global constraint and a set of filtering rules that exploit the structure of our problem. We theoretically and experimentally compare all approaches. Our results demonstrate that the filtering rules of the global constraint outperform all other approaches when a catalogue is dense, and mixed consistency pays off when a catalogue is sparse.

We investigate the computational complexity of testing dominance and consistency in CP-nets. Previously, the complexity of dominance has been determined for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. In our main results, we show here that both dominance and consistency for general CP-nets are PSPACE-complete. We then consider the concept of strong dominance, dominance equivalence and dominance incomparability, and several notions of optimality, and identify the complexity of the corresponding decision problems. The reductions used in the proofs are from STRIPS planning, and thus reinforce the earlier established connections between both areas.

Most classical scheduling formulations assume a fixed and known duration for each activity. In this paper, we weaken this assumption, requiring instead that each duration can be represented by an independent random variable with a known mean and variance. The best solutions are ones which have a high probability of achieving a good makespan. We first create a theoretical framework, formally showing how Monte Carlo simulation can be combined with deterministic scheduling algorithms to solve this problem. We propose an associated deterministic scheduling problem whose solution is proved, under certain conditions, to be a lower bound for the probabilistic problem. We then propose and investigate a number of techniques for solving such problems based on combinations of Monte Carlo simulation, solutions to the associated deterministic problem, and either constraint programming or tabu search. Our empirical results demonstrate that a combination of the use of the associated deterministic problem and Monte Carlo simulation results in algorithms that scale best both in terms of problem size and uncertainty. Further experiments point to the correlation between the quality of the deterministic solution and the quality of the probabilistic solution as a major factor responsible for this success.

The integration of spatial datasets from different sources is becoming an increasingly important issue. It is very desirable to have a rigorous approach to integration, as an ad hoc approach can easily lead to incorrect inferences. This paper takes a formal approach, giving the beginnings of a logical semantics framework which allows meaning to be defined mathematically for spatial datasets which represent certain types of thematic map data. The basic idea is to interpret the datasets as summarizations of spatial variables, which are in turn interpreted as sets of possible worlds (ways the world could be). This semantics approach can give a formal meaning to pairs (or sets) of such datasets, which can then be used to determine the valid inferences from an integrated dataset.

This paper is a response to Michael Laviolette and John W. Seaman Jr.'s ( ibid. vol.2, no.1, p.4 (1994)) position paper "The efficacy of fuzzy representations of uncertainty," which criticizes fuzzy representations of uncertainty, and suggests that Bayesian probability can do better. The commenter argues that the author's make some misleading comments about Bayesian probability, and he briefly discusses the problem of giving a satisfactory interpretation of membership functions.>