Conversational recommendation: Theoretical model and complexity analysis

Recommender systems help users find items of interest in situations of information overload in a personalized way, using needs and preferences of individual users. In conversational recommendation approaches, the system acquires needs and preferences in an interactive, multi-turn dialog. This is usually driven by incrementally asking users about their preferences about item features or individual items. A central research goal in this context is efficiency, evaluated concerning the number of required interactions until a satisfying item is found. Today, research on dialog efficiency is almost entirely empirical, aiming to demonstrate, for example, that one strategy for selecting questions to ask the user is better than another one in a given application. This work complements empirical research with a theoretical, domain-independent model of conversational recommendation. This model, designed to cover a range of application scenarios, allows us to investigate the efficiency of conversational approaches in a formal way, particularly concerning the computational complexity of devising optimal interaction strategies. An experimental evaluation empirically confirms our findings.