Solution generation with qualitative models of preferences

We consider automated decision aids that help users select the best solution from a large set of options. For such tools to successfully accomplish their task, eliciting and representing users' decision preferences is a crucial task. It is usually too complex to get a complete and accurate model of their preferences, especially regarding the trade-offs between different criteria. We consider decision aid tools where users specify their preferences qualitatively: they are only able to state the criteria they consider, but not the precise numerical utility functions. For each criterion, the tool provides a standardized numerical function that is fixed and identical for all users and used to compare solutions. To compensate for the imprecision of this qualitative model, we let the user choose among a displayed set of possibilities rather than a single optimal solution. We consider the probability of finding the most preferred solution as a function of the number of displayed possibilities and the number of preferences. We present a probabilistic analysis, empirical validation on randomly generated configuration problems and a commercial application. We provide mathematical principles for the design of the selection mechanism, guaranteeing that users are able to find the target solution.