Tri multicritère interactif basé sur le concept de regret : approches avec seuils de préférence ou profils de référence

Session : SS5-2 / SS5 : Foundations and algorithms for ranking systems
Vendredi 12 février 15:00 - 16:00 Salle : CI2-06
Nawal Benabbou, Patrice Perny et Paolo Viappiani

Dans le domaine de l’aide à la décision, les problèmes de tri constituent l’une des trois problématiques de références. Il s’agit d’affecter des alternatives à des catégories prédéfinies. Dans la littérature, on distingue deux familles de méthodes lorsque les alternatives sont évaluées sur plusieurs critères : avec seuils de préférence et avec profils de référence. Afin de déterminer la catégorie où doit être assignée une alternative, les deux approches précédentes utilisent une fonction d’agrégation modélisant l’importance relative des critères. Il est ainsi nécessaire de proposer des procédures d’élicitation permettant de déterminer les paramètres de la fonction d’agrégation (e.g. jeu de poids, capacité) représentant au mieux les préférences du décideur. Il convient alors de considérer une fonction d’agrégation paramétrée suffisamment expressive pour approximer au mieux les préférences du décideur. L’intégrale de Choquet est une fonction d’agrégation très appréciée dans le domaine de l’aide à la décision, notamment de par sa capacité à modéliser des synergies positives et négatives entre critères. Cependant, l’élicitation d’une intégrale de Choquet est rendue difficile par la nature de ses paramètres, ces derniers étant en nombre exponentiel (un paramètre par sous ensemble de critères). Nous proposons d’adapter aux problèmes de tri l’approche d’élicitation incrémentale basée sur la minimisation des regrets, initialement introduite pour les problèmes de choix. Cette approche consiste à restreindre progressivement l’espace des paramètres possibles, en posant itérativement des questions au décideur, jusqu’à déterminer la solution optimale pour le décideur (ou presque optimale, la garantie de performance étant donnée par les regrets). Nous commencerons par introduire deux nouvelles définitions de regrets, mieux adaptées aux problèmes de tri : une pour les méthodes avec seuils de préférence, une pour les méthodes avec profils de référence. Puis, nous montrerons comment le calcul de ces regrets peut se faire efficacement pour une intégrale de Choquet. Enfin, nous comparerons expérimentalement différentes stratégies de génération de questions.

Mots clés : décision multicritère, problèmes de tri, élicitation incrémentale