Braziunas, Darius (University of Toronto) | Boutilier, Craig (University of Toronto)

The effective tailoring of decisions to the needs and desires of specific users requires automated mechanisms for preference assessment. 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.

Rational decision making requires full knowledge of the utility function of the person affected by the decisions. However, in many cases, the task of acquiring such knowledge is not feasible due to the size of the outcome space and the complexity of the utility elicitation process. Given that the amount of utility information we can acquire is limited, we need to make decisions with partial utility information and should carefully select which utility elicitation questions we ask. In this paper, we propose a new approach for this problem that utilizes a prior probability distribution over the person's utility function, perhaps learned from a population of similar people. The relevance of a utility elicitation question for the current decision problem can then be measured using its value of information. We propose an algorithm that interleaves the analysis of the decision problem and utility elicitation to allow these two tasks to inform each other. At every step, it asks the utility elicitation question giving us the highest value of information and computes the best strategy based on the information acquired so far, stopping when the expected utility loss resulting from our recommendation falls below a pre-specified threshold. We show how the various steps of this algorithm can be implemented efficiently.

Preference elicitation is a central problem in AI, and has received significant attention in single-agent settings. It is also a key problem in multiagent systems, but has received little attention here so far. In this setting, the agents may have different preferences that often must be aggregated using voting. This leads to interesting issues because what, if any, information should be elicited from an agent depends on what other agents have revealed about their preferences so far. In this paper we study effective elicitation, and its impediments, for the most common voting protocols.

Braziunas, Darius (University of Toronto) | Boutilier, Craig (University of Toronto)

Benabbou, Nawal (Université Pierre et Marie Curie - LIP6) | Perny, Patrice (Université Pierre et Marie Curie - LIP6)

The aim of this paper is to propose a new approach interweaving preference elicitation and search to solve multiobjective optimization problems. We present an interactive search procedure directed by an aggregation function, possibly non-linear (e.g. an additive disutility function, a Choquet integral), defining the overall cost of solutions. This function is parameterized by weights that are initially unknown. Hence, we insert comparison queries in the search process to obtain useful preference information that will progressively reduce the uncertainty attached to weights. The process terminates by recommending a near-optimal solution ensuring that the gap to optimality is below the desired threshold. Our approach is tested on multiobjective state space search problems and appears to be quite efficient both in terms of number of queries and solution times.