Dubus, Jean-Philippe (Université Paris 6) | Gonzales, Christophe (Université Paris 6) | Perny, Patrice (Université Paris 6)

This paper deals with Decision-Making in the context of multiattribute utility theory and, more precisely, with the problem of efficiently determining the best alternative w.r.t. an agent's preferences (choice problem). We assume that alternatives are elements of a product set of attributes and that the agent's preferences are represented by a generalized additive decomposable (GAI) utility on this set. Such a function allows an efficient representation of interactions between attributes while preserving some decomposability of the model. GAI utilities can be compiled into graphical structures called GAI networks that can be exploited to solve choice problems using collect/distribute schemes essentially similar to those used in Bayesian networks. In this paper, rather than directly using this scheme on the GAI network for determining the most preferred alternative, we propose to work with another GAI function, acting as an upper-bound on utility values and enhancing the model's decomposability. This method still provides the exact optimal solution but speeds up significantly the search. It proves to be particularly useful when dealing with choice and ranking under constraints and within collective Decision-Making, where GAI nets tend to have a large size. We present an efficient algorithm for determining this new GAI function and provide experimental results highlighting the practical efficiency of our procedure.

We consider a set of alternatives having a combinatorial structure. We assume that preferences are compactly represented by graphical utility models derived from generalized additive decomposable (GAI) utility functions. Such functions enable to model interactions between attributes while preserving some decomposability property. We address the problem of finding a compromise solution from several GAI utilities representing different points of view on the alternatives. This scheme can be applied both to multicriteria decision problems and to collective decision making problems over combinatorial domains. We propose a procedure using graphical models for the fast determination of a Pareto-optimal solution achieving a good compromise between the conflicting utilities. The procedure relies on a ranking algorithm enumerating solutions according to the sum of all the GAI utilities until a boundary condition is reached. Numerical experiments are provided to highlight the practical efficiency of our procedure.

Any automated decision support software must tailor its actions or recommendations to the preferences of different users. Thus it requires some representation of user preferences as well as a means of eliciting or otherwise learning the preferences of the specific user on whose behalf it is acting. While additive preference models offer a compact representation of multiattribute utility functions, and ease of elicitation, they are often overly restrictive. The more flexible generalized additive independence (GAI) model maintains much of the intuitive nature of additive models, but comes at the cost of much more complex elicitation. In this article, we summarize the key contributions of our earlier paper (UAI 2005): (a) the first elaboration of the semantic foundations of GAI models that allows one to engage in preference elicitation using local queries over small subsets of attributes rather than global queries over full outcomes; and (b) specific procedures for Bayesian preference elicitation of the parameters of a GAI model using such local queries.

Dubus, Jean-Philippe (Université Paris 6) | Gonzales, Christophe (Université Paris 6) | Perny, Patrice (Université Paris 6)

This paper deals with multiobjective optimization in the context of multiattribute utility theory. The alternatives (feasible solutions) are seen as elements of a product set of attributes and preferences over solutions are represented by generalized additive decomposable (GAI) utility functions modeling individual preferences or criteria. Due to decomposability, utility vectors attached to solutions can be compiled into a graphical structure closely related to junction trees, the so-called GAI net. We first show how the structure of the GAI net can be used to determine efficiently the exact set of Pareto-optimal solutions in a product set and provide numerical tests on random instances. Since the exact determination of the Pareto set is intractable in worst case, we propose a near admissible algorithm with performance guarantee, exploiting the GAI structure to approximate the set of Pareto optimal solutions. We present numerical experimentations, showing that both utility decomposition and approximation significantly improve resolution times in multiobjective search problems.

We provide a brief overview of recent direct preference elicitation methods: these methods ask users to answer (ideally, a small number of) queries regarding their preferences and use this information to recommend a feasible decision that would be (approximately) optimal given those preferences. We argue for the importance of assessing numerical utilities rather than qualitative preferences and survey several utility elicitation techniques from artificial intelligence, operations research, and conjoint analysis. Specifically, since the ability to make reasonable decisions on behalf of a user depends on that user's preferences over outcomes in the domain in question, AI systems must assess or estimate these preferences before making decisions. Designing effective preference assessment techniques to incorporate such user-specific considerations (that is, breaking the preference bottleneck) is one of the most important problems facing AI. In this brief survey, we focus on explicit elicitation techniques where a system actively queries a user to glean relevant preferences. Preference elicitation is difficult for two main reasons. First, many decision problems have exponentially sized outcome spaces, defined by the possible values of outcome attributes. As an illustrative example, consider sophisticated flight selection: possible outcomes are defined by attributes such as trip cost, departure time, return time, airline, number of connections, flight length, baggage weight limit, flight class, (the possibility of) lost luggage, flight delays, and other stochastic outcomes. An ideal decision support system should be able to use, for example, precise flight delay statistics and incorporate a user's relative tolerance for delays in making recommendations. Representing and eliciting preferences for all outcomes in a case like this is infeasible given the size of the outcome space. A second difficulty arises due to the fact that quantitative strength of preferences, or utility, is needed to trade off, for instance, the odds of flight delays with other attributes. Unfortunately, people are notoriously inept at quantifying their preferences with any degree of precision, adding to the challenges facing automated utility elicitation.