Interactive assessment of user preference models: The automated Travel assistant Greg Linden, Steve Hanks, Neal Lesh Department of Computer Science and Engineering, University of Washington, Seattle, WA, USA Abstract: This paper presents the candidate/critique model of interactive problem solving, which an automated problem solver communicates candidate solutions to the user and the user critiques those solutions. The system starts with minimal information about the user's preferences, and preferences are elicited and inferred incrementally by analyzing the critiques. The system's goal is to present"good"candidates to the user, but to do so it must learn as much as possible about his preferences in order to improve its choice of candidates in subsequent iterations. This system contrasts with traditional decision- analytic and planning frameworks in which a complete model is elicited beforehand or constructed by a human expert. The paper presents the Automated Tranel Assistant, an implemented prototype of the model that interactively builds flight itineraries using real ime airline information. The ata is available on the world wide web and has had over 4000 users between May and October 1996 1 Introduction Building an accurate user model is essential to decision making and decision-support tasks,a model of the user s preferences is required to make good decisions or to suggest good alternatives. Representations for preference models have been studied extensively in the literature on multi-attribute utility theory (e.g. Keeney and Raiffa, 1976), which provides compact representations and elicitation techniques for preference models, but generally assumes that the model is built by a human expert. Problem solvers like Al planning algorithms generall assume that the complete preference model is provided as an input, but this is not a good approach to interactive problem solving in complex domains. Ahead-of-time elicitation demands a tremendous amount of information from the user, most of which will be irrelevant to solving the particular problem at hand. An alternative approach has been to infer a user model automatically over multiple interactions with the user that is used to support decision making and information filtering(e.g. Thomas and Fischer, 1996, McCalla et al., 1996, and Mukhopadhyay nd Mostafa, 1996). But, there is also a class of problems for which a user model must be built up quickly and without previous problem-solving episodes, thus requiring the direct participati of the user. Consider, for example, the following interaction between a travel agent and a client This work was supported in part by ARPA/Rome Labs grant F30602-95-1-0024. Thanks to Oren Etzioni, Dan Weld, Adam Carlson, Marc Friedman, Keith Golden, Nicholas Kushmerick, and the anonymous reviewers for good comments and suggestionInteractive Assessment of User Preference Models: The Automated Travel Assistant Greg Linden, Steve Hanks, Neal Lesh * Department of Computer Science and Engineering, University of Washington, Seattle, WA, USA Abstract: This paper presents the candidate/critique model of interactive problem solving, in which an automated problem solver communicates candidate solutions to the user and the user critiques those solutions. The system starts with minimal information about the user’s preferences, and preferences are elicited and inferred incrementally by analyzing the critiques. The system’s goal is to present “good” candidates to the user, but to do so it must learn as much as possible about his preferences in order to improve its choice of candidates in subsequent iterations. This system contrasts with traditional decision￾analytic and planning frameworks in which a complete model is elicited beforehand or is constructed by a human expert. The paper presents the Automated Travel Assistant, an implemented prototype of the model that interactively builds flight itineraries using real￾time airline information. The ATA is available on the World Wide Web and has had over 4000 users between May and October 1996. 1 Introduction Building an accurate user model is essential to decision making and decision-support tasks; a model of the user' s preferences is required to make good decisions or to suggest good alternatives. Representations for preference models have been studied extensively in the literature on multi-attribute utility theory (e.g. Keeney and Raiffa, 1976), which provides compact representations and elicitation techniques for preference models, but generally assumes that the model is built by a human expert. Problem solvers like AI planning algorithms generally assume that the complete preference model is provided as an input, but this is not a good approach to interactive problem solving in complex domains. Ahead-of-time elicitation demands a tremendous amount of information from the user, most of which will be irrelevant to solving the particular problem at hand. An alternative approach has been to infer a user model automatically over multiple interactions with the user that is used to support decision making and information filtering (e.g. Thomas and Fischer, 1996, McCalla et al., 1996, and Mukhopadhyay and Mostafa, 1996). But, there is also a class of problems for which a user model must be built up quickly and without previous problem-solving episodes, thus requiring the direct participation of the user. Consider, for example, the following interaction between a travel agent and a client: ——— * ———— This work was supported in part by ARPA/Rome Labs grant F30602-95-1-0024. Thanks to Oren Etzioni, Dan Weld, Adam Carlson, Marc Friedman, Keith Golden, Nicholas Kushmerick, and the anonymous reviewers for good comments and suggestions