Structures de coopération

Formation de coalition fondée sur l’utilité

Les approches pour la formation de coalition fondée sur l’utilité suivent le principe bellum omnium contra omnes, les agents ne coopèrent les uns avec les autres qu’avec le but de maximiser leur propre utilité, qui peut représenter, selon les applications, de l’argent, du temps, du carburant, etc. De manière générale, ces approches sont fondées sur la théorie des jeux, qui fournit des outils pour permettre aux agents de décider avec qui coopérer, mais également des critères formels par exemple pour déterminer la stabilité d’une éventuelle coalition. 

Formalisation

 La manière la plus classique de formaliser le problème de la formation de coalition suivant la théorie des jeux est la suivante : le problème se compose d’un ensemble d’agents Γ dont tout sous-ensemble est appelé coalition, et d’une fonction ν qui associe à toute coalition de Γ sa valeur, c’està-dire le gain total espéré pour cette coalition (le plus souvent sous forme monétaire). Les membres d’une coalition sont considérés comme liés par un contrat de redistribution de la valeur de la coalition entre ses membres. On fait généralement l’hypothèse que la valeur d’une coalition ne dépend pas des agents n’en faisant pas partie et qu’il ne peut y avoir de redistribution à l’extérieur de la coalition. Enfin, la fonction ν est supposée connue par tous. La solution d’un tel problème est une partition de Γ associée à l’utilité espérée par chaque agent, calculée à partir de la part qu’il reçoit sur la valeur totale de sa coalition (selon le contrat de redistribution). On pourra se référer à [Kahan et Rapoport, 1984] ou [Shehory et Kraus, 1995] pour une formalisation plus détaillée que ce que nous proposons ici. Il y a en réalité deux problèmes à résoudre : 1. Comment choisir le mode de redistribution de la valeur des coalitions entre leurs membres et comment coopérer au sein de ces coalitions ? 2. Quelles coalitions former ? 

Rationalité individuelle et collective 

La notion de rationalité individuelle est généralement tenue pour acquise dans un problème de formation de coalition. Elle représente le fait qu’un agent ne décide de se joindre à une coalition que si son utilité espérée au sein de cette coalition est supérieure à celle qu’il obtiendrait en restant seul. On parle alors souvent d’agent égoïste ou libre [Vauvert et El Fallah-Seghrouchni, 2000]. On peut étendre la notion de rationalité aux coalitions [Shehory et Kraus, 1995]. Une coalition rationnelle n’accepte qu’un agent se joigne à elle que si sa valeur s’en trouve augmentée. Tous les environnements n’ont pas cette propriété, on peut très bien imaginer une situation dans laquelle un agent est ajouté à une coalition uniquement à son profit et à celui d’un autre membre très « influent » dans cette coalition, sans que cela soit profitable au groupe. Dans ce cas, certains membres perdent au change, mais leur situation ne serait pas nécessairement meilleure en dehors de la coalition. 

Additivité

 Certaines propriétés du problème (qui s’expriment dans la fonction ν) peuvent avoir une influence déterminante sur la forme des coalitions, quels que soient les processus de décision des agents. Ainsi, un des paramètres les plus classiques d’un problème de formation de coalition est son « additivité », i.e. y a-t-il toujours plus à gagner en travaillant ensemble ? On parle de super-additivité lorsque : ν(C1 ∪ C2) > ν(C1) + ν(C2) pour toutes coalitions disjointes C1 et C2. Le second problème (quelles coalitions former) ne se pose alors pas pour des agents individuellement rationnels qui formeront nécessairement une seule coalition comprenant tous les agents. Reste alors à déterminer le mécanisme de redistribution de la valeur entre les membres. La solution la plus classique, considérée comme la plus « équitable », et qui sert souvent de référence pour en évaluer d’autres est la valeur de Shapley [Shapley, 1953]. On considère un problème de formation de coalition comme sousadditif1 s’il existe deux coalitions disjointes C1 et C2, telles que ν(C1∪C2) < ν(C1) + ν(C2). Le problème de savoir quelle coalition former se pose alors.

Stabilité 

L’objectif d’un mécanisme de formation de coalition est de former des coalitions stables. La question de la stabilité peut être formulée du point de vue individuel ou collectif et être évaluée selon des critères directement issus de la théorie des jeux. La valeur de Shapley (cf. paragraphe précédent) en est un bon exemple, mais elle ne s’applique qu’au cas super-additif, tout comme d’autres tels le core, le bargaining set ou le kernel [Kahan et Rapoport, 1984]. Le critère individuel principal de stabilité est la rationalité individuelle : chaque agent d’une coalition doit obtenir une utilité au moins égale à celle qu’il recevrait en étant seul. Une telle situation correspond à ce qu’on appelle un équilibre de Nash [Nash, 1951] i.e. une situation dans laquelle aucun agent n’a intérêt à dévier unilatéralement de sa position (ici, son appartenance ou non à une coalition). D’un point de vue collectif, le concept d’optimum de Pareto [Pareto, 1896] est plus adapté : on considère qu’une configuration A (de manière générale une distribution de coalitions associées à leurs fonctions de répartition) Pareto-domine une autre configuration B si et seulement si tous les agents ont une utilité dans la configuration A au moins égale à celle qu’ils ont dans la configuration B et si au moins un agent a dans A une utilité strictement supérieure à celle qu’il obtient dans B. On parle d’optimum de Pareto pour une configuration qui n’est Pareto-dominée par aucune autre, c’est vers cet objectif que tend un mécanisme de formation de coalition « collectivement rationnel ». 

Négociation

Les critères issus de la théorie des jeux nous donnent de précieux moyens de caractérisation des solutions possibles à un problème de formation de coalition. En revanche ils ne nous fournissent aucun indice sur la manière dont les agents peuvent procéder pour atteindre ces solutions. En effet ces critères ne sont calculables que si l’on dispose de toutes les informations concernant les préférences des agents (fonctions d’utilité individuelles, ressources…) Or il n’est généralement pas possible d’obtenir une telle situation de connaissance totale dans un système multiagent en raison notamment des difficultés liées aux communications (voir chapitre 3). Ainsi, on a souvent recours à un processus incrémental de formation de coalition fondé sur la négociation entre agents. Les agents susceptibles de former une coalition communiquent selon certains protocoles, ils expriment leurs besoins, font des concessions, jusqu’à obtenir une solution agréable à tous. Par exemple, dans [Soh et Tsatsoulis, 2002b], l’agent qui est à l’origine du processus de formation de coalition sélectionne à la hâte un ensemble d’agents qui sont des voisins, puis affine le processus en conduisant en parallèle des négociations avec chaque membre potentiel dans un processus d’argumentation au cours duquel contraintes et engagements sont échangés. Pour finir, l’initiateur scelle le statut de la coalition par un engagement. De nombreuses autres approches de la formation de coalition par négociation existent [Sandholm et Lesser, 1995], souvent liées à des applications de type commercial [Sandholm, 2000] avec des agents purement égoïstes, mais la formation de coalition peut aller d’un bout à l’autre du spectre agents égoïstes – résolution distribuée de problème [Zhang et al., 2002].