Urszula Chajewska, Daphne Koller, and Ronald Parr, Stanford University
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 making decisions based on limited utility information, and for targetting our utility elicitation process so as to lead to a good decision using a small number of questions. Our approach is based on the idea that we have 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 then computes the best strategy based on the information acquired so far. The process continues until the expected utility loss resulting from our (possibly suboptimal) recommendation falls below a pre-specified threshold. We show how the various steps of this algorithm can be implemented efficiently.