CONTEXT: Preference elicitation on combinatorial domains is a challenging issue for supporting individual or collective decision making. In combinatorial optimization problems, systematic elicitation methods aiming at fully specifying a preference model are not feasible due to the large amount of solutions. Hence one often has to make a decision with incomplete preferences. Even when the Decision Maker is available to answer some preference queries, the elicitation burden must be kept as low as possible. Fortunately, very often, an optimal solution can be identified without knowing the model precisely. This explains the interest for incremental elicitation procedures, in which preference queries are selected iteratively, to be as informative as possible at every step, so as to progressively reduce the set of admissible parameters of the preference model, until an optimal solution can be determined. This approach which has been successfully applied for decision making on explicit sets in various contexts, is harder to implement on implicit sets. The aim of the internship is to participate to the study currently developed on this topic in the decision team at LIP6 and to develop new procedures.</li>
OBJECTIVES: Several problems may be considered. First, given an incomplete set of preference statements, we may study the determination of possibly and necessary optimal solutions relatively to specific models used in decision theory and/or social choice. The determination of a possibly optimal solution can be first investigated on explicit sets of solutions, but the aim is to propose algorithms able to compute possibly optimal solutions on combinatorial sets of alternatives. Then, another problem which is even more in the core of the ongoing study concerns the elaboration and test of new algorithms interleaving elicitation with search to support individual or collective decision making in preference-based optimization problems. This problem can be studied in various contexts such as multicriteria decision support, fair multiagent optimization, and/or robust optimization. Finally, there are contexts in which the preference information cannot be obtained upon request but is progressively revealed by a flow of preference statements arriving randomly. In this last context, it may be interesting to investigate how general search procedures can be adapted to provide online algorithms able to determine dynamically the possibly optimal solutions. The task of the student will not consists of addressing all these lines of research but some of them will be selected to study solution algorithms on particular preference-based optimization problems. </li>