La formation de coalitions est une méthode d'interaction importante pour les systèmes multi-agents qui implique le regroupement de plusieurs agents au sein de différentes coalitions afin d'atteindre efficacement leurs objectifs individuels ou collectifs. La formation de certaines coalitions peut être plus intéressante que d'autres et le choix des coalitions à former implique généralement l'évaluation de plusieurs structures de coalitions. Le choix des coalitions à former est d'une importance cruciale, car il peut avoir un impact majeur sur le succès global de tout le processus. Il s'agit d'un problème majeur en intelligence artificielle et en théorie des jeux qui est au coeur de nombreuses applications pratiques, telles que les transports, la gestion de crises, tel que les catastrophes, et les réseaux de capteurs distribués. Un défi crucial dans la formation de coalitions est la génération de structure de coalitions, où les agents sont regroupés dans une structure de coalitions---c'est-à-dire des coalitions disjointes dans lesquelles chaque agent n'appartient qu'à une seule coalition---d'une manière qui maximise le bien-être social. Cependant, ce problème de génération d'une structure de coalitions optimale est exceptionnellement complexe en raison de la croissance exponentielle du nombre de solutions potentielles à mesure que le nombre d'agents impliqués augmente. Dans cette thèse, nous abordons ce problème en introduisant un ensemble d'algorithmes originaux conçus pour fournir des solutions optimales ou approximatives.

Tout d'abord, nous introduisons de nouveaux concepts et méthodes pour le problème de la génération de structures de coalitions, y compris des phases offlines qui améliorent l'efficacité du processus de recherche. Plus précisément, nous divisons la génération de structures de coalitions en deux phases : une phase offline et une phase online, ce qui permet une configuration automatisée des algorithmes pour ce problème. Ceci est basé sur des résultats non triviaux de l'analyse de l'espace de recherche qui a révélé que les algorithmes exacts pour ce problème peuvent être améliorés grâce à leur paramétrage automatique.

Deuxièmement, nous développons un algorithme qui utilise une nouvelle représentation de l'espace de recherche, qui partitionne l'espace des solutions possibles en sous-espaces et rassemble les solutions d'une toute nouvelle manière. Cette représentation permet non seulement d'optimiser l'évaluation des structures de coalition, mais aussi d'éliminer le traitement redondant des structures de coalitions communes, ce qui se traduit par une réduction significative du temps de calcul.