Constructive preference elicitation

When faced with large or complex decision problems, human decision makers (DM) can make costly mistakes, due to inherent limitations of their memory, attention and knowledge. Preference elicitation tools assist the decision maker in overcoming these limitations. They do so by interactively learning the DM's preferences through appropriately chosen queries and suggesting high-quality outcomes based on the preference estimates. Most state-of-the-art techniques, however, fail in constructive settings, where the goal is to synthesize a custom or entirely novel configuration rather than choosing the best option among a given set of candidates. Many wide-spread problems are constructive in nature: customizing composite goods such as cars and computers, bundling products, recommending touristic travel plans, designing apartments, buildings or urban layouts, etc. In these settings, the full set of outcomes is humongous and can not be explicitly enumerated, and the solution must be synthesized via constrained optimization. In this paper we describe recent approaches especially designed for constructive problems, outlining the underlying ideas and their differences as well as their limitations. In presenting them we especially focus on novel issues that the constructive setting brings forth, such as how to deal with sparsity of the DM's preferences, how to properly frame the interaction, and how to achieve efficient synthesis of custom instances.status: accepte