EXPLANATION IN RECOMMENDER SYSTEMS 187 that the recommendation dialogue is terminated only when the current query Q is such that r(Q)=r(e)for all possible extensions Q*of Q That is, the recommendation dialogue can be safely terminated only when it is certain that the recommendation will be the same no mat- ter how the user chooses to extend her query It may seem at first sight that testing the above condition for safe termination of the recommendation dialogue may require an exhaus- tive search over all possible extensions of the current query. How ever, McSherry(2003a)shows that it can be tested without relying on exhaustive search and with a computational cost that increases only linearly with the size of the case library. The criteria used in inn to recognise when the recommendation dialogue can be safely terminated are stated in the following theorem Theorem 2: The recommendation dialogue in iNN can be safely term nated if and only if the following conditions hold. L. any case that equals the similarity of the target case to the current uery has the same values as the target case for all remaining attri- butes 2. all cases that are less similar than the target case are dominated by Proof: See Appendix A Although expressed in terms of the target case in INN's goal-driven approach to attribute selection, the criteria identified in Theorem 2 are equivalent to the criteria we have shown to be essential to ensure that the recommendation dialogue can be safely terminated in any approach to attribute selection(McSherry 2003a) 3.5. Recommendation efficiency In previous work, we evaluated iNN in comparison with CCBR-PR algorithms based on a variety of different attribute-selection strategies (McSherry, 2003a). The performance measure of interest was mendation efficiency as measured by the average number of tions the user is asked before the final recommendation is made The algorithms compared differed only in their attribute-selection strategies, with termination of the recommendation dialogue basedEXPLANATION IN RECOMMENDER SYSTEMS 187 that the recommendation dialogue is terminated only when the current query Q is such that: r(Q∗ )=r(Q) for all possible extensions Q∗ of Q. That is, the recommendation dialogue can be safely terminated only when it is certain that the recommendation will be the same no mat￾ter how the user chooses to extend her query. It may seem at first sight that testing the above condition for safe termination of the recommendation dialogue may require an exhaus￾tive search over all possible extensions of the current query. How￾ever, McSherry (2003a) shows that it can be tested without relying on exhaustive search and with a computational cost that increases only linearly with the size of the case library. The criteria used in iNN to recognise when the recommendation dialogue can be safely terminated are stated in the following theorem. Theorem 2: The recommendation dialogue in iNN can be safely termi￾nated if and only if the following conditions hold: 1. any case that equals the similarity of the target case to the current query has the same values as the target case for all remaining attri￾butes, 2. all cases that are less similar than the target case are dominated by the target case. Proof: See Appendix A. Although expressed in terms of the target case in iNN’s goal-driven approach to attribute selection, the criteria identified in Theorem 2 are equivalent to the criteria we have shown to be essential to ensure that the recommendation dialogue can be safely terminated in any approach to attribute selection (McSherry 2003a). 3.5. Recommendation efficiency In previous work, we evaluated iNN in comparison with CCBR-PR algorithms based on a variety of different attribute-selection strategies (McSherry, 2003a). The performance measure of interest was recom￾mendation efficiency as measured by the average number of ques￾tions the user is asked before the final recommendation is made. The algorithms compared differed only in their attribute-selection strategies, with termination of the recommendation dialogue based