Le choix social computationnel vise à revisiter les problématiques étudiées en théorie du choix social, en adoptant le point de vue de l'informaticien. La théorie du choix social porte sur l'étude de l'agrégation de préférences individuelles en une préférence collective. L'ensemble des préférences individuelles est appelé profil de préférences dans la suite, chaque préférence individuelle étant exprimée sous la forme d'un rangement des candidats. Quelques exemples de questions étudiées en choix social computationnel : étant donnés un profil de préférences et une distance entre deux rangements, est-il facile de déterminer un rangement médian ? (Un rangement est dit médian s'il minimise la somme des distances aux préférences du profil.) Etant donné un profil de préférences, est-il facile d'identifier une structure dans les préférences des votants ? (La structure la plus connue est celle des préférences unimodales, c'est-à-dire des préférences compatibles avec un axe gauche-droite sur les candidats.) Afin d'évaluer sur des données réelles les contributions en choix social computationnel, une librairie nommée PrefLib (http://www.preflib.org/) est disponible en ligne, qui regroupe diverses données préférentielles réelles (votes à une élection, préférences sur des sushis...). Mentionnons également l'existence d'une interface web permettant de réaliser des sondages et d'illustrer différentes procédures de vote, nommée Whale 3 (http://strokes.imag.fr/whale3/).
De multiples procédures et concepts étudiés en théorie du choix social, et donc également en choix social computationnel, s'appuient sur le graphe de majorité. Le graphe de majorité est un graphe où chaque sommet correspond à un candidat, et un arc (x,y) existe si une majorité de votants préfèrent x à y. De façon surprenante, la généralisation de l'idée de graphe de majorité en un ensemble de fonctions de choix a été très peu étudiée. Une fonction de choix est une fonction d'ensemble, qui, étant donné un sous-ensemble de candidats, retourne le candidat préféré dans ce sous-ensemble. Le graphe de majorité peut être vu comme l'ensemble des fonctions de choix sur des couples de candidats. Le graphe de majorité sur m candidats est donc une façon d'encoder m(m-1)/2 fonctions de choix (une par couple de candidats). A partir d'un profil de préférences sur m candidats, on peut pourtant inférer 2^m fonctions de choix (définissant un hypergraphe de majorité), en utilisant par exemple la règle de la pluralité : le candidat préféré d'un sous-ensemble est celui placé le plus souvent par les votants en première position de ce sous-ensemble. L'information encodée par l'hypergraphe de majorité est plus riche que le simple graphe de majorité, mais plus synthétique que le profil complet de préférences.
L'objet de ce stage sera de s'appuyer sur cet hypergraphe de majorité pour définir des règles d'agrégation des préférences et/ou des structures de préférences, et évaluer la complexité algorithmique de leur mise en oeuvre/reconnaissance. Ainsi, les questions suivantes pourront être abordées : quel est le rangement médian pour l'hypergraphe de majorité ? Ce rangement médian est-il facile à déterminer ? Comment définir une structure sur les préférences, analogue aux préférences unimodales, qui se formulerait à l'aide d'une propriété sur l'hypergraphe de majorité ? Etant donné un profil de préférences, est-il facile de reconnaître cette structure ?
Afin d'évaluer si ces méthodes et concepts sont pertinents sur des données réelles, des tests seront menés sur des benchmarks issues de la librairie PrefLib (mentionnée plus haut). Enfin, selon l'évolution et la direction que prendra le stage, une intégration des outils développés dans la plate-forme Whale 3 (mentionnée plus haut) pourra être envisagée.
Ce stage s'adresse à un(e) étudiant(e) intéressé(e) par la décision et l'algorithmique pour l'intelligence artificielle et la recherche opérationnelle. Les outils formels utilisés seront en lien avec les UEs MOGPL, RP et COMPLEX en M1, et l'UE MADMC en M2.
Ce stage se déroulera dans l'équipe Décision du LIP6 et sera financé par le projet ANR CoCoRICo-CoDec (Calcul, Communication, Rationalité et Incitations en Décision Collective et Coopérative).