Prérequis : goût pour l'algorithmique et l'optimisation, intérêt pour le choix social computationnel.
Ce stage portera sur le problème de sériation et son application en choix social computationnel.
Le problème de sériation est apparu pour la première fois en archéologie, dans le but de déterminer une datation relative d'objets (fragments de poteries, outils en pierre...) trouvés sur divers sites. Formellement, étant donnée une matrice carrée M dont chaque composante Mij représente une mesure de similarité entre les objets i et j, il s'agit de trouver une permutation des indices des lignes et des colonnes de façon à ce que les valeurs croissent quand on s'éloigne de la diagonale. Des méthodes statistiques et des méthodes d'optimisation ont été proposées pour accomplir cette tâche, dans divers contextes.
L'objet de ce stage sera de tirer parti de ces méthodes pour résoudre un problème proche qui se pose en choix social computationnel : étant donnée une matrice de majorité, on cherche à identifier un axe qui fait sens (par exemple, un axe gauche-droite) sur les candidats.
Le stage comportera une partie d'état de l'art, où l'étudiant devra identifier les différentes méthodes qui ont été proposée pour le problème de sériation. Dans un deuxième temps, il s'agira d'étudier comment ces méthodes peuvent être adaptées au contexte de choix social computationnel qui nous intéresse ici. Enfin, dans un troisième temps, l'étudiant sera conduit à mener des expérimentations numériques sur des données réelles issues d'une librairie de préférences (Preflib).