logo EDITE Sujets de doctorat

Procedures incrémentales et algorithmes pour la décision collective

Sujet proposé par
Directeur de thèse:
Encadré par
Doctorant: Margot CALBRIX
Unité de recherche UMR 7606 Laboratoire d'informatique de Paris 6

Domaine: Sciences et technologies de l'information et de la communication

Projet

Le contexte de la thèse concerne les aspects computationnels de la décision collective sur domaine combinatoire. De nombreuses procédures de vote ont été proposées en théorie du Choix Social et leurs propriétés sont assez bien connues. En revanche, dès lors que l'ensemble des solutions potentielles a une structure combinatoire et est défini de manière implicite, la mise en oeuvre efficace de ces procédures pose de multiples problèmes liés à la représentation compacte des préférences, à leur élicitation, et au calcul des décisions optimales. En particulier, dans de tels problèmes il est souvent difficile d'obtenir une information complète sur les préférences des individus qui ne peuvent ou ne veulent expliciter l'intégralité de leur préférences. On doit donc travailler avec une information partielle qu'il convient d'enrichir progressivement jusqu'à pouvoir déterminer avec une confiance suffisante la ou les solutions optimales. Dans ce cadre, l'apport des approches incrémentales développées actuellement en IA pour la décision collective consiste à permettre une décision rapide en cherchant à minimiser l'effort d'élicitation et de communication des agents. L'objet de cette thèse est de développer des modèles et des algorithmes pour traiter ces problèmes.

Enjeux

Les procédures de décision collectives sont au coeur de multiples applications (e.g. systèmes de recommandation ou de configuration interactifs, allocation de ressources, élection de comités et sélection de projets, commerce électronique, vote électronique et démocratie participative). Leur conception et leur mise en œuvre réelle pose des problèmes nouveaux de représentation des préférences, de décision avec information partielle, et d'algorithmique discrète. Dans cette thèse, on envisage d'aborder tout ou partie des points suivants :

- conception de nouvelles procédure de décision collective et étude de leur propriétés axiomatiques

- détermination des solutions potentiellement optimales ou nécessairement optimales en vote combinatoire

- élaboration de procédures d'élicitation incrémentales efficaces pour la décision collective

- études de procédures à bas coût de communication pour la décision collective

- vote combinatoire sous incertitude

Ouverture à l'international

Cette thèse s'inscrit dans le cadre du choix social computationnel, un domaine qui connait actuellement une vive activité au niveau international, visible grâce à la montée du workshop international COMSOC, mais aussi à la présence toujours plus importante de cette thématique dans les conférences internationales généralistes en Intelligence Artificielle (AAMAS, IJCAI, AAAI, ECAI). Ce domaine est aussi très présent dans le GDR international ALGODEC (Algorithmique Decision Theory) et dans l'ANR CoCoRICo-CoDec (2014-2018), deux actions dans lesquelles le département DESIR du LIP6 est largement impliqué. De plus, une action COST récente sur le thème du choix social computationnel a favorisé le développement cette thématique en Europe ces dernières années. L'étudiant impliqué aura donc la possibilité d’interagir avec diverses équipes actives sur cette thématique au plan international.

Remarques additionnelles

Ce sujet convient particulièrement à un étudiant ayant effectué un master en Aide à la décision, Intelligence Artificielle,ou Recherche Opérationnelle.