Résumé Thèse Antoine Nongaillard


Les problèmes d'allocation de ressources suscitent un intérêt croissant aussi bien en à‰conomie qu'en Informatique. Dans ces problèmes, un ensemble de ressources doit être alloué à  un ensemble d'entités selon leurs propres préférences. De nombreux problèmes dans des domaines aussi divers que variés peuvent être modélisés grâce à  un problème d'allocation de ressources. L'auto-organisation de réseaux en télécommunications, la planification en logistique, ou des problèmes basés sur des réseaux sociaux peuvent en effet être représentés par des problèmes d'allocation de ressources.
Ordinairement, ces problèmes sont résolus grâce à  des méthodes centralisées, dans lesquelles une entité omnisciente détermine comment allouer les ressources de manière optimale. Cependant, ces approches font des hypothèses qui ne correspondent pas toujours à  la réalité. Dans bien des contextes, il n'est pas possible d'avoir une entité omnisciente. Certaines applications sont dynamiques et nécessitent une méthode de résolution adaptative qui puisse prendre en compte de nouvelles informations au cours de la résolution. Ces approches considèrent toujours que les possibilités de communi- cation entre les différents participants ne sont pas restreintes, ce qui n'est évidemment pas le cas dans la plupart des cas, comme dans les réseaux pair-à -pair par exemple o๠un pair ne peut communiquer qu'à  un ensemble restreint du système.
Dans cette étude de doctorat, nous nous focalisons sur les approches de ré-allocation distribuées, basées sur des systèmes multi-agents, qui transforment une allocation ini- tiale par des séquences de transactions locales entre agents. Nous cherchons à  con- cevoir des comportements d'agents menant un processus de négociation à  une alloca- tion socialement optimale. Cette allocation peut alors être vue comme un phénomène émergent. Nous voulons également identifier les paramètres favorisant l'efficacité des négociations ainsi que ceux qui la restreignent. Nous considérons différentes mesures de bien-être social et nous fournissons les comportements à  implémenter pour négocier efficacement dans chaque cas. Nous proposons une méthode adaptative et "anytime" où n'importe quel type de réseau d'accointances peut être considéré.