Cassandre Leroy  

We are currently working on preference elicitation problems on combinatorial domains. We are at the intersection between algorithmic decision theory and artificial intelligence. In algorithmic decision theory, we are interested in the formal modeling of preferences and the efficient resolution of decision problems. We use heuristic procedures and learning from artificial intelligence to recommend a solution.

In particular, we are interested in problems where solutions are represented by n-dimensional vectors. All solutions are represented by this performance vector.

To determine the value of a multi-criteria solution there is a rich literature that proposes different aggregators depending on the type of behavior that we want to translate. Indeed, if we want to express equality, we will use OWA with descreasing weights, but it's a comprise we will use weighted sum. The common point between all these models is that they are parameterizable and this parameter allows us to adapt the model to the decision-maker's preferences.

The classical approach in elicitation is to learn, through a history and therefore a database, the best possible parameters. We wanted to learn the parameter in order to solve the problem afterwards. However, there were two problems: a high sensitivity of the parameters and parameters that were difficult to determine precisely.

The recent approach we use here is that we do not want to learn the parameters exactly. Instead of looking for the weight set that exactly represents the decision maker's preferences, we will try to reduce the space of the weight sets sufficiently until we find the best solution for the decision maker. To make decisions with partial preference information, we use a méthod based on minimax regret criterion.

All the solutions are defined implicitly, because we are on combinatorial domain, we cannot enumerate them all but we know the conditions to define a solution. They are also too numerous to compare them all. The purpose of this thesis is to combine heuristic research and active learning to determine the decision maker's preferences. This allows us to attack difficult combinatorial problems that do not necessarily have an efficient algorithm for solving them. For example, in the figure above we can see a resolution of travelling salesman problem for 100 cities and 2 criteria. The decision maker is modeled by a weighted sum. We can see how the heuristic, in this case a local search, allows to approach, or return, the optimal solution of the decision maker.