Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 2 Décembre 2014

Analyser en moyenne des protocoles de négociation ?

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr