Bruno Zanuttini (GREYC, Caen)

Ce « séminaire » se voudra plutôt un groupe de travail, destiné à suggérer des
ponts entre des problématiques de l’intelligence artificielle et l’analyse en
moyenne ou en distribution d’algorithmes. Un problème qui me semble s’y prêter
tout particulièrement est celui de l’allocation décentralisée de biens. Dans
cette problématique, un ensemble d’agents doivent s’accorder sur un partage,
entre eux, d’un certain nombre de biens indivisibles. Je partirai d’un article
présenté aux journées d’intelligence artificielle fondamentale 2014, par
Damamme, Beynier et Maudet, qui étudie un protocole particulier pour ce faire
ce protocole part essentiellement d’une affectation arbitraire des ressources, puis permet aux agents d’échanger des biens de façon bilatérale, à condition que l’échange augmente la satisfaction de chacun, et ce jusqu’à stabilité (aucun échange rationnel possible). Les paramètres intéressants à étudier sont nombreux : qualité de l’allocation finale (probabilité d’être Pareto-optimale, valeur selon une mesure de bien-être social, etc.), nombre d’échanges avant stabilité pour ceux qui semblent les plus simples, mais aussi prix de l’anarchie pour un exemple a priori plus complexe.

Il me semble que l’analyse de ces paramètres est attaquable, tout en étant loin d’être triviale. En particulier, les données sont ici complexes : allocation initiale, préférences des agents au minimum (les domaines de ces données, notamment, sont combinatoires). L’espoir de cette présentation sera donc d’initier une collaboration sur ce sujet, qui présente un intérêt de recherche à la fois pour l’IA et pour l’analyse fine d’algorithmes.