– ComSoc

La théorie du choix social est une branche déjà classique de la théorie économique. Depuis quelques années, la communauté des informaticiens s?est saisie de ces mêmes problèmes avec une préoccupation plus algorithmique. L?importance de ces préoccupations tient au fait que la plupart des résultats classiques en théorie du choix social sont génériques, traitant de la décision collective de manière relativement indépendante de objet de la décision, de la taille du groupe devant prendre une décision et de la nature des objets à évaluer. Ces éléments deviennent essentiels dès lors, par exemple, que l?ensemble des objets à évaluer a une structure combinatoire. Une telle structure interdit de recueillir les préférences individuelles de manière naïve et soulève de délicats problèmes algorithmiques pour ce qui concerne la phase d?agrégation. La communauté française en théorie du choix social est en bonne place au niveau international (la revue Social Choice and Welfare est pilotée par un français). De même la communauté des informaticiens travaillant sur des questions algorithmiques en intelligence artificielle est également en bonne position au niveau international. La France devrait donc être en bonne place pour contribuer à un domaine en plein essor depuis quelques années : le choix social computationnel. Malheureusement ces deux communautés ont peu l?occasion de se rencontrer et, encore moins, d?élaborer des projets communs. Le but de ce projet est de structurer au niveau français ce champ en pleine émergence, en favorisant un travail pluridisciplinaire autour des problèmes algorithmiques soulevés par des questions de choix social. Il est facile d?illustrer l?importance de ces questions en utilisant un exemple simple. Supposons qu?un groupe ait à faire un choix parmi un ensemble de 20 projets non exclusifs. Ceci amène a répondre par oui ou par non à 20 questions. Un tel cadre semble bien adapté pour modéliser le comportement d?une assemblée législative devant accepter ou non des amendements à un projet de loi. Mais la taille de l?ensemble des décisions possible est de 2^{20}, soit environ 1 000 000. Il est clairement impossible d?interroger directement les membres du groupe pour qu?ils donnent leur préférence sur un tel ensemble. Même si cela était possible, le stockage d?un tel volume d?information poserait de redoutable problème. Enfin, l?application d?algorithme d?agrégation sur des données d?une telle taille est clairement une question délicate. Le projet est organisé autour de quatre groupes de travail. Le premier sera consacré à des méthodes d?élicitation et de représentation de préférences. L?idée est ici de tenter de tirer partie de propriétés d?indépendance diverses pour parvenir à interroger de manière efficace les membre du groupe sur leur préférence pour un très grand nombre d?objets et parvenir à une représentation compacte de telles préférences se prêtant bien à la fois au stockage et à l?application d?algorithmes efficaces. Le deuxième groupe de travail sera consacré aux questions d?équité et de justice. Si ces notions ont été bien étudiées par la littérature classique en choix social, les questions algorithmiques soulevées par la mise en ?uvre pratique de ces critères n?ont reçu que très peu d?attention. Or, il existe de très nombreuses situations où des questions de justice et d?équité se posent dans un cadre excluant tout approche algorithmique naïve. On peut, par exemple, songer à la question de l?établissement d?horaires de travail dans un établissement hospitalier, l?ensemble de ces horaires ayant une structure fortement combinatoire. Le troisième groupe de travail poursuivra des travaux déjà entamés sur la complexité algorithmiques de diverses procédures d?agrégation. Deux questions seront particulièrement étudiées : les procédures d?agrégation sur des domaines combinatoires et les possibles vertus de la complexité algorithmique comme barrière possible aux résultats de type Gibbard-Satterthwaite. Le dernier groupe de travail s?intéressera aux questions d?agrégation liées à l?incomplétude et/ou à la mauvaise connaissance des préférences. Ces questions sont naturelles dès lors que l?on se pose des problèmes d?agrégation relativement à des ensembles très vastes d?objets. Chacun de ces groupes de travail comprendra à la fois des économistes et des informaticiens. On espère ainsi au bout des trois ans que durera le projet, fonder de manière durable des centres de recherche d?excellence en France sur le choix social computationnel. Mots clés : Choix social computationnel, Vote, Complexité algorithmique, décision collective, partage et allocation équitable.