Le 09/12/2020 par meltem.ozturk :

Encadrants (contacts):  - Hugo Gilbert (LAMSADE-CNRS, Université Paris-Dauphine) :  <hugo.gilbert@dauphine.psl.eu> - Meltem Öztürk (LAMSADE-CNRS, Université Paris-Dauphine): <meltem.ozturk@lamsade.dauphine.fr> - Olivier Spanjaard (LIP6-CNRS, Sorbonne Université): <olivier.spanjaard@lip6.fr>     Lieu : Laboratoire d'Informatique de Paris 6. (ou Laboratoire d'Analyse et de Modélisation de Systèmes pour l'Aide à la Décision, Dauphine.)   Durée du stage : 6 mois (demarrage en fevrier, mars ou avril 2021)   Domaines : Recherche opérationnelle, intelligence artificielle et aide a la decision   Compétences du candidat : connaissances en théorie de la décision, algorithmique et programmation   Sujet : Dans de multiples applications, on est amené à comparer des ensembles d'objets pour prendre des décisions, par exemple pour constituer des équipes (en sport, en politique, ...), pour configurer des produits technologiques, pour comparer des ensembles de critères en analyse multicritère, ... Il est classique en aide à la décision et en recherche opérationnelle d'assigner une valeur numérique (utilité, score, …) à chaque élément, puis de comparer les sommes des valeurs numériques de ces éléments. Cette hypothèse est néanmoins forte car une telle information n'est pas toujours disponible de façon précise, et le choix d'un ensemble d'éléments plutôt que d'un autre est fortement sensible à des petites variations dans les valeurs numériques attribuées. Dans ce stage, nous nous intéresserons à des règles de dominance ordinale ne s'appuyant pas sur des valeurs numériques précises attribuées aux éléments, mais seulement sur une relation d'ordre (éventuellement partielle).   Objectif : Dans un premier temps, il s'agira d'étudier les propriétés de ces règles d'un point de vue axiomatique (par exemple, les règles sont-elles bien transitives ?) et d'un point vue algorithmique (est-il possible de comparer deux ensembles A et B en temps polynomial du nombre d'éléments de A et B ? Est-ce au contraire NP-complet ?). On s'intéressera ensuite à des aspects d'optimisation : étant donné une relation d'ordre sur les singletons et les paires, quelles sont les solutions non-dominées ? Enfin, on envisagera le problème inverse : en faisant l'hypothèse qu'un modèle de dominance donné a été employé pour comparer les ensembles, peut-on reconstituer la relation d'ordre sur les singletons et les paires à partir d'informations sur les dominances entre ensembles ? Ces travaux s'accompagneront d'expérimentations numériques sur des données synthétiques et/ou réelles (par exemple, des données issues de sports collectifs).     Plus de détails:   Règles de dominance ordinale.  Une règle de dominance ordinale couramment étudiée dans la littérature consiste à considérer qu'un ensemble A domine un ensemble B s'il existe une injection de B vers A telle qu'à chaque élément de B on peut associer un élément de A qui lui est préféré. Cette règle, qui peut être vue comme une contrepartie ordinale de l'opération de somme, ne permet toutefois pas de modéliser des interactions positives ou négatives entre éléments.   Notre approche.  Une façon d'y remédier est de supposer une information plus riche au départ, en considérant que l'on dispose d'une relation d'ordre qui porte à la fois sur les singletons et les paires d'éléments. Par exemple, pour un ensemble {1, ...,10} d'éléments, la relation d'ordre serait de la forme {1,2} > {3} > {4,5} > {1} > {2}>...  Différentes règles peuvent alors être envisagées pour étendre cette relation d'ordre à des ensembles d'éléments de cardinal quelconque : - La règle de dominance ordinale décrite plus haut peut à nouveau être employée en comparant un ensemble A à un ensemble B sur la base de tous les singletons et les paires inclus dans A et inclus dans B. - Un ensemble A domine un ensemble B s'il existe une partition PA de A et une partition PB de B en singletons et paires et une injection de PB vers PA telle qu'à chaque élément (singleton ou paire) de PB on peut associer un élément de PA qui lui est préféré. - Un ensemble A domine un ensemble B si pour toute assignation de valeurs numériques aux singletons et aux paires d'éléments la somme des valeurs des singletons et des paires de A est plus grande que la somme des valeurs pour B.     Références Salvador Barbera, Walter Bossert, and Prasanta K. Pattanaik. Ranking  sets of objects.  In S. Barbera, P.J. Hammond, and Ch. Seidl,  editors, Handbook of Utility Theory, volume 2. Kluwer Academic Publishers,  2004.   Edwin M Bartee.  Problem solving with ordinal measurement. Management  Science, 17(10):B–622, 1971.   Nawal Benabbou, Patrice Perny, and Paolo Viappiani. Incremental  elicitation of Choquet capacities for multicriteria choice, ranking and  sorting problems. Artificial Intelligence, 246:152–180, 2017.   Michel Grabisch, Jean-Luc Marichal, Radko Mesiar, and Endre Pap.  Aggregation Functions. Camb. U. Press, 2009.   Eyke Hüllermeier and Ali Fallah Tehrani. Efficient learning of  classifiers based on the 2-additive Choquet integral. In Comp.  Intelligence in Intelligent Data Analysis, pages 17–29. Springer, 2013.   Pedro Miranda, Elias F. Combarro, and Pedro Gil. Extreme points of some  families of nonadditive measures. European Journal of Operational  Research, 174(3):1865–1884, 2006.   Luca E Schäfer, Tobias Dietz, Maria Barbati, José Rui Figueira,  Salvatore Greco, and Stefan Ruzika.  The binary knapsack problem with  qualitative levels. European Journal of Operational Research, 2020