Modèles graphiques pour le choix social computationnel

Par Olivier Spanjaard , 8 janvier, 2016

La théorie du choix social vise à étudier les propriétés de différentes procédures de vote. Formellement, une procédure de vote vise à agréger des préférences individuelles sur un ensemble de candidats en un rangement collectif de ces candidats. Pour les procédures de vote les plus connues, le rangement collectif est facile à calculer à partir des préférences individuelles. Néanmoins il existe de nombreuses autres procédures de vote pour lesquelles le calcul du rangement collectif est un problème difficile.

Un moyen de contourner cette difficulté est d'identifier des structures particulières dans les préférences des votants. Par exemple, si les préférences des votants sont "single-crossing", c'est-à-dire que les votants peuvent être triés de la gauche vers la droite en sorte que pour tout couple (a,b) de candidats, il existe un bloc de gauche de votants qui préfèrent a à b, et un bloc de droite de votants qui préfèrent b à a, alors le problème de déterminer le rangement collectif devient facile pour la plupart des procédures de vote "raisonnables".

L'objet de ce projet est, dans un premier temps, d'implanter en Python différents algorithmes permettant d'identifier des structures dans les préférences des votants, sous la forme de modèles graphiques. Le développement d'un outil de visualisation de ces modèles sera aussi demandé. Ces algorithmes seront testés sur des données réelles de vote issues de la librairie PrefLib. Dans un deuxième temps, en fonction de l'avancée du projet, il sera aussi possible d'implanter une ou plusieurs procédures de vote exploitant les structures identifiées sur les préférences des votants.

Les prérequis sont un bon niveau en algorithmique et en optimisation combinatoire (UEs MOGPL et/ou COMPLEX). La connaissance du langage Python serait aussi appréciée.

Encadrant
Olivier Spanjaard
Nombre d'étudiants
2
Attribué
Oui
Obsolète
Non
Tags