Description
Date depot: 26 mars 2019
Titre: Algorithmique des préférences structurées en décision collective : reconnaissance et optimisation
Directeur de thèse:
Olivier SPANJAARD (LIP6)
Directeur de thèse:
Bruno ESCOFFIER (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Une base de préférences consiste en la donnée d'un ensemble de vecteurs caractéristiques, décrivant des individus, et des préférences de ces individus sur un même ensemble d'objets, préférences exprimées sous la forme d'un rangement. Les préférences sont dites structurées si elles s'articulent autour d'une structure commune sur les objets. Par exemple, dans un contexte politique, il est classique de supposer que les préférences de chaque individu sont décroissantes lorsque l'on s'éloigne de son candidat préféré le long d'un axe gauche-droite sur les candidats, axe sur lequel les individus s'accordent tous. D'autres structures de préférences ont été proposées et étudiées : préférences unimodales sur un arbre, sur un cycle, préférences Euclidiennes... Cette thèse vise à étudier les structures de préférences du point de vue de l'algorithmique, tant au niveau de 1) la complexité de la reconnaissance d'une structure que de 2) la complexité de problèmes de vote ou d'allocation de ressources avec préférences structurées (problèmes de détermination d'un vainqueur, d'élection d'un comité, de couplages avec préférences, de partage équitable, etc.). 1) Même si divers travaux dans la littérature ont abordé le problème de la reconnaissance de structures, les structures de préférences étudiées, malgré leur pertinence théorique, se rencontrent rarement en pratique car elles supposent que les préférences vérifient des conditions très fortes. Une des directions de recherche de la thèse visera à remédier à cet inconvénient, par l'introduction d'une fonction objectif mesurant la distance à une structure. Des travaux récents existent dans cette direction, mais il reste beaucoup à faire. 2) Certains problèmes de décision collective qui sont NP-difficiles dans le cas général peuvent devenir de complexité polynomiale pour des structures particulières de préférences. Ce type de résultats est d'autant plus utile si les structures étudiées se rencontrent facilement en pratique. Il sera donc intéressant d'étudier si les structures proposées dans cette thèse permettent de réduire la complexité de certains problèmes de décision collective. De plus, quand bien même le statut de complexité d'un problème reste inchangé, il reste possible d'envisager de tirer parti d'une structure de préférences pour développer des algorithmes plus efficaces de résolution.
Doctorant.e: Tydrichova Magdaléna