3.1 Design Principles The overall objective of the system is to help the user find an optimal solution quickly Hypothetically, presenting the optimal solution for the user immediately would clearly lead to a short, high-quality interaction, but the CCAs user model is initially only a very rough approximation of the user's true preferences and, as such, will not typically generate the optimal solution with respect to the user's true preferences In general, there are two ways to generate a short, high-quality interaction: Find a solution that satisfies the user during this iteration of the interaction and present information to the user that increases the likelihood of generating a satisfactory solution in a future iteration. The former can be implemented by optimizing over preferences and requires an accurate user model. The latter involves providing information that allows the user to evaluate the solutions, understand what types of solutions are available, and express additional preferences, refining the user model Our technique combines both of these approaches. The system has three goals in terms of resent Suggest solutions that are optimal or near-optimal with respect to the user preferences Inform the user of the full range of available solutions Present solutions that allow the CCa to learn more about the users preferences and update the user model Note that these three goals can often be in conflict. Suggesting optimal and near-optimal solutions can allow the user to end the interaction very quickly if the user model is accurate, but these solutions may not provide information about the range of options or motivate the user to provide additional preference information. Providing information about the range of available options allows the user to determine what better solutions are available and what the tradeoffs are between solutions, but these solutions are often sub-optimal. For example, in the travel domain, presenting the user with a $00 round-trip from Seattle to Chicago is meaningless unless the user has some information about the range of prices among all flights. Eliciting additional preference information may require presenting"highly critiqueable" solutions that are not optimal. In th next section, we discuss the problem of selecting solutions that satisfy these three goals 3.2 Algorithm In this section, we describe the CCa algorithm that uses the partial user model to sugges possible solutions to the user. We describe the CCa by first presenting a simple algorithm and then presenting a series of four improvements to this algorithm A straightforward CCA would simply rank all possible solutions according the stated preferences and display the top choices, selecting arbitrarily if the preferences did not provide a total order. For example, in the travel domain, if the user indicated that he wanted to a one-way flight from Seattle to Newark on January 2, this CCA would arbitrarily choose a few of the hundreds of available flights between those two cities on that day. If the user then stated a preference for cheaper flights, this CCa would display a few of the cheapest flights Will this approach work? As long as the user continues to state and refine constraints that reflect his true preferences, the user model will eventually converge to an accurate model of the users preferences. Thus, the CCa will eventually suggest the solution that optimally satisfies the3.1 Design Principles The overall objective of the system is to help the user find an optimal solution quickly. Hypothetically, presenting the optimal solution for the user immediately would clearly lead to a short, high-quality interaction, but the CCA’s user model is initially only a very rough approximation of the user’s true preferences and, as such, will not typically generate the optimal solution with respect to the user’s true preferences. In general, there are two ways to generate a short, high-quality interaction: Find a solution that satisfies the user during this iteration of the interaction and present information to the user that increases the likelihood of generating a satisfactory solution in a future iteration. The former can be implemented by optimizing over preferences and requires an accurate user model. The latter involves providing information that allows the user to evaluate the solutions, understand what types of solutions are available, and express additional preferences, refining the user model. Our technique combines both of these approaches. The system has three goals in terms of presenting solutions to the user: – Suggest solutions that are optimal or near-optimal with respect to the user preferences. – Inform the user of the full range of available solutions. – Present solutions that allow the CCA to learn more about the user’s preferences and update the user model. Note that these three goals can often be in conflict. Suggesting optimal and near-optimal solutions can allow the user to end the interaction very quickly if the user model is accurate, but these solutions may not provide information about the range of options or motivate the user to provide additional preference information. Providing information about the range of available options allows the user to determine what better solutions are available and what the tradeoffs are between solutions, but these solutions are often sub-optimal. For example, in the travel domain, presenting the user with a $300 round-trip from Seattle to Chicago is meaningless unless the user has some information about the range of prices among all flights. Eliciting additional preference information may require presenting “highly critiqueable” solutions that are not optimal. In the next section, we discuss the problem of selecting solutions that satisfy these three goals. 3.2 Algorithm In this section, we describe the CCA algorithm that uses the partial user model to suggest possible solutions to the user. We describe the CCA by first presenting a simple algorithm and then presenting a series of four improvements to this algorithm. A straightforward CCA would simply rank all possible solutions according the stated preferences and display the top choices, selecting arbitrarily if the preferences did not provide a total order. For example, in the travel domain, if the user indicated that he wanted to a one-way flight from Seattle to Newark on January 2, this CCA would arbitrarily choose a few of the hundreds of available flights between those two cities on that day. If the user then stated a preference for cheaper flights, this CCA would display a few of the cheapest flights. Will this approach work? As long as the user continues to state and refine constraints that reflect his true preferences, the user model will eventually converge to an accurate model of the user’s preferences. Thus, the CCA will eventually suggest the solution that optimally satisfies the