Numeric Estimation of Partial Utility Models for Automated Preference Interviewing

Many online systems today attempt to personalize their interaction with users. For example, electronic shops may want to provide decision support to users by recommending products, and portals may try to customize their content in a unique fashion for each user. Personalization requires a model of a user’s preferences, and in many cases, preferences are represented in the form of a utility function. Because it is difficult to elicit the information necessary to specify completely a user’s utility function, many online systems that employ user modeling must reason with partial utility models; for instance, an online recommender system might have to use incomplete information about a user’s preferences when choosing a product to suggest. Although a ranking of alternatives based on partial utility models cannot be certain, such a ranking can sometimes be beneficial. In that case, we require an easily interpretable numeric estimate of the utilities of alternatives. Existing systems that use numeric estimates of partial utility models have the problem that the estimates do not consistently improve in accuracy. Some sequences of questions that might be asked in order to elicit a user’s utility function can result in a final numeric estimate of an alternative that is actually more inaccurate than the starting estimate. We propose a simple means of numeric utility estimation that tracks the lower bound of a user’s utilities. Our defensive estimation technique has the advantages that it is guaranteed to improve in accuracy over time and that its estimates can be clearly understood by the user to represent the minimum utility of an alternative. These properties allow us to use an automated interview construction algorithm with full confidence that at termination the estimate of the user’s utility will be more accurate than at the beginning. The technique introduced in this paper also allows us to display a reasonable ranking of choices to the user at any point in an interview. In addition, we present a particular interview construction algorithm that, because of its use of our defensive utility estimation technique, is able to select the question that results in the greatest expected reduction in uncertainty of a partial utility model.